頁式虛擬存儲管理缺頁中斷的模擬系統(tǒng)的設(shè)計

1、目錄目錄1一 課程設(shè)計目的與功能21目的22初始條件23 開發(fā)環(huán)境24功能2二 需求分析，整體功能及設(shè)計數(shù)據(jù)結(jié)構(gòu)或模塊說明31 需求分析32 算法分析43 數(shù)據(jù)結(jié)構(gòu)64 各模塊函數(shù)功能說明7三 源程序的主要部分71 main函數(shù)72 替換算法實現(xiàn)函數(shù)8四 使用說明11五 運行結(jié)果與運行情況分析111 FIFO算法113 隨機替換算法133 OPT替換算法14結(jié)論15六自我評價與總結(jié)：15參考文獻16附錄16頁式虛擬存儲管理缺頁中斷的模擬系統(tǒng)的設(shè)計OPT、FIFO、隨機淘汰算法一 課程設(shè)計目的與功能1目的通過分析、設(shè)計和實現(xiàn)頁式虛擬存儲管理缺頁中斷的模擬系統(tǒng)，熟悉和掌握請求分頁式存儲管理的實現(xiàn)過

2、程，重點掌握當(dāng)請求頁面不在內(nèi)存而內(nèi)存塊已經(jīng)全部被占用時的替換算法，熟悉常見替換算法的原理和實現(xiàn)過程，并利用替換算法的評價指標(biāo)缺頁次數(shù)和缺頁率，來對各種替換算法進行評價比較。設(shè)計并實現(xiàn)出的結(jié)果程序要能夠很好地顯示頁面調(diào)入和替換詳細信息。2初始條件（1）預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，了解有關(guān)虛擬存儲器、頁式存儲管理等概念，并體會和了解缺頁和頁面置換的具體實施方法。（2）實踐準備：掌握一種計算機高級語言的使用3 開發(fā)環(huán)境（1）使用系統(tǒng)：Windows XP（2）使用語言：C+（3）開發(fā)工具：Visual C+ 6.04功能設(shè)計的結(jié)果程序能實現(xiàn)OPT、FIFO、隨機淘汰算法模擬頁式存儲管理

3、缺頁中斷，主要能夠處理以下的情形：(1) 用戶能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)；(2) 用戶能夠輸入給定的頁面，并計算發(fā)生缺頁的次數(shù)以及缺頁率；(3) 程序可隨機生成頁面序列，替代用戶輸入；(4) 缺頁時，如果發(fā)生頁面置換，輸出淘汰的頁號。二 需求分析，整體功能及設(shè)計數(shù)據(jù)結(jié)構(gòu)或模塊說明1 需求分析在純頁式存儲管理提高了內(nèi)存的利用效率，但并不為用戶提供虛存，換句話說，當(dāng)一個用戶程序的頁數(shù)大于當(dāng)前總空閑內(nèi)存塊數(shù)時，系統(tǒng)就不能將該程序裝入運行。即用戶程序?qū)⑹艿轿锢韮?nèi)存大小的限制。為了解決這個問題，人們提出了能提供虛存的存儲管理技術(shù)請求分頁存儲管理技術(shù)和請求分段技術(shù)。本設(shè)計實現(xiàn)請求分頁管理技術(shù)。請求分頁系

4、統(tǒng)是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能和頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。它允許只裝入部分頁面的程序和數(shù)據(jù)，便啟動運行。以后，再通過調(diào)頁功能和頁面置換功能，陸續(xù)把即將要運行的頁面調(diào)入內(nèi)存，同時把暫時不運行的頁面換出到外存上。置換時以頁面為單位，為了能實現(xiàn)請求調(diào)頁和置換功能，系統(tǒng)必須提供必要的硬件支持和相應(yīng)的軟件。其中硬件支持包括：請求分頁的頁表機制，它是在純分頁的頁表機制上增加若干項而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)；缺頁中斷機構(gòu)，當(dāng)要訪問的頁面尚未調(diào)入內(nèi)存時，便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存；地址變換機構(gòu)，它同樣是在純分頁地址變換機構(gòu)的基礎(chǔ)上形成的。實現(xiàn)請求分頁的軟件包括

