第7次常用页面置换算法模拟实验

1、.操作系统 课程实验报告姓名学号系计算机科学与技术任课教师贺辉指导教师贺辉评阅教师贺辉实验地点实验时间实验编号与实验名称：第 7 次常用页面置换算法模拟实验实验目的：通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。实验内容及要求（详见实验讲义）：实验要求 ：1）要求用你熟悉的程序设计语言编写和调试一个页面置换模拟程序；要求在主函数中测试。2）实验报告中必须包括：设计思想、数据定义（包括详细说明）、处理流程（详细算法描述和算法流程图）、源代码、运行结果、体会等部分。3）必须模拟

2、本实验内容中提到的算法中的至少2 种页面置换算法。4） 比较不同页面置换算法的效率实验内容编写一个程序，使用以下页面置换算法中的某2 种分别模拟一个分页系统，并统计同一个页面访问序列情况下不同页面置换算法引发的缺页中断次数。1、第二次机会算法（Second Chance）2、最近最少使用算法（Least Recently Used， LRU）3、最不常用算法（Not Frequently Used ， NFU ）4、最近未使用算法（Not Recently Used ， NRU ）5、时钟页面置换算法6、老化算法（ aging）页框的数量固定为4，虚拟页面数为 8。实验输入为访问页面序列，比如

3、0，1 ，3 ，2，7，1实验用到的软件（：）Vs， word， processon实验内容、 关键步骤（流程图、代码等）及结果分析（ 70 分）一、先进先出页面置换算法1、基本思想：地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中.断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。最简单的页面置换算法是先入先出（ FIFO）法。2、算法流程图3、步骤说明（1）初始化void init()/ 初始化inti;for (i = 0; i page_frame_number; i+)page

4、_tablei.page_id = -1;page_tablei.load_time = -1;page_tablei.last_visit_time = -1;（2）选择算法，输入插入页面号。进入判断函数intjudge()/ 判断页框是否满，或者页框里面是否已存在页面inti;.for (i = 0; i 0)return1;elsereturn-1;排序函数，将页面按装入时间从小到大排序（ 4）/ 如果页面未满，则将页面替换在空页框里 if (page_tablej.page_id = -1)page_tablej.page_id = page_id;page_tablej.load_t

5、ime = counter;page_tablej.last_visit_time = counter;page_interrupt_number+;则将页面替换在页框号最小的空页框里（5）/ 如果页面本身存在页框中，则执行一下代码page_tablej.last_visit_time = counter;则更新页面的最近访问时间（6）qsort(page_table,page_frame_number,sizeof ( structPage_table ), cmp3);/ 按照装入时间从小到大排序print(2);打印出页表详细信息printf( 页表信息： n 页号页框号装入时间最近访问

6、时间 n );for (j = 0; j 0)return1;elsereturn-1;（7）并计算出中断页面次数及命中概率，并打印页表出来intsum;sum = ( virtual_page_number- page_interrupt_number) * 100 /virtual_page_number);printf( 缺页中断次数： %dn , page_interrupt_number);printf( 中断命中率： %d%n, sum);printf( 打印出页面 n );for ( inti = 0; i page_frame_number; i+)for ( intg = 1

7、; g =virtual_page_number; g+)printf(%4d, prig);printf(n );4、实现（1）选择 FIFO 算法.（2）输入页面号，列出页表详细信息.（3）输入 -1 ，结束输入，显示统计结果及页表二、最近最少使用页面置换算法1、基本思想：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理比内存速度还要快的 cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最久使用的那个页面调出内存。2、算法流程图.3、步骤说明：（1）

8、初始化void init()/ 初始化inti;for (i = 0; i page_frame_number; i+)page_tablei.page_id = -1;page_tablei.load_time = -1;page_tablei.last_visit_time = -1;（2）选择算法，输入插入页面号。进入判断函数intjudge()/ 判断页框是否满，或者页框里面是否已存在页面inti;for (i = 0; i 0)return1;elsereturn-1;排序函数，将页面按最后访问时间从小到大排序（ 4）/ 如果页面未满，则将页面替换在空页框里 if (page_tab

9、lej.page_id = -1)page_tablej.page_id = page_id;page_tablej.load_time = counter;page_tablej.last_visit_time = counter;page_interrupt_number+;则将页面替换在页框号最小的空页框里（5）/ 如果页面本身存在页框中，则执行一下代码page_tablej.last_visit_time = counter;则更新页面的最近访问时间（6）qsort(page_table,page_frame_number,sizeof ( structPage_table ), cm

10、p2);/ 按照最后访问时间从小到大排序print(2);打印出页表详细信息printf( 页表信息： n 页号页框号装入时间最近访问时间 n );for (j = 0; j 0)return1;elsereturn-1;（7）并计算出中断页面次数及命中概率，并打印页表出来intsum;sum = ( virtual_page_number- page_interrupt_number) * 100 /virtual_page_number);printf( 缺页中断次数： %dn , page_interrupt_number);printf( 中断命中率： %d%n, sum);print

