C語(yǔ)言實(shí)現(xiàn)頁(yè)面置換算法

更新時(shí)間：2020年12月29日 17:41:33 作者：為中華之崛起而code

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

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

操作系統(tǒng)實(shí)驗(yàn)

頁(yè)面置換算法（FIFO、LRU、OPT）

概念：

1.最佳置換算法（OPT）（理想置換算法）：從主存中移出永遠(yuǎn)不再需要的頁(yè)面；如無(wú)這樣的頁(yè)面存在，則選擇最長(zhǎng)時(shí)間不需要訪問(wèn)的頁(yè)面。于所選擇的被淘汰頁(yè)面將是以后永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面，這樣可以保證獲得最低的缺頁(yè)率。
2.先進(jìn)先出置換算法（FIFO）：是最簡(jiǎn)單的頁(yè)面置換算法。這種算法的基本思想是：當(dāng)需要淘汰一個(gè)頁(yè)面時(shí)，總是選擇駐留主存時(shí)間最長(zhǎng)的頁(yè)面進(jìn)行淘汰，即先進(jìn)入主存的頁(yè)面先淘汰。其理由是：最早調(diào)入主存的頁(yè)面不再被使用的可能性最大。
3．最近最久未使用（LRU）算法：這種算法的基本思想是：利用局部性原理，根據(jù)一個(gè)作業(yè)在執(zhí)行過(guò)程中過(guò)去的頁(yè)面訪問(wèn)歷史來(lái)推測(cè)未來(lái)的行為。它認(rèn)為過(guò)去一段時(shí)間里不曾被訪問(wèn)過(guò)的頁(yè)面，在最近的將來(lái)可能也不會(huì)再被訪問(wèn)。所以，這種算法的實(shí)質(zhì)是：當(dāng)需要淘汰一個(gè)頁(yè)面時(shí)，總是選擇在最近一段時(shí)間內(nèi)最久不用的頁(yè)面予以淘汰。

題目：

編寫一個(gè)程序，實(shí)現(xiàn)本章所述的FIFO、LRU和最優(yōu)頁(yè)面置換算法。首先，生成一個(gè)隨機(jī)的頁(yè)面引用串，其中頁(yè)碼范圍為0-9.將這個(gè)隨機(jī)頁(yè)面引用串應(yīng)用到每個(gè)算法，并記錄每個(gè)算法引起的缺頁(yè)錯(cuò)誤的數(shù)量。實(shí)現(xiàn)置換算法，一遍頁(yè)面幀的數(shù)量可以從1~7。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int numbers[20]={7,0,1,2,
   0,3,0,4,
   2,3,0,3,
   2,1,2,0,
   1,7,0,1};//本地?cái)?shù)據(jù)，與課本一致，方便測(cè)試
int nums=0;//輸入棧的個(gè)數(shù)，為了方便使用，
int stack[20][7]={10};

void begin();
void randomnum();//用于產(chǎn)生隨機(jī)數(shù)
void init();//初始化
void FIFO();//FIFO算法
void LRU();//LRU算法
void OPT();//最優(yōu)頁(yè)面置換算法（OPT）
void print();//輸出

int main() {
 begin();
 FIFO();
 LRU();
 OPT();
 return 0;
}
void begin()//開始菜單界面
{
 int i,j,k;
 printf("請(qǐng)輸入頁(yè)面幀的數(shù)量(1-7)：");
 scanf("%d",&nums);
 for(k=0;;k++)
 {
 printf("是否使用隨機(jī)數(shù)產(chǎn)生輸入串（0：是，1：否）");
 scanf("%d",&j);
 if(j==0)
 {
  randomnum();
  break;
 }
 else if(j==1)
 {
  break;
 }
 else
 {
  printf("請(qǐng)輸入正確的選擇！\n");
 }
 }

 printf("頁(yè)面引用串為：\n");
 for(i=0;i<20;i++)
 {
 printf("%d ",numbers[i]);
 }
 printf("\n");
 init();
}
void randomnum()//如果需要使用隨機(jī)數(shù)生成輸入串，調(diào)用該函數(shù)
{
 srand(time(0));//設(shè)置時(shí)間種子
 for(int i = 0; i < 20; i++) {
 numbers[i] = rand() % 10;//生成區(qū)間0`9的隨機(jī)頁(yè)面引用串
 }
}
void init()//用于每次初始化頁(yè)面棧中內(nèi)容，同時(shí)方便下面輸出的處理
{
 int i,j;
 for(i=0;i<20;i++)
 for(j=0;j<nums;j++)
  stack[i][j]=10;
}

void print()//輸出各個(gè)算法的棧的內(nèi)容
{
 int i,j;
 for(i=0;i<nums;i++)
 {
 for(j=0;j<20;j++)
 {
  if(stack[j][i]==10)
  printf("* ");
  else
  printf("%d ",stack[j][i]);
 }
 printf("\n");
 }

}

void FIFO()//FIFO算法
{
 init();
 int i,j=1,n=20,k,f,m;
 stack[0][0]=numbers[0];

 for(i=1;i<20;i++)
 {
 f=0;
 for(m=0;m<nums;m++)
 {
  stack[i][m]=stack[i-1][m];
 }
 for(k=0;k<nums;k++)
 {
  if(stack[i][k]==numbers[i])
  {
  n--;
  f=1;
  break;
  }
 }
 if(f==0)
 {
  stack[i][j]=numbers[i];
  j++;
 }
 if(j==nums)
  j=0;
 }
 printf("\n");
 printf("FIFO算法：\n");
 print();
 printf("缺頁(yè)錯(cuò)誤數(shù)目為：%d\n",n);
}