5、用于實現(xiàn)請求調(diào)頁的軟件和實現(xiàn)頁面置換的軟件。他們在硬件的支持下，將程序正在運行時所需的但尚未在內(nèi)存的頁面調(diào)入內(nèi)存，再將內(nèi)存中暫時不用的頁面從內(nèi)存置換到外存磁盤上。為了實現(xiàn)請求分頁技術(shù)，頁表應(yīng)增加相應(yīng)的內(nèi)容，反映該頁是否在內(nèi)存，在外存的位置，和在內(nèi)存的時間的長短。請求分頁中的頁表如表1：表1虛擬頁號物理塊號狀態(tài)位輔存地址訪問字段修改位各字段說明如下：狀態(tài)位：用于指示該頁是否已調(diào)入內(nèi)存，供程序訪問時參考。訪問字段：用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或記錄本頁最近已有多長時間未被訪問，供替換頁面時參考。修改位：表示該頁面在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留有副本，因此，若未

6、被修改，在替換該頁時就不需要再將該頁寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址：用于指出該頁在外存上的地址，通常是物理塊號，供調(diào)入頁面時參考。在模擬系統(tǒng)的實現(xiàn)中，只需要用到虛擬頁號，物理塊號和中斷位。頁表可用一個結(jié)構(gòu)體的數(shù)組實現(xiàn)。請求分頁的具體實現(xiàn)過程如圖1圖1請求分頁流程圖2 算法分析在進程運行過程中，若其所要訪問的頁面不在內(nèi)存，這時候會產(chǎn)生一個缺頁中斷，并需要把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑已空閑空間時，為了保證該進程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)。但應(yīng)將哪個頁面調(diào)出，必須

7、根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面替換算法。虛擬內(nèi)存性能的好壞很大程度上由替換算法的好壞，替換算法的好壞，也將直接影響系統(tǒng)的性能，一個好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。常見置換算法有隨機淘汰算法（Random Glongram）、輪轉(zhuǎn)法（Round Robin）和先進先出(FIFO)、最近最久未使用頁面置換算法和理想型淘汰算法OPT（Optimal Replacement Algorithm）。本次所設(shè)計的模擬系統(tǒng)根據(jù)題目要求利用隨機淘汰算法，先進先出算法和理想型淘汰算法進行頁面替換，詳細算法原理如下：隨機淘汰算法：在系統(tǒng)設(shè)計人員無法確定哪些頁被訪問的概率較低時

8、，明智的作法是隨機地選擇某個用戶的頁并將其換出。隨機淘汰算法實現(xiàn)簡單，但是缺頁率高。先進先出算法：總是選擇在內(nèi)存駐留時間最長的一頁將其淘汰，因為最早調(diào)入內(nèi)存的頁，不再被使用的可能性比近期調(diào)入內(nèi)存的大。該算法實現(xiàn)簡單，只需要把一個進程調(diào)入內(nèi)存的頁面，按先后次序連結(jié)成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。但是該算法與進程實際運行的規(guī)律不相適應(yīng)，因為在進程中，有些頁面經(jīng)常被訪問，比如有全局變量、常用函數(shù)，例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。假定系統(tǒng)為某進程分配了三個可用物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，

9、1，2，0，1，7，0，1進程運行時，先將7，0，1三個頁面裝入內(nèi)存，且采用FIFO替換算法。當(dāng)有請求頁面2時，內(nèi)存中頁面7，0，1三個頁號可知道7先進入內(nèi)存，所以替換頁面1；當(dāng)請求頁面0時，可知，0在內(nèi)存中，不需要替換；當(dāng)請求頁面號3時內(nèi)存中0，1，2三個頁面0先進入內(nèi)存，替換0號頁。如此進行下去，可得出利用FIFO替換算法，以上請求頁面號序列共進行了12次頁面替換，比理想型算法要多出一倍。使用FIFO替換算法效率低的原因是：基于處理器按線性順序訪問地址空間這一假設(shè)。事實上，許多時候，處理器不是按線性順序訪問地址空間的。例如，執(zhí)行循環(huán)結(jié)構(gòu)的程序段。使用FIFO算法時，在未給進程或作業(yè)分配足夠

