Clock及改进Clock置换算法实现

1、操作系统课程设计报告书 Clock及改进Clock置换算法实现班 级 姓 名 学 号 指导老师 2014年3月12日 目 录一 、课程设计目的 . 3 二、系统分析与设计 . .3 三、算法流程图： . .4四、函数模块:.6 五、系统调试与结果： . .7 六、设计心得与体会： . .9 七 、源程序代码: .15 一、课程设计目的操作系统课程设计是为了对学习的操作系统课程更深刻的理解和巩固，对操作系统的整体进行一个模拟。通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、创

2、新能力及团队组织、协作开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。课程设计是自己独立完成一项任务的过程，编程过程中要充分调动个人的积极性，提高自身解决实际问题的能力，发现自身的编程错误习惯，提高编写程序的质量。同时，也为以后深入层次的学习及研究打基础。编程中少不了难题，遇到难题时需要的是用程序员的思维方式去考虑问题解决问题，还需要很大的精力和耐心，对于我们来说都是磨练和提高。二、系统分析与设计 在采用请求分页机制的操作系统中，当运行一个程序的时候，若要访问的页面不在内存中而需要把它们调入内存，但此时内存已无空闲空间，为了保证该进程能正常运行，需选择内存中暂时

3、不用的页面调出到磁盘交换区。选择调出哪个页面，由页面算法决定。页面置换算法的好坏，直接影响系统的性能，所以一个好的页面置换算法，应尽可能选择调出较长时间内不会再访问的页面，以保证较低的缺页率。2.1 Clock页面置换原理描述 Clock算法的思想：当某一页首次装入内存中时，则将该页框的使用位设置为1；当该页随后被访问到时（在访问产生缺页中断之后），它的使用位也会被设置为1。对于页面置换算法，用于置换算法，用于置换的候选页框集合（当前进程：局部范围；整个内存；全局范围）被看做是一个循环缓冲区，并且有一个指针与之相关联。当一页被置换时，该指针被设置成指向缓冲区中的下一页框。当需要置换一页时，操作

4、系统扫描缓冲区，以查找使用位被置为0的一页框。每当遇到一个使用位为1的页框时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有页框的使用位均为0时，则选择遇到的第一个页框置换；如果所有页框的使用位均为1时，则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，置换该页框中的页。 2.2 改进型 Clock页面置换原理描述 改进型的Clock算法的思想：在将一个页面换出时，如果该页已被修改过，便须将它重新写到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。同时满足这两条件的页面作为首先淘汰的页。由访问位A和修改位M可以组合成下面四种类型的页面：1 类（A=

5、0，M=0）：表示该页最近既未被访问、又未被修改，是最佳淘汰页。2 类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3 类（A=1，M=0）：最近已被访问，但未被修改，该页有可能再被访问。4 类（A=1，M=1）：最近已被访问且被修改，该页有可能再被访问。 在内存中的每个页必定是这四类页面之一，在进行页面置换时，其执行过程可分成以下三步：（1）从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。 （2） 如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A

6、=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有经过的页面的访问位置0。 （3） 如果第二步也失败，即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后，重复第一步，如果仍失败，必要时再重复第二步，此时就一定能够找到被淘汰的页。三、算法流程图：Clock置换算法流程图：改进型置换算法流程图：四、函数模块主函数模块函数名称：int main()功能：显示主菜单，调用函数检测模块函数名称：bool inblock(int num) 、bool inblock2(int num)功能：检测读入的页号是否存在内存中、检测页号是否在内存中并把访问

7、位和修改位置1修改模块函数名称：bool change()、int whichpage()功能：判断页面是否已经被修改、判断内存中第几个需要被置换Clock模块函数名称：void CLOCK(int num)功能：实现Clock置换算法，完成页面置换改进型Clock模块函数名称：void LCOCK(int num)功能：实现改进的ClockL置换算法，完成页面置换五、系统调试与结果六、程序清单#include<iostream>#include<stdlib.h>#include<time.h>#define N 20 /虚拟内存尺寸using names

8、pace std;int P; int const blockCount=3 ;/内存中的物理块数int count = 0;int blockblockCount;int const PageCount=15;/总的页面数int PagePageCount;int stateblockCount;/clock置换算法中，内存中的每个页面号对应的状态int state2blockCount2;/ 二维数组，第一行第一列为访问位，第一行的第二列为修改位double lost= 0.0;void generate_list(int *list,int e,int m,int t)int i,j=0

