使用C語言怎么制作一個頁面置換算法

本篇文章給大家分享的是有關使用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;
}

以上就是使用C語言怎么制作一個頁面置換算法，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。