10、它所需要的頁面數(shù)時，有時會出現(xiàn)分配的頁面數(shù)增，缺頁次數(shù)反而增加的現(xiàn)象（Belady現(xiàn)象）。 例如針對請求序列：1 2 3 4 1 2 5 1 2 3 4 5，若分配3個可用內(nèi)存塊，使用FIFO算法，一共會缺頁9次，缺頁率：75%；而如果分配4個可用內(nèi)存塊，則一共會缺頁10次，缺頁率：83.3%。理想型淘汰算法基本思想：當(dāng)要調(diào)入一新頁而必須淘汰一舊頁時，所淘汰的頁是以后不再使用的，或者是以后相當(dāng)長的時間內(nèi)不會使用的。采用理想型替換算法，通?？杀ＷC獲得最低的缺頁率。但是由于人們目前無法預(yù)知一個進程在內(nèi)存的若干個頁面中，哪個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，但是在模擬設(shè)計中，

11、由于是事先給定一個頁面序列，即知道各個時刻以前和以后的頁面出現(xiàn)情況，所以可實現(xiàn)該算法。在實際系統(tǒng)中，雖無法實現(xiàn)理想型淘汰算法，但是可用它來評價其他替換算法。用上面的例子，先將7，0，1三個頁面裝入內(nèi)存。以后當(dāng)進程要訪問頁面2時，將會產(chǎn)生缺頁中斷。此時OS根據(jù)最佳替換算法，將選擇頁面7予以淘汰，這是因為頁面0將作為第5個被訪問的頁面，頁面1是第14個被訪問的頁面，而頁面1則要在第18次頁面訪問時才需要調(diào)入。下次訪問頁面0時，因它已經(jīng)在內(nèi)存而不必產(chǎn)生缺頁中斷。當(dāng)進程訪問頁面3時，又將引起頁面1被淘汰；因為，它在現(xiàn)有的1，2，0三個頁面中，將是最后被訪問的。如此繼續(xù)，這個作業(yè)序列將會產(chǎn)生6次頁面置換

12、。理想型淘汰算法的具體工作流程如圖2：圖23 數(shù)據(jù)結(jié)構(gòu)模擬設(shè)計時，頁表用數(shù)組模擬。數(shù)組的數(shù)據(jù)類型為結(jié)構(gòu)體，結(jié)構(gòu)體有三個成員：int pageNum 表示頁面號；int memoryNum表示頁面所對應(yīng)的內(nèi)存塊號；int isInmemory是存在狀態(tài)位標(biāo)志，表示頁面是否在內(nèi)存，0表示不在內(nèi)存，1表示在內(nèi)存。程序中設(shè)定虛擬頁面號共10個，所以頁表大小為10，即10個元素的數(shù)組pageTable。在每一個算法函數(shù)中都要初始化頁表，否則，后面的算法會受前面算法結(jié)果的影響。struct pageint pageNum;int memoryNum;int isInmemory;page pageTabl

13、e10; 初始化頁表：for(int i=0;i<10;i+) pageTablei.pageNum=i;pageTablei.memoryNum=-1; /初始化時，內(nèi)存塊號為-1，即沒在內(nèi)存塊中。pageTablei.isInmemory =0; /初始化時，各頁面均不在內(nèi)存 頁面請求序列：int *in= new intinputSize。 模擬內(nèi)存：int *memory=new intmemorySize，在程序中模擬內(nèi)存存放頁面號。4 各模塊函數(shù)功能說明int Main（）函數(shù)提示并接受用戶輸入等待調(diào)入頁面數(shù)inputSize，可用物理塊數(shù)memorySize，并隨機生成in

14、putSize個請求頁面，或提示用戶自己輸入頁面序列。然后調(diào)用FIFO()、random()和OPT()函數(shù)實現(xiàn)按不同替換算法調(diào)入頁面進內(nèi)存。void FIFO()函數(shù)實現(xiàn)先進先出的替換算法調(diào)入頁面。void random()函數(shù)實現(xiàn)隨機替換算法調(diào)入頁面。void OPT()函數(shù)實現(xiàn)理想型替換算法。int getOPTPage(int page)用于獲取最優(yōu)替換頁面所在的內(nèi)存塊。該函數(shù)的算法實現(xiàn)流程圖如圖2。三 源程序的主要部分1 main函數(shù)int main()for(int i=0;i<10;i+) /初始化頁表pageTablei.pageNum=i;pageTablei.memo

