操作系统课程设计报告书
Clock及改进Clock置换算法实现
班级
姓名
学号
指导老师
2014年3月12日
目录
一、课程设计目的 (3)
二、系统分析与设计 ................... . (3)
三、算法流程图： ......... .. (4)
四、函数模块: (6)
五、系统调试与结果： .............. (7)
六、设计心得与体会： ............ .. (9)
七、源程序代码: (15)
一、课程设计目的
操作系统课程设计是为了对学习的操作系统课程更深刻的理解和巩固，对操作系统的整体进行一个模拟。通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、创新能力及团队组织、协作开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。
课程设计是自己独立完成一项任务的过程，编程过程中要充分调动个人的积极性，提高自身解决实际问题的能力，发现自身的编程错误习惯，提高编写程序的质量。同时，也为以后深入层次的学习及研究打基础。
编程中少不了难题，遇到难题时需要的是用程序员的思维方式去考虑问题解决问题，还需要很大的精力和耐心，对于我们来说都是磨练和提高。
二、系统分析与设计
在采用请求分页机制的操作系统中，当运行一个程序的时候，若要访问的页面不在内存中而需要把它们调入内存，但此时内存已无空闲空间，为了保证该进程能正常运行，需选择内存中暂时不用的页面调出到磁盘交换区。选择调出哪个页面，由页面算法决定。页面置换算法的好坏，直接影响系统的性能，所以一个好的页面置换算法，应尽可能选择调出较长时间内不会再访问的页面，以保证较低的缺页率。
2.1 Clock页面置换原理描述
Clock算法的思想：当某一页首次装入内存中时，则将该页框的使用位设置为1；当该页随后被访问到时（在访问产生缺页中断之后），它的使用位也会被设置为1。对于页面置换算法，用于置换算法，用于置换的候选页框集合（当前进程：局部范围；整个内存；全局范围）被看做是一个循环缓冲区，并且有一个指针与之相关联。当一页被置换时，该指针被设置成指向缓冲区中的下一页框。当需要置换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一页框。每当遇到一个使用位为1的页框时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有页框的使用位均为0时，则选择遇到的第一个页框置换；如果所有页框的使用位均为1时，则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，置换该页框中的页。
2.2 改进型Clock页面置换原理描述
改进型的Clock算法的思想：在将一个页面换出时，如果该页已被修改过，便须将它重新写到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。同时满足这两条件的页面作为首先淘汰的页。由访问位A和修改位M可以组合成下面四种类型的页面：
1 类（A=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=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有经过的页面的访问位置0。
（3）如果第二步也失败，即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后，重复第一步，如果仍失败，必要时再重复第二步，此时就一定能够找到被淘汰的页。
三、算法流程图：
Clock置换算法流程图：
改进型置换算法流程图：替换指针
四、函数模块
主函数模块
函数名称：int main()
功能：显示主菜单，调用函数
检测模块
函数名称：bool inblock(int num) 、bool inblock2(int num)
功能：检测读入的页号是否存在内存中、检测页号是否在内存中并把访问位和修改位置1
修改模块
函数名称：bool change()、int whichpage()
功能：判断页面是否已经被修改、判断内存中第几个需要被置换
Clock模块
函数名称：void CLOCK(int num)
功能：实现Clock置换算法，完成页面置换
改进型Clock模块
函数名称：void LCOCK(int num)
功能：实现改进的ClockL置换算法，完成页面置换
五、系统调试与结果
六、程序清单
#include
#include
#include
#define N 20 //虚拟内存尺寸
using namespace std;
int P;
int const blockCount=3 ;//内存中的物理块数
int count = 0;
int block[blockCount];
int const PageCount=15;//总的页面数
int Page[PageCount];
int state[blockCount];//clock置换算法中，内存中的每个页面号对应的状态
int state2[blockCount][2];// 二维数组，第一行第一列为访问位，第一行的第二列为修改位
double lost= 0.0;
void generate_list(int *list,int e,int m,int t)
{
int i,j=0,q=P,r;
srand((unsigned)time(NULL));
while(j { for(i=j;i { if(i==e) break; list[i]=(q+rand()%e)%N; //保证在虚拟内存的页号内 } j=i; r=rand()%100; if(r q=rand()%N; else q=(q+1)%N; } } //随机生产是否被修改的情况，prop(0……100),prop/100的概率为被修改 void generate_modify(int *mo,int e,int prop) { int i,t; for(i=0;i { t=rand()%100; if(t>prop) mo[i]=0; else mo[i]=1; } } //检测页号是否在内存中 bool inblock(int num) { for(int i=0; i { if(block[i] == Page[num]) { state[i] = 1; return true; } } return false; } //判断页面是否已经被修改 bool change() { if((rand()%2+1) == 1 ) { printf("该页面被修改!\n"); return true; } else return false; } //用于改进型clock置换算法，检测页号是否在内存中并把访问位和修改位置1 bool inblock2(int num) { for(int i=0;i if(block[i] == Page[num]){ if(change()){ state2[i][0] = 1; state2[i][1] = 1; } else{ state2[i][0] = 1; } return true; } } return false; } //用于改进型clock置换算法，判断内存中第几个需要被置换int whichpage(){ int j; for(j=0;j { if(state2[j][0] == 0&&state2[j][1] == 0) { return j; } } for(j=0;j { if(state2[j][0] == 0&&state2[j][1] == 1) { return j; } state2[j][0] = 0 ; } for(j=0;j { state2[j][0] =0 ; } return whichpage(); } //简单Clock置换算法 void CLOCK(int num) { int j; if(inblock(num)) { printf("命中!\n"); lost++; for(int i=0;i printf("物理块%d#中内容:%d\n",i,block [i]); } else if(count == blockCount) { //lost++; for(j=0;j { if(state[j] == 0) { break; } else{ state[j] = 0; } j++; j = j%3; } block[j] = Page[num]; state[j] = 1; for(int i=0;i printf("物理块%d#中内容:%d\n",i,block[i]); } else{ block[count] = Page[num]; count++; for(int i=0;i printf("物理块%d#中内容:%d\n",i,block[i]); } } //改进型clock置换算法 void LCLOCK(int num) { int j; if(inblock2(num)) { printf("命中!\n"); lost++; for(int i=0;i printf("物理块%d#中内容:%d\n",i,block[i]); } else if(count == blockCount) { //lost++; j = whichpage(); block[j] = Page[num]; state2[j][0] = 1; for(int i=0;i printf("物理块%d#中内容:%d\n",i,block[i]); } else{ block[count] = Page[num]; count++; for(int i=0;i printf("物理块%d#中内容:%d\n",i,block[i]); } } int main() { int a[N]; int mo[N]; 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 { Page[i] =rand()%9 + 1; printf("%d ",Page[i]); } char ch ; printf("\n"); printf("\t\t1 Clock置换算法\n"); printf("\t\t2 改进型Clock置换算法\n"); printf("\t\t3 退出!\n\n"); printf("请输入算法序号:\t\n"); while(1){ scanf("%c",&ch); switch(ch){ case '1':{ lost=0; count=0; for(int m=0;m { state[m] = 0; } for(int j=0;j { block[j]=0; } for(int i=0;i { printf("读入Page[%d]\n",i); CLOCK(i); } printf("页面访问次数: %d\n缺页次数: %0.lf\n",PageCount,PageCount-lost); printf("缺页率为:%0.001f\n",(PageCount-lost)/PageCount); printf("\n请输入算法序号:\t"); }break; case '2':{ lost = 0; count = 0; for(int m = 0; m < blockCount; m++) { for(int n = 0; n < 2;n++) state2[m][n] = 0; } for(int j = 0; j < blockCount; j++) { block[j] = 0; } for(int i = 0; i < PageCount; i++) { printf("读入Page[%d]\n",i); LCLOCK(i); } printf("页面访问次数: %d\n缺页次数: %0.lf\n",PageCount,PageCount-l ost); printf("缺页率为:%0.001f\n",(PageCount-lost)/PageCount); printf("\n请输入算法序号:\t"); }break; case '3':{ exit(0); } } } return 0; } 七、实验心得 通过这两周的课程设计,让我加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储,页面置换有了深入的了解,并能够用高级语言进行模拟演示。不仅提高对操作系统的了解，这次的课程设计也使自己的C语言编程能力加强了不少。虽然自己所做的很少也不够完善，但毕竟是我努力的结果。我也体会到，任何一门知识的掌握，仅靠学习理论知识是远远不够的，要与实际动手操作相结合才能达到功效。通过实践的学习，我认识到学好计算机要重视实践操作，不仅仅是学习C语言，还是其它的语言，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。在课程设计过程中，收获知识，提高能力的同时，我也学到了很多人生的哲理，懂得怎么样去制定计划，怎么样去实现这个计划，并掌握了在执行过程中怎么样去克服心理上的不良情绪。因此在以后的生活和学习的过程中，我一定会把课程设计的精神带到生活中，不畏艰难，勇往直前！
相关主题
文本预览