页面调度实验报告

1、设计题目课 程 设 计 主 要 内容一、课程设计的性质、目的和作用页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存 中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来， 供新页面使用。本实验的目的是通过编程实现几种常见的页面调度（置换）算法，加深读者对页面思 想的理解。二、课程设计的具体内容先进先出调度算法最近最少调度算法最近最不常用调度算法 SECOND二次机会调度算法各种算法同时显示三、课程设计的要求用自己熟悉的一种数据库开发工具，VC+等。指 建议：从学生的工作态度、工作量，设计（论文）的创造性、学术性、实用性及书

2、面表达能力等方面给出评价。导教师评估签名：200年 月 日、实验内容页面调度算法目前有许多页面调度算法，本实验主要涉及先进先出调度算法、最近最少调度算 法、最近最不常用调度算法。本实验使用页面调度算法时作如下假设，进程在创建时 由操作系统为之分配一个固定数目物理页，执行过程中物理页的数目和位置不会改 变。也即进程进行页面调度时只能在分到的几个物理页中进行。下面对各调度算法的思想作一介绍。先进先出调度算法先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组 成一个队列，每次调度队首页面予以淘汰。最近最少调

3、度算法先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序 执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他 们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近 一段时间以来最少使用的页面予以淘汰。 算法实现时需要为每个页面设置数据结构记 录页面自上次访问以来所经历的时间。最近最不常用调度算法由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一 段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面， 每次淘汰访问次数

4、最少的页面。算法实现时需要为每个页面设置计数器，记录访问次 数。计数器由硬件或操作系统自动定时清零。缺页调度次数和缺页中断率、缺页置换率计算缺页中断次数是缺页时发出缺页中断的次数。缺页中断率=缺页中断次数/总的页面引用次数*100%缺页调度次数是调入新页时需要进行页面调度的次数缺页置换率=缺页调度次数/总的页面引用次数*100%二、总体设计1、算法的原理说明FIFO先进先出调度算法：当页面框满时，最早进来的页面调出；LRU最近最少使用调度算法：当页面框满时，最近最少使用的页面调出LFU最近最不常用调度算法：当页面框满时，最近最不常用的页面调出SECOND二次机会调度算法:当页面框满时，页面调入

5、时R=0,当被访问时R = 1。发生替换时，先检查最 老的页面的R,如果为0则调出，若为1，则令R = 0，修改装入时间，如刚被装 入一样。然后继续搜索可替换页面2、设计思路本设计模拟实现中有以下几点：1 ：数据由data.txt和data2.txt.文档中提取。Txt文档必须放入与程序dubug相同的目 录。如果想添加数据，可以在此目录下新添文本文档。2：输入txt文件名自动获取页面号3：用队列来表示内存，且最多只能存放3个页面4：每次执行算法结束，第一行输出每次淘汰的页面号，若未淘汰则用表示。第二行 显示缺页的总次数。5：本程序涉及4个类，页面类，算法类，队列结点类，队列类。三、模拟实现1

6、：程序所需C+的库#include#include#include#include /文件输入输出函数库#include异常处理2：从Txt文档中提取页面号If stream infile(T_name);while(!infile.eof()( /eof()，infile 的文件尾状态infileArray_data; /读数据的时候因为数据间有一个空格才能完整的读 出，T_datai = Array_data;if(infile.eof() break;i+;T_num+;if(infile.eof() break;3:页面类定义class page 页面类public:int pagen

