第一篇：頁(yè)面置換算法模擬實(shí)驗(yàn) 操作系統(tǒng)大作業(yè)(含源文件)
“計(jì)算機(jī)操作系統(tǒng)”課程設(shè)計(jì)大作業(yè)
頁(yè)面置換算法模擬實(shí)驗(yàn)(含完整資料，可直接提交)
一、題目: 頁(yè)面置換算法模擬實(shí)驗(yàn)
二、目的
分別采用最佳(Optimal)置換算法、先進(jìn)先出(FIFO)頁(yè)面置換算法和最近最少使用(LRU)置換算法對(duì)用戶輸入的頁(yè)面號(hào)請(qǐng)求序列進(jìn)行淘汰和置換，從而加深對(duì)頁(yè)面置換算法的理解。
三、內(nèi)容和要求
請(qǐng)用C/C++語(yǔ)言編一個(gè)頁(yè)面置換算法模擬程序。用戶通過鍵盤輸入分配的物理內(nèi)存總塊數(shù)，再輸入用戶邏輯頁(yè)面號(hào)請(qǐng)求序列，然后分別采用最佳(Optimal)置換算法、先進(jìn)先出(FIFO)頁(yè)面置換算法和最近最少使用(LRU)置換算法三種算法對(duì)頁(yè)面請(qǐng)求序列進(jìn)行轉(zhuǎn)換，最后按照課本P150頁(yè)圖4-26的置換圖格式輸出每次頁(yè)面請(qǐng)求后各物理塊內(nèi)存放的虛頁(yè)號(hào)，并算出總的缺頁(yè)率（缺頁(yè)次數(shù)/總的請(qǐng)求次數(shù)）。最后三種頁(yè)面置換算法的優(yōu)缺點(diǎn)。
三種頁(yè)面置換算法的思想可參考教材P149-P152頁(yè)。
假設(shè)頁(yè)面號(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)行頁(yè)面轉(zhuǎn)換并輸出置換圖和缺頁(yè)次數(shù)、缺頁(yè)率。
四、提交內(nèi)容
0 本大作業(yè)每個(gè)人必須單獨(dú)完成。最后需提交的內(nèi)容包括：源程序（關(guān)鍵代碼需要注釋說明）、可運(yùn)行程序、運(yùn)行結(jié)果、算法思路及流程圖、心得體會(huì)。
大作業(yè)嚴(yán)禁抄襲。發(fā)現(xiàn)抄襲一律以不及格論。
請(qǐng)大家嚴(yán)格按照大作業(yè)題目來編寫程序，不要上交以前布置的大作業(yè)。如果提交的大作業(yè)題目與本文檔要求不符，成績(jī)一律為及格。
目錄
摘要.............................................................................................................2 正文.............................................................................................................2
1、設(shè)計(jì)思路..............................................................................................................3
2、各模塊的偽碼算法..............................................................................................6
3、函數(shù)的調(diào)用關(guān)系圖..............................................................................................8
4、測(cè)試....................................................................................................................13 設(shè)計(jì)總結(jié)..................................................................................................15 參考文獻(xiàn)..................................................................................................16 致 謝.......................................................................................................17 附錄：部分源程序代碼..........................................................................18
摘
要
UNIX中，為了提高內(nèi)存利用率，提供了內(nèi)外存進(jìn)程對(duì)換機(jī)制；內(nèi)存空間的分配和回收均以頁(yè)為單位進(jìn)行；一個(gè)進(jìn)程只需將其一部分（段或頁(yè)）調(diào)入內(nèi)存便可運(yùn)行；還支持請(qǐng)求調(diào)頁(yè)的存儲(chǔ)管理方式。當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)，發(fā)現(xiàn)其所在頁(yè)面不在內(nèi)存，就立即提出請(qǐng)求（向CPU發(fā)出缺頁(yè)中斷），由系統(tǒng)將其所需頁(yè)面調(diào)入內(nèi)存。這種頁(yè)面調(diào)入方式叫請(qǐng)求調(diào)頁(yè)，為實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)，核心配置了四種數(shù)據(jù)結(jié)構(gòu)：頁(yè)表、頁(yè)框號(hào)、訪問位、修改位、有效位、保護(hù)位等。此設(shè)計(jì)為了了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，練習(xí)并掌握UNIX提供的vi編輯器來編譯C程序，學(xué)會(huì)利用gcc、gdb編譯、調(diào)試C程序，學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問題，培養(yǎng)學(xué)生的能力。
關(guān)鍵字
UNIX
請(qǐng)求調(diào)頁(yè)
數(shù)據(jù)結(jié)構(gòu)
存儲(chǔ)管理
編輯器
調(diào)試
C程序
正
文
一、設(shè)計(jì)思路
頁(yè)面置換算法：當(dāng)CPU接收到缺頁(yè)中斷信號(hào)，中斷處理程序先保存現(xiàn)場(chǎng)，分析中斷原因，轉(zhuǎn)入缺頁(yè)中斷處理程序。該程序通過查找頁(yè)表，得到該頁(yè)所在外存的物理塊號(hào)。如果此時(shí)內(nèi)存未滿，能容納新頁(yè)，則啟動(dòng)磁盤I/O將所缺之頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。如果內(nèi)存已滿，則須按某種置換算法從內(nèi)存中選出一頁(yè)準(zhǔn)備換出，是否重新寫盤由頁(yè)表的修改位決定，然后將缺頁(yè)調(diào)入，修改頁(yè)表。利用修改后的頁(yè)表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個(gè)頁(yè)面的調(diào)入過程對(duì)用戶是透明的。此設(shè)計(jì)為了了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，練習(xí)并掌握UNIX提供的vi編輯器來編譯C程序，學(xué)會(huì)利用gcc、gdb編譯、調(diào)試C程序，學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問題，培養(yǎng)學(xué)生的動(dòng)手能力。
二、設(shè)計(jì)目的
1、用C語(yǔ)言實(shí)現(xiàn)頁(yè)面置換算法。
2、了解內(nèi)存分頁(yè)管理策略
3、掌握調(diào)頁(yè)策略
4、掌握一般常用的調(diào)度算法
5．選取調(diào)度算法中的典型算法，模擬實(shí)現(xiàn)。
三、設(shè)計(jì)任務(wù)
在Window98/2000 系統(tǒng)的TC2.0環(huán)境下運(yùn)行程序；通過從一般常用的調(diào)頁(yè)算法中選取典型算法程序，了解頁(yè)面管理的相關(guān)細(xì)節(jié)，并用程序設(shè)計(jì)實(shí)現(xiàn)該算法實(shí)驗(yàn)。
四、設(shè)計(jì)內(nèi)容與步驟
分頁(yè)存儲(chǔ)管理將一個(gè)進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁(yè)面或頁(yè)。
五、調(diào)頁(yè)策略
1)何時(shí)調(diào)入頁(yè)面
如果進(jìn)程的許多頁(yè)是存放在外存的一個(gè)連續(xù)區(qū)域中，則一次調(diào)入若干個(gè)相鄰的頁(yè)，會(huì)比一次調(diào)入一頁(yè)的效率更高效一些。但如果調(diào)入的一批頁(yè)面中的大多數(shù)都未被訪問，則又是低效的?？刹捎靡环N以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁(yè)策略，將那些預(yù)計(jì)在不久之后便會(huì)被訪問的頁(yè)面，預(yù)先調(diào)入內(nèi)存。如果預(yù)測(cè)較準(zhǔn)確，那么，這 種策略顯然是很有吸引力的。但目前預(yù)調(diào)頁(yè)的成功率僅為50%。且這種策略主要用于進(jìn)程的首次調(diào)入時(shí)，由程序員指出應(yīng)該先調(diào)入哪些頁(yè)。
2)請(qǐng)求調(diào)頁(yè)策略
當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁(yè)面不在內(nèi)存，便即提出請(qǐng)求，由OS將其所需頁(yè)面調(diào)入內(nèi)存。由請(qǐng)示調(diào)頁(yè)策略所確定調(diào)入的頁(yè)，是一定會(huì)被訪問的，再加之請(qǐng)求調(diào)頁(yè)策略比較易于實(shí)現(xiàn)，故在目前的虛擬存儲(chǔ)器中，大多采用此策略。但這種策略每次僅調(diào)入一頁(yè)，故須花費(fèi)較大的系統(tǒng)開銷，增加了磁盤I/O的啟用頻率。
3）從何處調(diào)入頁(yè)面
在請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對(duì)換頁(yè)面的對(duì)換區(qū)。通常，由于對(duì)換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對(duì)換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存，可分成如下三種情況：
(1)系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入 所需頁(yè)面，以提高調(diào)頁(yè)速度。為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對(duì)換區(qū)。
(2)系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁(yè)面時(shí)，由于它們未被修改而不必再將它們換出時(shí)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入。
(3)UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁(yè)面，都從文件區(qū)調(diào)入。而對(duì)于曾經(jīng)運(yùn)行過但又被換出的頁(yè)面，由于被放在對(duì)換區(qū)，因此在下次時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁(yè)面共享，因此，某進(jìn)程所請(qǐng)求的頁(yè)面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無須再?gòu)膶?duì)換區(qū)調(diào)入。
3頁(yè)面調(diào)入過程
每當(dāng)程序所要訪問的頁(yè)面未在內(nèi)存時(shí)，便向CPU發(fā)出一缺頁(yè)中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁(yè)中斷處理程序。該程序通過查找頁(yè)表，得到該頁(yè)在外在原物理 塊后，如果此時(shí)內(nèi)存能容納新頁(yè)，則啟動(dòng)磁盤I/O將所缺之頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁(yè)準(zhǔn)備換出；如果該頁(yè)未被修改過，可不必將該頁(yè)寫回磁盤；但如果此頁(yè)已被修改，則必須將它寫回磁盤，然后再把所缺的頁(yè)調(diào)入內(nèi)存，并修改頁(yè)表中的相應(yīng)表項(xiàng)，置其存在位“1”，并將此頁(yè)表項(xiàng)寫入快表中。在缺頁(yè)調(diào)入內(nèi)存后，利用修改后的頁(yè)表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個(gè)頁(yè)面的調(diào)入過程對(duì)用戶是透明的。
六、頁(yè)面置換算法
在進(jìn)程運(yùn)行過程中，若其所要訪問的頁(yè)面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送磁盤的對(duì)換區(qū)中。但應(yīng)將哪 個(gè)頁(yè)面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁(yè)面的算法稱為頁(yè)面置換算法(Page_Replacement Algorithms)。
一個(gè)好的頁(yè)面置換算法，應(yīng)具有較低的頁(yè)面更換頻率。從理論上講，應(yīng)將那些以后不再會(huì)訪問的頁(yè)面換出，或?qū)⒛切┰谳^長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問的頁(yè)面調(diào)出。
㈠常見置換算法
① 最佳置換算法(Optimal)：
它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的或許是在最長(zhǎng)(未來)時(shí)間內(nèi)不再被訪問的頁(yè)面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。但由于人目前還無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來最長(zhǎng)時(shí)間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，便可以利用此算法來評(píng)價(jià)其它算法。
② 先進(jìn)先出(FIFO)頁(yè)面置換算法：
這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁(yè)面。
③ LRU置換算法：
LRU(Least Recently Used)置換算法的描述
FIFO置換算法性能之所以較差，是因?yàn)樗罁?jù)的條件是各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間，而頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情況。最近最久未使用（LRU）置換算法，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無法預(yù)測(cè)各頁(yè)面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問字段，用來記錄一個(gè)頁(yè)面自上次被訪問以來所經(jīng)歷的時(shí)間t,，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大的，即最近最久未使用的頁(yè)面予以淘汰。
七、各模塊的偽碼算法
（1）先進(jìn)先出算法偽碼算法
void fifo()//先進(jìn)先出算法 { int i=2,m,j;queye=1;a[1][0]=a[0][0];for(j=1;j<20;j++){
if(i>3)i=1;
if(find(j)=='F')//調(diào)用查找函數(shù)
{
a[i][j]=a[0][j];
for(m=1;m<4;m++)
{
if(m!=i)a[m][j]=a[m][j-1];}
queye=queye+1;
i=i+1;
}
else
{
a[1][j]=a[1][j-1];
a[2][j]=a[2][j-1];
a[3][j]=a[3][j-1];
return('F');}（2）OPT置換算法偽碼算法
void opt()//OPT置換算法 { int i,j,m,t;a[1][0]=a[0][0];for(j=1;j<3;j++){
for(i=1;i { if((i-j)==1) a[i][j]=a[0][j]; else a[i][j]=a[i][j-1]; } } int findo(int j)//查找OPT的函數(shù) { if(a[1][j-1]==a[0][m])x=m; if(a[2][j-1]==a[0][m])y=m; if(a[3][j-1]==a[0][m])z=m;} //max=x;t=1;if(y>x && y>z)t=2;if(z>x && z>y)t=3;return(t);}（3）LRu置換算法偽碼算法 void lru()//LRu置換算法 { int u,j,i;int k;a[1][0]=a[0][0];//a[1][1]=a[0][0];for(j=1;j<3;j++){ for(i=1;i { if((i-j)==1) a[i][j]=a[0][j]; else a[i][j]=a[i][j-1]; } } queye=3;for(j=3;j<20;j++){ if(find(j)=='T')//調(diào)用查找函數(shù) { } a[3][j]=a[0][j]; int l(int j)//查找要替換的位置 { if(a[0][j]==a[1][j-1])return(1);if(a[0][j]==a[2][j-1])return(2);if(a[0][j]==a[3][j-1])return(3);} 3、函數(shù)的調(diào)用關(guān)系圖 Void fifo()函數(shù)流程圖： Char find()函數(shù)流程圖： Void opt()流程圖： int findo()流程圖： Void lru()流程圖： Int l()流程圖： 4、測(cè)試 請(qǐng)求頁(yè)式存儲(chǔ)管理中常用頁(yè)面置換算法運(yùn)行結(jié)果 設(shè)計(jì)總結(jié) 經(jīng)過本次課程設(shè)計(jì)，完成題目“常用頁(yè)面置換算法原理模擬實(shí)驗(yàn)”，熟悉了UNIX/LINUX的常用基本命令，理解并掌握了UNIX提供的vi編輯器來編譯C程序，學(xué)會(huì)利用gcc、gdb編譯、調(diào)試C程序。 做課程設(shè)計(jì)是為了對(duì)平時(shí)學(xué)習(xí)的理論知識(shí)與實(shí)際操作相結(jié)合，在理論和實(shí)踐上進(jìn)一步鞏固已學(xué)基本理論及應(yīng)用知識(shí)并加以綜合提高，學(xué)會(huì)將知識(shí)應(yīng)用于實(shí)際的方法，提高分析和解決問題的能力。在做課程設(shè)計(jì)的過程中，深深感覺到自身所學(xué)知識(shí)的有限。有些題目書本上沒有提及，所以就沒有去研究過，做的時(shí)候突然間覺得自己真的有點(diǎn)無知，雖然現(xiàn)在去看依然可以解決問題，但還是浪費(fèi)了許多，這一點(diǎn)是必須在以后的學(xué)習(xí)中加以改進(jìn)的地方，同時(shí)也要督促自己在學(xué)習(xí)的過程中不斷的完善自我。在設(shè)計(jì)過程中的思考和討論，對(duì)現(xiàn)有知識(shí)能夠運(yùn)用計(jì)算機(jī)來解決現(xiàn)實(shí)生活中的實(shí)際問題確立了信心，對(duì)模塊化程序設(shè)計(jì)思想有了比較清晰的印象，為今后的程序設(shè)計(jì)奠定了一定的心理和技術(shù)上的準(zhǔn)備。 這次課程設(shè)計(jì)加強(qiáng)了我對(duì)計(jì)算機(jī)操作系統(tǒng)的認(rèn)識(shí)，對(duì)我個(gè)人而言是對(duì)所學(xué)課程內(nèi)容掌握情況的一次自我驗(yàn)證。通過課程設(shè)計(jì)提高了我對(duì)所學(xué)知識(shí)的綜合應(yīng)用能力，全面檢查并掌握所學(xué)的內(nèi)容，培養(yǎng)獨(dú)立思考，在分析問題、解決問題的過程中，更是獲得一種成功的喜悅。 參考文獻(xiàn) 1.湯子瀛，哲鳳屏.《計(jì)算機(jī)操作系統(tǒng)》.西安電子科技大學(xué)學(xué)出版社.2.王清，李光明，《計(jì)算機(jī)操作系統(tǒng)》.冶金工業(yè)出版社.3.孫鐘秀等，操作系統(tǒng)教程.高等教育出版社 4.曾明，Linux操作系統(tǒng)應(yīng)用教程.陜西科學(xué)技術(shù)出版社.5.張麗芬，劉利雄.《操作系統(tǒng)實(shí)驗(yàn)教程》.清華大學(xué)出版社.6.孟靜，操作系統(tǒng)教程－－原理和實(shí)例分析.高等教育出版社 7.周長(zhǎng)林，計(jì)算機(jī)操作系統(tǒng)教程.高等教育出版社 8.張堯?qū)W，計(jì)算機(jī)操作系統(tǒng)教程，清華大學(xué)出版社 9.任滿杰，操作系統(tǒng)原理實(shí)用教程，電子工業(yè)出版社 致 謝 這次課程設(shè)計(jì)，我從“紙上談兵”到可以自己動(dòng)腦動(dòng)手分析調(diào)試程序，收獲不少。 首先要感謝有了這次實(shí)踐的機(jī)會(huì)，給了自己一個(gè)舞臺(tái)，同時(shí)也是對(duì)自身的檢驗(yàn)。還有多虧了老師們從理論到上機(jī)親自指導(dǎo)的辛苦教授，給予了我們最大幫助和全面指導(dǎo)，在這里，尤其感謝我的指導(dǎo)老師***老師、以及我的《操作系統(tǒng)》的授課老師***老師，你們不辭辛苦，在給很多學(xué)生指導(dǎo)的情況下還不厭其煩的給我們心指導(dǎo)，在這里，我衷心向你們致謝！最后還要感謝熱心的同學(xué)們，在我陷入誤區(qū)的時(shí)候，是他們熱心的幫助使我擺脫困境。 最后衷心感謝所有給予我?guī)椭椭笇?dǎo)的老師和同學(xué),沒有他們的幫助我的程序也不會(huì)完成得這么順利。 附錄：部分源程序代碼 #include “stdio.h” char find(int j);int findo(int j);int l(int j);int queye;double queyelu;char z='%';char a[4][20]={'7','0','1','2','0','3','0','4','2','3','0','3','2','1','2','0','1','7','0','1'};//char a[][]; void fifo()//先進(jìn)先出算法 { int i=2,m,j;queye=1;a[1][0]=a[0][0];for(j=1;j<20;j++){ if(i>3)i=1; if(find(j)=='F')//調(diào)用查找函數(shù) { a[i][j]=a[0][j]; for(m=1;m<4;m++) { if(m!=i)a[m][j]=a[m][j-1];} queye=queye+1; i=i+1; } else { a[1][j]=a[1][j-1]; a[2][j]=a[2][j-1]; a[3][j]=a[3][j-1]; } } for(i=0;i<4;i++)//輸出序列 { for(j=0;j<20;j++)。。。。。。。。。。。。。。。。。。。省略 操作系統(tǒng)課程第七次實(shí)驗(yàn)報(bào)告 姓名 學(xué)號(hào) 系 計(jì)算機(jī) 任課教師 指導(dǎo)教師 評(píng)閱教師 實(shí)驗(yàn)地點(diǎn) 綜合樓B102 實(shí)驗(yàn)時(shí)間 2012-9-26 實(shí)驗(yàn)課表現(xiàn) 出勤和個(gè)人表現(xiàn)Q1(15+15（組長(zhǎng)評(píng)分）=30分) 得分： 實(shí)驗(yàn) 總分 (Q1+Q2+Q3+Q4) 實(shí)驗(yàn)完成情況Q2(45分(組長(zhǎng)與教師評(píng)分的加權(quán)平均)) 得分： 實(shí)驗(yàn)編號(hào)與實(shí)驗(yàn)名稱： 實(shí)驗(yàn)七、常用頁(yè)面置換算法模擬實(shí)驗(yàn) 實(shí)驗(yàn)?zāi)康模?/p> 通過模擬實(shí)現(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理的幾種基本頁(yè)面置換算法，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握虛擬存儲(chǔ)請(qǐng)求頁(yè)式存儲(chǔ)管理中幾種基本頁(yè)面置換算法的基本思想和實(shí)現(xiàn)過程，并比較它們的效率。 實(shí)驗(yàn)內(nèi)容及要求（詳見實(shí)驗(yàn)講義與實(shí)驗(yàn)指導(dǎo)書）： 要求： 1）要求用你熟悉的程序設(shè)計(jì)語(yǔ)言編寫和調(diào)試一個(gè)頁(yè)面置換模擬程序；要求在主函數(shù)中測(cè)試。 2）實(shí)驗(yàn)報(bào)告中必須包括：設(shè)計(jì)思想、數(shù)據(jù)定義（包括詳細(xì)說明）、處理流程（詳細(xì)算法描述和算法流程圖）、源代碼、運(yùn)行結(jié)果、體會(huì)等部分。 3）必須模擬本實(shí)驗(yàn)內(nèi)容中提到的算法中的至少2種頁(yè)面置換算法。 4） 比較不同頁(yè)面置換算法的效率 內(nèi)容：編寫一個(gè)程序，使用以下頁(yè)面置換算法中的某2種分別模擬一個(gè)分頁(yè)系統(tǒng)，并統(tǒng)計(jì)同一個(gè)頁(yè)面訪問序列情況下不同頁(yè)面置換算法引發(fā)的缺頁(yè)中斷次數(shù)。 1、第二次機(jī)會(huì)算法（Second Chance） 2、最近最少使用算法（Least Recently Used，LRU） 3、最不常用算法（Not Frequently Used，NFU） 4、最近未使用算法（Not Recently Used，NRU） 5、時(shí)鐘頁(yè)面置換算法 6、老化算法（aging） 頁(yè)框的數(shù)量固定為4，虛擬頁(yè)面數(shù)為8。實(shí)驗(yàn)輸入為訪問頁(yè)面序列，比如0，1，3，2，7，1 實(shí)驗(yàn)用到的軟件（：） DevC++,Visio 實(shí)驗(yàn)內(nèi)容及關(guān)鍵步驟（代碼）Q3（15分） 得分： 流程圖：輸入頁(yè)面訪問序列 取訪問的頁(yè)號(hào) 查頁(yè)表 是否缺頁(yè)？ 是 置缺頁(yè)標(biāo)志flag為’*’ 按算法不同淘汰一頁(yè)面 調(diào)入所訪問的頁(yè)面 否 FIFO算法流程圖 LRU算法流程圖： 函數(shù)關(guān)系解釋圖： 實(shí)現(xiàn)結(jié)果： 圖1 圖2 代碼： #include #include #define MEMORY_SIZE /*物理塊數(shù)*/ #define PROESS_SIZE /*頁(yè)面號(hào)引用串個(gè)數(shù)*/#include #include /*全局變量*/ int mSIZE=4; int pSIZE=8; static int memery[4]={0}; /*物理塊中的頁(yè)號(hào)*/ static int page[8]={0}; /*頁(yè)面號(hào)引用串*/ static int temp[8][4]={0}; /*輔助數(shù)組*/ /*置換算法函數(shù)*/ void FIFO(); void LRU(); void OPT(); void designBy(); /*輔助函數(shù)*/ void print(unsigned int t); /*主函數(shù)*/ int main() { int i,k,code; designBy(); system(“color 0A“); puts(“請(qǐng)依次輸入頁(yè)面號(hào)(8個(gè))：“); for(i=0;i scanf(“%1d“,&page[i]); system(“cls“); system(“color 0E“); do{ puts(“輸入的頁(yè)面號(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)選擇頁(yè)面置換算法：＼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: system(“cls“); system(“color 0A“); exit(0); default: printf(“輸入錯(cuò)誤，請(qǐng)重新輸入：“); } printf(“按任意鍵重新選擇置換算法：>>>“); getch(); system(“cls“); }while (code!=3); getch(); } 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)/*頁(yè)面在物理塊中*/ printf(“ “); else printf(“ |%d|“,temp[i][j]); } /*每行顯示20個(gè)*/ if(i%20==0) continue; printf(“＼n“); } } printf(“----------------------------------------＼n“); printf(“缺頁(yè)次數(shù)：%d＼t＼t“,t+mSIZE); printf(“缺頁(yè)率：%d/%d＼n“,t+mSIZE,pSIZE); printf(“置換次數(shù)：%d＼t＼t“,t); printf(“訪問命中率：%d%%＼n“,(pSIZE-(t+mSIZE))*100/pSIZE); printf(“----------------------------------------＼n“); } /*先進(jìn)先出頁(yè)面置換算法*/ void FIFO() { int memery[10]={0}; int time[10]={0}; /*記錄進(jìn)入物理塊的時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁(yè)*/ 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 { /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*計(jì)算換出頁(yè)*/ max=time[0] for(m=2;m if(time[m] max=m; memery[max]=page[i]; time[max]=i; /*記錄該頁(yè)進(jìn)入物理塊的時(shí)間*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } print(count); } /*最近最久未使用置換算法*/ void LRU() { int memery[10]={0}; int flag[10]={0}; /*記錄頁(yè)面的訪問時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁(yè)*/ 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 { /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; else flag[j]=i; /*刷新該頁(yè)的訪問時(shí)間*/ } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*計(jì)算換出頁(yè)*/ max=flag[0] for(m=2;m if(flag[m] max=m; memery[max]=page[i]; flag[max]=i; /*記錄該頁(yè)的訪問時(shí)間*/ for(j=0;j temp[i][j]=memery[j]; } else { for(j=0;j temp[i][j]=memery[j]; } } // compute(); print(count); } /*顯示設(shè)計(jì)者信息*/ void designBy() { printf(“┏━━━━━━━━━━━━━━━━━━━━━━━━━┓＼n“); printf(“┃㊣ 實(shí)驗(yàn)七：頁(yè)面置換算法 ㊣┃＼n“); printf(“┃ 學(xué)號(hào)：1001010042 ┃＼n“); printf(“┃ 姓名：黃浩全 4.9.9.0>┃＼n“); printf(“┣━━━━━━━━━━━━━━━━━━━━━━━━━┫＼n“); } 實(shí)驗(yàn)過程中遇到的問題解決辦法與實(shí)驗(yàn)體會(huì)Q4（需手寫，10分） 得分： 1、在FIFO算法可以很容易用數(shù)組實(shí)現(xiàn)，而LRU算法可以用數(shù)組實(shí)現(xiàn)，不過用結(jié)構(gòu)體會(huì)更明顯簡(jiǎn)單。結(jié)構(gòu)體成員變量可以記錄頁(yè)號(hào)進(jìn)入的時(shí)間，和最近使用的記錄。相對(duì)比數(shù)組更容易理解和實(shí)現(xiàn)。 2:首先，F(xiàn)IFO（先進(jìn)先出）算法和LRU（最近未使用算法）兩者之間，F(xiàn)IFO算法明顯會(huì)比LRU容易理解，而且比LRU算法較容易實(shí)現(xiàn)，但在性能方面，LRU的確在優(yōu)化方面做的比較理想。再且在考慮頁(yè)框和頁(yè)表號(hào)之間的問題用代碼可以容易模擬，但是真是在物理內(nèi)存塊中是如何實(shí)現(xiàn)，那確實(shí)是很難以理解，需要真正理解到內(nèi)存內(nèi)部的知識(shí)才知道這兩個(gè)算法是怎么實(shí)現(xiàn)的。 評(píng)閱教師特殊評(píng)語(yǔ)： 評(píng)閱教師： 日 期： 計(jì)算機(jī)工程學(xué)院 實(shí)驗(yàn)報(bào)告書 課程名：《 操作系統(tǒng)原理A 》 題 目： 虛擬存儲(chǔ)器管理 頁(yè)面置換算法模擬實(shí)驗(yàn) 班 級(jí)： 學(xué) 號(hào)： 姓 名： 評(píng)語(yǔ)： 成績(jī)： 指導(dǎo)教師： 批閱時(shí)間： ****年**月**日 一、實(shí)驗(yàn)?zāi)康呐c要求 1.目的： 請(qǐng)求頁(yè)式虛存管理是常用的虛擬存儲(chǔ)管理方案之一。通過請(qǐng)求頁(yè)式虛存管理中對(duì)頁(yè)面置換算法的模擬，有助于理解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，并加深對(duì)請(qǐng)求頁(yè)式虛存管理的頁(yè)面調(diào)度算法的理解。 2.要求： 本實(shí)驗(yàn)要求使用C語(yǔ)言編程模擬一個(gè)擁有若干個(gè)虛頁(yè)的進(jìn)程在給定的若干個(gè)實(shí)頁(yè)中運(yùn)行、并在缺頁(yè)中斷發(fā)生時(shí)分別使用FIFO和LRU算法進(jìn)行頁(yè)面置換的情形。其中虛頁(yè)的個(gè)數(shù)可以事先給定（例如10個(gè)），對(duì)這些虛頁(yè)訪問的頁(yè)地址流（其長(zhǎng)度可以事先給定，例如20次虛頁(yè)訪問）可以由程序隨機(jī)產(chǎn)生，也可以事先保存在文件中。要求程序運(yùn)行時(shí)屏幕能顯示出置換過程中的狀態(tài)信息并輸出訪問結(jié)束時(shí)的頁(yè)面命中率。程序應(yīng)允許通過為該進(jìn)程分配不同的實(shí)頁(yè)數(shù)，來比較兩種置換算法的穩(wěn)定性。 二、實(shí)驗(yàn)說明 1．設(shè)計(jì)中虛頁(yè)和實(shí)頁(yè)的表示 本設(shè)計(jì)利用C語(yǔ)言的結(jié)構(gòu)體來描述虛頁(yè)和實(shí)頁(yè)的結(jié)構(gòu)。 pn pfn time pn pfn next 虛頁(yè)結(jié)構(gòu) 實(shí)頁(yè)結(jié)構(gòu) 在虛頁(yè)結(jié)構(gòu)中，pn代表虛頁(yè)號(hào)，因?yàn)楣?0個(gè)虛頁(yè)，所以pn的取值范圍是0—9。pfn代表實(shí)頁(yè)號(hào)，當(dāng)一虛頁(yè)未裝入實(shí)頁(yè)時(shí)，此項(xiàng)值為-1；當(dāng)該虛頁(yè)已裝入某一實(shí)頁(yè)時(shí)，此項(xiàng)值為所裝入的實(shí)頁(yè)的實(shí)頁(yè)號(hào)pfn。time項(xiàng)在FIFO算法中不使用，在LRU中用來存放對(duì)該虛頁(yè)的最近訪問時(shí)間。 在實(shí)頁(yè)結(jié)構(gòu)中中，pn代表虛頁(yè)號(hào)，表示pn所代表的虛頁(yè)目前正放在此實(shí)頁(yè)中。pfn代表實(shí)頁(yè)號(hào)，取值范圍（0—n-1）由動(dòng)態(tài)指派的實(shí)頁(yè)數(shù)n所決定。next是一個(gè)指向?qū)嶍?yè)結(jié)構(gòu)體的指針，用于多個(gè)實(shí)頁(yè)以鏈表形式組織起來，關(guān)于實(shí)頁(yè)鏈表的組織詳見下面第4點(diǎn)。 2．關(guān)于缺頁(yè)次數(shù)的統(tǒng)計(jì) 為計(jì)算命中率，需要統(tǒng)計(jì)在20次的虛頁(yè)訪問中命中的次數(shù)。為此，程序應(yīng)設(shè)置一個(gè)計(jì)數(shù)器count，來統(tǒng)計(jì)虛頁(yè)命中發(fā)生的次數(shù)。每當(dāng)所訪問的虛頁(yè)的pfn項(xiàng)值不為-1，表示此虛頁(yè)已被裝入某實(shí)頁(yè)內(nèi)，此虛頁(yè)被命中，count加1。最終命中率=count/20*100%。 3．LRU算法中“最近最久未用”頁(yè)面的確定 為了能找到“最近最久未用”的虛頁(yè)面，程序中可引入一個(gè)時(shí)間計(jì)數(shù)器countime，每當(dāng)要訪問一個(gè)虛頁(yè)面時(shí)，countime的值加1，然后將所要訪問的虛頁(yè)的time項(xiàng)值設(shè)置為增值后的當(dāng)前countime值，表示該虛頁(yè)的最后一次被訪問時(shí)間。當(dāng)LRU算法需要置換時(shí)，從所有已分配實(shí)頁(yè)的虛頁(yè)中找出time值為最小的虛頁(yè)就是“最近最久未用”的虛頁(yè)面，應(yīng)該將它置換出去。 4．算法中實(shí)頁(yè)的組織 因?yàn)槟芊峙涞膶?shí)頁(yè)數(shù)n是在程序運(yùn)行時(shí)由用戶動(dòng)態(tài)指派的，所以應(yīng)使用鏈表組織動(dòng)態(tài)產(chǎn)生的多個(gè)實(shí)頁(yè)。為了調(diào)度算法實(shí)現(xiàn)的方便，可以考慮引入free和busy兩個(gè)鏈表：free鏈表用于組織未分配出去的實(shí)頁(yè)，首指針為free_head，初始時(shí)n個(gè)實(shí)頁(yè)都處于free鏈表中；busy鏈表用于組織已分配出去的實(shí)頁(yè)，首指針為busy_head，尾指針為busy_tail，初始值都為null。當(dāng)所要訪問的一個(gè)虛頁(yè)不在實(shí)頁(yè)中時(shí)，將產(chǎn)生缺頁(yè)中斷。此時(shí)若free鏈表不為空，就取下鏈表首指針?biāo)傅膶?shí)頁(yè)，并分配給該虛頁(yè)。若free鏈表為空，則說明n個(gè)實(shí)頁(yè)已全部分配出去，此時(shí)應(yīng)進(jìn)行頁(yè)面置換：對(duì)于FIFO算法要將busy_head 所指的實(shí)頁(yè)從busy鏈表中取下，分配給該虛頁(yè)，然后再將該實(shí)頁(yè)插入到busy鏈表尾部；對(duì)于LRU算法則要從所有已分配實(shí)頁(yè)的虛頁(yè)中找出time值為最小的虛頁(yè)，將該虛頁(yè)從裝載它的那個(gè)實(shí)頁(yè)中置換出去，并在該實(shí)頁(yè)中裝入當(dāng)前正要訪問的虛頁(yè)。 三、程序流程圖 四、主要程序清單 #include #include /*全局變量*/ int mSIZE; /*物理塊數(shù)*/ int pSIZE; /*頁(yè)面號(hào)引用串個(gè)數(shù)*/ static int memery[10]={0}; /*物理塊中的頁(yè)號(hào)*/ static int page[100]={0}; /*頁(yè)面號(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)輸入頁(yè)面號(hào)引用串的個(gè)數(shù)(P<=100)：“); scanf(“%d“,&pSIZE); puts(“請(qǐng)依次輸入頁(yè)面號(hào)引用串(連續(xù)輸入，無需隔開)：“); for(i=0;i scanf(“%1d“,&page[i]); download(); do { puts(“輸入的頁(yè)面號(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)選擇頁(yè)面置換算法：＼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)/*頁(yè)面在物理塊中*/ printf(“ “); else printf(“ |%d|“,temp[i][j]); } /*每行顯示20個(gè)*/ if(i%20==0) continue; printf(“＼n“); } } printf(“----------------------------------------＼n“); printf(“缺頁(yè)次數(shù)：%d＼t＼t“,t+mSIZE); printf(“缺頁(yè)率：%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)先出頁(yè)面置換算法*/ void FIFO() { int memery[10]={0}; int time[10]={0}; /*記錄進(jìn)入物理塊的時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁(yè)*/ 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 { /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*計(jì)算換出頁(yè)*/ max=time[0] for(m=2;m if(time[m] max=m; memery[max]=page[i]; time[max]=i; /*記錄該頁(yè)進(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}; /*記錄頁(yè)面的訪問時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁(yè)*/ 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 { /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; else flag[j]=i; /*刷新該頁(yè)的訪問時(shí)間*/ } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*計(jì)算換出頁(yè)*/ max=flag[0] for(m=2;m if(flag[m] max=m; memery[max]=page[i]; flag[max]=i; /*記錄該頁(yè)的訪問時(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; /*記錄換出頁(yè)*/ 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 { /*判斷新頁(yè)面號(hào)是否在物理塊中*/ for(j=0,k=0;j { if(memery[j]!=page[i]) k++; } if(k==mSIZE) /*如果不在物理塊中*/ { count++; /*得到物理快中各頁(yè)下一次訪問時(shí)間*/ for(m=0;m { for(l=i+1;l if(memery[m]==page[l]) break; next[m]=l; } /*計(jì)算換出頁(yè)*/ 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++; /*得到物理快中各頁(yè)下一次訪問時(shí)間*/ for(m=0;m { for(l=i+1;l if(memery[m]==page[l]) break; next[m]=l; } /*計(jì)算換出頁(yè)*/ 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)中頁(yè)面調(diào)度的算法有了很大程度的了解，加深了對(duì)課程上知識(shí)的理解，也懂得了如何在程序中將這些算法實(shí)現(xiàn)，在程序中基本上實(shí)現(xiàn)了所要求的算法以及相關(guān)的性能分析，基本上實(shí)現(xiàn)了課程的要求。 這次作業(yè)也暴露了自己在某些方面的不足之處，自己的語(yǔ)言功底有一定的不足，以及一開始對(duì)某個(gè)算法不夠熟悉，將算法實(shí)現(xiàn)設(shè)計(jì)的比較復(fù)雜，此次自己的程序存在一些思想上的漏洞，反映出此次程序設(shè)計(jì)的要求有了一定的限制。 實(shí)驗(yàn)4 頁(yè)面置換算法（2學(xué)時(shí)） 一、實(shí)驗(yàn)?zāi)康?/p> 通過實(shí)驗(yàn)加強(qiáng)對(duì)虛擬存儲(chǔ)管理中頁(yè)面置換算法的理解和掌握。 二、實(shí)驗(yàn)內(nèi)容 編寫程序?qū)崿F(xiàn)虛擬存儲(chǔ)管理中OPT,FIFO,LRU頁(yè)面置換算法。 三、實(shí)驗(yàn)要求 1、任意給出一組頁(yè)面訪問順序（如頁(yè)面走向是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頁(yè)面置換算法模擬頁(yè)面置換過程并計(jì)算其缺頁(yè)率。 4、每訪問一個(gè)頁(yè)面均需給出內(nèi)存中的內(nèi)容（內(nèi)存中的頁(yè)面號(hào)），若有淘汰還需給出淘汰的頁(yè)面號(hào)。 5、通過給出特殊的頁(yè)面訪問順序，分配不同的物理塊，利用FIFO算法計(jì)算其缺頁(yè)率，進(jìn)一步理解Belady現(xiàn)象。 6、（附加）實(shí)現(xiàn)CLOCK置換算法，修改位可在確定頁(yè)面號(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的缺頁(yè)率為：”);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;//待替換的頁(yè)在以后第一次出現(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的缺頁(yè)率為：”);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的缺頁(yè)率為：”);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è) 一、題目: 頁(yè)面置換算法模擬實(shí)驗(yàn) 二、目的 分別采用最佳(Optimal)置換算法、先進(jìn)先出(FIFO)頁(yè)面置換算法和最近最少使用(LRU)置換算法對(duì)用戶輸入的頁(yè)面號(hào)請(qǐng)求序列進(jìn)行淘汰和置換，從而加深對(duì)頁(yè)面置換算法的理解。 三、內(nèi)容和要求 請(qǐng)用C/C++語(yǔ)言編一個(gè)頁(yè)面置換算法模擬程序。用戶通過鍵盤輸入分配的物理內(nèi)存總塊數(shù)，再輸入用戶邏輯頁(yè)面號(hào)請(qǐng)求序列，然后分別采用最佳(Optimal)置換算法、先進(jìn)先出(FIFO)頁(yè)面置換算法和最近最少使用(LRU)置換算法三種算法對(duì)頁(yè)面請(qǐng)求序列進(jìn)行轉(zhuǎn)換，最后按照課本P150頁(yè)圖4-26的置換圖格式輸出每次頁(yè)面請(qǐng)求后各物理塊內(nèi)存放的虛頁(yè)號(hào)，并算出每種算法的缺頁(yè)次數(shù)。最后評(píng)價(jià)三種頁(yè)面置換算法的優(yōu)缺點(diǎn)。 三種頁(yè)面置換算法的思想可參考教材P149-P152頁(yè)。 假設(shè)頁(yè)面號(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)行頁(yè)面轉(zhuǎn)換并輸出置換圖和缺頁(yè)次數(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è)。 頁(yè)面置換算法模擬實(shí)驗(yàn) 算法算法思路 模擬FIFOOPTLRU這3種頁(yè)面置換算法，先分配所需的內(nèi)存空間，在根據(jù)已知的序列，分別根據(jù)不同的頁(yè)面算法去訪問已知序列，得出不同內(nèi)存空間的置換算法的缺頁(yè)數(shù)量?？傮w流程圖 開始輸入內(nèi)存數(shù)執(zhí)行頁(yè)面置換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;// 賦予 頁(yè)號(hào) index =(index+1)%mem_num;// 每次取余 lack++; } } cout<<“FIFO算法：n”;cout<<“---**n”;cout<<“缺頁(yè)次數(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)存頁(yè)號(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<<“缺頁(yè)次數(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<<“缺頁(yè)次數(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)存大小（3/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è)頁(yè)面置換的知識(shí)點(diǎn)，同時(shí)參考了網(wǎng)絡(luò)上許多實(shí)現(xiàn)過程技巧，并在在紙上面簡(jiǎn)單畫出頁(yè)面如何記錄如何與內(nèi)存置換，這樣子比較方便寫出算法。由于這次設(shè)計(jì)的時(shí)間比較倉(cāng)促，其中不免會(huì)有些紕漏，比如在程序的實(shí)現(xiàn)上還不夠嚴(yán)謹(jǐn)，出錯(cuò)處理不夠完善等多方面問題，這些都有進(jìn)一步改善。同時(shí)，在這次編寫3個(gè)頁(yè)面算法的過程中，我學(xué)到了很多東西，無論在理論上還是實(shí)踐中，都得到不少的提高，這對(duì)以后的工作中會(huì)有一定的幫助。第二篇：操作系統(tǒng) 七次實(shí)驗(yàn)報(bào)告 常用頁(yè)面置換算法模擬實(shí)驗(yàn)
第三篇：計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)三頁(yè)面置換算法模擬實(shí)驗(yàn)
第四篇：計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)4頁(yè)面置換算法
第五篇：頁(yè)面置換算法模擬
點(diǎn)擊咨詢 