操作系統(tǒng)-請求頁式存儲管理實驗報告

1、操作系統(tǒng)實驗三存儲管理實驗班級:學(xué)號:姓名:TOC o 1-5 h z HYPERLINK l bookmark2 o Current Document 實驗?zāi)康? HYPERLINK l bookmark4 o Current Document 實驗內(nèi)容2 HYPERLINK l bookmark6 o Current Document 通過隨機數(shù)產(chǎn)生一個指令序列，共320條指令2 HYPERLINK l bookmark8 o Current Document 將指令序列變換成為頁地址流2 HYPERLINK l bookmark10 o Current Document 計算并輸出下述各

2、種算法在不同內(nèi)存容量下的命中率2 HYPERLINK l bookmark12 o Current Document 隨機數(shù)產(chǎn)生辦法3 HYPERLINK l bookmark20 o Current Document 環(huán)境說明3 HYPERLINK l bookmark24 o Current Document 程序設(shè)計說明3 HYPERLINK l bookmark26 o Current Document 全局變量3 HYPERLINK l bookmark28 o Current Document 隨機指令序列的產(chǎn)生4 HYPERLINK l bookmark34 o Current

3、Document FIFO算法4 HYPERLINK l bookmark36 o Current Document LRU算法4 HYPERLINK l bookmark38 o Current Document OPT算法5 HYPERLINK l bookmark40 o Current Document 編程實現(xiàn)（源程序）：5 HYPERLINK l bookmark98 o Current Document 運行結(jié)果及分析11運行（以某兩次運行結(jié)果為例，列表如下：）11Beladysanomaly11實驗?zāi)康拇鎯芾淼闹饕δ苤皇呛侠淼胤峙淇臻g。請求頁式管理是一種常用的虛擬存儲管理

4、技術(shù)。本實驗的目的是通過請求頁式存儲管理中頁面置換算法模擬設(shè)計，了解虛擬存儲技術(shù)的特點，掌握請求頁式存儲管理的頁面置換算法。實驗內(nèi)容通過隨機數(shù)產(chǎn)生一個指令序列，共320條指令指令的地址按下述原則生成：a）50%的指令是順序執(zhí)行的；b）25%的指令是均勻分布在前地址部分；c）25%的指令是均勻分布在后地址部分；具體的實施方法是：a）在0,319的指令地址之間隨機選取一起點m；b）順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令；c）在前地址0,m+1中隨機選取一條指令并執(zhí)行，該指令的地址為m，;d）順序執(zhí)行一條指令，其地址為m，+1;e）在后地址m，+2,319中隨機選取一條指令并執(zhí)行；f）重復(fù)上述步

5、驟a）f），直到執(zhí)行320次指令。（2）將指令序列變換成為頁地址流設(shè)：a）頁面大小為1K；b）用戶內(nèi)存容量為4頁到32頁；c）用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為:第0條第9條指令為第0頁（對應(yīng)虛存地址為0,9）；第10條第19條指令為第1頁（對應(yīng)虛存地址為10,19）；第310條第319條指令為第31頁（對應(yīng)虛存地址為310,319）。按以上方式，用戶指令可以組成32頁。（3）計算并輸出下述各種算法在不同內(nèi)存容量下的命中率a）先進先出的算法（FIFO）；b）最近最少使用算法（LRU）；c）最佳淘汰算法（OPT）；命中率=1-

6、頁面失效次數(shù)/頁地址流長度在本實驗中，頁地址流長度為320,頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。隨機數(shù)產(chǎn)生辦法關(guān)于隨機數(shù)產(chǎn)生辦法，可以采用操作系統(tǒng)提供的函數(shù)，如Linux或UNIX系統(tǒng)提供函數(shù)srand()和rand(),分別進行初始化和產(chǎn)生隨機數(shù)。例如：srand();語句可以初始化一個隨機數(shù)；a0=10*rand()/32767*319+1;a1=10*rand()/32767*a0;語句可以用來產(chǎn)生a0與a1中的隨機數(shù)。環(huán)境說明此實驗采用的是Win7下Code:blocks10.05編譯器編程。此word實驗文檔中采用notepad+的語法高亮。程序設(shè)計說明

