【操作系统】FIFO先进先出页面置换算法（C语言实现）

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