1、操作系統(tǒng)課程設(shè)計報告題目頁面置換算法專業(yè)計算機科學與技術(shù)小組成員:目錄1 .設(shè)計目的22 .課設(shè)要求23 .系統(tǒng)分析34 .系統(tǒng)設(shè)計34.1 問題分析34.2 程序整體框圖54.3 FIFO算法54.4 LRU算法64.5 OPT算法75 .功能與測試85.1 開始界面85.2 FIFO算法95.3 LRU算法1.Q.5.4 OPT算法1.Q.6 .結(jié)論11.7 .附錄12.1 .設(shè)計目的1、存儲治理的主要功能之一是合理地分配空間.請求頁式治理是一種常用的虛擬存儲治理技術(shù).本次設(shè)計的目的是通過請求頁式存儲治理中頁面置換算法模擬設(shè)計,了解虛擬存儲技術(shù)的特點,掌握請求頁式治理的頁面置換算法.2、提

2、升自己的程序設(shè)計水平、提升算法設(shè)計質(zhì)量與程序設(shè)計素質(zhì)；2 .課設(shè)要求設(shè)計一個請求頁式存儲治理方案.并編寫模擬程序?qū)崿F(xiàn)之.要求包含：1 .過隨機數(shù)產(chǎn)生一個指令序列,共320條指令.其地址按下述原那么生成：50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址局部；25%的指令是均勻分布在后地址局部；具體的實施方法是：在0,319的指令地址之間隨機選區(qū)一起點M;順序執(zhí)行一條指令,即執(zhí)行地址為M+1的指令；在前地址0,M+1中隨機選取一條指令并執(zhí)行,該指令的地址為M'順序執(zhí)行一條指令,其地址為M'+1;在后地址M'+2,319中隨機選取一條指令并執(zhí)行；重復AE,直到執(zhí)行32

3、0次指令.2 .指令序列變換成頁地址流設(shè)：1頁面大小為1K;用戶內(nèi)存容量為4頁到32頁；用戶虛存容量為32K.在用戶虛存中,按每K存放10條指令排列虛存地址,即320條指令在虛存中的存放方式為：第0條一第9條指令為第0頁對應(yīng)虛存地址為0,9;第10條一第19條指令為第1頁對應(yīng)虛存地址為10,19;000000000000000000000第310條一第319條指令為第31頁對應(yīng)虛存地址為310,319;按以上方式,用戶指令可組成32頁.3 .計算并輸出下述各種算法在不同內(nèi)存容量下的命中率.FIFO先進先出的算法LRU最近最少使用算法OPT最正確淘汰算法先淘汰最不常用的頁地址3 .系統(tǒng)分析在多道

4、程序環(huán)境下,要使程序運行,必須先為之創(chuàng)立進程.而創(chuàng)立進程的第一步是將程序和數(shù)據(jù)裝入內(nèi)存.存儲器實現(xiàn)的功能主要是內(nèi)存分配等功能,本模擬系統(tǒng)所要實現(xiàn)的就是將進程的程序和數(shù)據(jù)裝入內(nèi)存物理塊.具體需要實現(xiàn)的功能如下：1、讀入進程大小,進行分頁,確定每一頁的指令地址范圍；2、讀入一個指令,確定其所在頁面,讀入內(nèi)存物理塊中.物理塊空閑直接讀入,物理塊已滿,指向下步操作.3、物理塊已滿,將要淘汰原來首先進入到內(nèi)存中的頁面,即換出；然后將現(xiàn)在的指令地址頁面讀入物理塊中,即換入.4 .系統(tǒng)設(shè)計4.1 問題分析分頁存儲治理,是將一個進程的邏輯地址空間分成假設(shè)干個大小相等的片,稱為頁面或頁,并為各頁加以編號.相應(yīng)地

5、,也把內(nèi)存空間分成與頁面相同大小的假設(shè)干個存儲塊,稱為物理塊,在為進程分配內(nèi)存時,以塊為單位將進程中的假設(shè)干個頁分別裝入到多個可以不相鄰接的物理塊中系統(tǒng)為每個進程建立一個頁表,頁表給出邏輯頁號和具體內(nèi)存塊號相應(yīng)的關(guān)系.一個頁表中包含假設(shè)干個表目,表目的自然序號對應(yīng)于用戶程序中的頁號,表目中的塊號是該頁對應(yīng)的物理塊號.請求頁式存儲治理方式是一種實現(xiàn)虛擬存儲器的方式,是指在進程開始運行之前,不是裝入全部頁面,而是裝入一個或零個頁面,之后根據(jù)進程運行的需要,動態(tài)裝入其它頁面.當內(nèi)存空間已滿,而又需要裝入新的頁面時,那么根據(jù)某種算法淘汰某個頁面,以便裝入新的頁面.請求頁式存儲治理主要需要解決以下問題：