7、4.1.全局變量constintmaxn=320/序歹U個數(shù)constintmax=maxn+20/數(shù)組大小constintmaxp=max/10/最大頁數(shù)intinstmaxintpagemaxintsize/指令序列/頁地址流/內(nèi)存能容納的頁數(shù)boolinmaxp/該頁是否在內(nèi)存里，提高效率intpinmaxp/現(xiàn)在在內(nèi)存里的頁其中in數(shù)組是為了方便直接判斷該頁是否在內(nèi)存里，而不用遍歷內(nèi)存里所有頁來判斷。fault_n用來記錄缺頁次數(shù)。隨機指令序列的產(chǎn)生按照實驗要求的寫了，但是由于沒有考慮細(xì)節(jié)，開始時出了點問題。當(dāng)m=319時，我們順序執(zhí)行m+1會產(chǎn)生第32頁的頁地址，從而使頁地址沒能按要

8、求限制在0,31之間。解決方法：采用循環(huán)模加來避免超出范圍。但是這樣之后有可能出現(xiàn)模0的問題。所以我索性將等于0的模數(shù)都賦值為160.最后的程序如下。voidproduce_inst()intm,nintnum=0while(nummaxnm=rand()%maxninsnum+=(m+1)%maxnif(num=maxn)breakm=(m+2)%maxnif(m=0)m=160n=rand()%minsnum+=(n+1)%maxnif(num=maxn)breakn=(n+2)%maxnm=maxnnif(m=0)m=160m=rand()%m+ninsnum+=mFIFO算法定義變量p

9、tr。一開始先預(yù)調(diào)頁填滿內(nèi)存。在這一部分，ptr指向下一個要存放的位置。之后繼續(xù)執(zhí)行剩下的指令。此時，ptr表示隊列最前面的位置，即最先進來的位置，也就是下一個要被替換的位置。ptr用循環(huán)加，即模擬循環(huán)隊列。LRU算法定義數(shù)組ltu,即last_time_use來記錄該頁最近被使用的時間。定義變量ti模擬時間的變化，每執(zhí)行一次加一。這個算法，我沒有預(yù)調(diào)頁，而是直接執(zhí)行所有指令。若當(dāng)前需要的頁沒在內(nèi)存里，就尋找最近最少使用的頁，也就是ltu最小的頁，即最近一次使用時間離現(xiàn)在最久的頁，然后替換掉它?；蛘咴趦?nèi)存還未滿時，直接寫入，這個我以初始化內(nèi)存里所有頁為1來實現(xiàn)。若已經(jīng)在內(nèi)存里了，則只遍歷內(nèi)存內(nèi)

10、的頁，把當(dāng)前頁的最近使用時間改一下即可。OPT算法定義數(shù)組ntu,即next_time_use來記錄下一次被使用的時間，即將來最快使用時間。初始化為-1.開始時預(yù)調(diào)頁填滿內(nèi)存里的頁。同樣利用變量ptr來表示下一個要存放的位置從而控制預(yù)調(diào)頁的過程。接著初始化ntu數(shù)組為-1。然后求出每一頁下一次被使用的指令號，以此代替使用時間。如果所有剩下的序列都沒有用該頁時，則還是-1.這種值為-1的頁顯然是最佳替換對象。然后執(zhí)行所有剩下的指令。當(dāng)該頁不在內(nèi)存里時，遍歷ntu數(shù)組，遇到-1的直接使用該頁，沒有則用ntu值最大的，也就是最晚使用的。無論該頁在不在內(nèi)存里，因為這一次已經(jīng)被使用了，所以都應(yīng)該更新這個

11、頁的ntu，只需往前看要執(zhí)行的頁流，記錄下第一個遇到的該頁即可。如果沒有找到同樣添1即可。編程實現(xiàn)（源程序）：#include#include#include#includeusingnamespacestdconstintmaxn=320/序歹U個數(shù)constintmax=maxn+20/數(shù)組大小constintmaxp=max/10/最大頁數(shù)intinstmax/扌旨令序歹Uintpagemax/頁地址流intsize/內(nèi)存能容納的頁數(shù)boolinmaxp/該頁是否在內(nèi)存里，提高效率intpinmaxp/現(xiàn)在在內(nèi)存里的頁print(*n)print(*voidwelcome()On2011

