C語言實現(xiàn)頁面置換算法(FIFO、LRU)
更新時間：2021年12月11日 14:21:24 作者：S_MIL
這篇文章主要介紹了通過C語言實現(xiàn)的兩種頁面置換算法：先進(jìn)先出(FIFO)頁面置換算法和最近最久未使用(LRU)頁面置換算法。文中的代碼具有一定的學(xué)習(xí)或工作價值，快來跟隨小編學(xué)習(xí)一下吧
1.實現(xiàn)效果
2.實現(xiàn)源代碼?
#include<iostream>
#include<process.h>
#include<stdlib.h>
#include<ctime>
#include<conio.h>
#include<stdio.h>
#include<string.h>
using namespace std;
#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")/*表格控制*/
#define bsize 4 //物理塊大小
#define psize 16 //進(jìn)程大小
void chushihua();//初始化函數(shù)
void ymzh();
void yemianzhihuan ();
void changeaddr(struct Page p[], int logaddr);
void dizhizhuanhuan();
void menu();
int wang();
int yemianliu[32]={0};//全局變量數(shù)組,地址流
int p;
struct Page {
int pno;//頁號
int flag;//標(biāo)志位
int cno;//主存號
int modf;//修改位
int addr;//外存地址
}Page; //全局變量p是一共有多少地址流
typedef struct pagel
{
int num; /*記錄頁面號*/
int time; /*記錄調(diào)入內(nèi)存時間*/
}Pagel; /*頁面邏輯結(jié)構(gòu),方便算法實現(xiàn)*/
Pagel b[bsize]; /*內(nèi)存單元數(shù)*/
int c[bsize][psize];/*保存內(nèi)存當(dāng)前的狀態(tài):緩沖區(qū)*/
int queue[100];/*記錄調(diào)入隊列*/
int k;/*調(diào)入隊列計數(shù)變量*/
int phb[bsize]={0};//物理塊標(biāo)號
int pro[psize]={0};//進(jìn)程序列號
int flag[bsize]={0};//進(jìn)程等待次數(shù)(存放最久未被使用的進(jìn)程標(biāo)志)*/
int i=0,j=0;//i表示進(jìn)程序列號,j表示物理塊號*/
int m =-1,n =-1;//物理塊空閑和進(jìn)程是否相同判斷標(biāo)志*/
int mmax=-1, maxflag=0;//標(biāo)記替換物理塊進(jìn)程下標(biāo)*/
int count =0; //統(tǒng)計頁面缺頁次數(shù)
void chushihua() //初始化函數(shù)
{
int t;
srand(time(0));//隨機(jī)產(chǎn)生指令序列
p=12+rand()%32;
cout<<"地址流序列:";
cout<<endl;
for(i=0; i<p; i++)
{
t=1+rand()%9;
yemianliu[i]=t;//將隨機(jī)產(chǎn)生的指令數(shù)存入頁面流
}
for (i=p-1;i>=0;i--)
{
cout<<yemianliu[i]<<" ";
}
cout<<endl;
}
void ymzh()
{
chushihua();
yemianzhihuan();
}
void yemianzhihuan()
{
int a;
printf("----------------------------------\n");
printf("☆☆歡迎使用分頁模擬實驗系統(tǒng)☆☆\n");
printf("----------------------------------");
printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
printf("☆☆1.進(jìn)入硬件地址變換算法 ☆☆\n");
printf("☆☆------------------------☆☆\n");
printf("☆☆2.進(jìn)入頁面置換算法 ☆☆\n");
printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
printf("請輸入您的選擇:");
switch(a)
{
case 1:
ymzh();
break;
case 2:
wang();
break;
default:
cout<<"輸入有誤,請重新輸入!"<<endl;
break;
}
}
void changeaddr(struct Page p[], int logaddr){//地址變換
int j=logaddr/64;//對應(yīng)的塊號
int k=logaddr%64; //對應(yīng)的偏移量
int flag=0;
int addr;
for(int i=0;i<8;i++)
{
if(p[i].pno==j)//找到對應(yīng)的頁號
{
if(p[i].flag==1)//頁面標(biāo)志為1
{
addr=p[i].cno*64+k;
cout<<"物理地址為:"<<addr<<endl;
cout<<"詳細(xì)信息:"<<"\t頁面號:"<<p[i].pno<<"\t 主存號："<<p[i].cno<<"\t偏移量:"<<k<<endl;
flag=1;
break;
}
}
}
if(flag==0)
cout<<"該頁不在主存,產(chǎn)生缺頁中斷"<<endl;
}
void dizhizhuanhuan()
{
int a;
int ins;//指令邏輯地址
struct Page p[8];
p[0].pno=0;p[0].flag=1;p[0].cno=5;p[0].modf=1;p[0].addr=011;
p[1].pno=1;p[1].flag=1;p[1].cno=8;p[1].modf=1;p[1].addr=012;
p[2].pno=2;p[2].flag=1;p[2].cno=9;p[2].modf=0;p[2].addr=013;
p[3].pno=3;p[3].flag=1;p[3].cno=10;p[3].modf=0;p[3].addr=015;
p[4].pno=4;p[4].flag=0;p[4].addr=017;
p[5].pno=5;p[5].flag=0;p[5].addr=025;
p[6].pno=6;p[6].flag=0;p[6].addr=212;
p[7].pno=7;p[7].flag=0;p[7].addr=213;
printf("\t\t\t--------------------------------\n");
printf("\t\t\t☆☆歡迎使用分頁模擬實驗系統(tǒng)☆☆\n");
printf("\t\t\t---------------------------------\n");
printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
printf("\t\t\t☆☆1.輸入指令 ☆☆\n");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆2.進(jìn)入頁面置換算法 ☆☆\n");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆0.EXIT ☆☆\n");
printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
while(a!=0)
{
cout<<endl<<"請輸入您的選擇:";
cin>>a;
cout<<"頁號"<<"標(biāo)記位"<<"外存地址"<<"主存號"<<endl;
for(int i=0;i<8;i++)
{
cout<<p[i].pno<<"\t"<<p[i].flag<<"\t"<<p[i].addr<<"\t";
if(p[i].flag)
cout<<p[i].cno;
cout<<endl;
}
switch(a)
{
case 0:printf("\t\t\t再見!\t\t\t\n"); break;
case 1:
cout<<"請輸入指令的邏輯地址:";
cin>>ins;
changeaddr(p, ins);break;
case 2: system("CLS"); a=wang();break;
default:cout<<"輸入有誤,請重新輸入!"<<endl;break;
}
}
}
void menu()
{
int a;
printf("\t\t\t--------------------------------\n");
printf("\t\t\t☆☆歡迎使用分頁模擬實驗系統(tǒng)☆☆\n");
printf("\t\t\t---------------------------------\n");
printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
printf("\t\t\t☆☆1.輸入指令 ☆☆\n");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆2.進(jìn)入頁面置換算法 ☆☆\n");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆0.EXIT ☆☆\n");
printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
printf("請選擇所要執(zhí)行的操作:");
scanf("%d",&a);
switch(a)
{
case 0: printf("\t\t\t-再見!-\t\t\t\n");break;
case 1: dizhizhuanhuan (); break;
case 2: wang (); break;
default:cout<<"輸入有誤,請重新輸入!"<<endl;break;
}
}
int main()
{
menu();
}
//****************隨機(jī)產(chǎn)生序列號函數(shù)
int* build()
{
printf("隨機(jī)產(chǎn)生一個進(jìn)程序列號為:\n");
int i=0;
for(i=0; i<psize; i++)
{
pro[i]=10*rand()/(RAND_MAX+1)+1;
printf("%d ", pro[i]);
}
printf("\n");
return(pro);
}
//***************************************查找空閑物理塊
int searchpb()
{
for (j=0;j<bsize; j++)
{
if(phb[j] == 0)
{
m=j;
return m;
break;
}
}
return -1;
}
//************************************查找相同進(jìn)程
int searchpro()
{
for(j=0;j< bsize;j++)
{
if(phb[j] =pro[i])
{
n=j;
return j;
}
}
return -1;
}
//*************************初始化內(nèi)存
void empty()
{
for(i=0;i<bsize;i++)
phb[i]=0;
count=0; //計數(shù)器置零
} //******先進(jìn)先出頁面置換算法
void FIFO()
{
for( i=0; i<psize; i++)
{
// m=searchpb();
// n=searchpro();
//找到第一個空閑的物理快
for(j=0;j<bsize;j++) {
if(phb[j] == 0){
m=j;
break;
}
}
//找與進(jìn)程相同的標(biāo)號
for(j=0;j<bsize;j++) {
if(phb[j] == pro[i]){
n=j;
}
}
//找flag值最大的
for(j=0;j<bsize;j++)
{
if(flag[j]>maxflag)
{
maxflag = flag[j];
mmax = j;
}
}
if(n == -1)//不存在相同進(jìn)程
{
if(m != -1)//存在空閑物理塊
{
phb[m]=pro[i];//進(jìn)程號填入該空閑物理塊
// count++;
flag[m]=0;
for (j=0;j<=m; j++)
{
flag[j]++;
}
m=-1;
}
else//不存在空閑物理塊
{
phb[mmax] =pro[i];
flag[mmax] =0;
for (j=0;j<bsize;j++)
{
flag[j]++;
}
mmax = -1;
maxflag = 0;
count++;
}
}
else//存在相同的進(jìn)程
{
phb[n] = pro[i];
for(j=0;j<bsize;j++)
{
flag[j]++;
}
n=-1;
}
for(j=0;j < bsize;j++)
{
printf("%d ", phb[j]);
}
printf("\n");
}
printf("缺頁次數(shù)為:%d\n",count);
printf("缺頁率 :%16. 6f",(float)count/psize);
printf("\n");
}
/*初始化內(nèi)存單元、緩沖區(qū)*/
void Init(Pagel *b,int c[bsize][psize])
{
int i,j;
for (i=0;i<psize;i++)
{
b[i].num=-1;
b[i].time=psize-i-1;
}
for(i=0;i<bsize;i++)
for(j=0;j<psize;j++)
c[i][j]=-1;
}
/*取得在內(nèi)存中停留最久的頁面,默認(rèn)狀態(tài)下為最早調(diào)入的頁面*/
int GetMax(Pagel *b)
{
int i;
int max=-1;
int tag=0;
for(i=0;i<bsize;i++)
{
if(b[i].time>max)
{
max=b[i].time;
tag= i;
}
}
return tag;
}
/*判斷頁面是否已在內(nèi)存中*/
int Equation(int fold, Pagel *b)
{
int i;
for(i=0;i<bsize;i++)
{
if(fold==b[i]. num)
return i;
}
return -1;
}
/*LRU核心部分*/
void Lruu(int fold, Pagel *b)
{
int i;
int val;
val=Equation(fold, b);
if (val>=0)
{
b[val].time=0;
for(i=0;i<bsize;i++)
if (i!=val)
b[i].time++;
}
else
{
queue[++k]=fold;/*記錄調(diào)入頁面*/
val=GetMax(b);
b[val].num=fold;
b[val].time=0;
for (i=0;i<bsize;i++){
// URLcount++;
if (i!=val)
b[i].time++;
}
}
}
void LRU()
{
int i,j;
k=0;
Init(b, c);
for(i=0; i<psize; i++)
{
Lruu(pro[i],b);
c[0][i]=pro[i];
/*記錄當(dāng)前的內(nèi)存單元中的頁面*/
for(j=0;j<bsize;j++)
c[j][i]=b[j].num;
}
/*結(jié)果輸出*/
printf("內(nèi)存狀態(tài)為:\n");
Myprintf;
for(j=0;j<psize;j++)
printf("|%2d", pro[j]);
printf("|\n");
Myprintf;
for(i=0;i<bsize;i++)
{
for(j=0; j<psize; j++)
{
if(c[i][j]==-1)
printf("|%2c",32);
else
printf("|%2d",c[i][j]);
}
printf("|\n");
}
Myprintf;
// printf("\n調(diào)入隊列為:");
// for(i=0;i<k;i++)
// printf("%3d", queue[i]);
printf("\n缺頁次數(shù)為:%6d\n 缺頁率 :%16. 6f", k+1,(float)(k+1)/psize);
}
//********主函數(shù)
int wang()
{
int sel;
do{
printf("\t\t\t--------------------------------\n");
printf("\t\t\t☆☆歡迎使用分頁模擬實驗系統(tǒng)☆☆\n");
printf("\t\t\t---------------------------------\n");
printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
printf("\t\t\t☆☆ 虛擬內(nèi)存 ☆☆\n");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆1.產(chǎn)生隨機(jī)序列 ☆☆\n");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆2.最近最久未使用 ☆☆\n");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆3.先進(jìn)先出 ☆☆\n");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆0.退出 ☆☆\n");
printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
printf("請選擇所要執(zhí)行的操作:");
scanf("%d",&sel);
switch(sel)
{
case 0: printf("\t\t\t再見!t\t\t\n"); break;
case 1: build(); break;
case 2: printf("最近最久未使用\n"); LRU();empty(); printf("\n");break;
case 3: printf("先進(jìn)先出算法\n"); FIFO();empty();printf("\n");break;
default:printf("請輸入正確的選項號!");printf("\n\n");break;
}
}while(sel !=0 );
return sel;
}
到此這篇關(guān)于C語言實現(xiàn)頁面置換算法(FIFO、LRU)的文章就介紹到這了,更多相關(guān)C語言 頁面置換算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C/C++編寫推箱子小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要介紹了C++編程中的bad_cast異常,bad_cast異常通常出現(xiàn)于表達(dá)式中類型轉(zhuǎn)換錯誤時等一些場景,需要的朋友可以參考下2016-01-01
單值二叉樹你可能之前沒見過，如果二叉樹每個節(jié)點都具有相同的值，那么該二叉樹就是單值二叉樹，讓我們通過一個真題來深刻了解它吧2022-04-04
做OTA升級功能時，我們能直接拿到的往往只是升級包的鏈接，需要我們自己去下載，這時候就需要用到http下載器。本文將利用C語言實現(xiàn)簡單的http下載器，感興趣的可以了解一下2022-12-12
這學(xué)期實訓(xùn)的時候用MFC做過一個飛機(jī)大戰(zhàn)，很無聊的東西，一直想用Qt做一個;首先需要解決的問題是圖片的移動，怎么說飛機(jī)啊子彈啊都是動著的，圖片當(dāng)然要跑起來,感興趣的你可不要走開啊2013-01-01
這篇文章主要介紹了C++ 實現(xiàn)靜態(tài)單鏈表的實例的相關(guān)資料,需要的朋友可以參考下2017-06-06
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)發(fā)牌洗牌，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要為大家詳細(xì)介紹了如何利用C++實現(xiàn)一個命令行進(jìn)度條，文中的示例代碼講解詳細(xì)，具有一定的學(xué)習(xí)價值，感興趣的小伙伴可以了解一下2023-06-06
用C/C++實現(xiàn)linux下檢測網(wǎng)絡(luò)接口狀態(tài)
這篇文章主要為大家詳細(xì)介紹了用c/c++實現(xiàn)linux下檢測網(wǎng)絡(luò)接口狀態(tài)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-06-06
這篇文章主要介紹了C++多態(tài)的實現(xiàn)機(jī)制理解的相關(guān)資料,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2016-07-07