請(qǐng)求頁(yè)式管理缺頁(yè)中斷模擬設(shè)計(jì)FIFO,OPT

1、學(xué) 號(hào)： 0121110340232課 程 設(shè) 計(jì)題 目系統(tǒng)軟件開發(fā)實(shí)訓(xùn)A學(xué) 院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專 業(yè)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)班 級(jí)計(jì)算機(jī)1102班姓 名田藍(lán)指導(dǎo)教師 李玉強(qiáng)2014年1月13日課程設(shè)計(jì)任務(wù)書學(xué)生姓名： 田藍(lán) 專業(yè)班級(jí)： 計(jì)算機(jī)1102班 指導(dǎo)教師： 李玉強(qiáng) 工作單位： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: 請(qǐng)求頁(yè)式管理缺頁(yè)中斷模擬設(shè)計(jì)-FIFO、OPT初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，了解有關(guān)虛擬存儲(chǔ)器、頁(yè)式存儲(chǔ)管理等概念，并體會(huì)和了解缺頁(yè)和頁(yè)面置換的具體實(shí)施方法。2實(shí)踐準(zhǔn)備：掌握一種計(jì)算機(jī)高級(jí)語(yǔ)言的使用。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，

2、以及說(shuō)明書撰寫等具體要求）1實(shí)現(xiàn)指定淘汰算法。能夠處理以下的情形： 能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)； 能夠輸入給定的頁(yè)面，并計(jì)算發(fā)生缺頁(yè)的次數(shù)以及缺頁(yè)率； 缺頁(yè)時(shí)，如果發(fā)生頁(yè)面置換，輸出淘汰的頁(yè)號(hào)。2設(shè)計(jì)報(bào)告內(nèi)容應(yīng)說(shuō)明： 課程設(shè)計(jì)目的與功能； 需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說(shuō)明(功能與框圖)； 源程序的主要部分； 測(cè)試用例，運(yùn)行結(jié)果與運(yùn)行情況分析； 自我評(píng)價(jià)與總結(jié)。時(shí)間安排：設(shè)計(jì)安排3周：查閱、分析資料 1天系統(tǒng)軟件的分析與建模 4天系統(tǒng)軟件的設(shè)計(jì) 5天系統(tǒng)軟件的實(shí)現(xiàn) 3天撰寫文檔 1天課程設(shè)計(jì)驗(yàn)收答辯 1天設(shè)計(jì)驗(yàn)收安排：設(shè)計(jì)周的第三周的指定時(shí)間到實(shí)驗(yàn)室進(jìn)行上機(jī)驗(yàn)收。設(shè)計(jì)報(bào)告書收取時(shí)間：課程設(shè)計(jì)驗(yàn)收答

3、辯完結(jié)時(shí)。（注意事項(xiàng)：嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記）指導(dǎo)教師簽名： 2013 年 12 月 10日系主任（或責(zé)任教師）簽名： 2013 年 12 月 10日請(qǐng)求頁(yè)式管理缺頁(yè)中斷模擬設(shè)計(jì)FIFO、OPT1課程設(shè)計(jì)目的與功能 1.1設(shè)計(jì)目的 結(jié)合操作系統(tǒng)所學(xué)內(nèi)存頁(yè)式管理章節(jié)，掌握虛擬內(nèi)存設(shè)計(jì)的重要性，熟悉和掌握請(qǐng)求分頁(yè)式存儲(chǔ)管理的實(shí)現(xiàn)原理，通過(guò)分析、設(shè)計(jì)和實(shí)現(xiàn)頁(yè)式虛擬存儲(chǔ)管理缺頁(yè)中斷的模擬系統(tǒng)，重點(diǎn)掌握當(dāng)請(qǐng)求頁(yè)面不在內(nèi)存而內(nèi)存塊已經(jīng)全部被占用時(shí)的替換算法（主要通過(guò)FIFO和OPT實(shí)現(xiàn)），并考察替換算法的評(píng)價(jià)指標(biāo)缺頁(yè)次數(shù)和缺頁(yè)率，得到每次淘汰的頁(yè)面。高級(jí)語(yǔ)言設(shè)計(jì)并實(shí)現(xiàn)出的結(jié)果程序要能夠

4、很好地顯示頁(yè)面調(diào)入和替換詳細(xì)信息,能夠輸入要訪問(wèn)的頁(yè)面的順序，及能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)。1.2初始條件及可發(fā)環(huán)境 1.2.1初始條件 1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，了解有關(guān)虛擬存儲(chǔ)器、頁(yè)式存儲(chǔ)管理等概念，并體會(huì)和了解缺頁(yè)和頁(yè)面置換的具體實(shí)施方法。2實(shí)踐準(zhǔn)備：掌握一種計(jì)算機(jī)高級(jí)語(yǔ)言的使用。 1.2.2開發(fā)環(huán)境 （1）使用系統(tǒng)：Windows 7（2）使用語(yǔ)言：java（3）開發(fā)工具：eclipse1.3功能實(shí)現(xiàn) 設(shè)計(jì)的結(jié)果程序能實(shí)現(xiàn)FIFO、OPT算法模擬頁(yè)式存儲(chǔ)管理缺頁(yè)中斷，主要能夠處理以下的情形：(1) 用戶能夠輸入給定分配的內(nèi)存塊數(shù)；(2) 用戶輸入給定的頁(yè)面，并計(jì)算發(fā)

5、生缺頁(yè)的次數(shù)、缺頁(yè)率及淘汰頁(yè)面次序；（3） 缺頁(yè)時(shí)，如果發(fā)生頁(yè)面置換，輸出淘汰的頁(yè)號(hào)；(4) 程序可隨機(jī)生成頁(yè)面序列，或用戶輸入；（5）能夠顯示分配的內(nèi)存塊數(shù)的存儲(chǔ)情況2需求分析及設(shè)計(jì)說(shuō)明 2.1需求分析 由于純頁(yè)式存儲(chǔ)管理提高了內(nèi)存的利用效率，但并不為用戶提供虛存，并且會(huì)產(chǎn)生磁盤碎片問(wèn)題。用戶程序?qū)⑹艿轿锢韮?nèi)存大小的限制。而虛存的存儲(chǔ)管理技術(shù)請(qǐng)求分頁(yè)存儲(chǔ)管理技術(shù)和請(qǐng)求分段技術(shù)，則很好的解決了這個(gè)問(wèn)題。該設(shè)計(jì)虛擬實(shí)現(xiàn)請(qǐng)求分頁(yè)管理（只實(shí)現(xiàn)FIFO和OPT）。請(qǐng)求分頁(yè)系統(tǒng)是在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能和頁(yè)面置換功能所形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。它允許只裝入部分頁(yè)面的程序和數(shù)據(jù)，便啟動(dòng)運(yùn)行。以

6、后，再通過(guò)調(diào)頁(yè)功能和頁(yè)面置換功能，陸續(xù)把即將要運(yùn)行的頁(yè)面調(diào)入內(nèi)存，同時(shí)把暫時(shí)不運(yùn)行的頁(yè)面換出到外存上，置換時(shí)以頁(yè)面為單位。實(shí)現(xiàn)將程序正在運(yùn)行時(shí)所需的但尚未在內(nèi)存的頁(yè)面調(diào)入內(nèi)存，再將內(nèi)存中暫時(shí)不用的頁(yè)面從內(nèi)存置換到外存磁盤上。而我選擇的是FIFO,OPT調(diào)度算法。主要考慮三種情況：1.不缺頁(yè)，此時(shí)我不需要從外存中調(diào)入新的頁(yè)面進(jìn)入內(nèi)存；2.缺頁(yè)，但是內(nèi)存空間塊數(shù)沒(méi)有滿，不需要淘汰內(nèi)存中的頁(yè)面，把缺頁(yè)的頁(yè)面直接調(diào)入內(nèi)存中；3.缺頁(yè)，但是內(nèi)存空間已經(jīng)滿了，訪問(wèn)頁(yè)面時(shí)需要淘汰舊的的頁(yè)面，從外存中調(diào)入新的頁(yè)面進(jìn)入內(nèi)存中。請(qǐng)求分頁(yè)的具體實(shí)現(xiàn)過(guò)程如圖1圖1請(qǐng)求分頁(yè)流程圖 2.2設(shè)計(jì)說(shuō)明 2.2.1算法分析在進(jìn)

7、程運(yùn)行過(guò)程中，若其所要訪問(wèn)的頁(yè)面不在內(nèi)存，需要把它們調(diào)入內(nèi)存，但已無(wú)空閑已空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送磁盤的對(duì)換區(qū)。但應(yīng)將哪個(gè)頁(yè)面調(diào)出，必須根據(jù)替換算法來(lái)確定。該設(shè)計(jì)采用的是常見(jiàn)置換算法中的先進(jìn)先出(FIFO)、理想型淘汰算法OPT(Optimal Replacement Algorithm）。詳細(xì)算法原理如下：FIFO(先進(jìn)先出算法)基本思想：總是選擇在內(nèi)存駐留時(shí)間最長(zhǎng)的一頁(yè)將其淘汰，因?yàn)樽钤缯{(diào)入內(nèi)存的頁(yè)，不再被使用的可能性比近期調(diào)入內(nèi)存的大。該算法實(shí)現(xiàn)簡(jiǎn)單，只需要把一個(gè)進(jìn)程調(diào)入內(nèi)存的頁(yè)面，按先后次序連結(jié)成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針

8、，使它總是指向最老的頁(yè)面。但是該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁(yè)面經(jīng)常被訪問(wèn)，比如有全局變量、常用函數(shù)，例程等的頁(yè)面，F(xiàn)IFO算法并不能保證這些頁(yè)面不被淘汰。使用FIFO替換算法效率比較低，可能會(huì)比理想型算法要多出一倍。低的原因是：基于處理器按線性順序訪問(wèn)地址空間這一假設(shè)。事實(shí)上，許多時(shí)候，處理器不是按線性順序訪問(wèn)地址空間的。例如，執(zhí)行循環(huán)結(jié)構(gòu)的程序段。使用FIFO算法時(shí)，在未給進(jìn)程或作業(yè)分配足夠它所需要的頁(yè)面數(shù)時(shí)，有時(shí)會(huì)出現(xiàn)分配的頁(yè)面數(shù)增，缺頁(yè)次數(shù)反而增加的現(xiàn)象（Belady現(xiàn)象）。 例如針對(duì)請(qǐng)求序列：1 2 3 4 1 2 5 1 2 3 4 5，若分配3個(gè)可用內(nèi)存塊

9、，使用FIFO算法，一共會(huì)缺頁(yè)9次，缺頁(yè)率：75%；而如果分配4個(gè)可用內(nèi)存塊，則一共會(huì)缺頁(yè)10次，缺頁(yè)率：83.3%。OPT(理想型淘汰算法)基本思想：當(dāng)要調(diào)入一新頁(yè)而必須淘汰一舊頁(yè)時(shí)，所淘汰的頁(yè)是以后不再使用的，或者是以后相當(dāng)長(zhǎng)的時(shí)間內(nèi)不會(huì)使用的。采用理想型替換算法，通?？杀ＷC獲得最低的缺頁(yè)率。但是由于人們目前無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法是無(wú)法實(shí)現(xiàn)的，但是在模擬設(shè)計(jì)中，由于是事先給定一個(gè)頁(yè)面序列，即知道各個(gè)時(shí)刻以前和以后的頁(yè)面出現(xiàn)情況，所以可實(shí)現(xiàn)該算法。在實(shí)際系統(tǒng)中，雖無(wú)法實(shí)現(xiàn)理想型淘汰算法，但是可用它來(lái)評(píng)價(jià)其他替換算法。2.2.2數(shù)

10、據(jù)結(jié)構(gòu) 主函數(shù)運(yùn)用兩個(gè)數(shù)組a、b,數(shù)組a用于存放輸入的待處理頁(yè)面號(hào)，b數(shù)組用于記錄內(nèi)存中頁(yè)面的置換情況。 FIFO（先來(lái)先出算法）：將每次進(jìn)入的頁(yè)面往數(shù)組b的最后添加，當(dāng)缺頁(yè)發(fā)生時(shí)，則淘汰b0即可。定義兩個(gè)變量：是否缺頁(yè)的變量f：f=0時(shí)：表示不缺頁(yè)，不需要淘汰頁(yè)面；f=1時(shí)，表示缺頁(yè)。而缺頁(yè)時(shí)又需要分兩種情況，這時(shí)定義另一個(gè)變量v，來(lái)表示缺頁(yè)時(shí)，內(nèi)存是否有空余：v=1時(shí)：表示發(fā)生缺頁(yè)，但是內(nèi)存空間有空余，不需要淘汰頁(yè)面，直接把缺頁(yè)的頁(yè)面號(hào)調(diào)入內(nèi)存中；v=0時(shí)：表示發(fā)生缺頁(yè)，但是內(nèi)存空間已經(jīng)滿了，需要淘汰頁(yè)面，再把缺頁(yè)的頁(yè)面號(hào)調(diào)入內(nèi)存中。 OPT（理想型淘汰算法）：也是運(yùn)用兩個(gè)跟FIFO算法中

11、一樣含義的數(shù)組a,b.不缺頁(yè)的情況和缺頁(yè)，但是內(nèi)存空間有空余的情況的實(shí)現(xiàn)跟FIFO一樣的，但是主要的區(qū)別是缺頁(yè)但是空間已滿，需要淘汰頁(yè)面的情況，OPT中淘汰頁(yè)面的算法比FIFO中較復(fù)雜。運(yùn)用了HashMap，通過(guò)來(lái)記錄內(nèi)存空間數(shù)組b中的每一個(gè)元素在a中即將訪問(wèn)的頁(yè)面號(hào)中對(duì)應(yīng)的最遠(yuǎn)的位置，以便來(lái)確定a中在內(nèi)存空間的但未被訪問(wèn)的頁(yè)面的最遠(yuǎn)的頁(yè)面號(hào)的距離。也通過(guò)一個(gè)返回類型為HashMap的函數(shù)：compare（a，b，i）來(lái)實(shí)現(xiàn)求得對(duì)應(yīng)的最遠(yuǎn)距離的元素，從何確定應(yīng)該淘汰內(nèi)存中的哪一個(gè)頁(yè)面。在OPT中也定義兩個(gè)變量：是否缺頁(yè)的變量f：f=0時(shí)：表示不缺頁(yè)，不需要淘汰頁(yè)面；f=1時(shí)，表示缺頁(yè)。而缺頁(yè)時(shí)

12、又需要分兩種情況，這時(shí)定義另一個(gè)變量v，來(lái)表示缺頁(yè)時(shí)，內(nèi)存是否有空余：v=1時(shí)：表示發(fā)生缺頁(yè)，但是內(nèi)存空間有空余，不需要淘汰頁(yè)面，直接把缺頁(yè)的頁(yè)面號(hào)調(diào)入內(nèi)存中；v=0時(shí)：表示發(fā)生缺頁(yè)，但是內(nèi)存空間已經(jīng)滿了，需要淘汰頁(yè)面，再把缺頁(yè)的頁(yè)面號(hào)調(diào)入內(nèi)存中。3源程序的主要部分3.1主函數(shù)輸入輸出部分：public static void main(String arge) throws IOExceptionSystem.out.print(請(qǐng)輸入頁(yè)面使用列表,以空格分開:); Scanner sc = new Scanner(System.in); String input = sc.nextLine

13、(); String aList = input.split(s); int aFIFO = new intaList.length; int aOPT = new intaList.length; try for( int strIndex = 0; strIndex aList.length; strIndex+ ) aFIFOstrIndex = Integer.valueOf( aListstrIndex); aOPTstrIndex = Integer.valueOf( aListstrIndex); catch(Exception e) System.out.println(輸入的

14、必須是數(shù)字,請(qǐng)重新開始！); System.exit(0); System.out.print( 請(qǐng)輸入內(nèi)存空間大小: ); Scanner bsc = new Scanner(System.in); int bLength = bsc.nextInt(); System.out.println( bLength );if( bLength = 0 )System.out.println( 內(nèi)存空間輸入錯(cuò)誤，當(dāng)前輸入為0 ); System.exit(0); int bFIFO = new intbLength;int bOPT = new intbLength;for( int bIndex

15、 = 0; bIndex bLength; bIndex+ )bFIFObIndex = -2;bOPTbIndex = -2;Person person = new Person();System.out.println( FIFO );person.fifo(aFIFO, bFIFO); System.out.println(nOPT);person.opt(aFIFO, bOPT);3.2 FIFO主要代碼：public void fifo( int a, int b ) int count = 0; /用來(lái)記錄缺頁(yè)的次數(shù)int n = a.length;int m = b.length

16、;int i,j,f,v;for( i = 0; i n; i+ )f = 1; /f=1：表示缺頁(yè)，需要淘汰頁(yè)面；f=0：表示不缺頁(yè)v = 0; /v=1：表示發(fā)生缺頁(yè)！內(nèi)存有空余，可直接調(diào)入內(nèi)存；v=0；發(fā)生缺頁(yè)，內(nèi)存空間已滿，需要淘汰頁(yè)面for( j = 0; j m; j+ )if( bj = ai ) /表示不缺頁(yè)f = 0;if( bj = -2) /b【j】的初始值為-2，表示發(fā)生缺頁(yè)，但內(nèi)存有空余 v = 1;break;if( f = 0 )System.out.println( 不缺頁(yè) ); else if( v = 1 ) System.out.print(ai + );

17、System.out.println(發(fā)生缺頁(yè)！內(nèi)存有空余，可直接調(diào)入內(nèi)存);bj =a i;count+; else System.out.print(ai);System.out.print(發(fā)生缺頁(yè)! 淘汰頁(yè)面為： + b0); /每次發(fā)生缺頁(yè)時(shí)都淘汰b0/*淘汰頁(yè)面的過(guò)程，因?yàn)槿表?yè)時(shí)都淘汰b0，故淘汰頁(yè)面時(shí)將b1m-1向前移動(dòng)，即bj=bj+1 * 而把新調(diào)入內(nèi)存的頁(yè)面號(hào)加入到數(shù)組的最后一個(gè)元素b【m-1中*/System.out.println();for(j=0;jm-1;j+)bj=bj+1; bm-1=ai;count+;System.out.print(內(nèi)存空間的存儲(chǔ)情況為：

18、 );for( int t = 0; t b.length; t+ )System.out.print(bt + );System.out.println( );double rate = (double)count/n;System.out.println(發(fā)生缺頁(yè)的次數(shù): + count);System.out.println(缺頁(yè)率為： + rate);3.3 OPT主要代碼：public void opt(int a,int b)int count = 0; /用來(lái)記錄缺頁(yè)的次數(shù)int n = a.length;int m = b.length;int i,j,f,v; for( i

19、= 0; i n; i+ )f = 1;v = 0;for( j = 0; j m; j+ ) if( bj = ai) f = 0;if( bj = -2 ) v = 1;break;if( f = 0 ) System.out.println(不缺頁(yè));else if( v = 1 ) System.out.print( ai + );System.out.println( 發(fā)生缺頁(yè)！內(nèi)存有空余，可直接調(diào)入內(nèi)存 );bj = ai;count+;elseint distance = 0; /表示b中的所有元素中在a中最遠(yuǎn)的的下標(biāo)int bFarEstIndex = 0; /表示要淘汰的頁(yè)面

20、在b中的下標(biāo)HashMap targetMap = compare( b, a, i );for( int bIndex = 0; bIndex b.length; bIndex+ )if( targetMap.get( bbIndex ) = 0 ) /表示bbIndex在a未被訪問(wèn)的頁(yè)面號(hào)中再也不會(huì)出現(xiàn)，直接淘汰，跳出循環(huán)System.out.print( ai );System.out.println( 發(fā)生缺頁(yè)! 淘汰頁(yè)面為： + bbIndex );bbIndex = a i;count+;break; else if( distance targetMap.get( bbIndex

21、 ) )bFarEstIndex = bIndex;distance = targetMap.get( bbIndex );if( distance != 0 )System.out.print( ai );System.out.println( 發(fā)生缺頁(yè)! 淘汰頁(yè)面為： + bbFarEstIndex);count+;bbFarEstIndex = ai;System.out.print( 內(nèi)存空間的存儲(chǔ)情況為： );for( int t = 0; t b.length; t+ )System.out.print(bt + );System.out.println( );double rat

22、e = (double)count/n;System.out.println(發(fā)生缺頁(yè)的次數(shù): + count);System.out.println(缺頁(yè)率為： + rate);/*aIndex是指a中即將要訪問(wèn)的的頁(yè)面號(hào)的下標(biāo)， * compare()函數(shù)運(yùn)用HashMap，通過(guò)它的key，value值來(lái)求內(nèi)存空間數(shù)組b中的每一個(gè)元素在a中即將被訪問(wèn)的頁(yè)面號(hào)中的各自最遠(yuǎn)的的位置， * key對(duì)應(yīng)著bNum，而value值對(duì)應(yīng)著最遠(yuǎn)距離。即bNum中記錄著b中每個(gè)元素在a中的最遠(yuǎn)距離*/public HashMap compare( int b, int a ,int aIndex )Has

23、hMap targetMap = new HashMap();for( int bNum : b ) targetMap.put( bNum , 0 ); /for( int index = aIndex+1 ; index a.length; index+ )int aTemp = aindex; /依次把a(bǔ)中即將要訪問(wèn)的的頁(yè)面號(hào)后面未被訪問(wèn)的頁(yè)面號(hào)賦給aTempfor( int bNum : b ) /遍歷數(shù)組b，把b每個(gè)元素的再即將訪問(wèn)的a中的最遠(yuǎn)距離放入其元素bNum中if( bNum = aTemp )targetMap.put( bNum , index );/把對(duì)應(yīng)的最遠(yuǎn)下標(biāo)放入

24、bNum中return targetMap;4 測(cè)試用例，運(yùn)行結(jié)果與運(yùn)行情況分析1. 輸入的頁(yè)面號(hào)為：1 2 3 4 1 2 5 1 2 3 4 5內(nèi)存空間塊數(shù)：4輸出結(jié)果為：2.輸入的頁(yè)面號(hào)為：1 2 3 4 1 2 5 1 2 3 4 5內(nèi)存空間塊數(shù)：4輸出結(jié)果為：2. 輸入的頁(yè)面號(hào)為：2 3 4 5 1 2 3 4 1 5內(nèi)存空間塊數(shù)：3輸出結(jié)果為：5 自我評(píng)價(jià)與總結(jié) 本周我們進(jìn)行了系統(tǒng)軟件開發(fā)實(shí)訓(xùn)的課程設(shè)計(jì)，在拿到題目以后便著手準(zhǔn)備，通過(guò)查閱課本和相關(guān)的資料，對(duì)本次課程設(shè)計(jì)要實(shí)現(xiàn)的功能有了深刻的了解，在此基礎(chǔ)上寫起實(shí)驗(yàn)代碼變得心應(yīng)手。現(xiàn)將本次課程設(shè)計(jì)總結(jié)如下：本次課程設(shè)計(jì)順利的實(shí)現(xiàn)了對(duì)

25、頁(yè)面置換算法FIFO和OPT的模擬演示。通過(guò)本次課程設(shè)計(jì),加深了對(duì)操作系統(tǒng)的認(rèn)識(shí),了解了操作系統(tǒng)中各種資源分配算法的實(shí)現(xiàn),特別是對(duì)虛擬存儲(chǔ),頁(yè)面置換有了深入的了解,并且用java來(lái)實(shí)現(xiàn)了該實(shí)驗(yàn)，提高了自己的編程能力，同時(shí)也使自己對(duì)java的熟悉能力提高了很多。頁(yè)面置換算法FIFO和 OPT理解起來(lái)相當(dāng)容易，但在實(shí)際編程實(shí)現(xiàn)的時(shí)候需要注意各種細(xì)節(jié)，需要耐心細(xì)致，實(shí)際編程中遇到一些細(xì)節(jié)上的小問(wèn)題確實(shí)需要仔細(xì)考慮才行。從實(shí)驗(yàn)結(jié)果分析可知，OPT置換算法的效率要高于FIFO置換算法，這也符合理論分析。遺憾的是，OPT算法無(wú)法在操作系統(tǒng)中實(shí)現(xiàn)，因?yàn)樗蟊仨氼A(yù)先知道每一個(gè)進(jìn)程的訪問(wèn)串。本次課程設(shè)計(jì)中的不

26、足之處在于所采用的數(shù)據(jù)結(jié)構(gòu)不夠合理，輸入的頁(yè)面序列是保存在一個(gè)數(shù)組中，有最大長(zhǎng)度的限制，應(yīng)該采用像動(dòng)態(tài)鏈表等數(shù)據(jù)結(jié)構(gòu)，減少靜態(tài)方法的限制。通過(guò)這次課程設(shè)計(jì)，進(jìn)一步的加深了對(duì)課本上知識(shí)的理解和掌握，更深的體會(huì)到了操作系統(tǒng)的構(gòu)造性能在計(jì)算機(jī)系統(tǒng)中的重要性，更深貼的體會(huì)到了實(shí)踐的重要性，只有將在課堂上學(xué)到的知識(shí)融入于實(shí)踐中，才能鍛煉我們的思維能力、培養(yǎng)我們學(xué)以致用靈感，在以后的學(xué)習(xí)中，在學(xué)好理論知識(shí)的同時(shí)，我會(huì)更加重視每一次實(shí)驗(yàn)，使自己能更好的將知識(shí)用于實(shí)踐中。最后，感謝在課程設(shè)計(jì)過(guò)程中給予我?guī)椭耐瑢W(xué)和在檢查驗(yàn)收過(guò)程中提出本次課程設(shè)計(jì)中不足之處的老師，是你們的幫助和指正讓我明白的自己的不足，謝謝你

27、們!本科生課程設(shè)計(jì)成績(jī)?cè)u(píng)定表班級(jí)：計(jì)算機(jī)1102班姓名：田藍(lán)學(xué)號(hào)：0121110340232序號(hào)評(píng)分項(xiàng)目滿分實(shí)得分1學(xué)習(xí)態(tài)度認(rèn)真、遵守紀(jì)律102設(shè)計(jì)分析合理性103設(shè)計(jì)方案正確性、可行性、創(chuàng)造性204設(shè)計(jì)結(jié)果正確性405設(shè)計(jì)報(bào)告的規(guī)范性106設(shè)計(jì)驗(yàn)收10總得分/等級(jí)評(píng)語(yǔ)：注：最終成績(jī)以五級(jí)分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下為不及格指導(dǎo)教師簽名：2014 年月日附件：源代碼：import java.io.*;import java.util.HashMap;import java.util.Scanner;public clas

28、s Person /先入先出的調(diào)度算法過(guò)程public void fifo( int a, int b ) int count = 0; /用來(lái)記錄缺頁(yè)的次數(shù)int n = a.length;int m = b.length;int i,j,f,v;for( i = 0; i n; i+ )f = 1; /f=1：表示缺頁(yè)，需要淘汰頁(yè)面；f=0：表示不缺頁(yè)v = 0; /v=1：表示發(fā)生缺頁(yè)！內(nèi)存有空余，可直接調(diào)入內(nèi)存；v=0；發(fā)生缺頁(yè)，內(nèi)存空間已滿，需要淘汰頁(yè)面for( j = 0; j m; j+ )if( bj = ai ) /表示不缺頁(yè)f = 0;if( bj = -2) /b【j】的

29、初始值為-2，表示發(fā)生缺頁(yè)，但內(nèi)存有空余 v = 1;break;if( f = 0 )System.out.println( 不缺頁(yè) ); else if( v = 1 ) System.out.print(ai + );System.out.println(發(fā)生缺頁(yè)！內(nèi)存有空余，可直接調(diào)入內(nèi)存);bj =a i;count+; else System.out.print(ai);System.out.print(發(fā)生缺頁(yè)! 淘汰頁(yè)面為： + b0); /每次發(fā)生缺頁(yè)時(shí)都淘汰b0/*淘汰頁(yè)面的過(guò)程，因?yàn)槿表?yè)時(shí)都淘汰b0，故淘汰頁(yè)面時(shí)將b1m-1向前移動(dòng)，即bj=bj+1 * 而把新調(diào)入內(nèi)存的

30、頁(yè)面號(hào)加入到數(shù)組的最后一個(gè)元素b【m-1中*/System.out.println();for(j=0;jm-1;j+)bj=bj+1; bm-1=ai;count+;System.out.print(內(nèi)存空間的存儲(chǔ)情況為： );for( int t = 0; t b.length; t+ )System.out.print(bt + );System.out.println( );double rate = (double)count/n;System.out.println(發(fā)生缺頁(yè)的次數(shù): + count);System.out.println(缺頁(yè)率為： + rate);/最佳調(diào)度算法

31、public void opt(int a,int b)int count = 0; /用來(lái)記錄缺頁(yè)的次數(shù)int n = a.length;int m = b.length;int i,j,f,v; for( i = 0; i n; i+ )f = 1;v = 0;for( j = 0; j m; j+ ) if( bj = ai) f = 0;if( bj = -2 ) v = 1;break;if( f = 0 ) System.out.println(不缺頁(yè));else if( v = 1 ) System.out.print( ai + );System.out.println( 發(fā)生

32、缺頁(yè)！內(nèi)存有空余，可直接調(diào)入內(nèi)存 );bj = ai;count+;elseint distance = 0; /表示b中的所有元素中在a中最遠(yuǎn)的的下標(biāo)int bFarEstIndex = 0; /表示要淘汰的頁(yè)面在b中的下標(biāo)HashMap targetMap = compare( b, a, i );for( int bIndex = 0; bIndex b.length; bIndex+ )if( targetMap.get( bbIndex ) = 0 ) /表示bbIndex在a未被訪問(wèn)的頁(yè)面號(hào)中再也不會(huì)出現(xiàn)，直接淘汰，跳出循環(huán)System.out.print( ai );System

33、.out.println( 發(fā)生缺頁(yè)! 淘汰頁(yè)面為： + bbIndex );bbIndex = a i;count+;break; else if( distance targetMap.get( bbIndex ) )bFarEstIndex = bIndex;distance = targetMap.get( bbIndex );if( distance != 0 )System.out.print( ai );System.out.println( 發(fā)生缺頁(yè)! 淘汰頁(yè)面為： + bbFarEstIndex);count+;bbFarEstIndex = ai;System.out.pr

34、int( 內(nèi)存空間的存儲(chǔ)情況為： );for( int t = 0; t b.length; t+ )System.out.print(bt + );System.out.println( );double rate = (double)count/n;System.out.println(發(fā)生缺頁(yè)的次數(shù): + count);System.out.println(缺頁(yè)率為： + rate);/*aIndex是指a中即將要訪問(wèn)的的頁(yè)面號(hào)的下標(biāo)， * compare()函數(shù)運(yùn)用HashMap，通過(guò)它的key，value值來(lái)求內(nèi)存空間數(shù)組b中的每一個(gè)元素在a中即將被訪問(wèn)的頁(yè)面號(hào)中的各自最遠(yuǎn)的的位置， * key對(duì)應(yīng)著bNum，而value值對(duì)應(yīng)著最遠(yuǎn)距離。即bNum中記錄著b中每個(gè)元素在a中的最遠(yuǎn)距離*/public HashMap compare( int b, int a ,int aIndex )HashMap targetMap = new HashMap();for( int bNum : b ) targetMap.put( bNum , 0 ); /for( int index = aIndex+1 ; index a.