12、1206Byschneeprint(*班級：09211311班內(nèi)序號：30*n)print(*nn)voidinput_hint()2-setmemorypagenumber(4to4-solvebyLRUalgorithm)0-exit)print(n1-createnewinstruetionsequence32)n)print(3-solvebyFIFOalgorithmprint(5-solvebyOPTalgorithmprint(*PleaseinputYourchoice:)/*通過隨機數(shù)產(chǎn)生一個指令序列，共320條指令*/voidproduce_inst()intm,nintn

13、um=0while(nummaxnm=rand()%maxninsnum+=(m+1)%maxnif(num=maxn)breakm=(m+2)%maxnif(m=0)m=160n=rand()%minsnum+=(n+1)%maxnif(num=maxn)breakn=(n+2)%maxnm=maxnnif(m=0)m=160m=rand()%m+ninsnum+=m/*將指令序列變換成為頁地址流*/voidturn_page_address()for(inti=0imaxni+)pagi=insti/10voidFIFO_solve()memse(in,false,sizeof(in)in

14、tfault_n=0/缺頁率intptr,i/預(yù)調(diào)頁填滿空間ptr=0/下一個要放的位置for(i=0imaxn&ptrsizei+)if(!inpagei)piptr-+=pageiipagei=truefault+/繼續(xù)執(zhí)行剩下的指令ptr=0/隊列里最先進來的位置，即下一個要被替換的位置for(imaxni+)if(!inpagei)ninptr=falsepagei=truepntr=pageifault+pt=(ptr+1)%sizefault_nn+0.0)/320.0)print(nByFIFOalgorithm,thefaultnumberis:%dn,print(thehit

15、ratiois:%.2lf八n(1(faultvoidLRUsolve()intltumaxp/lasttimeuseintti=1/模擬時間intfaultn=0memse(ltu,0,sizeof(ltu)memse(in,false,sizeof(in)memse(pin,1,sizeof(pin)intmin,ptr,i,jfor(i=0imaxniif(!inpagei)/尋找lrum=nptr=0for(j=0jVsizej+)if(ltujmin)m=nltujP=j/替換或?qū)懭雐f(pinptr!=1)prinptr=falseinagei=truepintr=pageifau

16、lt+lt：Utr=ti+else/已經(jīng)在內(nèi)存里則只需更改最近使用時間for(j=0jVsizej+)if(pinj=pagei)js=ti+breakprintfnByLRUalgorithm,thefaultnumberis:%dn,fault_nprintfthehitratiois:%.2lfn(1(fault_n+0.0)/320.0)voidOPT_solve()/next_time_use0intntumaxpintfault_n=inti,jmemse(in,false,sizeof(in)memse(ntu,1,sizeof(ntu)/預(yù)調(diào)頁填滿intptr=0for(i=0

17、imaxn&fault_nsizei+)if(!inpagei)pagei|=truepptr=pageifault+p+/初始化ntu數(shù)組ptr=0for(jijmaxnptrjif(ntupagej=1)ntuagej|=jptrintmaxfor(imaxni+)if(!inpagei)ma=0ptr=0for(j=0jVsizej+)if(ntupinjp=口breakif(ntupinjmaxm=xntupinjp=口ininptr=falseinagei=truepiptr=pageifault+ntjpagei=1for(j=i+1jmaxnj+)if(pagej=pagei)p

18、agei=jbreakprintfnByOPTalgorithm,thefaultnumberis:%dn,fault_n)printfthehitratiois:%.2lfn(1(fault_n+0.0)/320.0)intmain()sran(time(NULL)welcom()intchoicewhile(1)input_hintscan(%d,&choice)print(n)if(choice=0)prin(BYE-BYE!n)breakif(choice=1)produce_in(：turn_page_addre()prin(NewpageaddresssequenceissetOK

19、!n)elseif(choice=2)prin(Pleaseinputthesizeofmemorypagenumber:)sca(%d,&size)elseif(choice=3)FIFO_sol()elseif(choice=4)LRU_solelseif(choice=5)OPT_solelseprin(INPUTERROR!n)return0運行結(jié)果及分析6.1.運行（以某兩次運行結(jié)果為例，列表如下：內(nèi)存451015202532FIFO2852722301781359032LRU2852742241851399132OPT22120214096684832FIFO2722622061671288232LRU2712652041631308632OPT20118312792664732隨著頁數(shù)的增多，除了FIFO對某些序列會有Be