操作系统课程实验报告断。

当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。

而用来选择淘汰哪一页的规则叫做页面置换算法。

最简单的页面置换算法是先入先出（FIFO）法。

2、算法流程图3、步骤说明（1）初始化void init(){//初始化int i;for (i = 0; i < page_frame_number; i++){page_table[i].page_id = -1;page_table[i].load_time = -1;page_table[i].last_visit_time = -1;}}（2）选择算法，输入插入页面号。

进入判断函数int judge(){//判断页框是否满，或者页框里面是否已存在页面int i;for (i = 0; i < page_frame_number; i++){if (page_table[i].page_id == -1 || page_table[i].page_id == page_id)return i;}return -2;}之后根据返回数的不同决定了不同类型返回-2则说明页框满且页框里面没有存在要插入的页面。

返回-1则说明页框未满返回其它数则说明页框里存在相同的页面（3）//当没有空页框，并且页面本身也没有存在，则执行一下代码qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp);//按照装入时间从小到大排序page_table[0].page_id = page_id;page_table[0].load_time = counter;page_table[0].last_visit_time = counter;page_interrupt_number++;将页框号为0的页面置换成最新插入的页面。

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;}排序函数，将页面按装入时间从小到大排序（4）//如果页面未满，则将页面替换在空页框里if (page_table[j].page_id == -1){page_table[j].page_id = page_id;page_table[j].load_time = counter;page_table[j].last_visit_time = counter;page_interrupt_number++;则将页面替换在页框号最小的空页框里（5）//如果页面本身存在页框中，则执行一下代码page_table[j].last_visit_time = counter;则更新页面的最近访问时间（6）qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp3);//按照装入时间从小到大排序print(2);打印出页表详细信息printf("页表信息：\n页号页框号装入时间最近访问时间\n");for (j = 0; j < page_frame_number; j++){printf("%4d%8d%7d%7d\n", page_table[j].page_id, j, page_table[j].load_time,page_table[j].last_visit_time);}; break;排序函数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;elsereturn -1;}}（7）并计算出中断页面次数及命中概率，并打印页表出来int sum;sum = ((virtual_page_number - page_interrupt_number) * 100 / virtual_page_number);printf("缺页中断次数：%d\n", 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", pr[i][g]);}printf("\n");}4、实现（1）选择FIFO算法（2）输入页面号，列出页表详细信息（3）输入-1，结束输入，显示统计结果及页表二、最近最少使用页面置换算法1、基本思想：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。

反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。

这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。

因此，我们只需要在每次调换时，找到最近最久使用的那个页面调出内存。

2、算法流程图3、步骤说明：（1）初始化void init(){//初始化int i;for (i = 0; i < page_frame_number; i++){page_table[i].page_id = -1;page_table[i].load_time = -1;page_table[i].last_visit_time = -1;}}（2）选择算法，输入插入页面号。

进入判断函数int judge(){//判断页框是否满，或者页框里面是否已存在页面int i;for (i = 0; i < page_frame_number; i++){if (page_table[i].page_id == -1 || page_table[i].page_id == page_id) return i;}return -2;}之后根据返回数的不同决定了不同类型返回-2则说明页框满且页框里面没有存在要插入的页面。

返回-1则说明页框未满返回其它数则说明页框里存在相同的页面（3）//当没有空页框，并且页面本身也没有存在，则执行一下代码qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp1);//按照最后访问时间从小到大排序page_table[0].page_id = page_id;page_table[0].load_time = counter;page_table[0].last_visit_time = counter;page_interrupt_number++;将页框号为0的页面置换成最新插入的页面。

int cmp1(const void *p, const void *q){//按照最后访问时间从小到大排序int c = (*(struct Page_table*)p).last_visit_time - (*(structPage_table*)q).last_visit_time;if (c > 0)return 1;elsereturn -1;}排序函数，将页面按最后访问时间从小到大排序（4）//如果页面未满，则将页面替换在空页框里if (page_table[j].page_id == -1){page_table[j].page_id = page_id;page_table[j].load_time = counter;page_table[j].last_visit_time = counter;page_interrupt_number++;则将页面替换在页框号最小的空页框里（5）//如果页面本身存在页框中，则执行一下代码page_table[j].last_visit_time = counter;则更新页面的最近访问时间（6）qsort(page_table, page_frame_number, sizeof(struct Page_table), cmp2);//按照最后访问时间从小到大排序print(2);打印出页表详细信息printf("页表信息：\n页号页框号装入时间最近访问时间\n");for (j = 0; j < page_frame_number; j++){printf("%4d%8d%7d%7d\n", page_table[j].page_id, j, page_table[j].load_time, page_table[j].last_visit_time);}; break;排序函数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 - (*(structPage_table*)q).last_visit_time;if (c > 0)return 1;elsereturn -1;}}（7）并计算出中断页面次数及命中概率，并打印页表出来int sum;sum = ((virtual_page_number - page_interrupt_number) * 100 / virtual_page_number);printf("缺页中断次数：%d\n", 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", pr[i][g]);}printf("\n");}4、实现（1）选择LRU算法（2）输入页面号，并打印出详细页表（3）输入-1，结束输入，显示统计结果及页表三、代码// ConsoleApplication2.cpp : 定义控制台应用程序的入口点。