操作系統(tǒng)課程設(shè)計-模擬請求分頁調(diào)度算法

操作系統(tǒng)課程設(shè)計報告院（系）：計算機(jī)工程學(xué)院專業(yè)：計算機(jī)科學(xué)與技術(shù)專業(yè)題目：模擬請求分頁調(diào)度算法＿＿＿＿＿學(xué)生姓名:班級：學(xué)號:起迄日期:設(shè)計地點:指導(dǎo)教師:課程設(shè)計目的操作系統(tǒng)是管理計算機(jī)硬件的軟件。它也為應(yīng)用程序提供一個基礎(chǔ)，在計算機(jī)用戶與計算機(jī)硬件之間扮演一個中間者的角色。在完成操作系統(tǒng)各部分實驗的基礎(chǔ)上，對操作系統(tǒng)的整體進(jìn)行一個模擬，通過實踐加深對各個部分的管理功能的認(rèn)識，還能進(jìn)一步分析各個部分之間的聯(lián)系，最后達(dá)到對完整系統(tǒng)的理解。本課程設(shè)計的目的綜合應(yīng)用學(xué)生所學(xué)知識，建立系統(tǒng)和完整的計算機(jī)系統(tǒng)概念，理解和鞏固操作系統(tǒng)基本理論、原理和方法，掌握多道程序設(shè)計基本技能。研究計算機(jī)操作系統(tǒng)的基本原理和算法，掌握操作系統(tǒng)的進(jìn)程管理、存儲管理、文件管理和設(shè)備管理的基本原理與主要算法。目的是使學(xué)生掌握常用操作系統(tǒng)的一般管理方法，了解它是如何組織和運(yùn)作的，對操作系統(tǒng)的核心概念和算法有一個透徹的理解，并對系統(tǒng)運(yùn)行的機(jī)制有一個全面的掌握，從而充分理解系統(tǒng)調(diào)用與程序設(shè)計之間的關(guān)系。由于本課程設(shè)計比較復(fù)雜，因此也鍛煉了同學(xué)們在編程方面的能力和解決實際問題的能力，在軟件開發(fā)方面，也提高了創(chuàng)新的能力；由于在設(shè)計的同時必須查閱大量的資料和書籍，所以也鍛煉的調(diào)查研究查閱技術(shù)文獻(xiàn)以及編寫軟件設(shè)計文檔的能力。課程設(shè)計內(nèi)容在進(jìn)程運(yùn)行過程中，當(dāng)所要訪問的頁面不在內(nèi)存時，則應(yīng)將它調(diào)入內(nèi)存。假如在此時內(nèi)存已無空閑空間，則應(yīng)選擇一頁調(diào)出。將哪個頁面調(diào)出，則須根據(jù)一定的算法來確定。需要調(diào)入頁面時，選擇內(nèi)存中哪個物理頁面被置換。把未來不再使用的或短期內(nèi)較少使用的頁面調(diào)出，通常只能在局部性原理指導(dǎo)下依據(jù)過去的統(tǒng)計數(shù)據(jù)進(jìn)行預(yù)測。模擬仿真請求分頁調(diào)度算法OPT、FIFO、LRU、LFU、CLOCK等模擬頁面調(diào)度算法，并提供性能比較分析功能。通過編寫和調(diào)試存儲管理的模擬程序以加深對存儲管理方案的理解。熟悉虛存管理的各種頁面淘汰算法。通過編寫和調(diào)試地址轉(zhuǎn)換過程的模擬程序以加強(qiáng)對地址轉(zhuǎn)換過程的了解。系統(tǒng)分析與設(shè)計系統(tǒng)分析操作系統(tǒng)中的請求分頁系統(tǒng)是建立在基本分頁基礎(chǔ)上的，為了能支持虛擬存儲功能而增加了調(diào)頁功能和頁面置換功能。每當(dāng)程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表后，得到該頁在外存的物理塊后，如果此時內(nèi)存能容納新頁，則啟動磁盤I/O將所卻之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出；如果該頁未被修改，可不必將該頁寫回磁盤；但如果此頁已被修改，則必須將它寫回磁盤，然后再把所缺的也調(diào)入內(nèi)存，并修改頁表中的相應(yīng)表項，置其存在位為“1”，并將此頁表項寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個頁面的調(diào)入過程對用戶是透明的。2、系統(tǒng)設(shè)計：在運(yùn)行過程中，若其所要訪問的頁面不再內(nèi)存而需把它們掉入內(nèi)存，應(yīng)將哪個頁面調(diào)出需根據(jù)一定的算法來確定，置換算法的好壞將直接影響到系統(tǒng)的性能。一個好的頁面置換算法應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不會再訪問的頁面換出，或把那些再較長時間內(nèi)不會再訪問的頁面調(diào)出。①最佳置換算法(Optimal)：它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。但由于人目前還無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，便可以利用此算法來評價其它算法。②先進(jìn)先出(FIFO)頁面置換算法：這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，因此對首總是最先進(jìn)去的頁面，這樣置換總是位于隊首的一頁。③LRU置換算法：最近最久未使用（LRU）置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無法預(yù)測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法可利用一個特殊的棧來保存當(dāng)前使用的各個頁面的頁面號，每當(dāng)進(jìn)程訪問某頁面時，便將該頁面的頁面號從該棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用的頁面。④CLOCK置換算法：簡單CLOCK置換算法只需為每頁設(shè)置一位訪問位，當(dāng)頁面被訪問時，其訪問位置1.置換算法在選擇一位淘汰時，只需檢查頁的訪問位。如果是0，則選擇該頁換出，如果是1，則重新將它置為0，暫不換出，而給該頁第二次駐留內(nèi)存的機(jī)會，在按照FIFO算法檢查第一個頁面。LRU算法是較好的一種算法，而由于LRU在硬件上要求較多，在實際應(yīng)用中多采用LRU的近似算法。CLOCK算法就是用得較多的一種LRU近似算法。⑤最少使用(LFU:LeastFrequentlyUsed)置換算法：在采用該算法時，應(yīng)為在內(nèi)存中的每個頁面設(shè)置一個二維數(shù)組來記錄每個頁面被訪問的頻率。該置換算法選擇在最近時期使用最少的頁面為淘汰頁。3、模塊設(shè)計：1）涉及的抽象數(shù)據(jù)類型集合（ArrayList）：集合可以隨著元素的增加而自定增加長度，也可刪除指定的元素，在指定的位置增加元素。隊列（Queue）：定義了一個可以先進(jìn)先出的數(shù)組，進(jìn)入時在隊尾加入，出隊時只能是隊首。棧（Stack）：定義了一個先進(jìn)后出的數(shù)組，進(jìn)棧和出棧都是在棧頂執(zhí)行的。二維數(shù)組：定義了第二維的元素就是第一維元素的標(biāo)志位。2）主程序的流程以及模塊之間的層次關(guān)系圖1：程序模塊圖4、數(shù)據(jù)結(jié)構(gòu)說明：集合：定義了用來存放所有頁面索引號的序列的一個集合，同時也定義了一個表示物理快的集合，用來存放內(nèi)存中物理塊所存放的頁面號，在使用過程中可以隨時增加和刪除，用在頁面置換時，可以在指定位置增加和刪除元素。隊列：定義了一個與內(nèi)存物理塊容量相同的隊列，同內(nèi)存快一樣用來存放頁面號，充分體現(xiàn)類先進(jìn)先出的作用，在FIFO算法中可以隨時找出要置換的頁面號，即位于隊首的頁面。棧：定義了一個與內(nèi)存物理塊容量相同的隊列，同內(nèi)存快一樣用來存放頁面號。每當(dāng)進(jìn)程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用的頁面號。二維數(shù)組：在Clock算法中，定義一個二維數(shù)組，即給在內(nèi)存中的每個頁面號都定義一個訪問位，在根據(jù)算法來找到要置換的頁面號；在LFU算法中定義一個二維數(shù)組，給每個頁面號都定義一個訪問位來計算被訪問的頻率，最后比較頻率來得出應(yīng)該被置換的頁面號。5、算法流程圖：主程序流程圖：圖2：主程序流程圖實現(xiàn)各個算法的流程圖：圖3：FIFO算法流程圖圖4：OPT算法程序流程圖圖5：LRU算法程序流程圖圖6：Clock算法程序流程圖圖7：LFU算法流程圖四、模塊調(diào)試與系統(tǒng)測試1、模塊調(diào)試輸入的數(shù)據(jù)可以通過自動產(chǎn)生隨機(jī)數(shù)獲得，也可以通過輸入獲得。自動產(chǎn)生的隨機(jī)數(shù)是為16個1~9的隨機(jī)int型數(shù)，而輸入獲得的數(shù)則是小于或等于16個的1~9的int型數(shù)。如果輸入的是字符或超過了1~9的范圍則會出現(xiàn)錯誤提示，并且在清除后可在重新輸入。輸出是1~9的頁面號，即輸出在訪問每個頁面時內(nèi)存中物理塊的頁面號的情況，同時也輸出每種算法的缺頁次數(shù)和缺頁率，以及每個算法的基本性能。程序所能達(dá)到的基本功能是根據(jù)所選的算法輸出運(yùn)用該算法在內(nèi)存中的頁面調(diào)度情況，并根據(jù)缺頁情況算出該算法的缺頁率，同時給出該算法的一些基本特點。在提供索引號的時候可以通過隨機(jī)獲取，也可以自行輸入，并且可以隨時清除所輸入或顯示的內(nèi)容，并可以無限循環(huán)的展現(xiàn)不同索引序列所表示的不同頁面調(diào)度情況。2、系統(tǒng)測試測試方法黒盒測試測試報告：表一：測試分析表測試數(shù)據(jù)輸入預(yù)期輸出結(jié)果實際輸出結(jié)果是否符合預(yù)定結(jié)果隨機(jī)輸入：4514417346448482得到正確的索引號（1~9）序列，在選擇不同的算法條件下輸出正確的頁面調(diào)度情況，以及正確的缺頁率索引號序列正確，頁面調(diào)度情況正確，缺頁率也正確符合預(yù)定結(jié)果固定輸入：2452673得到正確的索引號（1~9）序列，在選擇不同的算法條件下輸出正確的頁面調(diào)度情況，以及正確的缺頁率索引號序列正確，頁面調(diào)度情況正確，缺頁率也正確符合預(yù)定結(jié)果固定輸入：24674812系統(tǒng)提示：輸入格式錯誤，輸入1~9的數(shù)系統(tǒng)提示：輸入格式錯誤，輸入1~9的數(shù)符合預(yù)定結(jié)果固定輸入：2464dr6系統(tǒng)提示：輸入格式錯誤，輸入1~9的數(shù)系統(tǒng)提示：輸入格式錯誤，輸入1~9的數(shù)符合預(yù)定結(jié)果在未輸入索引號的情況下選擇算法系統(tǒng)提示：還未得到索引號系統(tǒng)提示：還未得到索引號符合預(yù)定結(jié)果3、調(diào)試分析：1）在實現(xiàn)LRU算法時，要將棧中指定的元素移到棧頂，但是一開始這個方法在運(yùn)行到一定的頁面序列后會出現(xiàn)索引越界的異常，通過與同學(xué)一晚上的討論，最后修改了一下算法，從而算法能夠準(zhǔn)確的實現(xiàn)。2）在實現(xiàn)Clock算法時，一開始沒考慮到每次置換頁面后指針會下移一位，導(dǎo)致程序運(yùn)行正確但結(jié)果錯誤，經(jīng)過仔細(xì)研究，最后算法中加入了指針的移動才得到正確的結(jié)果。3）在計算缺頁率時，由于訪問頁面次數(shù)不是固定的，得到的缺頁率可能是一個無限循環(huán)的小數(shù)，因此經(jīng)過在網(wǎng)上查找相關(guān)資料后用，用一個方法即可只輸出小數(shù)點后兩位。4）在增加了手動輸入索引號后，要再次使用算法時會出現(xiàn)異常，經(jīng)過加入異常捕獲后，就可以循環(huán)輸入索引號并使用算法了。5）在實現(xiàn)Clock算法時，由于語言限制無法使用指針和鏈表，致使算法實現(xiàn)的比較復(fù)雜，同時也限制了物理塊的塊數(shù)，因此不能增加隨意選擇物理塊數(shù)的功能。五、用戶手冊本程序使用的平臺是VisualStudio2008，需要安裝該軟件，直接雙擊安裝即可。將本程序在VisualStudio2008中打開，然后點擊“啟動調(diào)試”即可運(yùn)行出界面。eq\o\ac(○,1)如果想要獲得隨機(jī)的頁面號序列，則直接點擊按鈕“得到隨機(jī)索引號”即可，在相應(yīng)的文本框中就會顯示索引頁面號，然后在“選擇置換算法”下面的ComoBox控件下拉選項中選擇所要用的算法，即可顯示出頁面調(diào)用情況以及該算法的缺頁率和其基本特點。eq\o\ac(○,2)如果要有用戶自己輸入頁面索引序列，則將“固定輸入”控件選中，然后在“引用率”文本框中輸入頁面號序列（個數(shù)必須小于或等于16），然后按“得到索引號”按鈕，最后選擇同1一樣選擇算法即可。eq\o\ac(○,3)如果輸入錯誤，則可以按“清空”按鈕清除所有顯示的內(nèi)容。本程序可以循環(huán)使用得到不同的索引序列，以及不同的頁面調(diào)度情況。六、程序清單列出主要/關(guān)鍵算法的程序清單，要求加上詳細(xì)的程序注釋（函數(shù)體/過程注釋，與語句行注釋）usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Windows.Forms;usingSystem.Collections;namespaceWindowsFormsApplication1{publicpartialclassForm1:Form{ArrayListpageOrder;//定義存放索引號序列的集合inttextchoice=0;//定義全局變量來確定將輸出放到哪個文本框中doubleMissingRate;//聲明缺頁率的變量intpagecount;//定義所訪問到的頁面數(shù)變量TextBox[]text;//存放內(nèi)存頁面號的文本框的數(shù)組TextBox[]order;//存放索引號的文本框的數(shù)組privatedoublediseffect=0;//定義一個變量diseffect記錄總共換入頁面的次數(shù)。publicdoubleDiseffect{get{returndiseffect;}set{diseffect=value;}}//判斷是否在內(nèi)存中publicboolInmemory(ArrayLista,intt){for(inti=0;i<a.Count;i++){if((int)a[i]==t)returntrue;}returnfalse;}//判斷內(nèi)存是否已滿publicboolIsFull(ArrayLista){if(a.Count==a.Capacity)returntrue;elsereturnfalse;}//若頁面經(jīng)過了置換則將內(nèi)存中頁面狀況打印出來publicvoidPrint(ArrayLista){if(a.Count==1){text[textchoice].Text=a[0].ToString();textchoice+=3;}if(a.Count==2){text[textchoice].Text=a[0].ToString();textchoice++;text[textchoice].Text=a[1].ToString();textchoice+=2;}if(a.Count==3){for(inti=0;i<a.Count;i++){text[textchoice].Text=a[i].ToString();textchoice++;}}}//若沒有發(fā)生頁面置換則不打印頁面publicvoidPrintp(ArrayLista){if(a.Count==1){text[textchoice].Text="";textchoice+=3;}if(a.Count==2){text[textchoice].Text="";textchoice++;text[textchoice].Text="";textchoice+=2;}if(a.Count==3){for(inti=0;i<a.Count;i++){text[textchoice].Text="";textchoice++;}}}#regionFIFO算法//FIFO置換算法publicvoidFIFOpage(){ArrayListpageList=newArrayList(3);Queuequ=newQueue(3);inttemp,m;try{if(txtpageorder.Text=="")//若未得到索引號，則拋出異常thrownewException();for(inti=0;i<pageOrder.Count;i++)//根據(jù)進(jìn)程的頁面號來訪問頁面{if(!Inmemory(pageList,(int)pageOrder[i]))//當(dāng)前訪問的頁面號不在內(nèi)存中{if(!IsFull(pageList))//內(nèi)存未滿{pageList.Add(pageOrder[i]);qu.Enqueue(pageOrder[i]);}else//內(nèi)存已存滿{temp=(int)qu.Dequeue();//得到要被置換出來的值qu.Enqueue(pageOrder[i]);m=pageList.IndexOf(temp);//得到被置換的位置pageList.RemoveAt(m);//從內(nèi)存中取出pageList.Insert(m,pageOrder[i]);//放入到取出的位置Diseffect++;}Print(pageList);//打印內(nèi)存頁面情況}else//在內(nèi)存中{Printp(pageList);}}textchoice=0;Missing_Rate();//計算缺頁率//填充ListView控件listView1.Items[1].SubItems.Add(Convert.ToDouble(MissingRate).ToString("0.00")+"%");listView1.Items[1].SubItems.Add("利用歷史信息，但不反映程序的局部性");MissingRate=0;}catch{MessageBox.Show("還沒得到索引號","提示",MessageBoxButtons.OK,MessageBoxIcon.Warning);}}#endregion#regionLRU//將指定棧中的元素放到棧頂publicvoiddelete(Stacks,intnum){int[]a=newint[s.Count];s.CopyTo(a,0);inti=System.Array.IndexOf(a,num);//找到要刪除元素的位置for(intp=i-1;p>=0;p--)//將找到的元素放到數(shù)組首位{a[p+1]=a[p];}a[0]=num;s.Clear();for(intn=a.Count()-1;n>=0;n--)//將數(shù)組復(fù)制到棧中{s.Push(a[n]);}}//LRU置換算法publicvoidLRUpage(){ArrayListpageList=newArrayList(3);Stackstack=newStack();inttemp,m;try{if(txtpageorder.Text=="")//若未得到索引號，則拋出異常thrownewException();for(inti=0;i<pageOrder.Count;i++)//根據(jù)進(jìn)程的頁面號來訪問頁面{if(!Inmemory(pageList,(int)pageOrder[i]))//當(dāng)前訪問的頁面不在內(nèi)存中{if(!IsFull(pageList))//內(nèi)存未滿{pageList.Add(pageOrder[i]);stack.Push(pageOrder[i]);}else//內(nèi)存已存滿{int[]array=newint[stack.Count];stack.CopyTo(array,0);temp=array[stack.Count-1];//得到要被置換出來的值m=pageList.IndexOf(temp);//得到被置換的位置delete(stack,temp);//將指定元素放到棧頂stack.Pop();stack.Push(pageOrder[i]);pageList.RemoveAt(m);//從內(nèi)存中取出pageList.Insert(m,pageOrder[i]);//放入到取出的位置Diseffect++;}Print(pageList);}else//在內(nèi)存中,就將該元素放到棧頂{delete(stack,(int)pageOrder[i]);Printp(pageList);}}textchoice=0;Missing_Rate();//計算缺頁率//填充ListView控件listView1.Items[2].SubItems.Add(Convert.ToDouble(MissingRate).ToString("0.00")+"%");listView1.Items[2].SubItems.Add("計數(shù)器硬件較少，主存頁面表可由軟硬件實現(xiàn)修改，根據(jù)“歷史”預(yù)測“未來”。");MissingRate=0;}catch{MessageBox.Show("還沒得到索引號","提示",MessageBoxButtons.OK,MessageBoxIcon.Warning);}}#endregion#regionLFU//判斷哪個頁面是最少使用的publicintLeast_use(int[,]p,ArrayListlist){inttemp=p[(int)list[0]-1,1];//標(biāo)志位intret=(int)list[0];//頁面號for(inti=0;i<p.GetLength(0);i++){if(p[i,1]<temp&&list.Contains(p[i,0]))//找到內(nèi)存中計數(shù)器值最小的頁面號{temp=p[i,1];ret=p[i,0];//計數(shù)值最小的頁面號}}returnret;}//LFU置換算法publicvoidLFUpage(){//PageOrder();ArrayListpageList=newArrayList(3);int[,]page=newint[9,2];for(intj=0;j<page.GetLength(0);j++)//為每個頁面都定義一個訪問位，初值為0{page[j,0]=j+1;page[j,1]=0;}inttemp,m;try{if(txtpageorder.Text=="")//若未得到索引號，則拋出異常thrownewException();for(inti=0;i<pageOrder.Count;i++){if(!Inmemory(pageList,(int)pageOrder[i]))//頁面不在內(nèi)存中{if(!IsFull(pageList))//內(nèi)存未滿{pageList.Add(pageOrder[i]);page[(int)pageOrder[i]-1,1]++;}else//內(nèi)存已存滿{temp=Least_use(page,pageList);//得到要被置換出來的值m=pageList.IndexOf(temp);//得到被置換的位置pageList.RemoveAt(m);//從內(nèi)存中取出pageList.Insert(m,pageOrder[i]);//放入到取出的位置//頁面置換后，將計數(shù)器清0for(intk=0;k<3;k++){page[(int)pageList[k]-1,1]=0;}page[(int)pageOrder[i]-1,1]++;//置換的頁面標(biāo)志計數(shù)器加1Diseffect++;}Print(pageList);}else//在內(nèi)存中,就將該元素放到棧頂{page[(int)pageOrder[i]-1,1]++;Printp(pageList);}}textchoice=0;Missing_Rate();//計算缺頁率//填充ListView控件listView1.Items[4].SubItems.Add(Convert.ToDouble(MissingRate).ToString("0.00")+"%");listView1.Items[4].SubItems.Add("淘汰一定時期內(nèi)被訪問次數(shù)最少的頁。");MissingRate=0;}catch{MessageBox.Show("還沒得到索引號","提示",MessageBoxButtons.OK,MessageBoxIcon.Warning);}}#endregion#regionOPT//判斷哪個頁面是以后最長時間內(nèi)不用的publicintLong_Not_Use(ArrayListlist,ArrayListpa,intindex){//得到內(nèi)存中每個頁面在集合中的索引號inti=pa.IndexOf(list[0],index);intj=pa.IndexOf(list[1],index);intm=pa.IndexOf(list[2],index);//如果索引號小于0，則表示后面沒有再用到該頁面，即該頁面為要置換的頁面if(i<0)return(int)list[0];if(j<0)return(int)list[1];if(m<0)return(int)list[2];intma,max;//找到索引號最大的頁面，即為未來最久不會用到的頁面，也是應(yīng)被置換的頁面ma=j>m?j:m;max=i>ma?i:ma;if(max==i)return(int)list[0];if(max==j)return(int)list[1];elsereturn(int)list[2];}//置換算法OPTpublicvoidOPTpage(){ArrayListpageList=newArrayList(3);inttemp,m;try{if(txtpageorder.Text=="")//若未得到索引號，則拋出異常thrownewException();for(inti=0;i<pageOrder.Count;i++){if(!Inmemory(pageList,(int)pageOrder[i]))//頁面不在內(nèi)存中{if(!IsFull(pageList))//內(nèi)存未滿{pageList.Add(pageOrder[i]);}else//內(nèi)存已存滿{temp=Long_Not_Use(pageList,pageOrder,i);//得到要被置換出來的值m=pageList.IndexOf(temp);//得到被置換的位置pageList.RemoveAt(m);//從內(nèi)存中取出pageList.Insert(m,pageOrder[i]);//放入到取出的位置Diseffect++;}Print(pageList);}else//在內(nèi)存中{Printp(pageList);}}textchoice=0;Missing_Rate();//計算缺頁率//填充控件listView1.Items[0].SubItems.Add(Convert.ToDouble(MissingRate).ToString("0.00")+"%");listView1.Items[0].SubItems.Add("命中率高，但難于實現(xiàn)，是理想算法。");MissingRate=0;}catch{MessageBox.Show("還沒得到索引號","提示",MessageBoxButtons.OK,MessageBoxIcon.Warning);}}#endregion#region簡單Clock算法//找到要置換的頁面publicintfind_page(ArrayLista,int[,]p){inttemp=(int)a[0];for(inti=0;i<a.Count;i++){if(p[(int)a[i]-1,1]==0)//如果訪問位為0，返回該頁面號{temp=(int)a[i];break;}p[(int)a[i]-1,1]=0;//訪問位為1，暫不換出，將訪問位置0}returntemp;}publicvoidClock_page(){ArrayListpageList=newArrayList(3);ArrayListexchange=newArrayList(3);int[,]page=newint[9,2];for(intj=0;j<page.GetLength(0);j++)//為每個頁面定義一個訪問位{page[j,0]=j+1;page[j,1]=0;}inttemp,m,n;try{if(txtpageorder.Text=="")//若未得到索引號，則拋出異常thrownewException();for(inti=0;i<pageOrder.Count;i++){if(!Inmemory(pageList,(int)pageOrder[i]))//頁面不在內(nèi)存中{if(!IsFull(pageList))//內(nèi)存未滿{pageList.Add(pageOrder[i]);exchange.Add(pageOrder[i]);page[(int)pageOrder[i]-1,1]=1;//該頁面的訪問位置1}else//內(nèi)存已存滿{temp=find_page(exchange,page);//得到要被置換出來的值m=pageList.IndexOf(temp);//得到被置換的位置pageList.RemoveAt(m);//從內(nèi)存中取出pageList.Insert(m,pageOrder[i]);//放入到取出的位置page[(int)pageOrder[i]-1,1]=1;//被置換進(jìn)來的頁面訪問位置1n=exchange.IndexOf(temp);exchange.RemoveAt(n);exchange.Insert(n,pageOrder[i]);//exchange=pageList;//將被置換的位置的下一個頁面作為下次循環(huán)的首次訪問對象if(m==0){inth;h=(int)exchange[0];//h=(int)pageOrder[i];exchange[0]=exchange[1];exchange[1]=exchange[2];exchange[2]=h;}if(m==1){inth;h=(int)exchange[1];exchange[1]=exchange[0];exchange[0]=exchange[2];exchange[2]=h;}Diseffect++;}Print(pageList);}else//在內(nèi)存中{page[(int)pageOrder[i]-1,1]=1;//頁面在內(nèi)存中，則訪問位置1Printp(pageList);}}textchoice=0;Missing_Rate();//計算缺頁率//填充控件listView1.Items[3].SubItems.Add(Convert.ToDouble(MissingRate).ToString("0.00")+"%");listView1.Items[3].SubItems.Add("使用硬件少，是一種LRU近似算法");MissingRate=0;}catch(NullReferenceException){MessageBox.Show("還沒得到索引號","提示",MessageBoxButtons.OK,MessageBoxIcon.Warning);}}#endregion//計算缺頁率，并輸出publicvoidMissing_Rate(){doubled;d=Diseffect/pagecount*100;//計算缺頁率txtMissing.Text=Diseffect.ToString();txtMissingRate.Text=Convert.ToDouble(d).ToString("0.00")+"%";//小數(shù)點后保留兩位小數(shù)MissingRate=d;Diseffect=0;}publicForm1(){InitializeComponent();//將顯示索引號序列的文本框放到一個數(shù)組中order=newTextBox[16]{text1,text2,text3,text4,text5,text6,text7,text8,text9,text10,text11,text12,text13,text14,text15,text16};//將顯示內(nèi)存中頁面號的文本框放到一個數(shù)組中text=newTextBox[48]{txt1,txt2,txt3,txt4,txt5,txt6,txt7,txt8,txt9,txt10,txt11,txt12,txt13,txt14,txt15,txt16,txt17,txt18,txt19,txt20,txt21,txt22,txt23,txt24,txt25,txt26,txt27,txt28,txt29,txt30,txt31,txt32,txt33,txt34,txt35,txt36,txt37,txt38,txt39,txt40,txt41,txt42,txt43,txt44,txt45,txt46,txt47,txt48};//初始化ListView控件listView1.Items.Add("OPT算法",0);listView1.Items.Add("FIFO算法",1);listView1.Items.Add("LRU算法",2);listView1.Items.Add("Clock算法",3);listView1.Items.Add("LFU算法",4);}//得到進(jìn)程頁面的進(jìn)入順序，調(diào)用16個頁面privatevoidbutton1_Click(objectsender,EventArgse){pageOrder=newArrayList();if(checkBox1.Checked)//固定輸入被選中則進(jìn)行輸入形式獲得集索引號{Stringw="";inti;try{for(i=0;i<16;i++){if(order[i].Text=="")//得到輸入數(shù)字的個數(shù){break;}inttemp=int.Parse(order[i].Text);if(temp<1||temp>9)//輸入的數(shù)字不在1~9之間則拋出異常，等待重新輸入thrownewException();pageOrder.Add(temp);w=w+pageOrder[i]+"";}txtpageorder.Text=w;pagecount=i;}catch{MessageBox.Show("輸入格式錯誤，請輸入1~9的數(shù)","提示",MessageBoxButtons.OK,MessageBoxIcon.Warning);}}else{//用獲取隨機(jī)數(shù)來得到16個索引號序列Randomrandom=newRandom();Strings="";for(inti=0;i<16;i++){pageOrder.Add(random.Next(1,9));s=s+pageOrder[i]+"";}txtpageorder.Text=s;for(inti=0;i<pageOrder.Count;i++)//將得到的索引號顯示在相應(yīng)的文本框中{order[i].Text=pageOrder[i].ToString();}pagecount=16;}for(inti=0;i<48;i++)//在重新獲取索引號序列時，前面所顯示的內(nèi)容將清空，{text[i].Text="";}txtMissing.Text="";txtMissingRate.Text="";Diseffect=0;comboBox1.Text="";//清空ListView的內(nèi)容listView1.Items.RemoveAt(4);listView1.Items.RemoveAt(3);listView1.Items.RemoveAt(2);listView1.Items.RemoveAt(1);listView1.Items.RemoveAt(0);listView1.Items.Add("OPT算法",0);listView1.Items.Add("FIFO算法",1);listView1.Items.Add("LRU算法",2);listView1.Items.Add("Clock算法",3);listView1.Items.Add("LFU算法",4);}privatevoidcomboBox1_SelectedIndexChanged(objectsender,EventArgse)//選擇不同的算法{intindex=comboBox1.SelectedIndex;