【操作系統(tǒng)】 置換策略模擬實(shí)現(xiàn)
【實(shí)現(xiàn)目標(biāo)】
? ? ?實(shí)現(xiàn)OPT,LRU,FIFO,CLOCK置換策略，并計(jì)算缺頁(yè)次數(shù)和缺頁(yè)率。
【算法分析】
? ? 1.OPT策略——最佳策略
? ? ? ? ? ? ? ? ? ? ? ?即根據(jù)將來(lái)的結(jié)果選擇替換的頁(yè)，但實(shí)際是不可能實(shí)現(xiàn)的，因?yàn)槲磥?lái)是無(wú)法預(yù)知的。但是可以作為性能分析的參照。
? ? 2.LRU策略——最近最少使用
? ? ? ? ? ? ? ? ? ? ? ?選出內(nèi)存中離現(xiàn)在使用時(shí)間最久遠(yuǎn)的頁(yè)進(jìn)行替換。
? ? 3.FIFO策略——先進(jìn)先出
? ? ? ? ? ? ? ? ? ? ? ?如題，就是按照順序進(jìn)行替換。
? ? 4.CLOCL策略——時(shí)鐘策略
? ? ? ? ? ? ? ? ? ? ? 每一個(gè)頁(yè)框?qū)?yīng)一個(gè)01狀態(tài)位，若頁(yè)框還未滿，則放入，并將該位置為1。若已滿，當(dāng)頁(yè)在內(nèi)部時(shí)，不用替換。否則，循環(huán)掃描使用位，碰到為0的則替換，若為1則置為0。若全為1，則再次循環(huán)時(shí)，會(huì)自動(dòng)替換第一個(gè)0。（每次循環(huán)是從上次替換的位置開(kāi)始，若沒(méi)發(fā)生替換，即在內(nèi)存中，不會(huì)移動(dòng)位置！）
【實(shí)驗(yàn)數(shù)據(jù)】
12 3
2 3 2 1 5 2 4 5 3 2 5 2
【實(shí)驗(yàn)結(jié)果】
【實(shí)驗(yàn)代碼】
? ??
#include
#include
#include
#define inf 0x3f3f3f3f
#define seq_sz 50
#define frame_sz 50
using namespace std;
//序列數(shù)，葉框數(shù)
int amount,volume;
int min(int a,int b)
{
???return a<b?a:b;
}
//序列，葉框
int seq[seq_sz],frame[frame_sz];
?
//OPT策略
void OPT()
{
??int cnt=0;
??printf("OPT:n");
??memset(frame,-1,sizeof(frame));
??//val數(shù)組狀態(tài)位，表征下一次使用時(shí)間，初始值為無(wú)窮大
??int val[frame_sz],p,maxx;
??for(int i=0;i<amount;i++)
?? {
?????bool flag=0;
?????for(int j=0;j<volume;j++)
?????{
????????if(frame[j]==seq[i])
????????{
???????????flag=1;
???????????break;
????????}
?????}
?????if(!flag)
?????{
???????cnt++;
???????if(cnt>volume)
???????{
???????????memset(val,inf,sizeof(val));
???????????for(int j=i;j<amount;j++)
???????????{
??????????????? for(int k=0;k<volume;k++)
??????????????? {
??????????????????? if(frame[k]==seq[j])
??????????????????? {
????????????????????? ??val[k]=min(val[k],j);
??????????????????? }
??????????????? }
???????????}
???????????p=0;
???????????maxx=val[0];
???????????for(int j=1;j<volume;j++)
???????????{
??????????????? if(val[j]>maxx)
??????????????? {
??????????????????? maxx=val[j];
??????????????????? p=j;
??????????????? }
???????????}
???????????frame[p]=seq[i];
???????}
???????else
???????{
?????????frame[cnt-1]=seq[i];
???????}
?????}
?????for(int j=0;j<volume;j++)
?????{
???????if(frame[j]!=-1)
?????????printf("%6d?",frame[j]);
???????else
?????????printf("Empty!? ");
?????}
?????printf("n");
?? }
?? //輸出缺頁(yè)次數(shù)和缺頁(yè)率
??printf("Pages missed: %d???Pages missing Rate:%.2lf%nn",cnt,cnt*100.0/amount);
}
//LRU策略
void LRU()
{
?printf("LRU:n");
?//cnt為缺頁(yè)次數(shù)，val表征最近使用時(shí)間，也是選擇標(biāo)準(zhǔn)
? intcnt=0,val[frame_sz],p,minn;
?memset(frame,-1,sizeof(frame));
?for(int i=0;i<amount;i++)
? {
?????bool flag=0;
?????for(int j=0;j<volume;j++)
?????{
????????if(frame[j]==seq[i])
????????{
???????????flag=1;
???????????val[j]=i;
???????????break;
????????}
?????}
?????if(!flag)
?????{
????????cnt++;
????????if(cnt>volume)
????????{
???????????minn=val[0];
???????????p=0;
???????????for(int j=1;j<volume;j++)
???????????{
??????????????? if(val[j]<minn)
??????????????? {
??????????????????? minn=val[j];
??????????????????? p=j;
??????????????? }
???????????}
???????????frame[p]=seq[i];
???????????val[p]=i;
????????}
????????else
????????{
???????????frame[cnt-1]=seq[i];
???????????val[cnt-1]=i;
????????}
?????}
?????for(int j=0;j<volume;j++)
?????{
???????if(frame[j]!=-1)
?????????printf("%6d?",frame[j]);
???????else
?????????printf("Empty!? ");
?????}
?????printf("n");
? }
? //輸出缺頁(yè)次數(shù)，缺頁(yè)率
?printf("Pages missed: %d???Pages missing Rate:%.2lf%nn",cnt,cnt*100.0/amount);
}
//FIFO策略
void FIFO()
{
??printf("FIFO:n");
??//qe模擬隊(duì)列，模除循環(huán)
??int qe[frame_sz],p=0,cnt=0;
??memset(frame,-1,sizeof(frame));
??for(int i=0;i<amount;i++)
?? {
?????bool flag=0;
?????for(int j=0;j<volume;j++)
?????{
????????if(frame[j]==seq[i])
????????{
???????????flag=1;
???????????break;
????????}
?????}
?????if(!flag)
?????{
????????cnt++;
????????frame[p%volume]=seq[i];
????????p++;
?????}
?????for(int j=0;j<volume;j++)
?????{
???????if(frame[j]!=-1)
?????????printf("%6d?",frame[j]);
???????else
?????????printf("Empty!? ");
?????}
?????printf("n");
?? }
??printf("Pages missed: %d???Pages missing Rate:%.2lf%nn",cnt,cnt*100.0/amount);
}
//CLOCK策略
void CLOCK()
{
??printf("CLOCK:n");
??//status狀態(tài)位
??bool status[frame_sz];
??int p=0,cnt=0;
??memset(frame,-1,sizeof(frame));
??memset(status,0,sizeof(status));
??for(int i=0;i<amount;i++)
?? {
?????bool flag=0;
?????for(int j=0;j<volume;j++)
?????{
????????if(frame[j]==seq[i])
????????{
???????????flag=1;
???????????status[j]=1;
???????????break;
????????}
?????}
?????if(!flag)
?????{
????????? cnt++;
???????while(1)
???????{
???????????p%=volume;
?? ?????????bool sign=0;
???????????for(;p<volume;p++)
???????????{
??????????????? if(status[p])
????????????????? status[p]=0;
??????????????? else
??????????????? {
??????????????????? sign=1;
??????????????????? status[p]=1;
??????????????????? frame[p]=seq[i];
??????????????????? p++;
??????????????????? break;
??????????????? }
???????????}
???????????if(sign)break;
???????}
?????}
?????for(int j=0;j<volume;j++)
?????{
???????if(frame[j]!=-1)
?????????printf("%6d?",frame[j]);
???????else
?????????printf("Empty!? ");
?????}
?????printf("n");
?? }
??printf("Pages missed: %d???Pages missing Rate:%.2lf%nn",cnt,cnt*100.0/amount);
}
int main()
{
??while(~scanf("%d%d",&amount,&volume))
?? {
?????for(int i=0;i<amount;i++)
???????scanf("%d",&seq[i]);
?????for(int i=0;i<amount;i++)
???????printf(" %d",seq[i]);
?????printf("n");
?????//分別測(cè)試
?????OPT();
?????LRU();
?????FIFO();
?????CLOCK();
?? }?
下載文檔
