C語言實現(xiàn)頁面置換先進先出算法（FIFO）

更新時間：2020年12月29日 11:28:16 作者：little pepper

這篇文章主要為大家詳細介紹了C語言實現(xiàn)頁面置換，先進先出算法（FIFO），文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了C語言實現(xiàn)頁面置換算法的具體代碼，供大家參考，具體內(nèi)容如下

一、設(shè)計目的

加深對請求頁式存儲管理實現(xiàn)原理的理解，掌握頁面置換算法中的先進先出算法。

二、設(shè)計內(nèi)容

設(shè)計一個程序，有一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，實現(xiàn)下述三種算法中的任意兩種，計算訪問命中率（命中率=1-頁面失效次數(shù)/頁地址流長度）。附加要求：能夠顯示頁面置換過程。

該系統(tǒng)頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令對應(yīng)的頁不在內(nèi)存的次數(shù)。
程序首先用srand()和rand()函數(shù)分別進行初始化、隨機數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對不同的算法計算出相應(yīng)的命中率。

通過隨機數(shù)產(chǎn)生一個指令序列。共320條指令，指令的地址按下述原則生成：

（1）50%的指令是順序執(zhí)行的。
（2）25%的指令是均勻分布在前地址部分。
（3）25%的指令是均勻分布在后地址部分。

具體的實施方法如下：

在【0，319】的指令地址之間隨機選取一起點m。
順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令。
在前地址【0,m+1】中隨機選取一條指令并執(zhí)行，該指令的地址為m'。
順序執(zhí)行一條指令，其地址為m'+1。
在后地址【m'+2,319】中隨機選取一條指令并執(zhí)行。
重復(fù)步驟（1）-（5），直到320次指令。
將指令序列變換為頁地址流。

設(shè)：

頁面大小為1KB。
用戶內(nèi)存容量4頁到32頁。
用戶虛存容量為32KB。
在用戶虛存中，按每K存放10條指令虛存地址，即320條指令在虛存中的存放方式為：
第0條～9條指令為第0頁（對應(yīng)虛存地址為【0，9】）。
第10條～19條指令為第1頁（對應(yīng)虛存地址為【10，19】）。
……
第310條～319條指令為第31頁（對應(yīng)虛擬地址為【310，319】）。
按以上方式，用戶指令可組成32頁。
計算每種算法在不同內(nèi)存容量下的命中率。

三、程序結(jié)構(gòu)

首先，用srand()和rand()函數(shù)分別進行初始化、隨機數(shù)定義和產(chǎn)生指令序列；
接著，將指令序列變換成相應(yīng)的頁地址流；
然后，并針先進先出算法計算出相應(yīng)的命中率和輸出頁面置換過程。

源程序：

#include<stdio.h>
#include<stdlib.h>
#define N 320
int num[N]; //存放隨機數(shù) 
int page[N]; //存放頁地址流 
int mc[33]; //memory capacity內(nèi)存容量 ，并初始化為0 
 
void randomnumber()//random number隨機數(shù) 程序第一步，產(chǎn)生320個指令序列 
{ 
 int pc;
 int flag=0; 
 scanf("%d",&pc); 
 printf("\n在0-319之間產(chǎn)生的320個隨機數(shù)如下:\n"); 
 for(int i=0;i<320;i++) 
 { 
 num[i]=pc; 
 if(flag%2==0) pc=++pc%320; //flag=0||2 50%的指令是順序執(zhí)行的 
 if(flag==1) pc=rand()% (pc-1); //flag=1 25%的指令是均勻分布在前地址部分 
 if(flag==3) pc=pc+1+(rand()%(320-(pc+1))); //flag=3 25%的指令是均勻分布在后地址部分 
 flag=++flag%4; 
 printf("%3d ",num[i]); 
 if((i+1)%10==0) printf("\n"); //每行輸出10個數(shù) 
 } 
} 
 
void pageaddress() //pageaddress頁地址 程序第二步，將指令序列變換為頁地址流 
{ 
 for(int i=0;i<320;i++) 
 { 
 printf("%3d ",page[i]=num[i]/10); 
 if((i+1)%10==0) printf("\n"); //每行輸出10個數(shù) 
 } 
}
 
int FIFO(int capacity)
{
 int j,x,y,m;
 int sum=0; //mc中分配的個數(shù) 
 int exist=0; //命中次數(shù) 
 int flag; //標志是否命中 flag=0沒命中 flag=1命中 
 int ep=1; //elimination position淘汰位置 
 mc[1]=page[0];
 printf(" %2d加入 \t",page[0]);
 for(m=1;m<=capacity;m++) //輸出當前內(nèi)存塊的存儲情況 
 printf("%2d ",mc[m]);
 printf("\n");
 sum+=1; 
 for(j=1;j<320;j++)
 { 
 flag=0; 
 for(y=1;y<=sum;y++) //判斷這個頁地址流是否命中 
 if(mc[y]==page[j]) {
 exist++;
 flag=1;
 printf(" %2d命中 \t",page[j]);
 for(m=1;m<=capacity;m++) //輸出當前內(nèi)存塊的存儲情況 
 printf("%2d ",mc[m]);
 printf("\n");
 break;} 
 //沒命中 
 if(flag==0) 
 {
 if(sum<capacity) //還有空塊 
 {for(x=1;x<=capacity;x++) //查找內(nèi)存塊中第一個空塊 
 if(mc[x]==-1) {
 mc[x]=page[j];
 sum++;
 printf(" %2d加入 \t",page[j]);
 for(m=1;m<=capacity;m++) //輸出當前內(nèi)存塊的存儲情況 
 printf("%2d ",mc[m]);
 printf("\n");
 break;}
 }
 else if(sum>=capacity)
 {
 int t=mc[ep];
 mc[ep]=page[j];
 printf(" %2d置換%2d\t",page[j],t);
 for(m=1;m<=capacity;m++) //輸出當前內(nèi)存塊的存儲情況 
 printf("%2d ",mc[m]);
 printf("\n");
 ep+=1;
 if(ep==capacity+1) ep=1; 
 } 
 }
 } 
 printf("\nexist=%d\n命中率=%lf",exist,exist/320.0);
} 
int main()
{
 int capacity; //內(nèi)存塊數(shù) 
 printf("請輸入第一條指令號(0~319):");
 randomnumber();
 printf("\n指令序列對應(yīng)的頁地址流:\n"); 
 pageaddress(); 
 printf("\n\n\n\t\t先進先出算法(FIFO):\n\n");
 printf("請輸入內(nèi)存塊數(shù)（4-32）：");
 scanf("%d",&capacity);
 for(int i=1;i<=32;i++) //給數(shù)組賦初值 
 mc[i]=-1;
 FIFO(capacity); 
 return 0;
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: