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

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、老化算法（aging） 页框的数量固定为4，虚拟页面数为8。实验输入为访问页面序列

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

4、ast_visit_time = -1; （2）选择算法，输入插入页面号。进入判断函数int judge()age_id = -1 | page_tablei.page_id = page_id) return i; return -2;之后根据返回数的不同决定了不同类型返回-2则说明页框满且页框里面没有存在要插入的页面。返回-1则说明页框未满返回其它数则说明页框里存在相同的页面（3）age_id = page_id; page_table0.load_time = counter; page_table0.last_visit_time = counter; page_interrupt_n

5、umber+;将页框号为0的页面置换成最新插入的页面。int cmp(const void *p, const void *q)oad_time - (*(struct Page_table*)q).load_time; if (c 0) return 1; else return -1;排序函数，将页面按装入时间从小到大排序（4）age_id = -1) page_tablej.page_id = page_id; page_tablej.load_time = counter; page_tablej.last_visit_time = counter; page_interrupt_nu

6、mber+;则将页面替换在页框号最小的空页框里（5）ast_visit_time = counter;则更新页面的最近访问时间（6）qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp3);age_id, j, page_tablej.load_time, page_tablej.last_visit_time); ; break;排序函数int cmp3(const void *p, const void *q)age_id != -1 & (*(struct Page_table*)q).page_id !=

7、 -1) int c = (*(struct Page_table*)p).load_time - (*(struct Page_table*)q).load_time; if (c 0) return 1; else return -1; （7）并计算出中断页面次数及命中概率，并打印页表出来int sum; sum = (virtual_page_number - page_interrupt_number) * 100 / virtual_page_number); printf(缺页中断次数：%dn, page_interrupt_number); printf(中断命中率：%d%n,

8、sum); printf(打印出页面n); for (int i = 0; i page_frame_number; i+) for (int g = 1; g 0) return 1; else return -1;排序函数，将页面按最后访问时间从小到大排序（4）age_id = -1) page_tablej.page_id = page_id; page_tablej.load_time = counter; page_tablej.last_visit_time = counter; page_interrupt_number+;则将页面替换在页框号最小的空页框里（5）ast_visi

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

10、)p).last_visit_time - (*(struct Page_table*)q).last_visit_time; if (c 0) return 1; else return -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);

11、for (int i = 0; i page_frame_number; i+) for (int g = 1; g 0) return 1; else return -1;int cmp1(const void *p, const void *q)ast_visit_time - (*(struct Page_table*)q).last_visit_time; if (c 0) return 1; else return -1;int cmp2(const void *p, const void *q)age_id != -1 & (*(struct Page_table*)q).page

12、_id != -1) int c = (*(struct Page_table*)p).last_visit_time - (*(struct Page_table*)q).last_visit_time; if (c 0) return 1; else return -1; int cmp3(const void *p, const void *q)age_id != -1 & (*(struct Page_table*)q).page_id != -1) int c = (*(struct Page_table*)p).load_time - (*(struct Page_table*)q

13、).load_time; if (c 0) return 1; else return -1; void init()age_id = -1; page_tablei.load_time = -1; page_tablei.last_visit_time = -1; void print(int x)age_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

14、 80; i+) printf(-); printf(n); break; case 4:for (i = 0; i 80; i+) printf(-); printf(ttLRU算法模拟过程n); for (i = 0; i page_id; if (page_id = -1) break; j = judge(); if (j = -2)age_id = page_id; page_table0.load_time = counter; page_table0.last_visit_time = counter; page_interrupt_number+; elseage_id = -

15、1) page_tablej.page_id = page_id; page_tablej.load_time = counter; page_tablej.last_visit_time = counter; page_interrupt_number+; elseast_visit_time = counter; counter+; qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp3);age_id; int sum; sum = (virtual_page_number - page_interrupt

16、_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(); if (j = -2)age_id = page_id; page_table0.load_time = counter; page_tabl

17、e0.last_visit_time = counter; page_interrupt_number+; else if (page_tablej.page_id = -1)age_id = page_id; page_tablej.load_time = counter; page_tablej.last_visit_time = counter; page_interrupt_number+; elseast_visit_time = counter; counter+; qsort(page_table, page_frame_number, sizeof(struct Page_ta

18、ble), cmp2);age_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; else printf(输入出错，请重新输入n); if (strcmp(algorithm, F) = 0) fifo(); else lru(); system(pause); return 0;实验过程中遇到的问题解决办法与实验体会（10分）【请注意：此处必须如实填写，为空或不适均扣10分】