頁面置換算法課程設計

1、操作系統(tǒng)課程設計報告題目頁面置換算法專業(yè)計算機科學與技術小組成員:目錄1 .設計目的22 .課設要求23 .系統(tǒng)分析34 .系統(tǒng)設計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 .結論11.7 .附錄12.1 .設計目的1、存儲治理的主要功能之一是合理地分配空間.請求頁式治理是一種常用的虛擬存儲治理技術.本次設計的目的是通過請求頁式存儲治理中頁面置換算法模擬設計,了解虛擬存儲技術的特點,掌握請求頁式治理的頁面置換算法.2、提

2、升自己的程序設計水平、提升算法設計質量與程序設計素質；2 .課設要求設計一個請求頁式存儲治理方案.并編寫模擬程序實現(xiàn)之.要求包含：1 .過隨機數產生一個指令序列,共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 .指令序列變換成頁地址流設：1頁面大小為1K;用戶內存容量為4頁到32頁；用戶虛存容量為32K.在用戶虛存中,按每K存放10條指令排列虛存地址,即320條指令在虛存中的存放方式為：第0條一第9條指令為第0頁對應虛存地址為0,9;第10條一第19條指令為第1頁對應虛存地址為10,19;000000000000000000000第310條一第319條指令為第31頁對應虛存地址為310,319;按以上方式,用戶指令可組成32頁.3 .計算并輸出下述各種算法在不同內存容量下的命中率.FIFO先進先出的算法LRU最近最少使用算法OPT最正確淘汰算法先淘汰最不常用的頁地址3 .系統(tǒng)分析在多道

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

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

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

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

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

9、及內存分區(qū)有了更深的了解,特別是頁面置換算法的應用.但也應看到對于實際的存儲器應用還有很多地方不能實現(xiàn)真實,在今后的學習中應對所學知識做更深入的挖掘,對于各種算法應用更好的利用.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+)/將頁地址流轉換為頁面走向并輸出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+)/初始化結構體struPagei.pageNum=i;struPagei.flag=0;struPagei.count=0;struPagei.distance=320;intpageReplaceNum=0;/替換的頁面數doubleshootRate;/命中率intmemorySize=Int32.Parse(comboBox1.Text);/內存的容量StringoutputString=""/每次替換后的內存狀態(tài)intpageLoadedNum=0;/已裝入內存的頁面數intarray=new

14、intmemorySize;/暫存已裝入內存的頁面號for(inti=0;i<memorySize;i+)arrayi=-1;for(intj=0;j<320;j+)if(struPagepagej.flag=0)pageReplaceNum+;if(pageLoadedNum=memorySize)/內存空間已滿(struPagearray0.flag=0;for(intk=0;k<memorySize-1;k+)arrayk=arrayk+1;arraypageLoadedNum-1=pagej;struPagepagej.flag=1;else/內存空間還有空閑(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+)/初始化結構體struPagei.pageNum=i;struPagei.flag=0;struPagei.count=0;struPagei.distance=320;)intpageReplaceNum=0;/替換的頁面數doubleshootRate;/命中率intmemorySize=Int32.Parse(comboBox1.Text);/內存的容量Stringoutput

17、String=""/每次替換后的內存狀態(tài)intpageLoadedNum=0;/已裝入內存的頁面數intarray=newintmemorySize;/暫存已裝入內存的頁面號for(inti=0;i<memorySize;i+)arrayi=-1;for(intj=0;j<320;j+)struPagepagej.count=0;if(struPagepagej.flag=0)/頁面未曾裝入內存pageReplaceNum+;if(pageLoadedNum=memorySize)/內存空間已滿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/內存還有空閑j;struPagepagej.flag=1;arraypageLoadedNum+=pagefor(ints=0;s<pageLoadedNum;s+)struPagear

19、rays.count+;else/頁面已轉入內存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+)/初始化結構體struPagei.pageNum=i;struPagei.flag=0;struPagei.count=0;struPagei.distance=320;)intpageReplaceNum=0;/替換的頁面數doubleshootRate;/命中率intmemorySize=Int32.Par

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