操作系統(tǒng)-請(qǐng)求式存儲(chǔ)管理試驗(yàn)報(bào)告

1、操作系統(tǒng)實(shí)驗(yàn)三存儲(chǔ)管理實(shí)驗(yàn)班級(jí):學(xué)號(hào):姓名:1. 實(shí)驗(yàn)?zāi)康?2. 實(shí)驗(yàn)內(nèi)容2.通過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令2.(2) 將指令序列變換成為頁(yè)地址流 2.(3) 計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率 23. 隨機(jī)數(shù)產(chǎn)生辦法 3.環(huán)境說(shuō)明3.4. 程序設(shè)計(jì)說(shuō)明 3.4.1. 全局變量3.4.2. 隨機(jī)指令序列的產(chǎn)生 4.4.3. FIFO算法4.4.4. LRU算法4.4.5. OPT算法5.5. 編程實(shí)現(xiàn)(源程序)：5.6. 運(yùn)行結(jié)果及分析 .1.1.6.1. 運(yùn)行(以某兩次運(yùn)行結(jié)果為例，列表如下：)1.16.2. Belady s anomaly 111. 實(shí)驗(yàn)?zāi)康拇鎯?chǔ)管

2、理的主要功能之一是合理地分配空間。請(qǐng)求頁(yè)式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。掌握請(qǐng)求頁(yè)式本實(shí)驗(yàn)的目的是通過(guò)請(qǐng)求頁(yè)式存儲(chǔ)管理中頁(yè)面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn),存儲(chǔ)管理的頁(yè)面置換算法。2. 實(shí)驗(yàn)內(nèi)容（1）通過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共 320條指令指令的地址按下述原則生成：a）50%的指令是順序執(zhí)行的；b）25%的指令是均勻分布在前地址部分；c）25%的指令是均勻分布在后地址部分； 具體的實(shí)施方法是：a）在0，319的指令地址之間隨機(jī)選取一起點(diǎn)m;b）順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令；c）在前地址0， m+1 中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為m;d）順序執(zhí)行一條指令

3、，其地址為m+1;e）在后地址m +2，319中隨機(jī)選取一條指令并執(zhí)行；f）重復(fù)上述步驟a）f），直到執(zhí)行320次指令。（2）將指令序列變換成為頁(yè)地址流設(shè)：a）頁(yè)面大小為1K ；b）用戶內(nèi)存容量為4頁(yè)到32頁(yè)；c）用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為:第0條第9條指令為第0頁(yè)（對(duì)應(yīng)虛存地址為0，9）；第10條第19條指令為第1頁(yè)（對(duì)應(yīng)虛存地址為10，19）；第310條第319條指令為第31頁(yè)（對(duì)應(yīng)虛存地址為310，319）。 按以上方式，用戶指令可以組成32頁(yè)。（3）計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率a）先進(jìn)先出的

4、算法（FIFO）；b）最近最少使用算法（LRU）；c）最佳淘汰算法（OPT）；命中率=1-頁(yè)面失效次數(shù)/頁(yè)地址流長(zhǎng)度在本實(shí)驗(yàn)中，頁(yè)地址流長(zhǎng)度為320,頁(yè)面失效次數(shù)為每次訪問(wèn)相應(yīng)指令時(shí)，該指令所對(duì)應(yīng)的頁(yè)不在內(nèi)存的次數(shù)。3. 隨機(jī)數(shù)產(chǎn)生辦法關(guān)于隨機(jī)數(shù)產(chǎn)生辦法，可以采用操作系統(tǒng)提供的函數(shù)，如Linux或UNIX系統(tǒng)提供函數(shù)srand()和rand()，分別進(jìn)行初始化和產(chǎn)生隨機(jī)數(shù)。例如：sran d();語(yǔ)句可以初始化一個(gè)隨機(jī)數(shù)；a0=10*ra nd()/32767*319+1;a1=10*ra nd()/32767*a0;語(yǔ)句可以用來(lái)產(chǎn)生a0與a1 中的隨機(jī)數(shù)。環(huán)境說(shuō)明此實(shí)驗(yàn)采用的是 Win7下C

5、ode:blocks 10.05編譯器編程。此word實(shí)驗(yàn)文檔中采用 notepad+的語(yǔ)法高亮。4. 程序設(shè)計(jì)說(shuō)明4.1. 全局變量con stintmax n=320; /序列個(gè)數(shù)con stintmax=max n+ 20 ; /數(shù)組大小con stintmaxp=max/ 10 ; /最大頁(yè)數(shù)intin stmax;/指令序列intpagemax;/頁(yè)地址流intsize;/內(nèi)存能容納的頁(yè)數(shù)bool in maxp ;/該頁(yè)是否在內(nèi)存里，提高效率int pin maxp ;/現(xiàn)在在內(nèi)存里的頁(yè)其中in數(shù)組是為了方便直接判斷該頁(yè)是否在內(nèi)存里，而不用遍歷內(nèi)存里所有頁(yè)來(lái)判斷。 fault n用

