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

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

2、本实验内容中提到的算法中的至少2种页面JL换算法。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。实验输入为访问页面序列，比如0, 1

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

4、_time = -1;page_tablei last_visit_time = T；(2) 选择算法，输入插入页面号。进入判斷函数int judge()age_id = T 11 page_tableipage_id page_id) return i;return -2;之后根据返回数的不同决定了不同矣型返回-2则说明页框满且页框里面没有存在要插入的页面。返回-1則说明页框未满返回其它数則说明页框里存在相同的页面(3) age_id = page_id;page_table0 Ioad_time = counter；page_table0 Iast_visit_time = counter

5、；page_interrupt_number+；将页框号为0的页面置换成最新插入的页面。int cmp(const void *pf const void *q)oad_time - (*(struct Page_table*)q) load_time；if (c 0)return 1;elsereturn -1;排序函数，将页面按装入时间从小到大排序(4) aged = -1) Ipage_tablejpage_id = page_id;page_tablej Ioad_time = counter；page_tablej Iast_visit_time = counter;page_int

6、errupt_number+；则将页面替换在页框号呆小的空页框里(5) ast_visit_time = counter;则更新页面的最近访问时间(6) qsort(page_table, page_.frame_number, sizeof (struct Page_table), cmp3) ；age_id, j, page_tablej Ioad_time, page_tablej Iast_visit_time); break；排序函数int cmp3(const void *pt const void *q) age_id != -1 & (*(struct Page_tabIe*)

7、q). paged != -1)1int c = (*(struct Page_tabIe*)p). Ioad_time - (*(struct Page_tabIe*)q). Ioad_time: if (c 0)return 1;elsereturn -1;(7) 并计算出中断页面次数及命中概平，并打印页表出来int sum；sum = (virtual_page_number - page_interrupt_number) * 100 / virtual_page_number);pr intf (缺页中斯次数:%dnM, pagenterrupt_number)；printf(中断命

8、中率:%d%n sum)；printf(打印出页面nH);for (int i =0; i page_frame_number; i+)for (i nt g = 1; g 0)return 1;elsereturn -1;排序函数，将页面按最后访问时间从小到大排序(4) aged = -1) page_tablejpage_id = page_id;page_tablej Ioad_time = counter；page_tablej Iast_visit_time = counter;page_interrupt_number+；则将页面替换在页框号呆小的空页框里(5) ast_visit

9、_time = counter;则更新页面的最近访问时间(6) qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp2)；age_id, j, page_tablej Ioad_time, page_tablej Iast_visit_time); break；排序函数int cmp2(const void *p, const void *q)age_id != -1 & (*(struct Page_tabIe*)q).page_id != -1)int c = (*(struct PagetabIe*)p).

10、 Iast_visit_time - (*(structPage_tabIe*)q) last_vis it_t ime;if (c 0)return 1;elsereturn -1;(刀并计算出中断页面次数及命中概平，并打印页表出来int sum；sum = (virtuaLpage_number - page_interrupt_number) * 100 / virtual_page_number); pr intf (缺页中斷次數:%dnM, page_i nter rupt_number);printf(中斯命中半：%d%n sum)；printfC打印出页面nH)；for (int

11、 i =0; i page_frame_number； i+)for (i nt g = 1; g 0)return 1;elsereturn -1;1void init () age_id = T ;page_tablei Ioad_time = -1;page_tablei Iast_visit_time = -1;1void pr int(int x) age_id, j, page_tablej Ioad_time, page_tablej Iast_visit_time); break；case 3:for (i = 0; i 80: i+)pr intf (,-n);printf

12、(HttFIF0 算法模拟过程rT);for (i = 0; i 80; i卄)printf ;pr intf (Xn*); break;case 4：for (i = 0; i 80; i+)pr intf ;printf(HttLRU 算法模拟过程n”)；for (i = 0; i 80; i卄)printf ;printf (Xn);int judge()age_id = -1 | page_tableipage_id = page_id)return i;return -2;1void fifoO int j;print；print；printf (-请依次输入页面号(最多8个。输入-

13、1结束输入，统计出缺页次数):M); while (1) cin page_id;if (page_id = -1)break；j = judge 0;if (j -2)age_id = page_id;page_table0 Ioad_time = counter；page_table0 Iast_visit_time = counter;page_i nter rupt_number+；1else age_id = -1)page_tablejpage_id = page_id;page_tablej Ioad_time = counter；page_tablej Iast_visit_t

14、ime = counter; page_interrupt_number+;eIseast_v i s i t_t i me = counter;counter*；qsort (page_table, page_frame_number, sizeof (struct Page_table), cmp3)；age_id;1int sum；sum = (virtuaI_page_number - page_interrupt_number) * 100 / virtual_page_number); pr intf (缺页中斷次数:%dn, pagenterrupt_number);pr int

15、f (中斯命中半：sum)；printfC打印出页面nH)；for (int i =0; i page_frame_number； i+)for (int g = 1; g = virtual_page_number; g+)pr intf (r，%4dM, pr i g);1pr intf (nn,f);1 void IruO int j;print；print；printfC请依次输入页面号(最多8个。输入T结束输入,统计出缺页次数):M);while (1) cin page_id;if (page_id = -1)break；j = judge 0; if (j -2)age_id =

16、 page_id;page_table0 Ioad_time = counter；page_table0 Iast_visit_time = counter；page_i nter rupt_number+；1else if (page_tabIej. paged = -1) age_id = page_id;page_tablej Ioad_time = counter；page_tablej Iast_visit_time = counter;page_int e r r upt_numbe r +;eIseast_v i s i t_t i me = counter；counter*；q

17、sort (page_table, page_frame_number, sizeof (struct Page_table), cmp2);age_id;1int sum；sum = (virtual_page_number - page_interrupt_number) * 100 / virtual_page_number); pr intf (缺页中断次数：%dnn, page_interrupt_number)；pr intf (中斯命中半：%d%n sum)；printf(-打印出页面nH);for (int i =0; i page_frame_number; i+)for (i nt g = 1; g = v i rtual_page_number； g+)printf(R%4dM, prig)；1pr intf (Mn,f);