15、ryNum=-1;pageTablei.isInmemory =0; cout<<"輸入待調(diào)入頁面數(shù)"<<endl;cin>>inputSize; cout<<"輸入可使用的物理塊數(shù)："<<endl;cin>>memorySize; int temp;srand( (unsigned)time( NULL ) );cout<<"隨機生成頁面請求序列(0-9)"<<endl;for( i=0;i<inputSize;i+)temp=ra

16、nd()%10;cout<<temp<<" "ini=temp;cout<<endl; FIFO(); random();OPT();return 0;2 替換算法實現(xiàn)函數(shù)void FIFO()cout<<"FIFO替換算法:"<<endl; for(int i=0;i<memorySize;i+)memoryi=-1; int lackTime=0; /記錄缺頁次數(shù)int replace=0; /獲得應(yīng)該被替換占用的物理塊號int isFull=0; /記錄物理塊是否已被占滿，當(dāng)isFu

17、ll=3時表示已經(jīng)裝滿int page=0; /記錄將要訪問的頁面號 do /物理塊未被占滿時 if(pageTableinpage.isInmemory =1) / ini在memory中 cout<<inpage<<" is in memory"<<endl;page+;continue; elselackTime+;cout<<inpage<<" not in memory!"<<endl; / 裝入內(nèi)存memoryisFull=inpage; for(int j=0;j<

18、;10;j+)if( pageTablej.memoryNum= isFull) pageTablej.memoryNum=-1; pageTablej.isInmemory=0;break;pageTableinpage.isInmemory=1;pageTableinpage.memoryNum=isFull; isFull+;page+;while(isFull!=memorySize);/物理塊被占滿時退出循環(huán) for( i=page;i<inputSize;i+)/此時page如果再次缺頁則發(fā)生替換if(pageTableini.isInmemory =1)/ini在memor

19、y中cout<<ini<<" is in memory"<<endl;continue;else /ini不在memory中l(wèi)ackTime+;memoryreplace=ini;for(int j=0;j<10;j+)if( pageTablej.memoryNum=replace)cout<<ini<<" not in memory!take place of page "；cout<<j<<endl; pageTablej.memoryNum=-1; page

20、Tablej.isInmemory=0; break; pageTableini.isInmemory=1;pageTableini.memoryNum=replace; replace=(replace+1)%memorySize; /替換頁面號的獲得cout<<"缺頁次數(shù)："<<lackTime<<endl;cout<<"缺頁率： "<<double(lackTime)/inputSize*100<<"%"<<endl; 其中replace根據(jù)不同

21、的替換算法不同而不同。若是先進先出替換算法則：replace=(replace+1)%memorySize;若是隨機替換算法則：replace=rand()%memorySize;若是理想型替換算法則：replace=getOPTPage(i)。getOPTPage(i)函數(shù)：int getOPTPage(int page)int *opt=new intmemorySize;for(int i=0;i<memorySize;i+)opti=0;for(i=0;i<memorySize;i+)for(int j=0;j<10;j+)if(pageTablej.memoryNu

22、m=i)for(int t=page+1;t<inputSize;t+)if(j=int)opti=t;break;if(opti=0)opti=inputSize; int optNum=0;for(i=0;i<memorySize;i+)if(opti>optoptNum)optNum=i; return optNum;四 使用說明 運行程序替換算法.exe，根據(jù)提示輸入等待調(diào)入頁面數(shù)和可使用的物理塊數(shù)，程序會提示是否隨機生成并顯示一個頁面請求序列，如果是，則隨機生成序列，否則，要求自行輸入序列。然后顯示利用各算法處理請求頁面的結(jié)果：如果頁面在內(nèi)存則顯示“ 頁面號is i

23、n memory ”，若不在內(nèi)存則顯示 “頁面號not in memory！take place of 被替換的頁面號”。處理完各頁面后，統(tǒng)計并顯示缺頁次數(shù)和缺頁率。五 運行結(jié)果與運行情況分析待調(diào)入頁面數(shù)：25可用物理塊數(shù)：3隨機生成頁面請求序列，如圖3：0 3 9 4 0 1 6 0 1 5 0 9 5 2 7 6 8 8 8 2 5 2 5 3 0圖31 FIFO算法運行結(jié)果，如圖4：圖4結(jié)果分析，如表2（×表示缺頁，并在下方填被替換的頁面號，表示不缺頁）：表20 3 9 4 0 1 6 0 1 5 0 9 5 2 7 6 8 8 8 2 5 2 5 3 0 0 0 0 4 4

24、4 6 6 6 6 6 9 9 9 9 6 6 6 6 6 5 5 5 5 5 3 3 3 0 0 0 0 0 5 5 5 5 2 2 2 8 8 8 8 8 8 8 3 3 9 9 9 1 1 1 1 1 0 0 0 0 7 7 7 7 7 2 2 2 2 2 0 × × × × × × × × × × × × ×× × × × × 0 3 9 4 0 1 6 5 0 9 2 7 6 8 2 通過表可以看出，利用隨

25、機替換算法，請求序列共缺頁18次，替換序列依次是：0 3 9 4 0 1 6 5 0 9 2 7 6 8 2，缺頁率72%，運行結(jié)果與分析結(jié)果一致。3 隨機替換算法運行結(jié)果，如圖5：圖5結(jié)果分析，如表3（×表示缺頁，并在下方填被替換的頁面號，表示不缺頁）：表30 3 9 4 0 1 6 0 1 5 0 9 5 2 7 6 8 8 8 2 5 2 5 3 0 0 0 0 4 4 4 4 0 0 0 0 0 0 0 0 6 6 6 6 6 5 5 5 5 5 3 3 3 0 1 6 6 1 1 1 9 9 9 7 7 7 7 7 7 7 7 7 7 0 9 9 9 9 9 9 9 5 5

26、 5 5 2 2 2 8 8 8 2 2 2 2 3 3 × × × × × × × × × × × × × × × × × × 0 3 0 1 4 6 9 1 5 9 0 2 8 6 2 7 通過表可以看出，利用隨機替換算法，請求序列共缺頁19次，替換序列依次是：0 3 0 1 4 6 9 1 5 9 0 2 8 6 2 7 缺頁率為76%，運行結(jié)果與分析結(jié)果一致。3 OPT替換算法運行結(jié)果，如圖6：圖6結(jié)果分析，

27、如表4（×表示缺頁，并在下方填被替換的頁面號，表示不缺頁）：表43 9 4 0 1 6 0 1 5 0 9 5 2 7 6 8 8 8 2 5 2 5 3 0 0 0 0 0 0 0 0 0 0 0 0 9 9 2 2 2 2 2 2 2 2 2 2 3 2 3 3 4 4 1 1 1 1 5 5 5 5 5 7 7 8 8 8 8 5 5 5 5 5 9 9 9 9 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 × × × × × × × × × × &

28、#215; × × × 3 4 9 1 0 9 5 7 8 2 3 通過表可以看出，利用隨機替換算法，請求序列共缺頁14次，替換序列依次是：3 4 9 1 0 9 5 7 8 2 3， 缺頁率為56%，運行結(jié)果與分析結(jié)果一致。結(jié)論通過測試運行，可以看出結(jié)果程序能滿足設(shè)計要求，提示用戶對請求序列的大小和可用內(nèi)存數(shù)量進行限制，并提示用戶輸入請求序列號，或系統(tǒng)隨機生成序列，按照不同的替換算法處理并且顯示請求頁面的調(diào)入和替換情況。通過以上運行，比較各種算法的缺頁次數(shù)和缺頁率，可以看出OPT替換算法具有最小的缺頁率。雖理論上最優(yōu)，但是實際卻無法實現(xiàn)該算法。六自我評價與總結(jié)：