6、來(lái)記錄缺頁(yè)次數(shù)。42 隨機(jī)指令序列的產(chǎn)生按照實(shí)驗(yàn)要求的寫(xiě)了，但是由于沒(méi)有考慮細(xì)節(jié)，開(kāi)始時(shí)出了點(diǎn)問(wèn)題。(1) 當(dāng)m=319時(shí)，我們順序執(zhí)行 m+1會(huì)產(chǎn)生第32頁(yè)的頁(yè)地址，從而使頁(yè)地址沒(méi)能按要求限制在0, 31之間。解決方法：采用循環(huán)模加來(lái)避免超出范圍。(2) 但是這樣之后有可能出現(xiàn)模0的問(wèn)題。所以我索性將等于0的模數(shù)都賦值為160.最后的程序如下。void produce, inst()intm , n ;intnum = 0;while(num maxn )m=rand () %maxn ;instnum+= ( m+1)% maxnif ( num = maxn ) breakm = ( m

7、+2) % maxn ;if (m = 0) m = 160 ;n = rand () %m ;instnum+ = (n +1)% maxn;if (num = maxn ) break ;n = ( n + 2) % maxn ;m = maxn - n ;if (m = 0) m = 160 ;m = rand () %m + n ;inst num+= m ;4.3. FIFO 算法定義變量ptr。一開(kāi)始先預(yù)調(diào)頁(yè)填滿內(nèi)存。在這一部分，ptr指向下一個(gè)要存放的位置。之后繼續(xù)執(zhí)行剩下的指令。此時(shí)， ptr表示隊(duì)列最前面的位置，即最先進(jìn)來(lái)的位置，也就是下一個(gè)要被替換 的位置。ptr用循環(huán)加，

8、即模擬循環(huán)隊(duì)列。4.4. LRU算法定義數(shù)組ltu, 即last_time_use 來(lái)記錄該頁(yè)最近被使用的時(shí)間。定義變量ti模擬時(shí)間的變化，每執(zhí)行一次加一。這個(gè)算法，我沒(méi)有預(yù)調(diào)頁(yè)，而是直接執(zhí)行所有指令。若當(dāng)前需要的頁(yè)沒(méi)在內(nèi)存里，就尋找最近最少使用的頁(yè)，也就是ltu最小的頁(yè)，即最近一次使用時(shí)間離現(xiàn)在最久的頁(yè)，然后替換掉它?；蛘咴趦?nèi)存還未滿時(shí)，直接寫(xiě)入，這個(gè)我以初始化內(nèi)存里所有頁(yè)為-1來(lái)實(shí)現(xiàn)。若已經(jīng)在內(nèi)存里了，則只遍歷內(nèi)存內(nèi)的頁(yè)，把當(dāng)前頁(yè)的最近使用時(shí)間改一下即可。4.5. OPT算法定義數(shù)組ntu,即next_time_use來(lái)記錄下一次被使用的時(shí)間，即將來(lái)最快使用時(shí)間。初始化為-1.開(kāi)始時(shí)預(yù)調(diào)頁(yè)

9、填滿內(nèi)存里的頁(yè)。同樣利用變量ptr來(lái)表示下一個(gè)要存放的位置從而控制預(yù)調(diào)頁(yè)的過(guò)程。接著初始化ntu數(shù)組為-1。然后求出每一頁(yè)下一次被使用的指令號(hào)，以此代替使用時(shí)間。如果所有剩下的序 列都沒(méi)有用該頁(yè)時(shí)，則還是-1.這種值為-1的頁(yè)顯然是最佳替換對(duì)象。然后執(zhí)行所有剩下的指令。當(dāng)該頁(yè)不在內(nèi)存里時(shí)，遍歷ntu數(shù)組，遇到-1的直接使用該頁(yè)，沒(méi)有則用ntu值最大的，也就是最晚使用的。無(wú)論該頁(yè)在不在內(nèi)存里，因?yàn)檫@一次已經(jīng)被使用了，所以都應(yīng)該更新這個(gè)頁(yè)的ntu，只需往前看要執(zhí)行的頁(yè)流，記錄下第一個(gè)遇到的該頁(yè)即可。如果沒(méi)有找到同樣添-1即可。5. 編程實(shí)現(xiàn)（源程序）：#i nclude #i nclude #in

