操作系统课程设计--程序实现页面置换算法设计（吃水果问题）.doc

1.课程设计题目 2.课程设计的目的 1、通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解。熟悉虚存管理的各种页面淘汰算法 2、通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。 功能描述编写了一个请求分页存储管理中的页面置换算法模拟程序 实现了界面设计和调用三种不同的置换算法 FIFO页面置换算法的实现 LRU页面置换算法的实现 OPT页面置换算法的实现 5.方案论证 在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。 最佳置换算法(Optimal)： 它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。 先进先出(FIFO)页面置换算法： 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 ?LRU置换算法： 即最近最少使用页面置换算法，是为虚拟页式存储管理服务的。 b．LRU算法： 实施框图的主体并运行和修改 //FIFO页面置换 if(c==f) /*选择FIFO算法*/ { n=0; cout页面置换情况: endl; while(im) { if(Search(p[i].num,page)=0)i++;/*找到相同的页面*/ else { if(t==N)t=0; else { n++;/*往后依次移一位*/ page[t].num=p[i].num; print(page); t++; } } } cout缺页次数：(n+1) 缺页率：(n+1)/mendl; } //LRU页面置换 if(c==l) /*选择LRU算法*/ { n=0; cout页面置换情况: endl; while(im) { int k; k=t=Search(p[i].num,page); /*找到相同的页面*/ if(t=0) page[t].time=0; else { n++; t=Max(page); page[t].num=p[i].num; /*记录当前的内存单元中的页面*/ page[t].time=0; } if(t==0){page[t+1].time++;page[t+2].time++;} /*相同页数为0，依次向后移一位*/ if(t==1){page[2].time++;page[0].time++;} /*相同页数为1，后一位向后移1位*/ if(t==2){page[1].time++;page[0].time++;} /*相同页数为2，不移动*/ if(k==-1) print(page); /*判断是否出错*/ i++; } cout缺页次数：(n+1) 缺页率：(n+1)/mendl; } 可用内存页面数：3 请输入实际页面：20 请输入各页面号： 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 选择界面： f: FIFO页面置换算法 l：LRU页面置换算法 o:OPT页面置换算法 按其他键结束 如图1所示。 图1 运行界面 输出结果： ①当输入f时，输出如下结果 页面置换情况： 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7