FIFO页面置换算法，计算缺页率，文末附代码，及例题解析
1、内容
在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
模拟内存的页式管理，实现内存的分配和调用，完成虚拟内存地址序列和物理内存的对应。在内存调用出现缺页时，调入程序的内存页。在出现无空闲页面时，使用先进先出（FIFO）算法实现页面置换。
2、页的结构
页的结构如下：
页号、页面号、时间戳（在本算法中未使用，在LRU中使用）
名称 | 符号 | 功能 |
页号 | Page_num | 记录页号 |
页面号 | Pframe_num | 记录页面号 |
FIFO页面置换算法选择在主存中停留时间最长(即最老)的一页置换，即先进入内存的页，先退出内存。理由是:最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上
通过使用线性表来实现页表，在每次需要淘汰页时，都是淘汰最先进入的页，这样就可以实现淘汰在主存中停留时间最长的页。
流程如下：
3、例题解析
在页式管理系统中，访问的顺序（访问串）为：1，2，3，4，1，2，5，1，2，3，4，5，当分配的页面数量为3时，请分别计算使用下述（1）替换算法的缺页次数，并画出页面置换图。
(1) FIFO。
| 访问串 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
| 页面1 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 5 | 5 | 3 | 4 | 4 |
| 页面2 | 1 | 2 | 3 | 4 | 1 | 2 | 2 | 2 | 5 | 3 | 3 | |
| 页面3 | 1 | 2 | 3 | 4 | 1 | 1 | 1 | 2 | 5 | 5 | ||
| 是否缺页 | 是 | 是 | 是 | 是 | 是 | 是 | 是 | 否 | 否 | 是 | 是 | 否 |
缺页率：9/12=0.75
4、代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include#include#define MAX_PAGES 20
#define MAX_PFRAME 20
#define INVALID -1
typedef 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;//缺页记录
int round = 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
{
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
{
diseffct++;//全程序只在本处处理缺页次数
printf("缺页\n");
}
}
int get_min_times(int page_num)
{
int i = 0, mintime = 2147483647, index = 0;
for (i = 0; i< page_num; i++)
{
if (page[i].timestamp< mintime)
{
mintime = page[i].timestamp;
index = i;
}
}
return index;
}
void LRU(int page_num, int pframe_id)
{
int empty = 0, index = 0;
for (int i = 0; i< page_num; i++)
{
if (page[i].pframe_num == -1) {
empty = 1;
index = i;
break;
}
}
if (empty == 1)//有空位置
{
page[index].pframe_num = pframe_id;
page[index].timestamp = round;
}
else//缺页
{
index = get_min_times(page_num);
page[index].pframe_num = pframe_id;
page[index].timestamp = round;
}
}
int get_index(int page_num, int target)
{
int index = 0;
for (int i = 0; i< page_num; i++)
{
if (page[i].pframe_num == target)
{
index = i;
break;
}
}
return index;
}
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");
round++;
printf("使用页面 %d\n", pframe_order[i]);
jugde = check_all_page(page_num, pframe_order[i]);
if (jugde == 1) //在虚拟页内
{
int tmp = get_index(page_num, pframe_order[i]);
page[tmp].timestamp = round;
i++;
}
else//不在页内就调用页面置换算法
{
LRU(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
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