6、系統(tǒng)如何獲知進程當前所需頁面不在主存；當發(fā)現(xiàn)缺頁時,如何把所缺頁面調(diào)入主存；當主存中沒有空閑的頁框時,為了要接受一個新頁,需要把老的一頁淘汰出去,根據(jù)什么策略選擇欲淘汰的頁面.4.2 程序整體框圖圖4-1程序整體框圖由于該算法規(guī)模較小,可以將該系統(tǒng)劃分為三塊,分別是：FIFO算法模塊、LRU算法模塊、OPT算法模塊.4.3 FIFO算法基于程序總是按線形順序來訪問物理空間這一假設(shè),總是淘汰最先調(diào)入主存的頁面,即淘汰在主存中駐留時間最長的頁面.4.4 LRU算法LRU置換算法,是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進行決策的.由于無法預測各頁面將來的使用情況,只能利用“最近的過去作為“最近的將來的近似,

7、因此,LRU置換算法是選擇最近最久未使用的頁面予以淘汰.該算法賦予每個頁面一個訪問字段,用來記錄一個頁面自上次被訪問以來所經(jīng)歷的次數(shù)count,當須淘汰一個頁面時,選擇現(xiàn)有頁面中其count值最大的,即最近最久未使用的頁面予以淘汰.count=04.5 OPT算法或距現(xiàn)在最當要調(diào)入一頁而必須淘汰舊頁時,應(yīng)該淘汰以后不再訪問的貢,長時間后要訪問的頁.它所產(chǎn)生的缺頁數(shù)最少.這只是一種理想的情況在面中查找圖4-4OPT算法程序流程圖5 .功能與測試5,1界面用戶進入系統(tǒng)之后,會有一個選擇算法的界面,如下列圖所示:選擇內(nèi)存容量,然后點擊“隨機生成頁地址流按鈕,生成頁地址流與頁面走向,如下列圖所示:圖5

8、-1選擇界面5.1 FIFO算法用戶點擊“FIFO算法按鈕,如下列圖所示:5.2 LRU算法用戶點擊“LRU算法按鈕,如下列圖所示:5.4OPT算法用戶點擊“OPT算法按鈕,如下列圖所示:6 .結(jié)論對于頁面算法,我們平時上課時,只是知道了頁面置換算法是怎么做的,并沒有想如何去實現(xiàn)這些算法.在真正要做的時候才發(fā)現(xiàn)了問題.在這次課程設(shè)計的過程中,由于之前大家對可視化程序設(shè)計不怎么熟悉,在寫代碼的時候有了許多的麻煩.最后,在小組成員耐心看了一些C#的書,并且多方實踐,終于完成了這次課程設(shè)計.通過該設(shè)計,我們學會了存儲器的治理內(nèi)容,利用C#語言實現(xiàn)進程裝入內(nèi)存的的過程,同時也對存儲器治理的多種裝入方式

9、及內(nèi)存分區(qū)有了更深的了解,特別是頁面置換算法的應(yīng)用.但也應(yīng)看到對于實際的存儲器應(yīng)用還有很多地方不能實現(xiàn)真實,在今后的學習中應(yīng)對所學知識做更深入的挖掘,對于各種算法應(yīng)用更好的利用.7 .附錄程序源代碼usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Data;usingSystem.Drawing;usingSystem.Linq;usingSystem.Text;usingSystem.Windows.Forms;namespacePageReplacepublicpartial

10、classForm1:Formpublicintpage=newint320;publicstructStruPagepublicintpageNum;publicintflag;publicintcount;publicintdistance;)publicStruPagestruPage=newStruPage32;/外存上的頁面publicForm1()InitializeComponent();comboBox1.DropDownStyle=ComboBoxStyle.DropDownList;for(inti=4;i<=32;i+)comboBox1.Items.Add(i);

