第一篇：實(shí)驗(yàn)5 頁面置換算法
實(shí)驗(yàn)5
頁面置換算法
一、實(shí)驗(yàn)題目：頁面置換算法（請(qǐng)求分頁）
二、實(shí)驗(yàn)?zāi)康模?/p>
進(jìn)一步理解父子進(jìn)程之間的關(guān)系。
1）理解內(nèi)存頁面調(diào)度的機(jī)理。2）掌握頁面置換算法的實(shí)現(xiàn)方法。3）通過實(shí)驗(yàn)比較不同調(diào)度算法的優(yōu)劣。4）培養(yǎng)綜合運(yùn)用所學(xué)知識(shí)的能力。
頁面置換算法是虛擬存儲(chǔ)管理實(shí)現(xiàn)的關(guān)鍵，通過本次試驗(yàn)理解內(nèi)存頁面調(diào)度的機(jī)制，在模擬實(shí)現(xiàn)FIFO、LRU等經(jīng)典頁面置換算法的基礎(chǔ)上，比較各種置換算法的效率及優(yōu)缺點(diǎn)，從而了解虛擬存儲(chǔ)實(shí)現(xiàn)的過程。將不同的置換算法放在不同的子進(jìn)程中加以模擬，培養(yǎng)綜合運(yùn)用所學(xué)知識(shí)的能力。
三、實(shí)驗(yàn)內(nèi)容及要求
這是一個(gè)綜合型實(shí)驗(yàn)，要求在掌握父子進(jìn)程并發(fā)執(zhí)行機(jī)制和內(nèi)存頁面置換算法的基礎(chǔ)上，能綜合運(yùn)用這兩方面的知識(shí)，自行編制程序。
程序涉及一個(gè)父進(jìn)程和兩個(gè)子進(jìn)程。父進(jìn)程使用rand()函數(shù)隨機(jī)產(chǎn)生若干隨機(jī)數(shù)，經(jīng)過處理后，存于一數(shù)組Acess_Series[]中，作為內(nèi)存頁面訪問的序列。兩個(gè)子進(jìn)程根據(jù)這個(gè)訪問序列，分別采用FIFO和LRU兩種不同的頁面置換算法對(duì)內(nèi)存頁面進(jìn)行調(diào)度。要求：
1）每個(gè)子進(jìn)程應(yīng)能反映出頁面置換的過程，并統(tǒng)計(jì)頁面置換算法的命中或缺頁情況。
設(shè)缺頁的次數(shù)為diseffect?？偟捻撁嬖L問次數(shù)為total_instruction。缺頁率 = disaffect/total_instruction 命中率 = 1-disaffect/total_instruction 2）將為進(jìn)程分配的內(nèi)存頁面數(shù)mframe 作為程序的參數(shù)，通過多次運(yùn)行程序，說明FIFO算法存在的Belady現(xiàn)象。
四、程序流程圖
開始創(chuàng)建子進(jìn)程1創(chuàng)建子進(jìn)程2
結(jié)束 子進(jìn)程1邏輯頁面讀完？N命中？N內(nèi)存頁面滿？Y命中次數(shù)+1YY最先進(jìn)入的進(jìn)程退出內(nèi)存頁面N當(dāng)前調(diào)入頁面進(jìn)入內(nèi)存頁面退出 2邏輯頁面讀完？N命中？N內(nèi)存頁面滿？N當(dāng)前調(diào)入頁面進(jìn)入內(nèi)存頁面Y被訪問次數(shù)最少的進(jìn)程退出內(nèi)存頁面Y命中次數(shù)+1，命中頁面訪問數(shù)+1Y退出
五、運(yùn)行結(jié)果及其說明
FIFO:
LRU:
：
六、回答以下問題： ① 父進(jìn)程、子進(jìn)程之間的并發(fā)執(zhí)行的過程
父進(jìn)程與子進(jìn)程之間的并發(fā)執(zhí)行宏觀并行，微觀串行。從宏觀來說，父進(jìn)程創(chuàng)建子進(jìn)程1，子進(jìn)程1和父進(jìn)程同時(shí)執(zhí)行，直到父進(jìn)程創(chuàng)建子進(jìn)程2遇到wait()函數(shù)掛機(jī)為止，當(dāng)子進(jìn)程1結(jié)束父進(jìn)程和子進(jìn)程2并發(fā)執(zhí)行到再次遇見wait()函數(shù)是掛起等待子進(jìn)程2結(jié)束，到子進(jìn)程2結(jié)束返回父進(jìn)程父進(jìn)程繼續(xù)執(zhí)行至結(jié)束。從微觀來說，父進(jìn)程先執(zhí)行至創(chuàng)建子進(jìn)程1，接下來父進(jìn)程掛起執(zhí)行子進(jìn)程1知道子進(jìn)程1結(jié)束回到父進(jìn)程；父進(jìn)程繼續(xù)執(zhí)行到創(chuàng)建子進(jìn)程2再次掛起，執(zhí)行子進(jìn)程2，直到子進(jìn)程2結(jié)束回到父進(jìn)程繼續(xù)執(zhí)行至結(jié)束。
② 通過完成實(shí)驗(yàn)，根據(jù)你的體會(huì)，闡述虛擬存儲(chǔ)器的原理。虛擬存儲(chǔ)器實(shí)際上是用來解決作業(yè)大而內(nèi)存小的問題，他通過頁面置換算法來提供遠(yuǎn)大于內(nèi)存地址空間的地址范圍，針對(duì)不同的程序?qū)⒉煌臄?shù)據(jù)頁面讀取到虛擬存儲(chǔ)器中用來實(shí)現(xiàn)。
③ 寫出FIFO算法中出現(xiàn)Belady現(xiàn)象的內(nèi)存頁面訪問序列。
4個(gè)內(nèi)存頁面數(shù)：
序列2 2 5 3 3 1 3 1 2 5 5 2 3個(gè)內(nèi)存頁面數(shù)：
序列2 1 3 2 1 4 3 1 3 1 5 5
7次命中，命中率為0.58 6次命中，命中率為0.5
七、程序源代碼、文檔注釋及文字說明
#include
main(){ srand(time(0));int pid1, pid2, fd[2], Acess_Series[12], temp;float effect, rate = 0;char str1[100], str2[100];struct M_Frame {
int page_no;
char flag;};struct M_Frame one_frame[4];one_frame[0].page_no = 0;one_frame[1].page_no = 0;one_frame[2].page_no = 0;one_frame[3].page_no = 0;effect = 0;int i = 0;printf(“內(nèi)存訪問頁面序列:”);for(;i<12;i++){
Acess_Series[i] = rand()% 5 + 1;
printf(“%d ”, Acess_Series[i]);} while((pid1 = fork())==-1);if(pid1 == 0){
int no = 0;
int pno = 0;
printf(“FIFO頁面置換算法:n”);
for(;no<12;no++)
{
printf(“調(diào)入的頁面號(hào)是%d ”, Acess_Series[no]);
int k = 0;
for(;k <= Frame;k++)
{
if(one_frame[k].page_no == Acess_Series[no]){ effect++;printf(“命中n”);break;}
if(one_frame[k].page_no == 0)
{
one_frame[k].page_no = Acess_Series[no];
printf(“未命中n”);
break;
}
if(k == Frame)
{
int j = 1;
for(;j <= Frame;j++)
{
one_frame[j1].page_no;one_frame[t1].page_no = one_frame[j].page_no;
}
one_frame[Frame].page_no = Acess_Series[no];
printf(“未命中n”);
}
}
printf(“內(nèi)存情況為:%d |%d |%d |%dn”, one_frame[0].page_no, one_frame[1].page_no, one_frame[2].page_no, one_frame[3].page_no);
}
rate = effect / 12;
printf(“命中次數(shù)：%fn”, effect);
printf(“命中率：%fn”, rate);
}
wait(0);
exit(0);} }
第二篇：計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)4頁面置換算法
實(shí)驗(yàn)4 頁面置換算法（2學(xué)時(shí)）
一、實(shí)驗(yàn)?zāi)康?/p>
通過實(shí)驗(yàn)加強(qiáng)對(duì)虛擬存儲(chǔ)管理中頁面置換算法的理解和掌握。
二、實(shí)驗(yàn)內(nèi)容
編寫程序?qū)崿F(xiàn)虛擬存儲(chǔ)管理中OPT,FIFO,LRU頁面置換算法。
三、實(shí)驗(yàn)要求
1、任意給出一組頁面訪問順序（如頁面走向是1、2、5、7、5、7、1、4、3、5、6、4、3、2、1、5、2）。
2、分配給該作業(yè)一定的物理塊（如3塊、4塊等）。
3、利用OPT,FIFO,LRU頁面置換算法模擬頁面置換過程并計(jì)算其缺頁率。
4、每訪問一個(gè)頁面均需給出內(nèi)存中的內(nèi)容（內(nèi)存中的頁面號(hào)），若有淘汰還需給出淘汰的頁面號(hào)。
5、通過給出特殊的頁面訪問順序，分配不同的物理塊，利用FIFO算法計(jì)算其缺頁率，進(jìn)一步理解Belady現(xiàn)象。
6、（附加）實(shí)現(xiàn)CLOCK置換算法，修改位可在確定頁面號(hào)時(shí)直接任意給出。
程序代碼（java）
package wcm4;
import java.util.LinkedList;import java.util.Scanner;
public class Test {
/**
* @param args
*/ LinkedList ll=new LinkedList();int a;int leng;int[] all={1,2,5,7,5,7,1,4,3,5,6,4,3,2,1,5,2};//int[] free=new int[all.length];
Object o=new Integer(a);public static void main(String[] args){
public void begin(){ System.out.println(“請(qǐng)選擇測(cè)試類型：”);System.out.println(“1 OPT;2 FiFO;3 LRU;4 CLOCK;5退出”);
} public void need(){ System.out.println(“請(qǐng)輸入分配給該作業(yè)的物理塊數(shù)：”);Scanner sc=new Scanner(System.in);leng=sc.nextInt();Scanner sc=new Scanner(System.in);int choose=sc.nextInt();while(choose!=5){
} switch(choose){ case 1:this.opt();break;case 2:this.fifo();break;case 3:this.lru();break;case 4:this.clock();break;} System.out.println(“請(qǐng)選擇測(cè)試類型：”);System.out.println(“1 OPT;2 FiFO;3 LRU;4 CLOCK;5退出”);sc=new Scanner(System.in);choose=sc.nextInt();// TODO Auto-generated method stub Test t=new Test();t.begin();
}
}
public void fifo(){ ll=new LinkedList();this.need();
int a=0;for(int i=0;i o=all[i];if(!ll.contains(o)){ } if(ll.size() } ll.add(o);o=ll.poll();a++;else{ o=null;} this.print();} System.out.println(“FIFO的缺頁率為：”);System.out.println(a);System.out.println(“——”);System.out.println(all.length); } public void opt(){//最佳置換算法 //leng=0;ll=new LinkedList();this.need();int a=0;//int temp=0;//int[] b=new int[leng]; for(int i=0;i int[] b=new int[leng];o=all[i];if(!ll.contains(o)){ if(ll.size() ll.add(o); } o=null;} else{ for(int j=i;j Object o1=new Integer(all[j]); } for(int k=0;k } if(ll.get(k).equals(o1)){ } if(b[k]==0){ b[k]=j;//待替換的頁在以后第一次出現(xiàn)的位置 } } if(b[leng-1]==0){ o=ll.set(leng-1, o);a++;} else{ int temp=0; } for(int m=0;m if(b[m]==0){ temp=m;break;} else if(b[m]>b[temp]){ } temp=m; } o=ll.set(temp, o);//替換以后離得最遠(yuǎn)的 a++;} else{ } o=null;this.print();} System.out.println(“OPT的缺頁率為：”);System.out.println(a);System.out.println(“——”);System.out.println(all.length); public void lru(){//最近最久未使用 } public void clock(){//簡(jiǎn)單clock ll=new LinkedList();this.need();int a=0;int[] b=new int[leng];for(int i=0;i o=all[i];if(!ll.contains(o)){ if(ll.size() o=all[i];if(!ll.contains(o)){ if(ll.size() } ll.add(o);o=ll.poll();a++;} else{ ll.add(o);ll.remove(o);o=null;} this.print();} System.out.println(“OPT的缺頁率為：”);System.out.println(a);System.out.println(“——”);System.out.println(all.length); } } else{ for(int j=0;j<=ll.size();j++){ if(b[j%ll.size()]==0){ } } } else{ int temp1=j%ll.size(); } o=ll.set(temp1, o); b[temp1]=0;//改變?cè)撐坏臉?biāo)記位 break; b[j%ll.size()]=1;a++;} else{ int temp=ll.indexOf(o);//找到該位 b[temp]=0;o=null;} this.print();System.out.println(“標(biāo)記位為：”);for(int k=0;k public void print(){ Object[] op=ll.toArray();for(int i=0;i ”);System.out.println(o);//System.out.println();System.out.print(op[i]);} } “計(jì)算機(jī)操作系統(tǒng)”課程設(shè)計(jì)大作業(yè) 一、題目: 頁面置換算法模擬實(shí)驗(yàn) 二、目的 分別采用最佳(Optimal)置換算法、先進(jìn)先出(FIFO)頁面置換算法和最近最少使用(LRU)置換算法對(duì)用戶輸入的頁面號(hào)請(qǐng)求序列進(jìn)行淘汰和置換，從而加深對(duì)頁面置換算法的理解。 三、內(nèi)容和要求 請(qǐng)用C/C++語言編一個(gè)頁面置換算法模擬程序。用戶通過鍵盤輸入分配的物理內(nèi)存總塊數(shù)，再輸入用戶邏輯頁面號(hào)請(qǐng)求序列，然后分別采用最佳(Optimal)置換算法、先進(jìn)先出(FIFO)頁面置換算法和最近最少使用(LRU)置換算法三種算法對(duì)頁面請(qǐng)求序列進(jìn)行轉(zhuǎn)換，最后按照課本P150頁圖4-26的置換圖格式輸出每次頁面請(qǐng)求后各物理塊內(nèi)存放的虛頁號(hào)，并算出每種算法的缺頁次數(shù)。最后評(píng)價(jià)三種頁面置換算法的優(yōu)缺點(diǎn)。 三種頁面置換算法的思想可參考教材P149-P152頁。 假設(shè)頁面號(hào)請(qǐng)求序列為4、3、2、1、4、3、5、4、3、2、1、5，當(dāng)分配給某進(jìn)程的物理塊數(shù)分別為3塊和4塊時(shí)，試用自己編寫的模擬程序進(jìn)行頁面轉(zhuǎn)換并輸出置換圖和缺頁次數(shù)。 四、提交內(nèi)容 本大作業(yè)每個(gè)人必須單獨(dú)完成，大作業(yè)以WORD附件形式提交。最后需提交的內(nèi)容包括：算法算法思路及流程圖、數(shù)據(jù)結(jié)構(gòu)說明、源程序（關(guān)鍵代碼需要注釋說明）、運(yùn)行結(jié)果截圖、心得體會(huì)及總結(jié)。 大作業(yè)嚴(yán)禁抄襲。發(fā)現(xiàn)抄襲一律以不及格論。 請(qǐng)大家嚴(yán)格按照大作業(yè)題目來編寫程序，不要上交以前布置的大作業(yè)。如果提交的大作業(yè)題目與本文檔要求不符，成績(jī)一律為不及格。 請(qǐng)大家按時(shí)在網(wǎng)院網(wǎng)上系統(tǒng)里提交大作業(yè)，過了規(guī)定時(shí)間將無法再補(bǔ)交大作業(yè)。 頁面置換算法模擬實(shí)驗(yàn) 算法算法思路 模擬FIFOOPTLRU這3種頁面置換算法，先分配所需的內(nèi)存空間，在根據(jù)已知的序列，分別根據(jù)不同的頁面算法去訪問已知序列，得出不同內(nèi)存空間的置換算法的缺頁數(shù)量?？傮w流程圖 開始輸入內(nèi)存數(shù)執(zhí)行頁面置換FIFOLRUOPT顯示結(jié)果結(jié)束 數(shù)據(jù)結(jié)構(gòu)說明 源程序（關(guān)鍵代碼需要注釋說明）FIFO關(guān)鍵源碼 LRU關(guān)鍵源碼 OPT關(guān)鍵源碼 程序源碼 #include int bno;//定義塊號(hào) int time;// 定義最近使用 int status;//定義命中狀態(tài) int order;//定義優(yōu)先級(jí) }; int list[12]={4,3,2,1,4,2,5,2,3,2,1,5};// 已知序列 // 輸出方法 void output(int *a ,int n){ for(int i=0;i cout<<*a<<'t'; a++;} cout<<'n';} void fifo(int *list,int mem_num){ page p[N];// 定義記錄數(shù)組 int flag;int mem[M];// 定義內(nèi)存 int index =0;// 默認(rèn)下標(biāo) int lack=0;// 初始化內(nèi)存 for(int i=0;i mem[i]=0;} // 遍歷序列 for(i=0;i flag=0;// 設(shè)置默認(rèn)命中 0 for(int j=0;j if(list[i]==mem[j]){ // 檢測(cè)序列與已知內(nèi)存值，命中返回flag flag=1; break; } } if(flag==1){ // 判斷是否命中，則對(duì) p 賦值 p[i].bno = j+1; p[i].pno = list[i]; p[i].status =1; }else{ p[i].pno = list[i]; p[i].status = 0; mem[index] = list[i]; p[i].bno = index+1;// 賦予 頁號(hào) index =(index+1)%mem_num;// 每次取余 lack++; } } cout<<“FIFO算法：n”;cout<<“---**n”;cout<<“缺頁次數(shù)：”<<'t'< cout<<“-----**n”;cout<<“序列號(hào)n”; cout<<“-----**n”;for(i=0;i cout<<“-----**n”;} for(i=mem_num;i } struct mem{ int order;//內(nèi)存優(yōu)先級(jí) 主要用于識(shí)別是否不常用 int pno;// 內(nèi)存頁號(hào) int time;// 記錄是否最近使用 }; void lru(int *list,int mem_num){ page p[N];// 定義記錄數(shù)組 int flag;mem m[M];// 定義內(nèi)存 int index =0;// 默認(rèn)下標(biāo) int lack=0;int temp;int max=0;// 內(nèi)存賦值 for(int i=0;i m[i].pno=0; //默認(rèn)初始優(yōu)先級(jí) 0 m[i].order = 0;} for(i=0;i flag=0; for(int j=0;j if(list[i]==m[j].pno){ flag=1; index=j; //m[j].order++; p[i].order =m[j].order; break; } } if(flag==1){ //命中后，p[i].bno = index+1; p[i].pno = list[i]; p[i].status = 1; p[i].order--; temp = p[i].order; for(j=0;j if(p[j].order temp=p[j].order; index = p[j].bno; } } }else{ p[i].status=0; p[i].pno = list[i]; m[index].pno = list[i]; m[index].order = p[i].order; p[i].bno = index+1; for(j=0;j if(m[j].order>max){ index = j; } } index =(index+1)%mem_num;// 每次取余有效的下標(biāo) //max++; lack++; } } cout<<“LRU算法：n”;cout<<“---**n”;cout<<“缺頁次數(shù)：”<<'t'< cout<<“-----**n”;cout<<“序列號(hào)n”; cout<<“-----**n”;for(i=0;i cout<<“-----**n”;} for(i=mem_num;i mem m[M];int flag=0;int index = 0;//下標(biāo) int max = N;int lack=0;for(int i=0;i m[i].pno=0; m[i].time = 0;//設(shè)置內(nèi)存使用頻率 } for(i=0;i flag=0; for(int j=0;j if(list[i]==m[j].pno){ flag=1; index = j; break; } } if(flag==1){ p[i].status =1; p[i].bno = index+1; p[i].pno = list[i]; for(j=0;j for(int g=i;g if(m[j].pno==list[g]){ m[j].time = N-g;//獲取到 最近使用 p[i].time = m[j].time; index = j; } } } }else{ p[i].status =0; p[i].pno = list[i]; m[index].pno = list[i]; m[index].time = N;//設(shè)置默認(rèn)不使用 p[i].bno =index+1; for(j=0;j if(m[j].time>max){ index = j; } } index =(index+1)%mem_num; lack++; } } cout<<“OPT算法：n”;cout<<“---**n”;cout<<“缺頁次數(shù)：”<<'t'< cout<<“-----**n”;cout<<“序列號(hào)n”; cout<<“-----**n”;for(i=0;i cout<<“-----**n”;} for(i=mem_num;i void main(){ int m;cout << “===========================n”;cout << “請(qǐng)輸入內(nèi)存大?。?/4）n”;cin >> m;cout << “===========================n”;opt(list,m);fifo(list,m);lru(list,m); } 運(yùn)行結(jié)果截圖 FIFO、LRU、OPT運(yùn)行截圖（開辟3個(gè)內(nèi)存空間）： FIFO、LRU、OPT運(yùn)行截圖（開辟4個(gè)內(nèi)存空間）： 心得體會(huì)及總結(jié)： 在開始做題目的時(shí)候，需要了解什么是FIOFOLRUOPT這3個(gè)頁面置換的知識(shí)點(diǎn)，同時(shí)參考了網(wǎng)絡(luò)上許多實(shí)現(xiàn)過程技巧，并在在紙上面簡(jiǎn)單畫出頁面如何記錄如何與內(nèi)存置換，這樣子比較方便寫出算法。由于這次設(shè)計(jì)的時(shí)間比較倉(cāng)促，其中不免會(huì)有些紕漏，比如在程序的實(shí)現(xiàn)上還不夠嚴(yán)謹(jǐn)，出錯(cuò)處理不夠完善等多方面問題，這些都有進(jìn)一步改善。同時(shí)，在這次編寫3個(gè)頁面算法的過程中，我學(xué)到了很多東西，無論在理論上還是實(shí)踐中，都得到不少的提高，這對(duì)以后的工作中會(huì)有一定的幫助。 《操作系統(tǒng)--頁面置換算法》 實(shí)驗(yàn)報(bào)告 姓 名： 范學(xué)升 學(xué) 號(hào)：1001050903 班 級(jí)：電科10-1班 專 業(yè)：電子信息科學(xué)與技術(shù) 一、實(shí)驗(yàn)?zāi)康?/p> 1．通過模擬實(shí)現(xiàn)幾種基本頁面置換的算法，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)。 2．掌握虛擬存儲(chǔ)請(qǐng)求頁式存儲(chǔ)管理中幾種基本頁面置換算法的基本思想，并至少用三種算法來模擬實(shí)現(xiàn)。 3．通過對(duì)幾種置換算法頁面的比較，來對(duì)比他們的優(yōu)缺點(diǎn)，并通過比較更換頻率來對(duì)比它們的效率。 二、實(shí)驗(yàn)內(nèi)容： 設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用下述算法來模擬實(shí)現(xiàn)頁面的置換： 1.先進(jìn)先出的算法（FIFO）2.最近最久未使用算法（LRU）3.最佳置換算法（OPT） 三、實(shí)驗(yàn)分析 在進(jìn)程運(yùn)行過程中，若其所訪問的頁面不存在內(nèi)存而需要把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑時(shí)，為了保證該進(jìn)程能夠正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的對(duì)換區(qū)中。但應(yīng)調(diào)出哪個(gè)頁面，需根據(jù)一定的算法來確定，算法的好壞，直接影響到系統(tǒng)的性能。 一個(gè)好的頁面置換算法，應(yīng)該有較低的頁面更換頻率。 假設(shè)分給一作業(yè)的物理塊數(shù)為3，頁面數(shù)為20個(gè)。頁面號(hào)為(20個(gè))： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 1．先進(jìn)先出(FIFO)置換算法的思路 該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面，按照先后次序連接成一個(gè)隊(duì)列，并設(shè)置一個(gè)替換指針，使它總指向最老的頁面。 2．最近久未使用(LRU)置換算法的思路 最近久未使用置換算法的替換規(guī)則，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況來進(jìn)行決策的。該算法賦予每個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間，當(dāng)需淘汰一個(gè)頁面的時(shí)候選擇現(xiàn)有頁面中其時(shí)間值最大的進(jìn) 行淘汰。 3.最佳（OPT）置換算法的思路 其所選擇的被淘汰的頁面，獎(jiǎng)是以后不使用的，或者是在未來時(shí)間內(nèi)不再被訪問的頁面，采用最佳算法，通?？杀ＷC獲得最低的缺頁率。 4．?dāng)?shù)據(jù)結(jié)構(gòu) struct pageInfor { int content;//頁面號(hào) int timer;//被訪問標(biāo)記 }; class PRA { public: PRA(void);int findSpace(void);//查找是否有空閑內(nèi)存 int findExist(int curpage);//查找內(nèi)存中是否有該頁面 int findReplace(void);//查找應(yīng)予置換的頁面 void display(void);//顯示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法 void BlockClear(void);//BLOCK清空，以便用另一種方法重新演示 pageInfor * block;//物理塊 pageInfor * page;//頁面號(hào)串 private: }; 5．FIFO頁面置換算法 當(dāng)需要訪問一個(gè)新的頁面時(shí)，首先調(diào)用findExist(i)函數(shù)來查看物理塊中是否就有這個(gè)頁面，若要查看的頁面物理塊中就有，則調(diào)用display函數(shù)直接顯示，不需要替換頁面；如果要查看的頁面物理塊中沒有，就需要尋找空閑物理塊放入，若存在有空閑物理塊，則將頁面放入；若沒有空閑物理塊，則調(diào)用findReplace函數(shù)替換頁面。并將物理塊中所有頁面timer++。 6．LRU頁面置換算法 當(dāng)需要訪問一個(gè)新的頁面，首先調(diào)用findExist(i)函數(shù)查看物理塊中是否就有這個(gè)頁面。 7.OPT頁面置換算法 當(dāng)需要訪問一個(gè)新的頁面，首先調(diào)用findExist(i)函數(shù)來查看物理塊中是否有這個(gè)頁面。 8．尋找置換頁面函數(shù)findReplace比較三個(gè)物理塊中的時(shí)間標(biāo)記timer，找到時(shí)間最久的。 四、源程序結(jié)構(gòu)分析 1． 程序結(jié)構(gòu) 程序共有以下九個(gè)部分： int findSpace(void);//查找是否有空閑內(nèi)存 int findExist(int curpage);//查找內(nèi)存中是否有該頁面 int findReplace(void);//查找應(yīng)予置換的頁面 void display(void);//顯示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法 void OPT(void);//OPT算法； void BlockClear(void);//BLOCK清空，以便用另一種方法重新演示 int main() //主程序 五、實(shí)驗(yàn)結(jié)果 1運(yùn)行后的初始界面 opt算法 3.FIFO算法 4LRU算法 計(jì)算機(jī)工程學(xué)院 實(shí)驗(yàn)報(bào)告書 課程名：《 操作系統(tǒng)原理A 》 題 目： 虛擬存儲(chǔ)器管理 頁面置換算法模擬實(shí)驗(yàn) 班 級(jí)： 學(xué) 號(hào)： 姓 名： 評(píng)語： 成績(jī)： 指導(dǎo)教師： 批閱時(shí)間： ****年**月**日 一、實(shí)驗(yàn)?zāi)康呐c要求 1.目的： 請(qǐng)求頁式虛存管理是常用的虛擬存儲(chǔ)管理方案之一。通過請(qǐng)求頁式虛存管理中對(duì)頁面置換算法的模擬，有助于理解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，并加深對(duì)請(qǐng)求頁式虛存管理的頁面調(diào)度算法的理解。 2.要求： 本實(shí)驗(yàn)要求使用C語言編程模擬一個(gè)擁有若干個(gè)虛頁的進(jìn)程在給定的若干個(gè)實(shí)頁中運(yùn)行、并在缺頁中斷發(fā)生時(shí)分別使用FIFO和LRU算法進(jìn)行頁面置換的情形。其中虛頁的個(gè)數(shù)可以事先給定（例如10個(gè)），對(duì)這些虛頁訪問的頁地址流（其長(zhǎng)度可以事先給定，例如20次虛頁訪問）可以由程序隨機(jī)產(chǎn)生，也可以事先保存在文件中。要求程序運(yùn)行時(shí)屏幕能顯示出置換過程中的狀態(tài)信息并輸出訪問結(jié)束時(shí)的頁面命中率。程序應(yīng)允許通過為該進(jìn)程分配不同的實(shí)頁數(shù)，來比較兩種置換算法的穩(wěn)定性。 二、實(shí)驗(yàn)說明 1．設(shè)計(jì)中虛頁和實(shí)頁的表示 本設(shè)計(jì)利用C語言的結(jié)構(gòu)體來描述虛頁和實(shí)頁的結(jié)構(gòu)。 pn pfn time pn pfn next 虛頁結(jié)構(gòu) 實(shí)頁結(jié)構(gòu) 在虛頁結(jié)構(gòu)中，pn代表虛頁號(hào)，因?yàn)楣?0個(gè)虛頁，所以pn的取值范圍是0—9。pfn代表實(shí)頁號(hào)，當(dāng)一虛頁未裝入實(shí)頁時(shí)，此項(xiàng)值為-1；當(dāng)該虛頁已裝入某一實(shí)頁時(shí)，此項(xiàng)值為所裝入的實(shí)頁的實(shí)頁號(hào)pfn。time項(xiàng)在FIFO算法中不使用，在LRU中用來存放對(duì)該虛頁的最近訪問時(shí)間。 在實(shí)頁結(jié)構(gòu)中中，pn代表虛頁號(hào)，表示pn所代表的虛頁目前正放在此實(shí)頁中。pfn代表實(shí)頁號(hào)，取值范圍（0—n-1）由動(dòng)態(tài)指派的實(shí)頁數(shù)n所決定。next是一個(gè)指向?qū)嶍摻Y(jié)構(gòu)體的指針，用于多個(gè)實(shí)頁以鏈表形式組織起來，關(guān)于實(shí)頁鏈表的組織詳見下面第4點(diǎn)。 2．關(guān)于缺頁次數(shù)的統(tǒng)計(jì) 為計(jì)算命中率，需要統(tǒng)計(jì)在20次的虛頁訪問中命中的次數(shù)。為此，程序應(yīng)設(shè)置一個(gè)計(jì)數(shù)器count，來統(tǒng)計(jì)虛頁命中發(fā)生的次數(shù)。每當(dāng)所訪問的虛頁的pfn項(xiàng)值不為-1，表示此虛頁已被裝入某實(shí)頁內(nèi)，此虛頁被命中，count加1。最終命中率=count/20*100%。 3．LRU算法中“最近最久未用”頁面的確定 為了能找到“最近最久未用”的虛頁面，程序中可引入一個(gè)時(shí)間計(jì)數(shù)器countime，每當(dāng)要訪問一個(gè)虛頁面時(shí)，countime的值加1，然后將所要訪問的虛頁的time項(xiàng)值設(shè)置為增值后的當(dāng)前countime值，表示該虛頁的最后一次被訪問時(shí)間。當(dāng)LRU算法需要置換時(shí)，從所有已分配實(shí)頁的虛頁中找出time值為最小的虛頁就是“最近最久未用”的虛頁面，應(yīng)該將它置換出去。 4．算法中實(shí)頁的組織 因?yàn)槟芊峙涞膶?shí)頁數(shù)n是在程序運(yùn)行時(shí)由用戶動(dòng)態(tài)指派的，所以應(yīng)使用鏈表組織動(dòng)態(tài)產(chǎn)生的多個(gè)實(shí)頁。為了調(diào)度算法實(shí)現(xiàn)的方便，可以考慮引入free和busy兩個(gè)鏈表：free鏈表用于組織未分配出去的實(shí)頁，首指針為free_head，初始時(shí)n個(gè)實(shí)頁都處于free鏈表中；busy鏈表用于組織已分配出去的實(shí)頁，首指針為busy_head，尾指針為busy_tail，初始值都為null。當(dāng)所要訪問的一個(gè)虛頁不在實(shí)頁中時(shí)，將產(chǎn)生缺頁中斷。此時(shí)若free鏈表不為空，就取下鏈表首指針?biāo)傅膶?shí)頁，并分配給該虛頁。若free鏈表為空，則說明n個(gè)實(shí)頁已全部分配出去，此時(shí)應(yīng)進(jìn)行頁面置換：對(duì)于FIFO算法要將busy_head 所指的實(shí)頁從busy鏈表中取下，分配給該虛頁，然后再將該實(shí)頁插入到busy鏈表尾部；對(duì)于LRU算法則要從所有已分配實(shí)頁的虛頁中找出time值為最小的虛頁，將該虛頁從裝載它的那個(gè)實(shí)頁中置換出去，并在該實(shí)頁中裝入當(dāng)前正要訪問的虛頁。 三、程序流程圖 四、主要程序清單 #include #include /*全局變量*/ int mSIZE; /*物理塊數(shù)*/ int pSIZE; /*頁面號(hào)引用串個(gè)數(shù)*/ static int memery[10]={0}; /*物理塊中的頁號(hào)*/ static int page[100]={0}; /*頁面號(hào)引用串*/ static int temp[100][10]={0}; /*輔助數(shù)組*/ /*置換算法函數(shù)*/ void FIFO(); void LRU(); void OPT(); /*輔助函數(shù)*/ void print(unsigned int t); void designBy(); void download(); void mDelay(unsigned int Delay); /*主函數(shù)*/ void main() { int i,k,code; printf(“請(qǐng)輸入物理塊的個(gè)數(shù)(M<=10)：“); scanf(“%d“,&mSIZE); printf(“請(qǐng)輸入頁面號(hào)引用串的個(gè)數(shù)(P<=100)：“); scanf(“%d“,&pSIZE); puts(“請(qǐng)依次輸入頁面號(hào)引用串(連續(xù)輸入，無需隔開)：“); for(i=0;i scanf(“%1d“,&page[i]); download(); do { puts(“輸入的頁面號(hào)引用串為：“); for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } } printf(“* * * * * * * * * * * * * * * * * * * * * * *＼n“); printf(“* 請(qǐng)選擇頁面置換算法：＼t＼t＼t *＼n“); printf(“* -----------------------------------------*＼n“); printf(“* 1.先進(jìn)先出(FIFO) 2.最近最久未使用(LRU) *＼n“); printf(“* 3.退出 *＼n“); printf(“* * * * * * * * * * * * * * * * * * * * * * *＼n“); printf(“請(qǐng)選擇操作：[ ]＼b＼b“); scanf(“%d“,&code); switch(code) { case 1: FIFO(); break; case 2: LRU(); break; case 3: OPT(); break; case 4: system(“cls“); //system(“color 0A“); exit(0); default: printf(“輸入錯(cuò)誤，請(qǐng)重新輸入：“); } printf(“按任意鍵重新選擇置換算法：>>>“); getchar(); } while (code!=4); getchar(); } /*載入數(shù)據(jù)*/ void download() { printf(“＼nFinish.＼n載入成功!“); } /*設(shè)置延遲*/ void mDelay(unsigned int Delay) { unsigned int i; for(;Delay>0;Delay--) { for(i=0;i<124;i++) { printf(“ ＼b“); } } } /*顯示設(shè)計(jì)者信息*/ void print(unsigned int t) { int i,j,k,l; int flag; for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf(“%d＼n“,page[i]); else printf(“%d “,page[i]); } for(j=0;j { for(i=20*k;(i if(i>=j) printf(“ |%d|“,temp[i][j]); else printf(“ | |“); } for(i=mSIZE+20*k;(i { for(flag=0,l=0;l if(temp[i][l]==temp[i-1][l]) flag++; if(flag==mSIZE)/*頁面在物理塊中*/ printf(“ “); else printf(“ |%d|“,temp[i][j]); } /*每行顯示20個(gè)*/ if(i%20==0) continue; printf(“＼n“); } } printf(“----------------------------------------＼n“); printf(“缺頁次數(shù)：%d＼t＼t“,t+mSIZE); printf(“缺頁率：%d/%d＼n“,t+mSIZE,pSIZE); printf(“置換次數(shù)：%d＼t＼t“,t); printf(“訪問命中率：%d%%＼n“,(pSIZE-(t+mSIZE))*100/pSIZE); printf(“----------------------------------------＼n“); } /*計(jì)算過程延遲*/ void compute() { int i; printf(“正在進(jìn)行相關(guān)計(jì)算，請(qǐng)稍候“); for(i=0;i++<30;printf(“＼b“)); for(i=0;i++<30;printf(“ “)); for(i=0;i++<30;printf(“＼b“)); } /*先進(jìn)先出頁面置換算法*/ void FIFO() { int memery[10]={0}; int time[10]={0}; /*記錄進(jìn)入物理塊的時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/ /*前mSIZE個(gè)數(shù)直接放入*/ for(i=0;i { memery[i]=page[i]; time[i]=i; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判斷新頁面號(hào)是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*計(jì)算換出頁*/ max=time[0] for(m=2;m if(time[m] max=m; memery[max]=page[i]; time[max]=i; /*記錄該頁進(jìn)入物理塊的時(shí)間*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } compute(); print(count); } /*最近最久未使用置換算法*/ void LRU() { int memery[10]={0}; int flag[10]={0}; /*記錄頁面的訪問時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/ /*前mSIZE個(gè)數(shù)直接放入*/ for(i=0;i { memery[i]=page[i]; flag[i]=i; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判斷新頁面號(hào)是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; else flag[j]=i; /*刷新該頁的訪問時(shí)間*/ } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*計(jì)算換出頁*/ max=flag[0] for(m=2;m if(flag[m] max=m; memery[max]=page[i]; flag[max]=i; /*記錄該頁的訪問時(shí)間*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } compute(); print(count); } /*最佳置換算法*/ void OPT() { int memery[10]={0}; int next[10]={0}; /*記錄下一次訪問時(shí)間*/ int i,j,k,l,m; int max; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/ /*前mSIZE個(gè)數(shù)直接放入*/ for(i=0;i { memery[i]=page[i]; for(j=0;j temp[i][j]=memery[j]; } for(i=mSIZE;i { /*判斷新頁面號(hào)是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*得到物理快中各頁下一次訪問時(shí)間*/ for(m=0;m { for(l=i+1;l if(memery[m]==page[l]) break; next[m]=l; } /*計(jì)算換出頁*/ max=next[0]>=next[1]?0:1; for(m=2;m if(next[m]>next[max]) max=m; /*下一次訪問時(shí)間都為pSIZE,則置換物理塊中第一個(gè)*/ memery[max]=page[i]; for(j=0;j temp[i][j]=memery[j]; } } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*得到物理快中各頁下一次訪問時(shí)間*/ for(m=0;m { for(l=i+1;l if(memery[m]==page[l]) break; next[m]=l; } /*計(jì)算換出頁*/ max=next[0]>=next[1]?0:1; for(m=2;m if(next[m]>next[max]) max=m; /*下一次訪問時(shí)間都為pSIZE,則置換物理塊中第一個(gè)*/ memery[max]=page[i]; for(j=0;j temp[i][j]=memery[j]; } } 五、程序運(yùn)行結(jié)果 ①FIFO ②LRU 六、實(shí)驗(yàn)體會(huì) 在做該次作業(yè)的時(shí)候，通過對(duì)課本相關(guān)內(nèi)容的溫習(xí)，以及對(duì)自己在網(wǎng)絡(luò)上找到的一些資源的了解。我對(duì)操作系統(tǒng)中頁面調(diào)度的算法有了很大程度的了解，加深了對(duì)課程上知識(shí)的理解，也懂得了如何在程序中將這些算法實(shí)現(xiàn)，在程序中基本上實(shí)現(xiàn)了所要求的算法以及相關(guān)的性能分析，基本上實(shí)現(xiàn)了課程的要求。 這次作業(yè)也暴露了自己在某些方面的不足之處，自己的語言功底有一定的不足，以及一開始對(duì)某個(gè)算法不夠熟悉，將算法實(shí)現(xiàn)設(shè)計(jì)的比較復(fù)雜，此次自己的程序存在一些思想上的漏洞，反映出此次程序設(shè)計(jì)的要求有了一定的限制。第三篇：頁面置換算法模擬
第四篇：頁面置換算法實(shí)驗(yàn)報(bào)告（精選）
第五篇：計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)三頁面置換算法模擬實(shí)驗(yàn)
點(diǎn)擊咨詢 