C語言實現頁面置換算法(FIFO、LRU)
更新時間：2021年12月11日 14:21:24 作者：S_MIL
這篇文章主要介紹了通過C語言實現的兩種頁面置換算法：先進先出(FIFO)頁面置換算法和最近最久未使用(LRU)頁面置換算法。文中的代碼具有一定的學習或工作價值，快來跟隨小編學習一下吧
1.實現效果
2.實現源代碼?
#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 //進程大小
void chushihua();//初始化函數
void ymzh();
void yemianzhihuan ();
void changeaddr(struct Page p[], int logaddr);
void dizhizhuanhuan();
void menu();
int wang();
int yemianliu[32]={0};//全局變量數組,地址流
int p;
struct Page {
int pno;//頁號
int flag;//標志位
int cno;//主存號
int modf;//修改位
int addr;//外存地址
}Page; //全局變量p是一共有多少地址流
typedef struct pagel
{
int num; /*記錄頁面號*/
int time; /*記錄調入內存時間*/
}Pagel; /*頁面邏輯結構,方便算法實現*/
Pagel b[bsize]; /*內存單元數*/
int c[bsize][psize];/*保存內存當前的狀態(tài):緩沖區(qū)*/
int queue[100];/*記錄調入隊列*/
int k;/*調入隊列計數變量*/
int phb[bsize]={0};//物理塊標號
int pro[psize]={0};//進程序列號
int flag[bsize]={0};//進程等待次數(存放最久未被使用的進程標志)*/
int i=0,j=0;//i表示進程序列號,j表示物理塊號*/
int m =-1,n =-1;//物理塊空閑和進程是否相同判斷標志*/
int mmax=-1, maxflag=0;//標記替換物理塊進程下標*/
int count =0; //統(tǒng)計頁面缺頁次數
void chushihua() //初始化函數
{
int t;
srand(time(0));//隨機產生指令序列
p=12+rand()%32;
cout<<"地址流序列:";
cout<<endl;
for(i=0; i<p; i++)
{
t=1+rand()%9;
yemianliu[i]=t;//將隨機產生的指令數存入頁面流
}
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.進入硬件地址變換算法 ☆☆\n");
printf("☆☆------------------------☆☆\n");
printf("☆☆2.進入頁面置換算法 ☆☆\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;//對應的塊號
int k=logaddr%64; //對應的偏移量
int flag=0;
int addr;
for(int i=0;i<8;i++)
{
if(p[i].pno==j)//找到對應的頁號
{
if(p[i].flag==1)//頁面標志為1
{
addr=p[i].cno*64+k;
cout<<"物理地址為:"<<addr<<endl;
cout<<"詳細信息:"<<"\t頁面號:"<<p[i].pno<<"\t 主存號："<<p[i].cno<<"\t偏移量:"<<k<<endl;
flag=1;
break;
}
}
}
if(flag==0)
cout<<"該頁不在主存,產生缺頁中斷"<<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.進入頁面置換算法 ☆☆\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<<"頁號"<<"標記位"<<"外存地址"<<"主存號"<<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.進入頁面置換算法 ☆☆\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();
}
//****************隨機產生序列號函數
int* build()
{
printf("隨機產生一個進程序列號為:\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;
}
//************************************查找相同進程
int searchpro()
{
for(j=0;j< bsize;j++)
{
if(phb[j] =pro[i])
{
n=j;
return j;
}
}
return -1;
}
//*************************初始化內存
void empty()
{
for(i=0;i<bsize;i++)
phb[i]=0;
count=0; //計數器置零
} //******先進先出頁面置換算法
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;
}
}
//找與進程相同的標號
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)//不存在相同進程
{
if(m != -1)//存在空閑物理塊
{
phb[m]=pro[i];//進程號填入該空閑物理塊
// 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//存在相同的進程
{
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("缺頁次數為:%d\n",count);
printf("缺頁率 :%16. 6f",(float)count/psize);
printf("\n");
}
/*初始化內存單元、緩沖區(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;
}
/*取得在內存中停留最久的頁面,默認狀態(tài)下為最早調入的頁面*/
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;
}
/*判斷頁面是否已在內存中*/
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;/*記錄調入頁面*/
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];
/*記錄當前的內存單元中的頁面*/
for(j=0;j<bsize;j++)
c[j][i]=b[j].num;
}
/*結果輸出*/
printf("內存狀態(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調入隊列為:");
// for(i=0;i<k;i++)
// printf("%3d", queue[i]);
printf("\n缺頁次數為:%6d\n 缺頁率 :%16. 6f", k+1,(float)(k+1)/psize);
}
//********主函數
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");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆1.產生隨機序列 ☆☆\n");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆2.最近最久未使用 ☆☆\n");
printf("\t\t\t☆☆------------------------☆☆\n");
printf("\t\t\t☆☆3.先進先出 ☆☆\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("先進先出算法\n"); FIFO();empty();printf("\n");break;
default:printf("請輸入正確的選項號!");printf("\n\n");break;
}
}while(sel !=0 );
return sel;
}
到此這篇關于C語言實現頁面置換算法(FIFO、LRU)的文章就介紹到這了,更多相關C語言 頁面置換算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
在C語言中，sizeof是一個非常常用的關鍵字，本文主要介紹了C語言?sizeof關鍵字的具體使用，包括sizeof 關鍵字的語法、用法、特點和注意事項，感興趣的可以了解一下2024-02-02
這篇文章主要為大家詳細介紹了如何使用C/C++實現手寫數字識別,分別處理 32*32 文本數據集和mnist 28*28 png數據集,感興趣的小伙伴可以跟隨小編一起了解一下2023-10-10
Qt?SQL模塊是Qt中用來操作數據庫的類，該類封裝了各種SQL數據庫接口，可以很方便的鏈接并使用。本文主要介紹了Qt數據庫QSql增刪改查組件的應用教程，感興趣的同學可以學習一下2021-12-12
這篇文章主要介紹了C語言結構體鏈表和指針實現學生管理系統(tǒng)，包括學生檔案管理子系統(tǒng)和學生成績管理子系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要為大家詳細介紹了C++數據結構之雙向鏈表，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
這篇文章主要為大家詳細介紹了OpenCV實現二值圖像的邊緣光滑處理，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
這篇文章主要為大家詳細介紹了C語言實現雙人反彈球游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
本文給大家分享給大家的是C語言的字符串大小比較的函數，有需要的小伙伴可以參考下。2015-07-07
在C++中，靜態(tài)成員是屬于整個類的而不是某個對象，靜態(tài)成員變量只存儲一份供所有對象共用。所以在所有對象中都可以共享它。使用靜態(tài)成員變量實現多個對象之間的數據共享不會破壞隱藏的原則，保證了安全性還可以節(jié)省內存2022-04-04
本篇文章是對c語言中用字符串數組顯示菜單的方法進行了詳細的分析介紹，需要的朋友參考下2013-05-05