7、umber;页面号int R; /此页面被调入时间，初次调入为零。每次调度R值加1；若命中则变回0；int hit; /命中次数page()pagenumber = 0;R = 0;hit = 0;4:队列结点类定义class Nodepublic:page data;Node *link;5算法类class Algorithmpublic:Node *next0;int total;/缺页的总页数int total_hit;/命 中次数public:Algorithm()(total = 0;total_hit = 0;void FIFO(int T_data,int T_num); /先进

8、先出算法void LRU(int T_data,int T_num); /最近最少使用调度算法void LFU(int T_data,int T_num);/最近最不常用调度算法void SECOND(int T_data,int T_num);/二 次机会算法;6队列类class Queue(public:int num;队列中元素个数Node *front; /指向头节点指针Node *rear; /指向尾节点指针public:Queue()(front = NULL;rear = NULL;num = 0;Queue();void add(page add_data); /入队page

9、putout();出队void Exchange(page data); /若队列中含有此页，则将此页与队尾交换位置bool look(page datas); 查看是否有相同项void output(); /输出矩阵page ChooseOut(page N1); /将队中某项出队;7：算法实现函数void Algorithm:FIFO(int T_data,int T_num)( /先进先出算法Queue Q1; 内存中的页面Queue Q2; 被置换出去的页面Queue FIFO_Q; /将文档中的数构成的矩阵转到队列中Node *next;page out;page T_x;/for(

10、int i = 0;i=T_num;i+)/将文档中的数构成的矩阵转到队列中T_x.pagenumber = T_datai;FIFO_Q.add(T_x);/next = FIFO_Q.front;while(next != NULL)(if(Q1.num data);total = total + 1;else(if(Q1.look(next-data) = false)(Q1.add(next-data);total = total + 1;else(total_hit = total_hit + 1;out.pagenumber = -1;/*Q2.add(out);else(if(Q

11、1.look(next-data) = false)(out = Q1.putout();Q2.add(out);Q1.add(next-data);total = total + 1;else(total_hit = total_hit + 1;out.pagenumber = -1;/*Q2.add(out);next = next-link;coutendl;coutFIFO 算法:endl;cout”每次淘汰的页面号:”；Q2.output();coutendl;cout缺页中断total_hitendl;cout置换中断totalendl;cout缺页中断率”total_hit/(t

12、otal_hit+total)endl;cout置换中断率total/(total_hit+total)endl;coutendl;/void Algorithm:LRU(int T_data,int T_num)/最近最少使用调度算法Queue Q1; 内存中的页面Queue Q2; 被置换出去的页面Queue FIFO_Q; /将文档中的数构成的矩阵转到队列中Node *next;page out;page T_x;/for(int i = 0;i=T_num;i+)/将文档中的数构成的矩阵转到队列中 T_x.pagenumber = T_datai;FIFO_Q.add(T_x);/ne

13、xt = FIFO_Q.front;while(next != NULL)if(Q1.num data);total = total + 1;elseif(Q1.look(next-data) = false)Q1.add(next-data);total = total + 1;elseQ1.Exchange(next-data); /若命中则将其置换的队尾，如同刚入队 total_hit = total_hit + 1;out.pagenumber = -1;/*Q2.add(out);elseif(Q1.look(next-data) = false)out = Q1.putout();

14、Q2.add(out);Q1.add(next-data);total = total + 1;else(Q1.Exchange(next-data); /若命中则将其置换的队尾，如同刚入队 total_hit = total_hit + 1;out.pagenumber = -1;/*Q2.add(out);next = next-link;coutendl;coutLRU 算法:endl;cout”每次淘汰的页面号:”；Q2.output();coutendl;cout缺页中断total_hitendl;cout置换中断totalendl;cout缺页中断率total_hit/(total

15、_hit+total)endl;cout置换中断率total/(total_hit+total)endl;coutendl;/void Algorithm:LFU(int T_data,int T_num)(/最近最不常用调度算法每次浏览的页面入队，页面号不同。当使用LFU算法时先查找队列中是否有该项，若有则出队Queue Q1; 内存中的页面Queue Q2; 被置换出去的页面Queue F_Q; 将文档中的数构成的矩阵转到队列中Node *next,*next2;page out;page T_x;int min;/for(int i = 0;i=T_num;i+)/将文档中的数构成的矩阵

16、转到队列中 T_x.pagenumber = T_datai;F_Q.add(T_x);/next = F_Q.front;while(next != NULL)if(Q1.num data);total = total + 1;else(if(Q1.look(next-data) = false)(Q1.add(next-data);total = total + 1;else(total_hit = total_hit + 1;next2 = Q1.front;while(next2-data.pagenumber != next-data.pagenumber)( next2 = nex

17、t2-link;next2-data.hit = next2-data.hit + 1;out.pagenumber = -1;/*Q2.add(out);else(if(Q1.look(next-data) = false)(next2 = Q1.front;min = Q1.front-data.hit;while(next2 != NULL)(if(next2-data.hit data.hit;next2 = next2-link;next2 = Q1.front;while(next2-data.hit != min)(置换出 next2-data 即最近一段时间使用次数最少的nex

18、t2 = next2-link;out = Q1.ChooseOut(next2-data);Q2.add(out);Q1.add(next-data);total = total + 1;else(total_hit = total_hit + 1;next2 = Ql.front;while(next2-data.pagenumber != next-data.pagenumber)( next2 = next2-link;next2-data.hit = next2-data.hit + 1;out.pagenumber = -1;/* Q2.add(out);next = next-l

19、ink;coutendl;coutLFU 算法:endl;cout”每次淘汰的页面号:”；Q2.output();coutendl;cout缺页中断total_hitendl;cout置换中断totalendl;cout缺页中断率total_hit/(total_hit+total)endl;cout置换中断率total/(total_hit+total)endl;coutendl;void Algorithm:SECOND(int T_data,int T_num)/二次机会算法Queue Q1; 内存中的页面Queue Q2; 被置换出去的页面Queue FIFO_Q; /将文档中的数构成

20、的矩阵转到队列中Node *next,*next2;page out;page T_x;/for(int i = 0;i=T_num;i+)/将文档中的数构成的矩阵转到队列中 T_x.pagenumber = T_datai;FIFO_Q.add(T_x);/next = FIFO_Q.front;while(next != NULL)if(Q1.num data);total = total + 1;else(if(Q1.look(next-data) = false)(Q1.add(next-data);total = total + 1;else(total_hit = total_hi

21、t + 1;next2 = Q1.front;while(next2-data.pagenumber != next-data.pagenumber)( next2 = next2-link;next2-data.R = 1;out.pagenumber = -1;/*Q2.add(out);else(if(Q1.look(next-data) = false)(next2 = Q1.front;while(next2 != NULL)(if(next2-data.R = 1)( next2-data.R = 0; Q1.Exchange(next2-data);else(out = Q1.p

22、utout();Q2.add(out);Q1.add(next-data);total = total + 1;break;next2 = Q1.front;else(total_hit = total_hit + 1;next2 = Q1.front;while(next2-data.pagenumber != next-data.pagenumber)( next2 = next2-link;next2-data.R = 1;out.pagenumber = -1；/*Q2.add(out);next = next-link;coutendl;coutSECOND 算法:endl;cout

23、”每次淘汰的页面号:”；Q2.output();coutendl;cout缺页中断total_hitendl;cout置换中断totalendl;cout缺页中断率”total_hit/(total_hit+total)endl;cout置换中断率total/(total_hit+total)endl;coutendl;8：主函数void main()(coutendlendlendl;coutendl;cout虚拟存储管理器的页面调度endl;coutendl;cout07信息与计算科学2班endl;cout陶弘杰20074704endl;cout2009.12.7endl;coutendl;coutendl;int x = 9;while(x != 0)(cout 1:FIFO 算法;2:LRU算法；3:LFU 算法endl;cout 4:SECOND算法；5:应用全部算法；0:退出”x;if(x = 0 ) break;int T_data258;int T_num = 0;char T_name50;int Array_data ;cout= 1 & x = 5)(coutT_na