void LRU()//LRU算法
{
 int i,j,m,k,sum=1;
 int sequence[7]={0};//記錄序列
 init();
 stack[0][0]=numbers[0];
 sequence[0]=nums-1;
 for(i=1;i<nums;i++)//前半部分，頁(yè)面空置的情況
 {
 for(j=0;j<nums;j++)
 {
  stack[i][j]=stack[i-1][j];
 }
 for(j=0;j<nums;j++)
 {
  if(sequence[j]==0)
  {
  stack[i][j]=numbers[i];
  break;
  }
 }
 for(j=0;j<i;j++)//將之前的優(yōu)先級(jí)序列都減1
 {
  sequence[j]--;
 }
 sequence[i]=nums-1;//最近使用的優(yōu)先級(jí)列為最高
 sum++;
 }
 for(i=nums;i<20;i++)//頁(yè)面不空，需要替換的情況
 {
 int f;
 f=0;
 for(j=0;j<nums;j++)
 {
  stack[i][j]=stack[i-1][j];
 }
 for(j=0;j<nums;j++)//判斷輸入串中的數(shù)字，是否已經(jīng)在棧中
 {
  if(stack[i][j]==numbers[i])
  {
  f=1;
  k=j;
  break;
  }
 }
 if(f==0)//如果頁(yè)面棧中沒(méi)有，不相同
 {
  for(j=0;j<nums;j++)//找優(yōu)先序列中為0的
  {
  if(sequence[j]==0)
  {
   m=j;
   break;
  }
  }
  for(j=0;j<nums;j++)
  {
  sequence[j]--;
  }
  sequence[m]=nums-1;
  stack[i][m]=numbers[i];
  sum++;
 }
 else//如果頁(yè)面棧中有，替換優(yōu)先級(jí)
 {
  if(sequence[k]==0)//優(yōu)先級(jí)為最小優(yōu)先序列的
  {
  for(j=0;j<nums;j++)
  {
   sequence[j]--;
  }
  sequence[k]=nums-1;
  }
  else if(sequence[k]==nums-1)//優(yōu)先級(jí)為最大優(yōu)先序列的
  {
  //無(wú)需操作
  }
  else//優(yōu)先級(jí)為中間優(yōu)先序列的
  {
  for(j=0;j<nums;j++)
  {
   if(sequence[k]<sequence[j])
   {
   sequence[j]--;
   }
  }
  sequence[k]=nums-1;
  }
 }
 }
 printf("\n");
 printf("LRU算法：\n");
 print();
 printf("缺頁(yè)錯(cuò)誤數(shù)目為：%d\n",sum);
}

void OPT()//OPT算法
{
 int i,j,k,sum=1,f,q,max;
 int seq[7]={0};//記錄序列
 init();
 stack[0][0]=numbers[0];
 seq[0]=nums-1;
 for(i=1;i<nums;i++)//前半部分，頁(yè)面空置的情況
 {
 for(j=0;j<nums;j++)
 {
  stack[i][j]=stack[i-1][j];
 }
 for(j=0;j<nums;j++)
 {
  if(seq[j]==0)
  {
  stack[i][j]=numbers[i];
  break;
  }
 }
 for(j=0;j<i;j++)//將之前的優(yōu)先級(jí)序列都減1
 {
  seq[j]--;
 }
 seq[i]=nums-1;//最近使用的優(yōu)先級(jí)列為最高
 sum++;
 }
 for(i=nums;i<20;i++)//后半部分，頁(yè)面棧中沒(méi)有空的時(shí)候情況
 {
 //k=nums-1;//最近的數(shù)字的優(yōu)先級(jí)
 for(j=0;j<nums;j++)//前面的頁(yè)面中內(nèi)容賦值到新的新的頁(yè)面中
 {
  stack[i][j]=stack[i-1][j];
 }
 for(j=0;j<nums;j++)
 {
  f=0;
  if(stack[i][j]==numbers[i])
  {
  f=1;
  break;
  }
 }
 if(f==0)//頁(yè)面中沒(méi)有，需要替換的情況
 {
  for(q=0;q<nums;q++)//優(yōu)先級(jí)序列中最大的就是最久未用的，有可能出現(xiàn)后面沒(méi)有在用過(guò)的情況
  {
  seq[q]=20;
  }
  for(j=0;j<nums;j++)//尋找新的優(yōu)先級(jí)
  {
  for(q=i+1;q<20;q++)
  {
   if(stack[i][j]==numbers[q])
   {
   seq[j]=q-i;
   break;
   }
  }
  }
  max=seq[0];
  k=0;
  for(q=0;q<nums;q++)
  {
  if(seq[q]>max)
  {
   max=seq[q];
   k=q;
  }
  }
  stack[i][k]=numbers[i];
  sum++;
 }
 else
 {
  //頁(yè)面棧中有需要插入的數(shù)字，無(wú)需變化，替換的優(yōu)先級(jí)也不需要變化
 }
 }
 printf("\n");
 printf("OPT算法：\n");
 print();
 printf("缺頁(yè)錯(cuò)誤數(shù)目為：%d\n",sum);
}

運(yùn)行結(jié)果截圖：