1、操作系統(tǒng)實驗報告班級:計科0801班姓名：韓偉偉學(xué)號：08407106時間：2011-5-25實驗五請求頁式存儲管理的頁面置換算法一實驗?zāi)康耐ㄟ^請求頁式存儲管理中頁面置換算法模擬程序，了解虛擬存儲技術(shù)的特點，掌握請求頁式存儲管理的頁面置換算法。二實驗屬性設(shè)計三實驗內(nèi)容通過隨機數(shù)產(chǎn)生一個指令序列，共320條指令，指令的地址按下述原則生產(chǎn)：50的指令是順序執(zhí)行的；25的指令是均勻分布在前地址部分；25的指令是均勻分布在后地址部分。將指令序列變換成為頁地址流設(shè)頁面大小為1K；用戶內(nèi)存容量為4頁到32頁；用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放

2、方式為：第0條至第9條指令為第0頁；第10條至19條指令為第1頁；第條至條指令為第31頁。計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。先進先出算法(FIFO)最近最少使用算法(LRU)最佳使用算(OPT)命中率=1頁面失效次數(shù)/頁地址流長度本實驗中，頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。四.思路關(guān)于隨機數(shù)的產(chǎn)生辦法。首先要初始化設(shè)置隨機數(shù)，產(chǎn)生序列的開始點，例如，通過下列語句實現(xiàn)：srand(400)；計算隨機數(shù)，產(chǎn)生320條指令序列m=160；for(i=0；iV80；i+=j=i*4；aj=m；aj+1=m+1；aj+2=aj*1.0*

3、rand()/32767；aj+3=aj+2+1m=aj+3+(319-aj+3)*1.0*rand()/32767；將指令序列變換成為頁地址流for（k=0；kV320；k+）pt=ak/10；pd=ak%10；計算不同算法的命中率rate=1-1.0隨*機*產(chǎn)*生*序列號函數(shù)U/320；其中U為缺頁中斷次數(shù)，320是頁地址流長度。(4)輸出格式kfifo1ru40.230.25321.01.0五實驗報告i寫出你編寫的語言程序。表格控制物理塊大小進程大小記錄頁面號記錄調(diào)入內(nèi)存時間頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便/算*法實現(xiàn)設(shè)計*內(nèi)存單元數(shù)暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)10記0錄調(diào);入隊列*/*調(diào)入隊列

4、計數(shù)變量*/*物理塊標(biāo)號進程序列號進程等待次數(shù)存放最久未被使用的進程標(biāo)志表示進程序列號表示物理塊號物理塊空閑和進程是否相同判斷標(biāo)志標(biāo)記替換物理塊進程下標(biāo)=0;統(tǒng)計頁面缺頁次數(shù)/隨機產(chǎn)生一個進程序列號為:/*查查*找*相*同*進程找*空*閑*物理塊*初*始*化*內(nèi)*計數(shù)器置零/*先*進*先*出*頁面置換算法找值最大的不存在相同進程存在空閑物理塊進程號填入該空閑物理塊不存在空閑物理塊缺頁次數(shù)為:*初始化內(nèi)存單元、緩沖區(qū)存在相同的進程取*得在內(nèi)存中停留最久的頁面,默認(rèn)狀態(tài)下為最早調(diào)入的頁面*判斷頁面是否已在內(nèi)存中核心部分記錄調(diào)入頁面記錄當(dāng)前的內(nèi)存/單*元中的頁面結(jié)果輸/出*/內(nèi)存狀態(tài)為：調(diào)入隊列為缺

5、頁次數(shù)為：缺頁率:主*函*數(shù)*歡迎進入操作系統(tǒng)界面虛擬內(nèi)存-、產(chǎn)生隨機序列-請-請-請、最久未使用-)-請-請-請、先進先出-)-請-請-請、最佳置換算法-請-請-請生生請生生請、生三生請種生算5法的比較()-請-請-請、退出-請選擇所要執(zhí)行的操作再見！最久未使用算先進先出算先進先出算法最久未使用算法請輸入正確的選項號!產(chǎn)生的隨機序列：髓機產(chǎn)生二個進程序列號為最近最少使用算法執(zhí)行結(jié)果如下：請求頁式管理的基本原理是將邏輯地址空間分成大小相同的頁，將存儲地址空間分塊，頁和塊的大小相等，通過頁表進行管理。頁式系統(tǒng)的邏輯地址分為頁號和頁內(nèi)位移量。頁表包括頁號和塊號數(shù)據(jù)項，它們一一對應(yīng)。根據(jù)邏輯空間的頁

6、號，查找頁表對應(yīng)項找到對應(yīng)的塊號，塊號乘以塊長，加上位移量就行成存儲空間的物理地址。每個作業(yè)的邏輯地址空間是連續(xù)的，重定位到內(nèi)存空間后就不一定連續(xù)了。3.寫出這三種頁面置換算法的實現(xiàn)思想。FIFO算法總是淘汰最先調(diào)入主存的頁面，即淘汰在主存中駐留時間最長的頁面，認(rèn)為駐留時間最長的頁不再使用的可能性較大。LRU算法淘汰的頁面是最近一段時間內(nèi)最久未被訪問的那一頁，它是基于程序局部性原理來考慮的，認(rèn)為那些剛被使用過的頁面可能還要立即被使用，而那些在較長時間內(nèi)未被使用的頁面可能不會立即使用。OPT算法，當(dāng)要調(diào)入一頁而必須淘汰舊頁時，應(yīng)該淘汰以后不再訪問的頁，或距現(xiàn)在最長時間后要訪問的頁面。4對不同算法的性能進行評價。FIFO算法較易實現(xiàn)，對具有線性順序特征的程序比較適用，而對具有其他特征的程序則效率不高，此算法還可能出現(xiàn)抖動現(xiàn)象(Belady)異常。LRU算法基于程序的局部性原理，所以適用用大多數(shù)程序，此算實現(xiàn)