11、)privatevoidbtnRand_Click(objectsender,EventArgse)intaddress=newint320;this.rtboxAddress.Text=""this.rtboxPage.Text=""Randomram=newRandom();for(inti=0;i<317;)/生成頁地址流intm=ram.Next(319);addressi+=m+1;intm_=ram.Next(0,m+1);addressi+=m_+1;addressi+=ram.Next(m_+2,319);for(intj=0;j&

12、lt;320;j+)/將頁地址流轉(zhuǎn)換為頁面走向并輸出pagej=addressj/10;this.rtboxAddress.Text+=addressj.ToString()+"t"this.rtboxPage.Text+=pagej.ToString()+"t"this.btnFCFS.Visible=true;this.btnLRU.Visible=true;this.btnOPT.Visible=true;privatevoidbtnFCFS_Click(objectsender,EventArgse)(/this.btnFCFS.BackColo

13、r=Color.Yellow;for(inti=0;i<32;i+)/初始化結(jié)構(gòu)體struPagei.pageNum=i;struPagei.flag=0;struPagei.count=0;struPagei.distance=320;intpageReplaceNum=0;/替換的頁面數(shù)doubleshootRate;/命中率intmemorySize=Int32.Parse(comboBox1.Text);/內(nèi)存的容量StringoutputString=""/每次替換后的內(nèi)存狀態(tài)intpageLoadedNum=0;/已裝入內(nèi)存的頁面數(shù)intarray=new

14、intmemorySize;/暫存已裝入內(nèi)存的頁面號for(inti=0;i<memorySize;i+)arrayi=-1;for(intj=0;j<320;j+)if(struPagepagej.flag=0)pageReplaceNum+;if(pageLoadedNum=memorySize)/內(nèi)存空間已滿(struPagearray0.flag=0;for(intk=0;k<memorySize-1;k+)arrayk=arrayk+1;arraypageLoadedNum-1=pagej;struPagepagej.flag=1;else/內(nèi)存空間還有空閑(str

15、uPagepagej.flag=1;arraypageLoadedNum+=pagej;for(inti=0;i<memorySize;i+)(if(arrayi=-1)outputString+="t"elseoutputString+=arrayi.ToString()+"t"outputstring+="n"shootRate=1-pageReplaceNum/320.0;this.rtboxMemory.Text=""this.shootRateBox.Text=shootRate.ToString(

16、);this.rtboxMemory.Text=outputString;privatevoidbtnLRU_Click(objectsender,EventArgse)for(inti=0;i<32;i+)/初始化結(jié)構(gòu)體struPagei.pageNum=i;struPagei.flag=0;struPagei.count=0;struPagei.distance=320;)intpageReplaceNum=0;/替換的頁面數(shù)doubleshootRate;/命中率intmemorySize=Int32.Parse(comboBox1.Text);/內(nèi)存的容量Stringoutput

17、String=""/每次替換后的內(nèi)存狀態(tài)intpageLoadedNum=0;/已裝入內(nèi)存的頁面數(shù)intarray=newintmemorySize;/暫存已裝入內(nèi)存的頁面號for(inti=0;i<memorySize;i+)arrayi=-1;for(intj=0;j<320;j+)struPagepagej.count=0;if(struPagepagej.flag=0)/頁面未曾裝入內(nèi)存pageReplaceNum+;if(pageLoadedNum=memorySize)/內(nèi)存空間已滿intmax=0;for(intk=1;k<pageLoade

18、dNum;k+)/找出count最小的頁面if(struPagearrayk.count>struPagearraymax.count)max=k;/進行頁面替換struPagearraymax.flag=0;struPagepagej.flag=1;arraymax=pagej;for(intn=0;n<pageLoadedNum;n+)struPagearrayn.count+;else/內(nèi)存還有空閑j;struPagepagej.flag=1;arraypageLoadedNum+=pagefor(ints=0;s<pageLoadedNum;s+)struPagear

19、rays.count+;else/頁面已轉(zhuǎn)入內(nèi)存for(intt=0;t<pageLoadedNum;t+)struPagearrayt.count+;for(inti=0;i<memorySize;i+)if(arrayi=-1)outputString+="t"elseoutputstring+=arrayi.ToString()+"t")outputstring+="n")shootRate=1-pageReplaceNum/320.0;this.rtboxMemory.Text=""this.s

20、hootRateBox.Text=shootRate.ToString();this.rtboxMemory.Text=outputString;)privatevoidbtnOPT_Click(objectsender,EventArgse)for(inti=0;i<32;i+)/初始化結(jié)構(gòu)體struPagei.pageNum=i;struPagei.flag=0;struPagei.count=0;struPagei.distance=320;)intpageReplaceNum=0;/替換的頁面數(shù)doubleshootRate;/命中率intmemorySize=Int32.Par

21、se(comboBox1.Text);/內(nèi)存的容量StringoutputString=""每次替換后的內(nèi)存狀態(tài)intpageLoadedNum=0;/已裝入內(nèi)存的頁面數(shù)intarray=newintmemorySize;/暫存已裝入內(nèi)存的頁面號for(inti=0;i<memorySize;i+)arrayi=-1;for(intj=0;j<320;j+)if(struPagepagej.flag=0)/頁面未曾裝入內(nèi)存pageReplaceNum+;if(pageLoadedNum=memorySize)/內(nèi)存空間已滿intmax=0;for(intk=1;k<pageLoadedNum;k+)/找出distance最遠的頁面if(struPagearrayk.distance>struPagearraymax.distance)max=