利用C語言實(shí)現(xiàn)頁面置換算法的詳細(xì)過程
更新時(shí)間：2022年11月25日 10:53:47 作者：braylon_zhang
一個(gè)好的頁面置換算法,應(yīng)具有較低的頁面更換頻率,從理論上講,應(yīng)該保留最近重復(fù)訪問的頁面,將以后都不再訪問或者很長時(shí)間內(nèi)不再訪問的頁面調(diào)出,下面這篇文章主要給大家介紹了關(guān)于利用C語言實(shí)現(xiàn)頁面置換算法的相關(guān)資料,需要的朋友可以參考下
操作系統(tǒng)實(shí)驗(yàn)
頁面置換算法（FIFO、LRU、OPT）
概念：
1.最佳置換算法（OPT）（理想置換算法）：從主存中移出永遠(yuǎn)不再需要的頁面；如無這樣的頁面存在，則選擇最長時(shí)間不需要訪問的頁面。于所選擇的被淘汰頁面將是以后永不使用的，或者是在最長時(shí)間內(nèi)不再被訪問的頁面，這樣可以保證獲得最低的缺頁率。
2.先進(jìn)先出置換算法（FIFO）：是最簡單的頁面置換算法。這種算法的基本思想是：當(dāng)需要淘汰一個(gè)頁面時(shí)，總是選擇駐留主存時(shí)間最長的頁面進(jìn)行淘汰，即先進(jìn)入主存的頁面先淘汰。其理由是：最早調(diào)入主存的頁面不再被使用的可能性最大。
3．最近最久未使用（LRU）算法：這種算法的基本思想是：利用局部性原理，根據(jù)一個(gè)作業(yè)在執(zhí)行過程中過去的頁面訪問歷史來推測(cè)未來的行為。它認(rèn)為過去一段時(shí)間里不曾被訪問過的頁面，在最近的將來可能也不會(huì)再被訪問。所以，這種算法的實(shí)質(zhì)是：當(dāng)需要淘汰一個(gè)頁面時(shí)，總是選擇在最近一段時(shí)間內(nèi)最久不用的頁面予以淘汰。
題目：
編寫一個(gè)程序，實(shí)現(xiàn)本章所述的FIFO、LRU和最優(yōu)頁面置換算法。首先，生成一個(gè)隨機(jī)的頁面引用串，其中頁碼范圍為0-9.將這個(gè)隨機(jī)頁面引用串應(yīng)用到每個(gè)算法，并記錄每個(gè)算法引起的缺頁錯(cuò)誤的數(shù)量。實(shí)現(xiàn)置換算法，一遍頁面幀的數(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)頁面置換算法（OPT）
void print();//輸出
int main() {
begin();
FIFO();
LRU();
OPT();
return 0;
}
void begin()//開始菜單界面
{
int i,j,k;
printf("請(qǐng)輸入頁面幀的數(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("頁面引用串為：\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ī)頁面引用串
}
}
void init()//用于每次初始化頁面棧中內(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("缺頁錯(cuò)誤數(shù)目為：%d\n",n);
}
void LRU()//LRU算法
{
int i,j,m,k,sum=1,f;
int sequence[7]={0};//記錄序列
init();
stack[0][0]=numbers[0];
sequence[0]=nums;
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++) //判斷要插入的是否在棧中已經(jīng)存在
{
f=0;
if(stack[i][j]==numbers[i])
{
f=1;
sum--;
sequence[j]=nums;
break;
}
}
for(j=0;j<nums;j++)
{
if(sequence[j]==0&&f==0)
{
stack[i][j]=numbers[i];
sequence[i]=nums;//最近使用的優(yōu)先級(jí)列為最高
break;
}
}
for(j=0;j<i;j++)//將之前的優(yōu)先級(jí)序列都減1
{
if(sequence[j]!=0)
sequence[j]--;
}
//sequence[i]=nums;
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++)//判斷輸入串中的數(shù)字，是否已經(jīng)在棧中
{
if(stack[i][j]==numbers[i])
{
f=1;
k=j;
break;
}
}
if(f==0)//如果頁面棧中沒有，不相同
{
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ō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)先序列的
{
//無需操作
}
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("缺頁錯(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++)//前半部分，頁面空置的情況
{
for(j=0;j<nums;j++)
{
stack[i][j]=stack[i-1][j];
}
for(j=0;j<nums;j++) //判斷要插入的是否在棧中已經(jīng)存在
{
f=0;
if(stack[i][j]==numbers[i])
{
f=1;
sum--;
//b++;
seq[j]=nums;
break;
}
}
for(j=0;j<nums;j++)
{
if(seq[j]==0&&f==0)
{
stack[i][j]=numbers[i];
seq[j]=nums;//最近使用的優(yōu)先級(jí)列為最高
break;
}
// else if(seq[j]==0&&f==1){
// b++;
// sum--;
// seq[j]=nums-1;
// break;
// }
}
for(j=0;j<nums;j++)//將之前的優(yōu)先級(jí)序列都減1
{
if(seq[j]!=0)
seq[j]--;
}
sum++;
}
for(i=nums;i<20;i++)//后半部分，頁面棧中沒有空的時(shí)候情況
{
//k=nums-1;//最近的數(shù)字的優(yōu)先級(jí)
for(j=0;j<nums;j++)//前面的頁面中內(nèi)容賦值到新的新的頁面中
{
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++)//優(yōu)先級(jí)序列中最大的就是最久不會(huì)用的，有可能出現(xiàn)后面沒有在用過的情況
{
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
{
//頁面棧中有需要插入的數(shù)字，無需變化，替換的優(yōu)先級(jí)也不需要變化
}
}
printf("\n");
printf("OPT算法：\n");
print();
printf("缺頁錯(cuò)誤數(shù)目為：%d\n",sum);
}
運(yùn)行結(jié)果截圖：
總結(jié)
設(shè)置多個(gè)數(shù)組，一個(gè)用來模仿棧，一個(gè)用來存要存取的頁面，還有在OPT算法和LRU算法中，記錄棧中每個(gè)數(shù)據(jù)的替換優(yōu)先級(jí)。
之前的代碼寫的有點(diǎn)爛，重新看了一次才感覺之前的有多爛，哈哈哈哈哈，這個(gè)代碼能在linux上跑通的，在windows上肯定也沒得問題
相關(guān)文章
C語言中如何在結(jié)構(gòu)體內(nèi)定義函數(shù)
這篇文章主要介紹了C語言中如何在結(jié)構(gòu)體內(nèi)定義函數(shù)問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
C語言實(shí)現(xiàn)2048游戲（ege圖形庫版）
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)2048游戲，ege圖形庫版，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-12-12
最近我學(xué)習(xí)了C++中的STL庫中的vector容器，對(duì)于常用容器，我們不僅要會(huì)使用其常用的函數(shù)接口，我們還有明白這些接口在其底層是如何實(shí)現(xiàn)的。所以特意整理出來一篇博客供我們學(xué)習(xí)2022-08-08
C++實(shí)現(xiàn)正整數(shù)的四則運(yùn)算表達(dá)式
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)正整數(shù)的四則運(yùn)算表達(dá)式，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-06-06
C++使用HTTP庫和框架輕松發(fā)送HTTP請(qǐng)求
使用C++編程發(fā)送HTTP請(qǐng)求通常需要使用第三方的HTTP庫或框架,本文主要介紹了C++使用HTTP庫和框架輕松發(fā)送HTTP請(qǐng)求,感興趣的可以了解一下2023-12-12
單例模式（Singleton Pattern）是最簡單的設(shè)計(jì)模式之一。這種類型的設(shè)計(jì)模式屬于創(chuàng)建型模式，它提供了一種創(chuàng)建對(duì)象的最佳方式，這種模式涉及到一個(gè)單一的類，該類負(fù)責(zé)創(chuàng)建自己的對(duì)象，同時(shí)確保只有單個(gè)對(duì)象被創(chuàng)建2022-06-06
最近的要用到CSV格式的數(shù)據(jù),所以這篇文章講述一下QT讀取CSV文件數(shù)據(jù),下面這篇文章主要給大家介紹了關(guān)于Qt讀寫CSV文件的三種方式及優(yōu)劣對(duì)比的相關(guān)資料,需要的朋友可以參考下2023-11-11
short與int轉(zhuǎn)換的小例子，需要的朋友可以參考一下2013-04-04
字符串是我們?cè)偈煜げ贿^的東西了，任何語言中字符串都是基礎(chǔ)都要經(jīng)常用到，那么在不同語言中字符串的用法一樣嗎？下面我們來看看C語言與C++中字符串使用的比較2022-05-05
c++和python實(shí)現(xiàn)順序查找實(shí)例
這篇文章主要介紹了c++和python實(shí)現(xiàn)順序查找實(shí)例，流程即將目標(biāo)數(shù)值和數(shù)據(jù)庫中的每個(gè)數(shù)值進(jìn)行比較，如果相同則搜索完成，如果不同則繼續(xù)比較下一處，下面來看看具體的實(shí)例操作吧,需要的朋友可以參考一下2022-03-03