11、f( 打印出页面 n );for ( inti = 0; i page_frame_number; i+)for ( intg = 1; g =virtual_page_number; g+)printf(%4d, prig);printf(n );4、实现（1）选择 LRU 算法（2）输入页面号，并打印出详细页表.（3）输入 -1 ，结束输入，显示统计结果及页表.三、代码/ ConsoleApplication2.cpp :定义控制台应用程序的入口点。/#includestdafx.h#include#include#include#includeusing namespace std;#d

12、efinepage_frame_number 4/ 页框数#definevirtual_page_number8 / 虚拟页面数intpage_id, counter = 0;/输入 id 和计数器char algorithm20;/算法选择intpage_interrupt_number = 0;intcount=0; / 计数器intprpage_frame_number virtual_page_number ;structPage_table intpage_id; / 页号intload_time;/装入时间intlast_visit_time;/最后访问时间page_table p

13、age_frame_number; / 页框intcmp( constvoid* p, const void * q) / 按照装入时间从小到大排序intc = (*(structPage_table *) p).load_time - (*(struct Page_table *) q).load_time;if(c 0)return1;elsereturn-1;.intcmp1( constvoid * p,constvoid * q) / 按照最后访问时间从小到大排序intc = (*(structPage_table *) p).last_visit_time - (*(structP

14、age_table *) q).last_visit_time;if(c 0)return1;elsereturn-1;int cmp2( const void * p, const void * q) / 按照最后访问时间从小到大排序 , ，并且不要排序没页面的部分if(*(structPage_table *) p).page_id != -1 & (*(structPage_table *) q).page_id != -1)intc = (*(structPage_table *) p).last_visit_time - (*(structPage_table *) q).last_

15、visit_time;if(c 0)return1;elsereturn-1;int cmp3( const void * p, const void * q) / 按照装入时间从小到大排序 , ，并且不要排序没页面的部分if(*(structPage_table *) p).page_id != -1 & (*(structPage_table *) q).page_id != -1)intc = (*(structPage_table *) p).load_time - (*(structPage_table *) q).load_time;if(c 0)return1;elseretur

16、n-1;void init()/ 初始化inti;for (i = 0; i page_frame_number; i+)page_tablei.page_id = -1;page_tablei.load_time = -1;page_tablei.last_visit_time = -1;void print(intx ) / 打印信息inti, j;switch( x).case 0:for (i = 0; i 80; i+)printf(- );printf(tt试验七常用页面置换算法模拟实验n );for (i = 0; i 80; i+)printf(- );printf(n );p

17、rintf( 选择算法： F/L （ FIFO 算法 /LRU 算法） n );break ;case 1:printf( 请输入访问页面的顺序, 以“ -1 ”结束： n );break ;case 2:printf( 页表信息： n 页号页框号装入时间最近访问时间 n );for (j = 0; j page_frame_number; j+)printf(%4d%8d%7d%7dn, page_tablej.page_id, j, page_tablej.load_time,page_tablej.last_visit_time);break ;case 3: for (i = 0; i

18、 80; i+)printf(- );printf(ttFIFO算法模拟过程 n );for (i = 0; i 80; i+)printf(- );printf(n );break ;case 4: for (i = 0; i 80; i+)printf(- );printf(ttLRU算法模拟过程 n );for (i = 0; i 80; i+)printf(- );printf(n );intjudge()/ 判断页框是否满，或者页框里面是否已存在页面inti;for (i = 0; i page_id;if(page_id = -1).break ;j = judge();if(j

19、= -2)/ 当没有空页框，并且页面本身也没有存在，则执行一下代码qsort(page_table,page_frame_number, sizeof ( structPage_table ), cmp);/ 按照装入时间从小到大排序page_table0.page_id = page_id;page_table0.load_time = counter;page_table0.last_visit_time = counter;page_interrupt_number+;else / 如果页面未满，则将页面替换在空页框里if(page_tablej.page_id = -1)page_ta

20、blej.page_id = page_id;page_tablej.load_time = counter;page_tablej.last_visit_time = counter;page_interrupt_number+;else / 如果页面本身存在页框中，则执行一下代码page_tablej.last_visit_time = counter;counter+;qsort(page_table,page_frame_number,sizeof ( structPage_table ), cmp3);/ 按照装入时间从小到大排序print(2);for ( inti = 0; i

21、page_frame_number; i+)pricounter = page_tablei.page_id;intsum;sum = ( virtual_page_number- page_interrupt_number) * 100 /virtual_page_number);printf( 缺页中断次数： %dn , page_interrupt_number);printf( 中断命中率： %d%n, sum);printf( 打印出页面 n );for ( inti = 0; i page_frame_number; i+)for ( intg = 1; g page_id;if(

22、page_id = -1)break ;j = judge();if(j = -2)/ 当没有空页框，并且页面本身也没有存在，则执行一下代码qsort(page_table,page_frame_number,sizeof ( structPage_table ), cmp1);/ 按照最后访问时间从小到大排序page_table0.page_id = page_id;page_table0.load_time = counter;page_table0.last_visit_time = counter;page_interrupt_number+;else if(page_tablej.page_id = -1) / 如果页面未满，则将页面替换在空页框里 page_tablej.page_id = page_id;page_tablej.load_time = counter;page_tablej.las