FIFO頁面置換算法，計算缺頁率，文末附代碼，及例題解析
1、內(nèi)容
? ? ? ? 在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不在內(nèi)存中，則產(chǎn)生缺頁中斷。當發(fā)生缺頁中斷時，如果操作系統(tǒng)內(nèi)存中沒有空閑頁面，則操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法。
? ? ? ? 模擬內(nèi)存的頁式管理，實現(xiàn)內(nèi)存的分配和調(diào)用，完成虛擬內(nèi)存地址序列和物理內(nèi)存的對應。在內(nèi)存調(diào)用出現(xiàn)缺頁時，調(diào)入程序的內(nèi)存頁。在出現(xiàn)無空閑頁面時，使用先進先出（FIFO）算法實現(xiàn)頁面置換。
2、頁的結(jié)構(gòu)
頁的結(jié)構(gòu)如下：
? 頁號、頁面號、時間戳（在本算法中未使用，在LRU中使用）
| 名稱 |
符號 |
功能 |
| 頁號 |
Page_num |
記錄頁號 |
| 頁面號 |
Pframe_num |
記錄頁面號 |
? ? ? FIFO頁面置換算法選擇在主存中停留時間最長(即最老)的一頁置換，即先進入內(nèi)存的頁，先退出內(nèi)存。理由是:最早調(diào)入內(nèi)存的頁，其不再被使用的可能性比剛調(diào)入內(nèi)存的可能性大。建立一個FIFO隊列，收容所有在內(nèi)存中的頁。被置換頁面總是在隊列頭上進行。當一個頁面被放入內(nèi)存時，就把它插在隊尾上
? ? ? ?通過使用線性表來實現(xiàn)頁表，在每次需要淘汰頁時，都是淘汰最先進入的頁，這樣就可以實現(xiàn)淘汰在主存中停留時間最長的頁。
流程如下：
3、例題解析
在頁式管理系統(tǒng)中，訪問的順序（訪問串）為：1，2，3，4，1，2，5，1，2，3，4，5，當分配的頁面數(shù)量為3時，請分別計算使用下述（1）替換算法的缺頁次數(shù)，并畫出頁面置換圖。
(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 <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("請輸入頁面的數(shù)量：");
scanf("%d", page_n);
printf("請輸入頁的數(shù)量：");
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中的數(shù)字,每輸入一個數(shù)輸入一次回車,輸入-1表示結(jié)束）:\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++;//全程序只在本處處理缺頁次數(shù)
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為頁的數(shù)量，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為虛擬頁的數(shù)量，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) {//在虛擬頁內(nèi)
i++;
}
else//不在頁內(nèi)就調(diào)用頁面置換算法
{
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個頁，內(nèi)存中有3個頁面，訪問串是1、2、3、2、4、5、2
文章來源：http://www.zghlxwxcb.cn/news/detail-505604.html
缺頁率為：0.857143文章來源地址http://www.zghlxwxcb.cn/news/detail-505604.html
到了這里，關(guān)于【操作系統(tǒng)】FIFO先進先出頁面置換算法（C語言實現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
