C語言實現頁面置換算法

本文實例為大傢分享瞭C語言實現頁面置換算法的具體代碼,供大傢參考,具體內容如下

操作系統實驗

頁面置換算法(FIFO、LRU、OPT)

概念:

1.最佳置換算法(OPT)(理想置換算法):從主存中移出永遠不再需要的頁面;如無這樣的頁面存在,則選擇最長時間不需要訪問的頁面。於所選擇的被淘汰頁面將是以後永不使用的,或者是在最長時間內不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。
2.先進先出置換算法(FIFO):是最簡單的頁面置換算法。這種算法的基本思想是:當需要淘汰一個頁面時,總是選擇駐留主存時間最長的頁面進行淘汰,即先進入主存的頁面先淘汰。其理由是:最早調入主存的頁面不再被使用的可能性最大。
3.最近最久未使用(LRU)算法:這種算法的基本思想是:利用局部性原理,根據一個作業在執行過程中過去的頁面訪問歷史來推測未來的行為。它認為過去一段時間裡不曾被訪問過的頁面,在最近的將來可能也不會再被訪問。所以,這種算法的實質是:當需要淘汰一個頁面時,總是選擇在最近一段時間內最久不用的頁面予以淘汰。

題目:

編寫一個程序,實現本章所述的FIFO、LRU和最優頁面置換算法。首先,生成一個隨機的頁面引用串,其中頁碼范圍為0-9.將這個隨機頁面引用串應用到每個算法,並記錄每個算法引起的缺頁錯誤的數量。實現置換算法,一遍頁面幀的數量可以從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};//本地數據,與課本一致,方便測試
int nums=0;//輸入棧的個數,為瞭方便使用,
int stack[20][7]={10};

void begin();
void randomnum();//用於產生隨機數
void init();//初始化
void FIFO();//FIFO算法
void LRU();//LRU算法
void OPT();//最優頁面置換算法(OPT)
void print();//輸出

int main() {
 begin();
 FIFO();
 LRU();
 OPT();
 return 0;
}
void begin()//開始菜單界面
{
 int i,j,k;
 printf("請輸入頁面幀的數量(1-7):");
 scanf("%d",&nums);
 for(k=0;;k++)
 {
  printf("是否使用隨機數產生輸入串(0:是,1:否)");
  scanf("%d",&j);
  if(j==0)
  {
   randomnum();
   break;
  }
  else if(j==1)
  {
   break;
  }
  else
  {
   printf("請輸入正確的選擇!\n");
  }
 }

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

void print()//輸出各個算法的棧的內容
{
 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("缺頁錯誤數目為:%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++)//前半部分,頁面空置的情況
 {
  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++)//將之前的優先級序列都減1
  {
   sequence[j]--;
  }
  sequence[i]=nums-1;//最近使用的優先級列為最高
  sum++;
 }
 for(i=nums;i<20;i++)//頁面不空,需要替換的情況
 {
  int f;
  f=0;
  for(j=0;j<nums;j++)
  {
   stack[i][j]=stack[i-1][j];
  }
  for(j=0;j<nums;j++)//判斷輸入串中的數字,是否已經在棧中
  {
   if(stack[i][j]==numbers[i])
   {
    f=1;
    k=j;
    break;
   }
  }
  if(f==0)//如果頁面棧中沒有,不相同
  {
   for(j=0;j<nums;j++)//找優先序列中為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//如果頁面棧中有,替換優先級
  {
   if(sequence[k]==0)//優先級為最小優先序列的
   {
    for(j=0;j<nums;j++)
    {
     sequence[j]--;
    }
    sequence[k]=nums-1;
   }
   else if(sequence[k]==nums-1)//優先級為最大優先序列的
   {
    //無需操作
   }
   else//優先級為中間優先序列的
   {
    for(j=0;j<nums;j++)
    {
     if(sequence[k]<sequence[j])
     {
      sequence[j]--;
     }
    }
    sequence[k]=nums-1;
   }
  }
 }
 printf("\n");
 printf("LRU算法:\n");
 print();
 printf("缺頁錯誤數目為:%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++)//前半部分,頁面空置的情況
 {
  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++)//將之前的優先級序列都減1
  {
   seq[j]--;
  }
  seq[i]=nums-1;//最近使用的優先級列為最高
  sum++;
 }
 for(i=nums;i<20;i++)//後半部分,頁面棧中沒有空的時候情況
 {
  //k=nums-1;//最近的數字的優先級
  for(j=0;j<nums;j++)//前面的頁面中內容賦值到新的新的頁面中
  {
   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)//頁面中沒有,需要替換的情況
  {
   for(q=0;q<nums;q++)//優先級序列中最大的就是最久未用的,有可能出現後面沒有在用過的情況
   {
    seq[q]=20;
   }
   for(j=0;j<nums;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
  {
   //頁面棧中有需要插入的數字,無需變化,替換的優先級也不需要變化
  }
 }
 printf("\n");
 printf("OPT算法:\n");
 print();
 printf("缺頁錯誤數目為:%d\n",sum);
}

運行結果截圖:


這個代碼能在linux上跑通的,在windows上肯定也沒得問題

以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。

推薦閱讀: