Linux頁(yè)面置換算法的C語(yǔ)言實(shí)現(xiàn)
更新時(shí)間：2020年12月29日 11:04:17 作者：蕾蕾昔
這篇文章主要為大家詳細(xì)介紹了Linux頁(yè)面置換算法的C語(yǔ)言實(shí)現(xiàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
Linux頁(yè)面置換算法的C語(yǔ)言實(shí)現(xiàn)
編寫(xiě)算法，實(shí)現(xiàn)頁(yè)面置換算法FIFO、LRU、OPT；針對(duì)內(nèi)存地址引用串，進(jìn)行頁(yè)面置換算法進(jìn)行頁(yè)面置換。
其中，算法所需的各種參數(shù)由輸入產(chǎn)生（手工輸入或者隨機(jī)數(shù)產(chǎn)生）；輸出內(nèi)存駐留的頁(yè)面集合，缺頁(yè)次數(shù)以及缺頁(yè)率。
#include <stdio.h>
//#include <conio.h>
#include <stdlib.h>
#include <time.h>//隨機(jī)數(shù)
#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") //*表格控制*/
int M;
int N;
typedef struct page
{
int num; /*記錄頁(yè)面號(hào)*/
int time; /*記錄調(diào)入內(nèi)存時(shí)間*/ //（lru那用到）
int index; //記錄調(diào)入內(nèi)存的先后次序 //從1開(kāi)始（FIFO那用到）
}Page; /* 頁(yè)面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/
Page b[10]; /*內(nèi)存單元數(shù)*/ //從0開(kāi)始
int c[10][150]; /*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)*/
int queue[100]; /*記錄調(diào)入隊(duì)列*/
int K; /*調(diào)入隊(duì)列計(jì)數(shù)變量*/
/*初始化內(nèi)存單元、緩沖區(qū)*/
void Init(Page *b,int c[10][150])
{
int i,j;
for(i=0;i<M;i++)
{
b[i].num=-1;
b[i].time=M-i-1;
b[i].index=i+1;
}
for(i=0;i<M;i++)
for(j=0;j<N;j++)
c[i][j]=-1;
}
/*取得在內(nèi)存中停留最久的頁(yè)面,默認(rèn)狀態(tài)下為最早調(diào)入的頁(yè)面*/
int GetMaxTime(Page *b)
{
int i;
int max=-1;
int tag=0;
for(i=0;i<M;i++)
{
if(b[i].time>max)
{
max=b[i].time;
tag=i;
}
}
return tag;
}
/**int GetMinTime(Page *b)
{
int i;
int min=1000;
int tag=0;
for(i=0;i<M;i++)
{
if(b[i].time<min)
{
min=b[i].time;
tag=i;
}
}
return tag;
} **/
/*判斷頁(yè)面是否已在內(nèi)存中*/
int Equation(int fold,Page *b)
{
int i;
for(i=0;i<M;i++)
{
if (fold==b[i].num)
return i;
}
return -1;
}
//LRU核心部分 最近最久未使用置換算法
void Lru(int fold,Page *b)
{
int i;
int val;
val=Equation(fold,b); //判斷頁(yè)面是否已在內(nèi)存中，val代表在內(nèi)存中的位置
if (val>=0) //在內(nèi)存中
{
b[val].time=0; //存在就把那個(gè)東西的時(shí)間變成0
for(i=0;i<M;i++)
if (i!=val)
b[i].time++; // 其他的時(shí)間就要累加
}
else
{
queue[++K]=fold;/*記錄調(diào)入頁(yè)面*/
val=GetMaxTime(b); //取得在內(nèi)存中停留最久的頁(yè)面,默認(rèn)狀態(tài)下為最早調(diào)入的頁(yè)面，val代表在內(nèi)存中的位置
b[val].num=fold;
b[val].time=0;
for(i=0;i<M;i++)
if (i!=val)
b[i].time++;
}
}
//FIFO核心部分 先進(jìn)先出置換算法
void FIFO(int fold,Page *b)
{
int i;
int val;
bool flag=false;
val=Equation(fold,b); //判斷頁(yè)面是否已在內(nèi)存中，val代表在內(nèi)存中的位置
if (val<0) //不在內(nèi)存中
{
queue[++K]=fold;/*記錄調(diào)入頁(yè)面*/
for(i=0;i<M;i++)
{
if (b[i].num<0)//如果有空
{
b[i].num=fold;
b[i].index=i+1;
flag=true;
break;
}
}
if (flag==false)//如若沒(méi)有空余則找到最先進(jìn)去的被淘汰
{
for(i=0;i<M;i++)
{
if(b[i].index==1)
{
val=i;
}
}
b[val].num=fold;
b[val].index=M;
for(i=0;i<M;i++)
{
if(i!=val)
b[i].index--; //因?yàn)橛幸粋€(gè)被淘汰了，所有其他的Index就需要更新
}
}
}
}
//Optimal核心部分 最佳置換算法
void Optimal(int a[150],int pos,Page *b)
{
int i,j;
int val;
int fold=a[pos];
bool flag=false;
val=Equation(fold,b); //判斷頁(yè)面是否已在內(nèi)存中，val代表在內(nèi)存中的位置
if (val<0) //不在內(nèi)存中
{
queue[++K]=fold;/*記錄調(diào)入頁(yè)面*/
for(i=0;i<M;i++)
{
if (b[i].num<0)
{
b[i].num=fold;
flag=true;
break;
}
}
if (flag==false)
{
for(i=0;i<M;i++)
{
for(j=pos+1;j<N;j++)
{
if (b[i].num!=a[j])
{ b[i].time= 1000; }//如果后面不需要再用它了把時(shí)間改成最大1000
else
{
b[i].time=j;//否則賦值為j
break;
}
}
}
val=GetMaxTime(b); //取得在內(nèi)存中停留最久的頁(yè)面,默認(rèn)狀態(tài)下為最早調(diào)入的頁(yè)面，val代表在內(nèi)存中的位置
b[val].num=fold;
}
}
}
void LruMain(int a[150])
{
int i,j;
K=-1;
Init(b, c);
for(i=0;i<N;i++) //
{
Lru(a[i],b);
c[0][i]=a[i];
/*記錄當(dāng)前的內(nèi)存單元中的頁(yè)面*/
for(j=0;j<M;j++)
c[j][i]=b[j].num;
}
/*結(jié)果輸出*/
printf("\n內(nèi)存狀態(tài)為：\n");
Myprintf;
for(j=0;j<N;j++)
printf("|%2d ",a[j]);
printf("|\n");
Myprintf; //#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") //*表格控制*/
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
if(c[j][i]==-1)
printf("%3c ",32);
else
printf("%3d ",c[j][i]);
}
printf("\n");
}
Myprintf;
printf("\n調(diào)入隊(duì)列為:");
for(i=0;i<K+1;i++)
printf("%3d",queue[i]);
printf("\n缺頁(yè)次數(shù)為：%6d\n缺頁(yè)率：%16.6f",K+1,(float)(K+1)/N);
}
void FIFOMain(int a[150])
{
int i,j;
K=-1;
Init(b, c);
for(i=0;i<N;i++) //
{
FIFO(a[i],b);
c[0][i]=a[i];
/*記錄當(dāng)前的內(nèi)存單元中的頁(yè)面*/
for(j=0;j<M;j++)
c[j][i]=b[j].num;
}
/*結(jié)果輸出*/
printf("\n內(nèi)存狀態(tài)為：\n");
Myprintf;
for(j=0;j<N;j++)
printf("|%2d ",a[j]);
printf("|\n");
Myprintf; //#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") //*表格控制*/
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
if(c[j][i]==-1)
printf("%3c ",32);//空格
else
printf("%3d ",c[j][i]);
}
printf("\n");
}
Myprintf;
printf("\n調(diào)入隊(duì)列為:");
for(i=0;i<K+1;i++)
printf("%3d",queue[i]);
printf("\n缺頁(yè)次數(shù)為：%6d\n缺頁(yè)率：%16.6f",K+1,(float)(K+1)/N);
}
void OptimalMain(int a[150])
{
int i,j;
K=-1;
Init(b, c);
for(i=0;i<N;i++) //
{
Optimal(a,i,b);
c[0][i]=a[i];
/*記錄當(dāng)前的內(nèi)存單元中的頁(yè)面*/
for(j=0;j<M;j++)
c[j][i]=b[j].num;
}
/*結(jié)果輸出*/
printf("\n內(nèi)存狀態(tài)為：\n");
Myprintf;
for(j=0;j<N;j++)
printf("|%2d ",a[j]);
printf("|\n");
Myprintf; //#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") //*表格控制*/
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
if(c[j][i]==-1)
printf("%3c ",32);
else
printf("%3d ",c[j][i]);
}
printf("\n");
}
Myprintf;
printf("\n調(diào)入隊(duì)列為:");
for(i=0;i<K+1;i++)
printf("%3d",queue[i]);
printf("\n缺頁(yè)次數(shù)為：%6d\n缺頁(yè)率：%16.6f",K+1,(float)(K+1)/N);
}
void main()
{
int a[150];
int i;
char s;
printf("請(qǐng)輸入物理塊數(shù)：");
scanf("%d",&M);
printf("請(qǐng)輸入所要訪(fǎng)問(wèn)的頁(yè)面數(shù)：");
scanf("%d",&N);
srand(time(NULL));
for(i=0;i<N;i++)
{
a[i]=rand()%10; /*隨機(jī)生成要訪(fǎng)問(wèn)的頁(yè)面流*/
}
printf("所要訪(fǎng)問(wèn)的頁(yè)面號(hào)序列為：");
for(i=0;i<N;i++)
printf("%d ",a[i]);
printf("\n");
printf("頁(yè)面置換步驟如下：\n");
while(1)
{
printf("\n\n///");
printf("\nPlease select 1:FIFO算法\n 2:LRU算法\n 3:Optimal算法\n 4:退出\n");
scanf("%s",&s);
switch(s)
{
case '1':FIFOMain(a);break;
case '2':LruMain(a); break;
case '3':OptimalMain(a); break;
case '4':exit(0); break;
}
}
}
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
c++實(shí)現(xiàn)跳躍表（Skip List）的方法示例
跳表（skiplist）是一個(gè)非常優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)簡(jiǎn)單，插入、刪除、查找的復(fù)雜度均為O(logN)，下面這篇文章主要介紹了c++實(shí)現(xiàn)跳躍表（Skip List）的相關(guān)資料，需要的朋友可以參考借鑒，下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2017-09-09
斐波那契數(shù)一般指斐波那契數(shù)列。 斐波那契數(shù)列（Fibonacci sequence），又稱(chēng)黃金分割數(shù)列，因數(shù)學(xué)家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱(chēng)為兔子數(shù)列2022-05-05
C語(yǔ)言實(shí)現(xiàn)學(xué)生打卡系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)學(xué)生打卡系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12
這篇文章主要介紹了C++設(shè)計(jì)模式之原型模式,本文講解了什么是原型模式、為什么要使用原型模式、代碼實(shí)例等內(nèi)容,需要的朋友可以參考下2014-09-09
C++中的while循環(huán)和for循環(huán)語(yǔ)句學(xué)習(xí)教程
這篇文章主要介紹了C++中的while循環(huán)和for循環(huán)語(yǔ)句學(xué)習(xí)教程,是C++入門(mén)學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言代碼實(shí)現(xiàn)俄羅斯方塊，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-01-01
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言代碼實(shí)現(xiàn)三子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
C語(yǔ)言單鏈表實(shí)現(xiàn)多項(xiàng)式相加
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言單鏈表實(shí)現(xiàn)多項(xiàng)式相加，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-10-10
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)詞法分析器，一個(gè)簡(jiǎn)單的詞法分析程序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-01-01
C++實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)(Map實(shí)現(xiàn))
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06