《2022年第次常用页面置换算法模拟实验 .pdf》由会员分享，可在线阅读，更多相关《2022年第次常用页面置换算法模拟实验 .pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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、基本思想：地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 16 页 - - - - - - - - - 断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面
4、置换算法。最简单的页面置换算法是先入先出（ FIFO）法。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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -
5、- - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 16 页 - - - - - - - - - for (i = 0; i 0) return 1; elsereturn -1; 排序函数，将页面按装入时间从小到大排序（4）/ 如果页面未满，则将页面替换在空页框里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_
6、number+; 则将页面替换在页框号最小的空页框里（5）/ 如果页面本身存在页框中，则执行一下代码page_tablej.last_visit_time = counter; 则更新页面的最近访问时间（6）qsort(page_table, page_frame_number, sizeof ( structPage_table ), cmp3);/ 按照装入时间从小到大排序print(2); 打印出页表详细信息printf(页表信息： n 页号页框号装入时间最近访问时间 n ); for (j = 0; j 0) return 1; elsereturn -1; （7）并计算出中断页面次数
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_number; i+) for ( int g = 1; g = virtual_page_number; g+) printf(%4d, pri
8、g); printf(n ); 4、实现（1）选择 FIFO 算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 16 页 - - - - - - - - - （2）输入页面号，列出页表详细信息名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 16 页 - - - - - - - - - （3）输入 -1，结束输入，显示统计结果及页表二、最近最少使用页
9、面置换算法1、基本思想：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最久使用的那个页面调出内存。2、算法流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 16 页 - - - - - - - - - 3、步骤说明：（1）初始化void init()/ 初始化i
10、nt 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）/ 如果页面未满，则将页面替换在空页框里if (page_tablej.page
11、_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
12、p2);/ 按照最后访问时间从小到大排序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( 中断命中率： %d%n
13、, 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）输入页面号，并打印出详细页表名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 16 页 - - - - - - - - - （3）输入 -1，结束输
14、入，显示统计结果及页表名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 16 页 - - - - - - - - - 三、代码/ ConsoleApplication2.cpp : 定义控制台应用程序的入口点。/#includestdafx.h#include#include#include#includeusingnamespace std; #definepage_frame_number 4 / 页框数#definevirtual_page_number 8 / 虚
15、拟页面数int page_id, counter = 0;/ 输入 id 和计数器char algorithm20;/ 算法选择int page_interrupt_number = 0; int count=0; / 计数器int pr page_frame_number virtual_page_number; structPage_table int page_id; / 页号int load_time; / 装入时间int last_visit_time; / 最后访问时间page_tablepage_frame_number; / 页框int cmp( constvoid * p,
16、constvoid * q) / 按照装入时间从小到大排序int c = (*(structPage_table *) p).load_time - (*(structPage_table *) q).load_time; if (c 0) return 1; elsereturn -1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 16 页 - - - - - - - - - int cmp1( constvoid * p, constvoid * q) / 按照
17、最后访问时间从小到大排序int c = (*(structPage_table *) p).last_visit_time - (*(structPage_table *) q).last_visit_time; if (c 0) return 1; elsereturn -1; int cmp2(constvoid * p, constvoid * q) / 按照最后访问时间从小到大排序, ，并且不要排序没页面的部分if (*(structPage_table *) p).page_id != -1 & (*(structPage_table *) q).page_id != -1) int
18、 c = (*(structPage_table *) p).last_visit_time - (*(structPage_table *) q).last_visit_time; if (c 0) return 1; elsereturn -1; int cmp3(constvoid * p, constvoid * q) / 按照装入时间从小到大排序, ，并且不要排序没页面的部分if (*(structPage_table *) p).page_id != -1 & (*(structPage_table *) q).page_id != -1) int c = (*(structPag
19、e_table *) p).load_time - (*(structPage_table *) q).load_time; if (c 0) return 1; elsereturn -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(intx) / 打印信息int i, j; switch ( x) 名师资料总结 - -
20、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 16 页 - - - - - - - - - case 0: for (i = 0; i 80; i+) printf(- ); printf(tt试验七常用页面置换算法模拟实验n ); for (i = 0; i 80; i+) printf(- ); printf(n ); printf(选择算法： F/L（FIFO算法/LRU 算法） n ); break; case 1:printf(请输入访问页面的顺序, 以“-1”结束： n );
21、 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+) printf(- ); printf(ttFIFO算法模拟过程 n ); for (i = 0; i 80; i+) printf(- );
22、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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共
23、 16 页 - - - - - - - - - break ; j = judge(); if (j = -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
24、 / 如果页面未满，则将页面替换在空页框里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+; else / 如果页面本身存在页框中，则执行一下代码page_tablej.last_visit_time = counter; counter+; qsort(page_table, page_frame_number, sizeof ( s
25、tructPage_table ), cmp3);/ 按照装入时间从小到大排序print(2); for ( int i = 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( 打印
26、出页面 n ); for ( int i = 0; i page_frame_number; i+) for ( int g = 1; g page_id; if (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 = c
27、ounter; 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.last_visit_time = counter; page_interrupt_number+; else / 如果页面本身存在页框中，则执行一下代码page_tablej.last_visit
28、_time = counter; counter+; qsort(page_table, page_frame_number, sizeof ( structPage_table ), cmp2);/ 按照最后访问时间从小到大排序print(2); for ( int i = 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(
29、 缺页中断次数： %dn, page_interrupt_number); printf( 中断命中率： %d%n , sum); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 16 页 - - - - - - - - - printf( 打印出页面 n ); for ( int i = 0; i page_frame_number; i+) for ( int g = 1; g algorithm; if (strcmp(algorithm, F ) = 0 | s
30、trcmp(algorithm, L ) = 0) break ; elseprintf(输入出错，请重新输入n ); if (strcmp(algorithm, F ) = 0) fifo(); else lru(); system( pause ); return 0; 实验过程中遇到的问题解决办法与实验体会（10 分）【 请注意： 此处必须如实填写，为空或不适均扣 10 分】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 16 页 - - - - - - - - -