頁面置換算法課程設(shè)計(jì)

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

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

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

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

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

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

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

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

9、及內(nèi)存分區(qū)有了更深的了解,特別是頁面置換算法的應(yīng)用.但也應(yīng)看到對(duì)于實(shí)際的存儲(chǔ)器應(yīng)用還有很多地方不能實(shí)現(xiàn)真實(shí),在今后的學(xué)習(xí)中應(yīng)對(duì)所學(xué)知識(shí)做更深入的挖掘,對(duì)于各種算法應(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)存的頁面號(hào)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)存的頁面號(hào)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;/進(jìn)行頁面替換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)存的頁面號(hào)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最遠(yuǎn)的頁面if(struPagearrayk.distance>struPagearraymax.distance)max=