?? 頁(yè)面置換算法.cpp
字號(hào):
// 頁(yè)面置換算法.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream.h>
#include<stdlib.h>
int npage=20;//請(qǐng)求頁(yè)面數(shù)
int mpage=3;//內(nèi)存中最大頁(yè)面數(shù)
int pagequeue[20];//請(qǐng)求頁(yè)面隊(duì)列
int b[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
int page[10];//內(nèi)存中頁(yè)面
int state[10];
int modify[20]={0,1,1,0,1,0,0,1,1,1,1,0,0,1,0,1,0,1,0,2};
float misshit;
int select2=9;
char select1;
int begin;
int i,j;
float missrate;
struct
{
int value[10];
int state[10];
int rear;
} queue;
void print();
void init()
{
int t=0;
int q=0;
bool full=false;
misshit=0;
begin=0;
missrate=0;
for(i=0;i<mpage;i++)
page[i]=-1;
while(t<npage)
{
bool get=false;
for(i=0;i<mpage;i++)
{
if(page[i]==pagequeue[t])
{
get=true;
state[i]=1;
}
}
if(get==true)
printf("頁(yè)面%d在內(nèi)存中已經(jīng)存在，即訪問(wèn)命中!\n",pagequeue[t]);
if(get==false)
{
printf("頁(yè)面%d在內(nèi)存中不存在，將其調(diào)入內(nèi)存!\n",pagequeue[t]);
page[q]=pagequeue[t];
state[q]=1;
q++;
}
print();
if(q==3)
{
break;
}
t++;
begin=t;
}//while
}
void print()
{
int b;
for(b=0;b<mpage;b++)
if(page[b]!=-1)
{
if(select2==4)
{
printf("%d(%d) \n",page[b],state[b]);
}
if(select2==5)
printf("%d(%d,%d) \n",page[b],state[b],modify[b]);
else
printf("%d ",page[b]);
}
printf("\n");
}
void Optimal()
{
int t=begin+1;
while(t<npage)
{
int c=0;
bool get=false;
int place[10]={0};
int longest=0;
for(i=0;i<mpage;i++)
{
if(pagequeue[t]==page[i])
{
get=true;
}
}
if(get==true)
printf("\n頁(yè)面%d 訪問(wèn)命中!\n",pagequeue[t]);
if(get==false)
{
for(i=0;i<mpage;i++)
{
bool have=false;
for(j=t+1;j<npage;j++)
{
if(page[i]==pagequeue[j])
{
place[i]=j;
have=true;
break;
}
}
if(have==false)
{
place[i]=100;
}
}//for
for(i=0;i<mpage;i++)
{
if(place[i]>c)
{
c=place[i];
longest=i;
}
}
printf("頁(yè)面%d 發(fā)生缺頁(yè)中斷!將頁(yè)面%d 換出頁(yè)面!\n",pagequeue[t],page[longest]);
page[longest]=pagequeue[t];
misshit++;
}//if
print();
t++;
}//while
missrate=misshit/npage;
printf("計(jì)算缺頁(yè)率為： %f\n",missrate);
}
void FIFO()
{
int t=begin+1;
int q=0;
while(t<npage)
{
bool get=false;
for(i=0;i<mpage;i++)
{
if(pagequeue[t]==page[i])
{
get=true;
}
}
if(get==true)
printf("頁(yè)面%d在內(nèi)存中已經(jīng)存在，即訪問(wèn)命中!\n",pagequeue[t]);
if(get==false)
{
printf("頁(yè)面%d 發(fā)生缺頁(yè)中斷!將頁(yè)面%d 換出!\n",pagequeue[t],page[q]);
page[q]=pagequeue[t];
q++;
misshit++;
}
if(q==mpage)
q=0;
print();
t++;
}//while
missrate=misshit/npage;
printf("計(jì)算缺頁(yè)率為： %f\n",missrate);
}
void LRU()
{
int t=begin+1;
int time[10]={0};
for(i=0;i<mpage;i++)
time[i]=i;
while(t<npage)
{
bool get=false;
for(i=0;i<mpage;i++)
{
if(page[i]==pagequeue[t])
{
get=true;
time[i]=t;
}
}
if(get==true)
printf("頁(yè)面%d在內(nèi)存中已經(jīng)存在，即訪問(wèn)命中!\n",pagequeue[t]);
if(get==false)
{
int temp=100;
int min;
for(i=0;i<mpage;i++)
{
if(time[i]<=temp)
{
temp=time[i];
min=i;
}
}//for
printf("頁(yè)面%d 發(fā)生缺頁(yè)中斷!將頁(yè)面%d 換出!\n",pagequeue[t],page[min]);
page[min]=pagequeue[t];
time[min]=t;
misshit++;
}//if
print();
t++;
}//while
missrate=misshit/npage;
printf("計(jì)算缺頁(yè)率為： %f\n",missrate);
}
void Clock()
{
int t=begin+1;
int q=0;
while(t<npage)
{
bool get=false;
for(i=0;i<mpage;i++)
{
if(pagequeue[t]==page[i])
{
get=true;
state[i]=1;
}
}
if(get==true)
printf("頁(yè)面%d在內(nèi)存中已經(jīng)存在，即訪問(wèn)命中!\n",pagequeue[t]);
if(get==false)
{
int n=2;
while(n>0)
{
while(q<mpage)
{
if(state[q]==0)
{
printf("頁(yè)面%d 發(fā)生缺頁(yè)中斷!將頁(yè)面%d 換出!\n",pagequeue[t],page[q]);
page[q]=pagequeue[t];
state[q]=1;
q++;
if(q==3)
{
q=0;
}
get=true;
break;
}
else
{
state[q]=0;
q++;
if(q==3)
{
q=0;
}
}//else
}//while
if(get==true) break;
q=0;
n--;
}//whlie
misshit++;
}//if
print();
t++;
}//while
missrate=misshit/npage;
printf("計(jì)算缺頁(yè)率為： %f\n",missrate);
}
void improve_Clock()
{
int t=begin+1;
int q=0;
while(t<npage)
{
bool get=false;
for(i=0;i<mpage;i++)
{
if(pagequeue[t]==page[i])
{
get=true;
modify[q]=modify[t];
state[i]=1;
}
}
if(get==true)
printf("頁(yè)面%d在內(nèi)存中已經(jīng)存在，即訪問(wèn)命中!\n",pagequeue[t]);
if(get==false)
{
int m=2;
while(m>0)
{
int n=3;
while(n>0)
{
while(q<mpage&&n==3)
{
if(state[q]==0&&modify[q]==0)
{
printf("頁(yè)面%d 發(fā)生缺頁(yè)中斷!將頁(yè)面%d 換出!\n",pagequeue[t],page[q]);
page[q]=pagequeue[t];
modify[q]=modify[t];
state[q]=1;
get=true;
break;
}
q++;
}//while第一遍循環(huán)
q=0;
while(q<mpage&&n==2)
{
if(state[q]==0&&modify[q]==1)
{
printf("頁(yè)面%d 發(fā)生缺頁(yè)中斷!將頁(yè)面%d 換出!\n",pagequeue[t],page[q]);
modify[q]=modify[t];
page[q]=pagequeue[t];
state[q]=1;
get=true;
break;
}
q++;
}
q=0;
while(q<mpage&&n==1&&m==2)
{
state[q]=0;
q++;
}
if(get==true) break;
q=0;
n--;
}//whlien
if(get==true) break;
m--;
}//whilem
misshit++;
}//if
for(i=0;i<mpage;i++)
printf("%d(%d,%d) \n",page[i],state[i],modify[i]);
t++;
}//while
missrate=misshit/npage;
printf("計(jì)算缺頁(yè)率為： %f\n",missrate);
}
void main()
{
cout<<"是否隨機(jī)產(chǎn)生頁(yè)面訪問(wèn)序列？（y/n）";
cin>>select1;
if(select1=='y')
{
cout<<"通過(guò)隨機(jī)方式，產(chǎn)生的頁(yè)面訪問(wèn)序列為："<<endl;
for(i=0;i<npage;i++)
{
pagequeue[i]=rand()%7;
cout<<pagequeue[i]<<" ";
}
}
else
{
for(i=0;i<npage;i++)
{
pagequeue[i]=b[i];
}
}
cout<<endl;
cout<<"0:退出"<<endl;
cout<<"1:最佳置換算法"<<endl;
cout<<"2:先進(jìn)先出頁(yè)面置換算法"<<endl;
cout<<"3:最近最久未使用置換算法"<<endl;
cout<<"4:簡(jiǎn)單Clock置換算法"<<endl;
cout<<"5:優(yōu)化Clock置換算法"<<endl;
printf("請(qǐng)選擇置換算法：\n");
while(select2!=0)
{
scanf("%d",&select2);
printf("\n");
switch (select2)
{
case 1:
init();
Optimal();
break;
case 2:
init();
FIFO();
break;
case 3:
init();
LRU();
break;
case 4:
init();
Clock();
break;
case 5:
init();
improve_Clock();
break;
}
}
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -