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

2、以及說明書撰寫等具體要求）1實(shí)現(xiàn)指定淘汰算法。能夠處理以下的情形： 能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)； 能夠輸入給定的頁面，并計(jì)算發(fā)生缺頁的次數(shù)以及缺頁率； 缺頁時(shí)，如果發(fā)生頁面置換，輸出淘汰的頁號(hào)。2設(shè)計(jì)報(bào)告內(nèi)容應(yīng)說明： 課程設(shè)計(jì)目的與功能； 需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明(功能與框圖)； 源程序的主要部分； 測試用例，運(yùn)行結(jié)果與運(yùn)行情況分析； 自我評價(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日請求頁式管理缺頁中斷模擬設(shè)計(jì)FIFO、OPT1課程設(shè)計(jì)目的與功能 1.1設(shè)計(jì)目的 結(jié)合操作系統(tǒng)所學(xué)內(nèi)存頁式管理章節(jié)，掌握虛擬內(nèi)存設(shè)計(jì)的重要性，熟悉和掌握請求分頁式存儲(chǔ)管理的實(shí)現(xiàn)原理，通過分析、設(shè)計(jì)和實(shí)現(xiàn)頁式虛擬存儲(chǔ)管理缺頁中斷的模擬系統(tǒng)，重點(diǎn)掌握當(dāng)請求頁面不在內(nèi)存而內(nèi)存塊已經(jīng)全部被占用時(shí)的替換算法（主要通過FIFO和OPT實(shí)現(xiàn)），并考察替換算法的評價(jià)指標(biāo)缺頁次數(shù)和缺頁率，得到每次淘汰的頁面。高級語言設(shè)計(jì)并實(shí)現(xiàn)出的結(jié)果程序要能夠

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

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

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

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

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

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

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

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

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

13、); String input = sc.nextLine(); 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( aListstrInd

14、ex); catch(Exception e) System.out.println("輸入的必須是數(shù)字,請重新開始！"); System.exit(0); System.out.print( "請輸入內(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" ); Sy

15、stem.exit(0); int bFIFO = new intbLength;int bOPT = new intbLength;for( int bIndex = 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,

16、 bOPT);3.2 FIFO主要代碼：public void fifo( int a, int b ) int count = 0; /用來記錄缺頁的次數(shù)int n = a.length;int m = b.length;int i,j,f,v;for( i = 0; i < n; i+ )f = 1; /f=1：表示缺頁，需要淘汰頁面；f=0：表示不缺頁v = 0; /v=1：表示發(fā)生缺頁！內(nèi)存有空余，可直接調(diào)入內(nèi)存；v=0；發(fā)生缺頁，內(nèi)存空間已滿，需要淘汰頁面for( j = 0; j < m; j+ )if( bj = ai ) /表示不缺頁f = 0;if( bj = -

17、2) /b【j】的初始值為-2，表示發(fā)生缺頁，但內(nèi)存有空余 v = 1;break;if( f = 0 )System.out.println( "不缺頁" ); else if( v = 1 ) System.out.print(ai + " ");System.out.println("發(fā)生缺頁！內(nèi)存有空余，可直接調(diào)入內(nèi)存");bj =a i;count+; else System.out.print(ai);System.out.print("發(fā)生缺頁! 淘汰頁面為：" + b0); /每次發(fā)生缺頁時(shí)都淘汰b

18、0/*淘汰頁面的過程，因?yàn)槿表摃r(shí)都淘汰b0，故淘汰頁面時(shí)將b1m-1向前移動(dòng)，即bj=bj+1 * 而把新調(diào)入內(nèi)存的頁面號(hào)加入到數(shù)組的最后一個(gè)元素b【m-1中*/System.out.println();for(j=0;j<m-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(" ");dou

19、ble rate = (double)count/n;System.out.println("發(fā)生缺頁的次數(shù): " + count);System.out.println("缺頁率為：" + rate);3.3 OPT主要代碼：public void opt(int a,int b)int count = 0; /用來記錄缺頁的次數(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+ ) i

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

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

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

23、; t+ )System.out.print(bt + " ");System.out.println(" ");double rate = (double)count/n;System.out.println("發(fā)生缺頁的次數(shù): " + count);System.out.println("缺頁率為：" + rate);/*aIndex是指a中即將要訪問的的頁面號(hào)的下標(biāo)， * compare()函數(shù)運(yùn)用HashMap，通過它的key，value值來求內(nèi)存空間數(shù)組b中的每一個(gè)元素在a中即將被訪問的頁面號(hào)中的各自最遠(yuǎn)

24、的的位置， * key對應(yīng)著bNum，而value值對應(yīng)著最遠(yuǎn)距離。即bNum中記錄著b中每個(gè)元素在a中的最遠(yuǎn)距離*/public HashMap<Integer,Integer> compare( int b, int a ,int aIndex )HashMap<Integer,Integer> targetMap = new HashMap<Integer, Integer>();for( int bNum : b ) targetMap.put( bNum , 0 ); /for( int index = aIndex+1 ; index <

25、a.length; index+ )int aTemp = aindex; /依次把a(bǔ)中即將要訪問的的頁面號(hào)后面未被訪問的頁面號(hào)賦給aTempfor( int bNum : b ) /遍歷數(shù)組b，把b每個(gè)元素的再即將訪問的a中的最遠(yuǎn)距離放入其元素bNum中if( bNum = aTemp )targetMap.put( bNum , index );/把對應(yīng)的最遠(yuǎn)下標(biāo)放入bNum中return targetMap;4 測試用例，運(yùn)行結(jié)果與運(yùn)行情況分析1. 輸入的頁面號(hào)為：1 2 3 4 1 2 5 1 2 3 4 5內(nèi)存空間塊數(shù)：4輸出結(jié)果為：2.輸入的頁面號(hào)為：1 2 3 4 1 2 5 1

26、 2 3 4 5內(nèi)存空間塊數(shù)：4輸出結(jié)果為：2. 輸入的頁面號(hào)為：2 3 4 5 1 2 3 4 1 5內(nèi)存空間塊數(shù)：3輸出結(jié)果為：5 自我評價(jià)與總結(jié) 本周我們進(jìn)行了系統(tǒng)軟件開發(fā)實(shí)訓(xùn)的課程設(shè)計(jì)，在拿到題目以后便著手準(zhǔn)備，通過查閱課本和相關(guān)的資料，對本次課程設(shè)計(jì)要實(shí)現(xiàn)的功能有了深刻的了解，在此基礎(chǔ)上寫起實(shí)驗(yàn)代碼變得心應(yīng)手?，F(xiàn)將本次課程設(shè)計(jì)總結(jié)如下：本次課程設(shè)計(jì)順利的實(shí)現(xiàn)了對頁面置換算法FIFO和OPT的模擬演示。通過本次課程設(shè)計(jì),加深了對操作系統(tǒng)的認(rèn)識(shí),了解了操作系統(tǒng)中各種資源分配算法的實(shí)現(xiàn),特別是對虛擬存儲(chǔ),頁面置換有了深入的了解,并且用java來實(shí)現(xiàn)了該實(shí)驗(yàn)，提高了自己的編程能力，同時(shí)也使自

27、己對java的熟悉能力提高了很多。  頁面置換算法FIFO和 OPT理解起來相當(dāng)容易，但在實(shí)際編程實(shí)現(xiàn)的時(shí)候需要注意各種細(xì)節(jié)，需要耐心細(xì)致，實(shí)際編程中遇到一些細(xì)節(jié)上的小問題確實(shí)需要仔細(xì)考慮才行。從實(shí)驗(yàn)結(jié)果分析可知，OPT置換算法的效率要高于FIFO置換算法，這也符合理論分析。遺憾的是，OPT算法無法在操作系統(tǒng)中實(shí)現(xiàn)，因?yàn)樗蟊仨氼A(yù)先知道每一個(gè)進(jìn)程的訪問串。本次課程設(shè)計(jì)中的不足之處在于所采用的數(shù)據(jù)結(jié)構(gòu)不夠合理，輸入的頁面序列是保存在一個(gè)數(shù)組中，有最大長度的限制，應(yīng)該采用像動(dòng)態(tài)鏈表等數(shù)據(jù)結(jié)構(gòu)，減少靜態(tài)方法的限制。通過這次課程設(shè)計(jì)，進(jìn)一步的加深了對課本上知識(shí)的理解和掌握，更深的

28、體會(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ī)椭耐瑢W(xué)和在檢查驗(yàn)收過程中提出本次課程設(shè)計(jì)中不足之處的老師，是你們的幫助和指正讓我明白的自己的不足，謝謝你們!本科生課程設(shè)計(jì)成績評定表班級：計(jì)算機(jī)1102班姓名：田藍(lán)學(xué)號(hào)：0121110340232序號(hào)評分項(xiàng)目滿分實(shí)得分1學(xué)習(xí)態(tài)度認(rèn)真、遵守紀(jì)律102設(shè)計(jì)分析合理性103設(shè)計(jì)方案正確性、可行性、創(chuàng)造性204設(shè)

29、計(jì)結(jié)果正確性405設(shè)計(jì)報(bào)告的規(guī)范性106設(shè)計(jì)驗(yàn)收10總得分/等級評語：注：最終成績以五級分制記。優(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 class Person /先入先出的調(diào)度算法過程public void fifo( int a, int b ) int count = 0; /用來記錄缺頁的次數(shù)int n = a.length;int m

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

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

32、);for(j=0;j<m-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ā)生缺頁的次數(shù): " + count);System.out.println(&quo

33、t;缺頁率為：" + rate);/最佳調(diào)度算法public void opt(int a,int b)int count = 0; /用來記錄缺頁的次數(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("不缺頁");else if( v =

34、1 ) System.out.print( ai + " ");System.out.println( "發(fā)生缺頁！內(nèi)存有空余，可直接調(diào)入內(nèi)存" );bj = ai;count+;elseint distance = 0; /表示b中的所有元素中在a中最遠(yuǎn)的的下標(biāo)int bFarEstIndex = 0; /表示要淘汰的頁面在b中的下標(biāo)HashMap<Integer,Integer> targetMap = compare( b, a, i );for( int bIndex = 0; bIndex < b.length; bIndex

35、+ )if( targetMap.get( bbIndex ) = 0 ) /表示bbIndex在a未被訪問的頁面號(hào)中再也不會(huì)出現(xiàn)，直接淘汰，跳出循環(huán)System.out.print( ai );System.out.println( "發(fā)生缺頁! 淘汰頁面為：" + bbIndex );bbIndex = a i;count+;break; else if( distance < targetMap.get( bbIndex ) )bFarEstIndex = bIndex;distance = targetMap.get( bbIndex );if( distan

36、ce != 0 )System.out.print( ai );System.out.println( "發(fā)生缺頁! 淘汰頁面為：" + 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 rate = (double)count/

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