10、 clude #in clude using n amespace stdcon stintmax n=320; /序列個(gè)數(shù)con stintmax=max n+ 20 ; /數(shù)組大小con stintmaxp=max/ 10 ; /最大頁(yè)數(shù)intin st max; / 指令序列int page max; / 頁(yè)地址流int size/內(nèi)存能容納的頁(yè)數(shù)bool in maxp ;/該頁(yè)是否在內(nèi)存里，提高效率int pin maxp ;/現(xiàn)在在內(nèi)存里的頁(yè)void welcomeprintf(printf(printf(printf()“*nBy sch nee On2011-12-06*n班級(jí)

11、:09211311 班內(nèi)序號(hào):*nn30*n););););void in put_h int()pri ntf32)n);pri ntfpri ntfpri ntf(n1-create new instruction sequenee 2-set memory page number(4 to(3-solve by FIFO algorithm(5-solve by OPT algorithm4-solve by LRU algorithm n0-exitn）；(*please input Your choice:I!);）；/*通過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令*/voidprod

12、uce_ inst()intm,n ;intnum = 0;while(num maxn )m=rand () %maxn ;instnum+= ( m+1)% maxnif(num = maxn ) break ;mif=(m+2) % maxn ;(m = 0) m = 160 ;n=rand () %m ;instnum+= (n +1)% maxnif(num = maxn ) break ;n=(n + 2) % maxn ;m=maxn - n ;if(m = 0) m = 160 ;m=rand () %m + n ;instnum+= m ;/*將指令序列變換成為頁(yè)地址流*/v

13、oid tur n_page_address()for ( int i =0; i maxn; i +) page i = in st i / 10 ; void FIFO_solve ()false , sizeof=0; /缺頁(yè)率(in )；memset ( in int fault_ n intptr , i/預(yù)調(diào)頁(yè)填滿空間ptr =0; /下一個(gè)要放的位置for ( i=0;i maxn & ptr size ;i +)if(! inpage i )pinptr += page i ;inpage i = true ;fault_n+;/繼續(xù)執(zhí)行剩下的指令ptr = 0; /隊(duì)列里最先

14、進(jìn)來(lái)的位置，即下一個(gè)要被替換的位置for (; i maxn ; i +)if (! in page i )inpin ptr = falseinpage i = truepinptr = page i ;fault_ n+;ptr=(ptr +1) %size,fault_n);(1-( fault_n+0.0 )/ 320.0 );printf ( nBy FIFO algorithm, the fault-page number is: %dn pri ntf(”the hit ratio is : %.2lfnvoidLRUsolve()intltumaxp ;/last_time_u

15、seintti=1 ;/模擬時(shí)間intfault_ n= i0;memset(ltu ,0,sizeof (ltu );memset(in , false,sizeof(inmemset(pin , - 1,sizeof(pin )intmin , ptr , i,j ;for(i=0; i maxn; i +)if(! in pagei )/尋找lrumin=;ptr=0;for (j =0;j size ;j +);if ( ltu j min )min= Itu j ;ptr= j ；/替換或?qū)懭雐f ( pin ptr !=- 1)in pin ptr = false ;in page

16、 i = true ;pin ptr = page i ;fault_ n+;Itu ptr = ti +;else /已經(jīng)在內(nèi)存里則只需更改最近使用時(shí)間for (j =0; j vsize ; j +)if ( pin j = page i )ltu j = ti +;break ;,fault_n);(1-( fault_n+0.0 )/ 320.0 );printf( nBy LRU algorithm, the fault-page number is: %dnpri ntf(”the hit ratio is : %.2lfnvoidOPT_solve ()intntu maxp ;

17、 next_time_useintfault_ n= 0;inti , j ;memsetmemset(in , false , sizeof ( in );(ntu , - 1, sizeof ( ntu );/預(yù)調(diào)頁(yè)填滿int ptr=:0;for ( i =0;i maxn & fault_nsizeif (! inpage i )inpage i = trueJpinptr = page i ;fault_ n+;ptr+;i +)/初始化ntu數(shù)組ptr = 0;for (j =i ; j maxn & ptr 32; j +) if ( ntu page j = - 1)ntu p

18、age j = j ;ptr+;int max ;for (; i maxn ; i +)if (! in page i )max= 0; ptr = 0;for (j =0; j max )max= ntu pin j ;ptr= j ;in pin ptr = false ;in page i = true ;pin ptr = page i ;fault_ n+;ntu page i = - 1;for (j =i +1; j maxn ; j +) if ( page j = page i ) ntu page i = j ;break,fault_n);(1-( fault_n+0.

19、0 )/ 320.0 );printf( nBy OPT algorithm, the fault-page number is: %dnpri ntf(”the hit ratio is : %.2lfnint mai n ()sra nd(time (NULL);welcome ();int choiceJwhile (1)in put_h int();scanf(%d ,&choiceprintf(n););if (choice = 0)pri ntf(BYE-BYE!n);break ;if ( choice = 1)produce, inst();turn _page_address();printf(New page address sequenee is set O