C語言實現頁面置換 先進先出算法（FIFO）
本文實例為大傢分享瞭C語言實現頁面置換算法的具體代碼，供大傢參考，具體內容如下
一、設計目的
加深對請求頁式存儲管理實現原理的理解，掌握頁面置換算法中的先進先出算法。
二、設計內容
設計一個程序，有一個虛擬存儲區和內存工作區，實現下述三種算法中的任意兩種，計算訪問命中率（命中率=1-頁面失效次數/頁地址流長度）。附加要求：能夠顯示頁面置換過程。
該系統頁地址流長度為320，頁面失效次數為每次訪問相應指令時，該指令對應的頁不在內存的次數。
程序首先用srand()和rand()函數分別進行初始化、隨機數定義和產生指令序列，然後將指令序列變換成相應的頁地址流，並針對不同的算法計算出相應的命中率。
通過隨機數產生一個指令序列。共320條指令，指令的地址按下述原則生成：
（1）50%的指令是順序執行的。
（2）25%的指令是均勻分佈在前地址部分。
（3）25%的指令是均勻分佈在後地址部分。
具體的實施方法如下：
在【0，319】的指令地址之間隨機選取一起點m。
順序執行一條指令，即執行地址為m+1的指令。
在前地址【0,m+1】中隨機選取一條指令並執行，該指令的地址為m’。
順序執行一條指令，其地址為m’+1。
在後地址【m’+2,319】中隨機選取一條指令並執行。
重復步驟（1）-（5），直到320次指令。
將指令序列變換為頁地址流。
設：
頁面大小為1KB。
用戶內存容量4頁到32頁。
用戶虛存容量為32KB。
在用戶虛存中，按每K存放10條指令虛存地址，即320條指令在虛存中的存放方式為：
第0條～9條指令為第0頁（對應虛存地址為【0，9】）。
第10條～19條指令為第1頁（對應虛存地址為【10，19】）。
……
第310條～319條指令為第31頁（對應虛擬地址為【310，319】）。
按以上方式，用戶指令可組成32頁。
計算每種算法在不同內存容量下的命中率。
三、程序結構
首先，用srand()和rand()函數分別進行初始化、隨機數定義和產生指令序列；
接著，將指令序列變換成相應的頁地址流；
然後，並針先進先出算法計算出相應的命中率和輸出頁面置換過程。
源程序：
#include<stdio.h>
#include<stdlib.h>
#define N 320
int num[N]; //存放隨機數
int page[N]; //存放頁地址流
int mc[33]; //memory capacity內存容量 ，並初始化為0
void randomnumber()//random number隨機數 程序第一步，產生320個指令序列
{
int pc;
int flag=0;
scanf("%d",&pc);
printf("\n在0-319之間產生的320個隨機數如下:\n");
for(int i=0;i<320;i++)
{
num[i]=pc;
if(flag%2==0) pc=++pc%320; //flag=0||2 50%的指令是順序執行的
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個數
}
}
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個數
}
}
int FIFO(int capacity)
{
int j,x,y,m;
int sum=0; //mc中分配的個數
int exist=0; //命中次數
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++) //輸出當前內存塊的存儲情況
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++) //輸出當前內存塊的存儲情況
printf("%2d ",mc[m]);
printf("\n");
break;}
//沒命中
if(flag==0)
{
if(sum<capacity) //還有空塊
{for(x=1;x<=capacity;x++) //查找內存塊中第一個空塊
if(mc[x]==-1) {
mc[x]=page[j];
sum++;
printf(" %2d加入 \t",page[j]);
for(m=1;m<=capacity;m++) //輸出當前內存塊的存儲情況
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++) //輸出當前內存塊的存儲情況
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; //內存塊數
printf("請輸入第一條指令號(0~319):");
randomnumber();
printf("\n指令序列對應的頁地址流:\n");
pageaddress();
printf("\n\n\n\t\t先進先出算法(FIFO):\n\n");
printf("請輸入內存塊數（4-32）：");
scanf("%d",&capacity);
for(int i=1;i<=32;i++) //給數組賦初值
mc[i]=-1;
FIFO(capacity);
return 0;
}
以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。