FIFO页面置换算法，计算缺页率，文末附代码，及例题解析
1、内容
在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
模拟内存的页式管理，实现内存的分配和调用，完成虚拟内存地址序列和物理内存的对应。在内存调用出现缺页时，调入程序的内存页。在出现无空闲页面时，使用先进先出（FIFO）算法实现页面置换。
2、页的结构
页的结构如下：
页号、页面号、时间戳（在本算法中未使用，在LRU中使用）
FIFO页面置换算法选择在主存中停留时间最长(即最老)的一页置换，即先进入内存的页，先退出内存。理由是:最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上
通过使用线性表来实现页表，在每次需要淘汰页时，都是淘汰最先进入的页，这样就可以实现淘汰在主存中停留时间最长的页。
流程如下：
3、例题解析
在页式管理系统中，访问的顺序（访问串）为：1，2，3，4，1，2，5，1，2，3，4，5，当分配的页面数量为3时，请分别计算使用下述（1）替换算法的缺页次数，并画出页面置换图。
(1) FIFO。
缺页率：9/12=0.75
4、代码如下：
#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>#include <stdlib.h>#define MAX_PAGES 20#define MAX_PFRAME 20#define INVALID -1typedef struct {int page_num;int pframe_num;int count;int timestamp;}page_type;page_type page[MAX_PAGES];typedef struct pf_struct {int pframe_num;//页面号struct pf_struct* next;}pf_type;pf_type pframe[MAX_PFRAME];int diseffct = 0;//缺页记录void InitPage(const int* page_n, const int* pframe_n){int total_vp = *page_n, total_pf = *pframe_n;int i = 0;diseffct = 0;for (i = 0; i < total_vp; i++)//虚拟页{page[i].page_num = i;page[i].pframe_num = INVALID;page[i].count = 0;page[i].timestamp = -1;}for (i = 0; i < total_pf - 1; i++){pframe[i].next = &pframe[i];pframe[i].pframe_num = i;}pframe[total_pf - 1].next = NULL;pframe[total_pf - 1].pframe_num = total_pf - 1;}double miss_page_rate(int pframe_order[100]) {int i = 0;double missrate = 0, count = 0;while (pframe_order[i] != -1){count++;i++;}missrate = diseffct / count;return missrate;}void menu(int* page_n, int* pframe_n){int a, b;printf("---------------------------------------------\n");printf("请输入页面的数量：");scanf("%d", page_n);printf("请输入页的数量：");scanf("%d", pframe_n);printf("--------------------------------------------\n");}int get_input_order(int fprame_order[100], int pframe_n){int p = 0;int tmp = 0;printf("请输入访问串（1到%d中的数字,每输入一个数输入一次回车,输入-1表示结束）:\n", pframe_n);while (1){scanf("%d", &tmp);fprame_order[p] = tmp;p++;if (tmp == -1){break;}}return p;}int check_all_page(int page_num, int target){int judge = 0;for (int i = 0; i < page_num; i++){if (page[i].pframe_num == target){judge = 1;}}if (judge == 1){return 1;}else{diseffct++;//全程序只在本处处理缺页次数return 0;}}void display(int page_num, int judge)//就是打印出所有的页{printf("页面号\t页号\t时间戳\n");for (int i = 0; i < page_num; i++){printf("%d\t%d\t%d\n", page[i].page_num, page[i].pframe_num, page[i].timestamp);}if (judge == 1) {printf("不缺页\n");}else{printf("缺页\n");}}void FIFO(int page_num, int pframe_id)//page_num为页的数量，pframe_id为页面号{int i, j;pf_type* p;for (i = page_num - 2; i >= 0; i--){//page[i + 1].count = page[i].count;page[i + 1].pframe_num = page[i].pframe_num;}page[0].pframe_num = pframe_id;}void execute_pagef(int pframe_order[100], int page_num)//page_num为虚拟页的数量，page_n指针和page_num的值一样{int i = 0, jugde = 0;while (pframe_order[i] != -1){printf("************************************\n");printf("使用页 %d\n", pframe_order[i]);jugde = check_all_page(page_num, pframe_order[i]);if (jugde == 1) {//在虚拟页内i++;}else//不在页内就调用页面置换算法{FIFO(page_num, pframe_order[i]);i++;}display(page_num, jugde);}}int main(){int* page_n = (int*)malloc(sizeof(int));int* pframe_n = (int*)malloc(sizeof(int));int pframe_order[100];int order_num = 0;menu(page_n, pframe_n);InitPage(page_n, pframe_n);order_num = get_input_order(pframe_order, *pframe_n);execute_pagef(pframe_order, *page_n);//printf("%d %d\n", *page_n, *pframe_n);printf("\n缺页率为： %lf", miss_page_rate(pframe_order));free(page_n);free(pframe_n);return 0;}
5、运行如下：
程序分为5个页，内存中有3个页面，访问串是1、2、3、2、4、5、2
缺页率为：0.857143
