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 -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;//缺页记录
 
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