操作系统课程设计-采用CLOCK置换算法仿真请求分页系统.doc

东莞理工学院城市学院计算机操作系统课程设计题目： 采用CLOCK置换算法仿真请求分页系统 专业： 软件工程 年级： 2014级 3班 小组成员： 指导教师： 时间： 2014.12.24 2014.12.26 地点： 东莞理工学院城市学院计算机与信息科学系制2014年 12月摘要在计算机操作系统中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺页中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页，为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。不适当的算法可能会导致进程发生“抖动”，频繁地更换页面会使进程大部分时间花费在置换工作上，所以置换算法的好坏直接影响到系统的性能。目录1.概述32.课程设计任务及要求42.1设计任务42.2 设计要求43.算法及数据结构43.1算法的总体思想43.1.1 RR算法53.1.2 CLOCK算法63.2 CLOCK置换算法73.2.1 功能73.2.2数据结构84. 程序设计与实现94.1 程序流程图94.2 程序代码114.3 实验结果155. 结论166.工作日志177. 收获、体会和建议。178. 参考文献。181.概述在采用请求分页机制的操作系统中，当运行一个程序的时候，若要访问的页面不在内存中而需要把它们调入内存，但此时内存已无空闲空间，为了保证该进程能正常运行，需选择内存中暂时不用的页面调出到磁盘交换区。选择调出哪个页面，由页面算法决定。页面置换算法的好坏，直接影响系统的性能，所以一个好的页面置换算法，应尽可能选择调出较长时间内不会再访问的页面，以保证较低的缺页率。“CLOCK页面置换算法”是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。在动态分区存储管理方式中，主要操作是分配内存和回收内存。2.课程设计任务及要求2.1设计任务用高级语言编写和调试一个内存分配程序，加深对内存分配算法的理解。使系统利用RR时间片轮转算法掉调度作业，并从内存区动态分配内存。设内存区的大小为number，表中每个空闲分区的大小可表示为N。虚拟存储区采用page类型二维数组实现，然后将虚拟存储区的首地址返回给调用者。当进程运行完毕释放内存时，系统根据回收区的首址，从内存区表中按CLOCK算法找到相应的插入点。2.2 设计要求1.实现请求分页存储管理方式的页面置换算法：CLOCK算法2.内存物理块数固定为15个，对多个作业采用可变分配全局置换的策略分配物理块3.作业数量与作业大小（10-20页）可在界面进行设置4.所有作业按RR算法进行调度，时间片长度为1秒5.可为每个作业随机产生引用的页面串，也可以人工输入引用的页面串，页面串长度50-100，要求必须包括作业所有的页面，可作为样例数据保存6.可读取样例数据（要求存放外部文件中）进行作业数量、作业大小、页面串长度的初始化7.要求采用可视化界面，模拟内存分配和使用情况图，可在运行过程中随时暂停，查看当前内存物理块使用情况。8.每次全部作业运行结束后，要求打印出访问命中率3.算法及数据结构3.1算法的总体思想系统整体流程图：3.1.1 RR算法基本原理：（1） 将所有的就绪进程按FCFS策略排成一个就绪队列；（2） 系统可设置每隔一定时间便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片；（3） 当它运行完毕后，又分配给就绪队列中新的队首进程，也让它执行一个时间片。保证就绪队列中所有进程在确定的时间段内，都能获得一个时间片的时间。运行步骤：（1） 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序。将它从就绪队列中删除，再调度就绪队列中的进程运行，并启动一个新时间片。（2） 在一个时间片用完时，计时器中断处理程序被激活，如果未运行完毕，调度程序就把它送往就绪队列的末尾。RR算法流程图：3.1.2 CLOCK算法基本原理：在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。1.为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，2.为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。3.为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。在动态分区存储管理方式中，主要操作是分配内存和回收内存。 4.除考虑页面的使用情况外，还须再增加一个因素置换代价，其差别在于该算法须同时检查访问位与修改位。执行步骤：1.Clock算法把内存中的所有页面通过链接指针接成一个循环队列。2.当某页被访问时，其访问位置被置成1.3.淘汰页面时，只需检查页的访问位。如果是0，就选择该页换出，若是1，则重新将它置为0，暂时不换出。4.按照FIFO算法检查下一个页面，检查最后个页面，若访问位为1，返回队首去检查第1个页面。原理流程图与示例图：Clock算法详细流程图如下：3.2 CLOCK置换算法3.2.1 功能时间片轮转算法，可以设置每隔一定的时间就产生一次中断，去激活进程调度程序进行调度，保证就绪队列中所有进程在确定的时间段内，都能获得一个时间片的时间。而时间片的大小对系统性能有很大的影响，系统可以通过时间片大小的设定，提升系统自身的性能。“CLOCK页面置换算法”是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。在动态分区存储管理方式中，主要操作是分配内存和回收内存。3.2.2数据结构类型名称说明Pagea存储页面情况的数组Intyks内存物理块长度intbf存储内存块数据数组Intbb置换算法中的辅助数组Intdys内存调页数Intzhs内存置换个数Cstringdyqk存放全部调页情况Cstrings得到一个置换页面情况boolcz判断当前页面在内存中是否存在IntiItemCount得到当前列表控件中的位置IntiItemCount1列表控件的行初始值Intl列表控件中列的值CListCtrlm_list记录单选按钮选择页面产生方式CStringm_xl;存放页面调用顺序的字符串Intm_zynum记录作业数量Intm_zysize记录作业大小CStringm_qyl记录算法运行完毕后的缺页率Intm_dys记录调页数Intm_zhs记录置换数CStringm_dyqk存放页面调用详细情况的数组4. 程序设计与实现程序结构介绍：4.1 程序流程图4.2 程序代码voidCLogin:OnOk() / TODO: Add your control notification handler code hereUpdateData(TRUE); / 获取输入数据if(m_username=Admin&m_password=password) CDialog:OnOK(); / 假如用户名和密码正确，就关闭对话框 /*假如用户名或密码错误，且还未超出登陆次数，就进行提示*/if(m_username!=Admin|m_password!=password)&(m_Time2)AfxMessageBox(登陆错误次数超过3次);CDialog:OnCancel(); 初始化设置列表控件的格式：intCClockDlg:InitListCtrlStyle()/获取ListCtrl的宽度CRectrect;m_list.GetClientRect(&rect);intnColInterval = rect.Width();/设置ListCtrl的样式m_list.SetExtendedStyle(LVS_EX_GRIDLINES | LVS_EX_FULLROWSELECT );/插入列索引、列名、列的文字格式，列宽m_list.InsertColumn(0, _T(作业), LVCFMT_RIGHT, int(nColInterval*0.1);m_list.InsertColumn(1, _T(0), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(2, _T(1), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(3, _T(2), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(4, _T(3), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(5, _T(4), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(6, _T(5), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(7, _T(6), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(8, _T(7), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(9, _T(8), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(10, _T(9), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(11, _T(10), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(12, _T(11), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(13, _T(12), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(14, _T(13), LVCFMT_LEFT, int(nColInterval*0.08);m_list.InsertColumn(15, _T(14), LVCFMT_LEFT, int(nColInterval*0.08);m_list.SetExtendedStyle(LVS_EX_FULLROWSELECT|LVS_EX_GRIDLINES);return 0;初始化列表框第一列内的内容：for (int i = 1; i =m_zynum ; i+)/根据i来生成卡号CStringstrCardID;strCardID.Format(作业_%d, i);/获取ListCtrl的当前记录条数iItemCountintiItemCount = m_list.GetItemCount();m_list.InsertItem(iItemCount,);/往第iItemCount插入第一列的数据数据，即插入卡号m_list.SetItemText(iItemCount,0, strCardID);定义一个page结构体：struct page int z;/页面内容intbz;/页面标志位;给产生随机序列按钮添加响应函数voidCClockDlg:OnBUTTONcsxl() / TODO: Add your control notification handler code hereintisCourse = GetCheckedRadioButton(IDC_RADIO1,IDC_RADIO2);/检查两个单选按钮if (isCourse = IDC_RADIO2)/如果选择第二个按钮FILE* fp;/定义文件指针CString s;CString s1;UpdateData(TRUE);m_xl=;yks=15;UpdateData(FALSE);UpdateData(TRUE);fp=fopen(d:b.txt,w);/打开文件b.txt，写for(int i=0;im_zysize*m_zynum;i+)ai.z=rand()%50+50;/产生随机数s.Format(%d,ai.z);m_xl+=s;/将字符串s接到m_xl后面if(i+1)%m_zysize=0) s1.Format(-作业%d,(i+1)/m_zysize);/输出回车，换行m_xl+=s1;m_xl+=rn;elsem_xl+= ;fprintf(fp,%s,m_xl);UpdateData(FALSE);if (m_zysize=0|m_zynum=0)MessageBox(请输入页面个数和页面大小,警告);elseMessageBox(请选择页面从文件读方式,警告！);打开文件读：voidCClockDlg:OnBUTTONread() / TODO: Add your control notification handler code hereintisCourse = GetCheckedRadioButton(IDC_RADIO1,IDC_RADIO2);if (isCourse = IDC_RADIO1)FILE *f;/文件指针CString s,s1,s2,filename;UpdateData(true);filename = m_filename;if(f=fopen(filename,r)=NULL)MessageBox(请输入文件名称！,警告！);if(f=fopen(filename,r)!=NULL)char str=fgetc(f);/得到f所指的字符while(str!= )/读取字符直到读到空格s.Format(%c,str);/将str赋值给ss1+=s;/将s接到s1后面str=fgetc(f);str=fgetc(f);/得到f所指的字符while(str!= )/读取字符直到读到空格s.Format(%c,str);s2+=s;str=fgetc(f);/将得到的s1，s2，分别转换成整型变量并分别赋值给m_zynum，m_zysize两个变量m_zynum = atoi(s1);m_zysize = atoi(s2);elseMessageBox(不能打开文件！,警告！);CLOCK页面置换算法：void Clock(intai)int f=0;for(int i=0;iyks;i+)if (bfi=ai) dyqk+=rn;f=1;bbi=0;/如果内存中已经存在，则将标志位f置为1if(f=0)int e=0,g=0,max=bb0;if(dysyks) bfdys=ai;dys+;for(int d=0;ddys;d+)bbd+;s.Format(%d,bfd);/将整形的bfd赋值给sdyqk+=s;/将s添加到dyqk字符串后面dyqk+= ;/dyqk字符串后面添加一个空格dyqk+=rn;/dyqk字符串后面添加一个回车换行符elsefor(int m=1;mmax) max=bbm;e=m;for(int h=0;hyks;h+) bbh+;bfe=ai;bbe=0;dys+;for(int c=0;cyks;c+)s.Format(%d,bfc);/将整形的bfd赋值给sdyqk+=s;/将s添加到dyqk字符串后面dyqk+= ;/dyqk字符串后面添加一个空格dyqk+=rn;dyqk字符串后面添加一个回车换行符实现暂停继续功能，其中设置一个m_pause整型变量，当点击暂停按钮时，将m_pause置为0，当点击继续按钮时将m_pause置为1，ontimer（）函数在执行时加入一个判断，只有当m_pause为1时才执行，这样就实现了暂停继续功能。void CClockDlg:OnButton() /暂停函数/ TODO: Add your control notification handler code herem_pause=0;void CClockDlg:OnContinue() /继续函数/ TODO: Add your control notification handler code herem_pause=1;SetTimer(1,1000,NULL);void CClockDlg:OnTimer(UINT nIDEvent)/时间函数SetTimer(1,1000,NULL );/设置时间函数，每隔1000毫秒执行一次OnTimer函数，实现动态显示，并实现暂停继续功能。KillTimer(1);/关掉时间函数4.3 实验结果1、登录页面与系统主页面：密码为password图1、登录界面图2、系统主界面2、 选择随机产生方式产生作业选择随机产生按钮，并在相应的对话框内输入正确的作业数量和作业大小，点击随机生成按钮图3、选择随机产生方式产生作业3、 对随机产生的作业进行CLOCK算法模拟（点击开始按钮之后）图4、对随机产生的作业进行CLOCK算法模拟5. 结论作业数页面大小调度页面数置换页面数平均缺页率21017285%31024980%410301575%315372278%320463176%通过以上数据显示，当页面大小一定时，作业数越大，调度的页面数越多，置换页面数也多，但是缺页率会降低；当作业数一定时，页面越大，需要调度的页面数越多，置换页面数也会增多，但是缺页率会降低。无论作业数还是页面大小增加，调