29、通過一周的努力，終于完成了模擬系統(tǒng)的設(shè)計和實現(xiàn)，并按照規(guī)范編寫了課程設(shè)計報告書。在這一周里，為了較好地完成本次設(shè)計任務(wù)，翻閱了大量的圖書資料，既有有關(guān)操作系統(tǒng)相關(guān)知識的，也有針對編寫用語言c+語言知識的。在翻閱查看相關(guān)資料的過程中，豐富和鞏固了操作系統(tǒng)的理論知識，對課堂上不明確和不懂的知識，如請求分頁的工作流程，都得到了很好補充學(xué)習(xí)，同時也增加了c+語言本身的應(yīng)用能力。本次設(shè)計作得比較好的地方有：流程清晰，通過繪制流程圖，較好地理解了請求分頁的工作流程；算法設(shè)計合理，容易理解，實現(xiàn)簡單；結(jié)果顯示清晰明了，能清晰地看出各請求頁面的存在和替換信息。設(shè)計中不足的地方：實際上請求分頁存儲管理中，為了增

30、加內(nèi)存的利用率，所分配的內(nèi)存是不連續(xù)的，但是在模擬系統(tǒng)中，用的是一個數(shù)組來模擬內(nèi)存空間，即使得所分配的內(nèi)存是連續(xù)的，與實際情況不相符合；另外，雖然幾經(jīng)調(diào)試和修改，但是程序中仍然有內(nèi)存訪問相關(guān)的問題。其他可用算法：請求分頁內(nèi)存管理的頁面替換還可以用LRU，即最近最久未使用替換算法。LRU的基本思想是：當(dāng)需要淘汰某一頁時，選擇離當(dāng)前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰。即當(dāng)需要淘汰一頁時，選擇最長時間未使用的頁。它是基于假設(shè)：如果某頁被訪問，它可能馬上還要被訪問；相反，如果某頁長時間未被訪問，它可能最近也不可能被訪問。實現(xiàn)時可為每個頁設(shè)置一個特定的單元，用于記錄自上次訪問以來所經(jīng)歷的時間t

31、，當(dāng)需要置換一頁時，選擇t最大的淘汰。通過對請求分頁替換模擬系統(tǒng)的設(shè)計和實現(xiàn)，鞏固了理論知識，對一些不明白的概念，有了很好的認識，同時增加了自己的程序算法設(shè)計能力和編程動手的能力。 參考文獻1 張堯?qū)W，史美林編著計算機操作系統(tǒng)教程（第二版）清華大學(xué)出版社2000 2孟靜操作系統(tǒng)原理教程清華大學(xué)出版社20003黃干平，陳洛資等計算機操作系統(tǒng)科學(xué)出版社19894湯子瀛，哲鳳屏，湯小丹編著計算機操作系統(tǒng)西安電子科技大學(xué)出版社1996附錄#include<iostream>#include<time.h>using namespace std;int inputSize;int

32、 memorySize;int *in; /請求序列int *memory; /模擬內(nèi)存void FIFO();void random();void OPT();int getOPTPage(int inPage);struct pageint pageNum;int memoryNum;int isInmemory;page pageTable10; /假設(shè)虛擬頁面數(shù)10個，頁表長度10int main()for(int i=0;i<10;i+) /初始化頁表pageTablei.pageNum=i;pageTablei.memoryNum=-1;pageTablei.isInmemo

33、ry =0; cout<<"輸入待調(diào)入頁面數(shù)"<<endl;cin>>inputSize; cout<<"輸入可使用的物理塊數(shù)"<<endl;cin>>memorySize; in= new intinputSize; memory=new intmemorySize; int temp;int select; srand( (unsigned)time( NULL ) );cout<<"隨機生成請求序列？(1是)"<<endl;cin&g

34、t;>select;if(select=1) cout<<"隨機生成頁面請求序列(0-9)"<<endl;for( i=0;i<inputSize;i+)temp=rand()%10;cout<<temp<<" "ini=temp;else cout<<"輸入"<<inputSize<<"個頁面號(0-9)"<<endl;for( i=0;i<inputSize;i+)cin>>temp;i

