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

《第7次常用页面置换算法模拟实验.doc》由会员分享，可在线阅读，更多相关《第7次常用页面置换算法模拟实验.doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流第7次 常用页面置换算法模拟实验.精品文档.操作系统课程实验报告姓名学号系计算机科学与技术任课教师贺辉指导教师贺辉评阅教师贺辉实验地点实验时间实验编号与实验名称：第7次 常用页面置换算法模拟实验实验目的：通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。实验内容及要求（详见实验讲义）：实验要求： 1）要求用你熟悉的程序设计语言编写和调试一个页面置换模拟程序；要求在主函数中测试。2）实验报告中必须包括：设计思想、数据定义（包括详细

2、说明）、处理流程（详细算法描述和算法流程图）、源代码、运行结果、体会等部分。3）必须模拟本实验内容中提到的算法中的至少2种页面置换算法。4） 比较不同页面置换算法的效率实验内容编写一个程序，使用以下页面置换算法中的某2种分别模拟一个分页系统，并统计同一个页面访问序列情况下不同页面置换算法引发的缺页中断次数。1、第二次机会算法（Second Chance）2、最近最少使用算法（Least Recently Used，LRU ）3、最不常用算法（Not Frequently Used，NFU）4、最近未使用算法（Not Recently Used ，NRU）5、时钟页面置换算法6、老化算法（agi

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

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

5、d = 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(struct Page_table), cmp3);/按照装入时间从小到大排序 print(2);打印出页表详细信息

6、printf(页表信息：n页 号 页框号 装入时间 最近访问时间n);for (j = 0; j 0)return 1;elsereturn -1;（7）并计算出中断页面次数及命中概率，并打印页表出来int sum;sum = (virtual_page_number - page_interrupt_number) * 100 / virtual_page_number);printf(缺页中断次数：%dn, page_interrupt_number);printf(中断命中率：%d%n, sum);printf(打印出页面n);for (int i = 0; i page_frame_n

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

8、2、算法流程图3、 步骤说明：（1）初始化void init()/初始化 int i;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）选择算法，输入插入页面号。进入判断函数int judge()/判断页框是否满，或者页框里面是否已存在页面int i;for (i = 0; i 0)return 1;elsereturn -1;排序函数，将页面按最后访问时间从小到大排序（4）/如果页面未满，则将页面

9、替换在空页框里if (page_tablej.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(stru

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

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

12、espace std;#define page_frame_number 4 /页框数 #define virtual_page_number 8 /虚拟页面数 int page_id, counter = 0;/输入id和计数器 char algorithm20;/算法选择 int page_interrupt_number = 0;int count=0;/计数器int prpage_frame_numbervirtual_page_number;struct Page_tableint page_id; /页号 int load_time; /装入时间 int last_visit_ti

13、me; /最后访问时间 page_tablepage_frame_number;/页框int cmp(const void *p, const void *q)/按照装入时间从小到大排序 int c = (*(struct Page_table*)p).load_time - (*(struct Page_table*)q).load_time;if (c 0)return 1;elsereturn -1;int cmp1(const void *p, const void *q)/按照最后访问时间从小到大排序int c = (*(struct Page_table*)p).last_visi

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

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

16、lsereturn -1;void init()/初始化 int i;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(int x)/打印信息 int i, j;switch (x)case 0:for (i = 0; i 80; i+)printf(-);printf(tt试验七 常用页面置换算法模拟实验n);for (i = 0; i 80; i+)printf(-);print

17、f(n);printf(选择算法：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 80; i+)pr

18、intf(-);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);int judge()/判断页框是否满，或者页框里面是否已存在页面int i;for (i = 0; i page_id;if (page_id = -1)break;j = judge();if (j = -2)/当没有空页框，并且页面本身也

19、没有存在，则执行一下代码qsort(page_table, page_frame_number, sizeof(struct Page_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_tablej.page_id = page_id;

20、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(struct Page_table), cmp3);/按照装入时间从小到大排序 print(2);for (int i = 0; i page_frame_number; i+)pri

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

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

23、page_tablej.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(struct Page_table), cmp2);/按照最后访问时间从小到大排序print(2);for (int i =

24、 0; i page_frame_number; i+)pricounter = page_tablei.page_id;int sum;sum = (virtual_page_number - page_interrupt_number) * 100 / virtual_page_number);printf(缺页中断次数：%dn, page_interrupt_number);printf(中断命中率：%d%n, sum);printf(打印出页面n);for (int i = 0; i page_frame_number; i+)for (int g = 1; g algorithm;if (strcmp(algorithm, F) = 0 | strcmp(algorithm, L) = 0)break;elseprintf(输入出错，请重新输入n);if (strcmp(algorithm, F) = 0)fifo();elselru();system(pause);return 0;实验过程中遇到的问题解决办法与实验体会（10分）【请注意：此处必须如实填写，为空或不适均扣10分】