9、,q=P,r;srand(unsigned)time(NULL);while(j<e)for(i=j;i<j+m;i+)if(i=e)break;listi=(q+rand()%e)%N; /保证在虚拟内存的页号内j=i;r=rand()%100;if(r<t)q=rand()%N;else q=(q+1)%N;/随机生产是否被修改的情况，prop(0100),prop/100的概率为被修改void generate_modify(int *mo,int e,int prop)int i,t;for(i=0;i<e;i+)t=rand()%100;if(t>pro

10、p)moi=0;elsemoi=1;/检测页号是否在内存中bool inblock(int num)for(int i=0; i<blockCount;i+)if(blocki = Pagenum)statei = 1;return true;return false;/判断页面是否已经被修改bool change()if(rand()%2+1) = 1 )printf("该页面被修改!n");return true;elsereturn false;/用于改进型clock置换算法，检测页号是否在内存中并把访问位和修改位置1bool inblock2(int num)

11、for(int i=0;i<blockCount;i+)if(blocki = Pagenum)if(change()state2i0 = 1;state2i1 = 1;elsestate2i0 = 1;return true;return false;/用于改进型clock置换算法，判断内存中第几个需要被置换int whichpage()int j;for(j=0;j<blockCount;j+) if(state2j0 = 0&&state2j1 = 0)return j;for(j=0;j<blockCount;j+ ) if(state2j0 = 0&

12、amp;&state2j1 = 1)return j;state2j0 = 0 ;for(j=0;j<blockCount;j+ )state2j0 =0 ;return whichpage();/简单Clock置换算法void CLOCK(int num)int j;if(inblock(num)printf("命中!n");lost+;for(int i=0;i<blockCount;i+) printf("物理块%d#中内容:%dn",i,block i);elseif(count = blockCount)/lost+;for

13、(j=0;j<blockCount; )if(statej = 0)break;elsestatej = 0;j+;j = j%3;blockj = Pagenum;statej = 1;for(int i=0;i<blockCount;i+) printf("物理块%d#中内容:%dn",i,blocki);elseblockcount = Pagenum;count+;for(int i=0;i<blockCount;i+) printf("物理块%d#中内容:%dn",i,blocki);/改进型clock置换算法void LCL

14、OCK(int num)int j;if(inblock2(num)printf("命中!n"); lost+;for(int i=0;i<blockCount;i+) printf("物理块%d#中内容:%dn",i,blocki);elseif(count = blockCount) /lost+;j = whichpage();blockj = Pagenum;state2j0 = 1;for(int i=0;i<blockCount;i+) printf("物理块%d#中内容:%dn",i,blocki);else

15、blockcount = Pagenum;count+;for(int i=0;i<blockCount;i+) printf("物理块%d#中内容:%dn",i,blocki);int main() int aN;int moN; int A=10; int e,m,prop,t,j;printf("页面走向为：");generate_list(a, e,m,t);generate_modify(mo,e,prop); for(int i = 0;i<PageCount;i+) Pagei =rand()%9 + 1;printf(&quo

16、t;%d ",Pagei);char ch ;printf("n");printf("tt1 Clock置换算法n");printf("tt2 改进型Clock置换算法n");printf("tt3 退出!nn");printf("请输入算法序号:tn"); while(1) scanf("%c",&ch); switch(ch) case '1':lost=0;count=0;for(int m=0;m<blockCount;m+)s

17、tatem = 0;for(int j=0;j<blockCount;j+)blockj=0;for(int i=0;i<PageCount;i+) printf("读入Page%dn",i); CLOCK(i); printf("页面访问次数: %dn缺页次数: %0.lfn",PageCount,PageCount-lost); printf("缺页率为:%0.001fn",(PageCount-lost)/PageCount); printf("n请输入算法序号:t"); break; case

18、'2': lost = 0;count = 0;for(int m = 0; m < blockCount; m+) for(int n = 0; n < 2;n+)state2mn = 0;for(int j = 0; j < blockCount; j+) blockj = 0;for(int i = 0; i < PageCount; i+) printf("读入Page%dn",i); LCLOCK(i); printf("页面访问次数: %dn缺页次数: %0.lfn",PageCount,PageCount-lost);printf("缺页率为:%0.001fn",(PageCount-lost)/PageCount); printf("n请输入算法序号:t"); break;case '3':exit(0); return 0;七、实验心得 通过这两周的课程设计,让我加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储,页面置换有了深入的了解,并能够用高级语言进行模拟演示。不仅提高对操作系统的了解，这次的课程设计也使自己的C语言编程能力加强了不少