35、ni=temp;cout<<endl; FIFO(); random();OPT();delete in;delete memory;return 0;void FIFO() /FIFO替換算法實現(xiàn)函數(shù)cout<<"FIFO替換算法:"<<endl; for(int i=0;i<memorySize;i+)memoryi=-1; int lackTime=0; /記錄缺頁次數(shù)int firstIn=0; /記錄最先被占用的物理塊號，裝有最先進入內(nèi)存的頁面號int isFull=0; /記錄物理塊是否已被占滿，當(dāng)isFull=3時表示

36、已經(jīng)裝滿，如果再缺頁則發(fā)生替換int page=0; /記錄將要訪問的頁面號 do /物理塊未被占滿時 if(pageTableinpage.isInmemory =1) / ini在memory中 cout<<inpage<<" is in memory"<<endl;page+;if(page=inputSize)break;else continue; elselackTime+;cout<<inpage<<" not in memory!"<<endl; / 裝入內(nèi)存memo

37、ryisFull=inpage; for(int j=0;j<10;j+)if( pageTablej.memoryNum= isFull) pageTablej.memoryNum=-1; pageTablej.isInmemory=0;break;pageTableinpage.isInmemory=1;pageTableinpage.memoryNum=isFull; isFull+;page+;if(page=inputSize)break;while(isFull!=memorySize); /物理塊被占滿時退出循環(huán) for( i=page;i<inputSize;i+)

38、 /此時page如果再次缺頁則發(fā)生替換if(pageTableini.isInmemory =1)/ini在memory中cout<<ini<<" is in memory"<<endl;continue;else /ini不在memory中l(wèi)ackTime+;memoryfirstIn=ini;for(int j=0;j<10;j+)if( pageTablej.memoryNum=firstIn)cout<<ini<<" not in memory!take place of page &quo

39、t;<<j<<endl; pageTablej.memoryNum=-1; pageTablej.isInmemory=0;break; pageTableini.isInmemory=1;pageTableini.memoryNum=firstIn; firstIn=(firstIn+1)%memorySize;cout<<"缺頁次數(shù)："<<lackTime<<endl;cout<<"缺頁率： "<<double(lackTime)/inputSize*100<&

40、lt;"%"<<endl; void random() /隨機替換算法實現(xiàn)函數(shù)for(int i=0;i<10;i+) /初始化頁表pageTablei.pageNum=i;pageTablei.memoryNum=-1;pageTablei.isInmemory =0;srand( (unsigned)time( NULL ) );cout<<"隨機替換算法:"<<endl;for(i=0;i<memorySize;i+)memoryi=-1; int lackTime=0;int replace=0;

41、/被替換的物理塊號int isFull=0;int page=0;doif(pageTableinpage.isInmemory =1) /ini在memory中 cout<<inpage<<" is in memory"<<endl;page+;if(page=inputSize)break;else continue; elselackTime+; cout<<inpage<<" not in memory!"<<endl; for(int j=0;j<10;j+)if(

42、pageTablej.memoryNum=isFull) pageTablej.memoryNum=-1; pageTablej.isInmemory=0;break;memoryisFull=inpage; / 裝入內(nèi)存pageTableinpage.isInmemory=1;pageTableinpage.memoryNum=isFull; isFull+;page+;if(page=inputSize)break;while(isFull!=memorySize); for( i=page;i<inputSize;i+)if(pageTableini.isInmemory =1)/

43、ini在memory中 cout<<ini<<" is in memory"<<endl;continue;else /ini不在memory中l(wèi)ackTime+; replace=rand()%memorySize; for(int j=0;j<10;j+)if( pageTablej.memoryNum=replace) cout<<ini<<" not in memory!take place of page "<<j<<endl; pageTablej.me

44、moryNum=-1; pageTablej.isInmemory=0;break; memoryreplace=ini; pageTableini.isInmemory=1;pageTableini.memoryNum=replace; cout<<"缺頁次數(shù)："<<lackTime<<endl;cout<<"缺頁率： "<<double(lackTime)/inputSize*100<<"%"<<endl;void OPT() /理想型替換算法實現(xiàn)函數(shù)for(int i=0;i<10;i+) /初始化頁表pageTablei.pageNum=i;pageTablei.memoryNum=-1;pageTablei.isInmemory =0;srand( (unsigned)time( NULL ) );cout<<"OPT替換算法:"<<endl;for(i=0;i<mem