1、計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱存儲(chǔ)管理實(shí)驗(yàn)序號(hào)2實(shí)驗(yàn)日期2013.11.27實(shí)驗(yàn)人一、實(shí)驗(yàn)?zāi)康暮鸵? 請(qǐng)求頁(yè)式存儲(chǔ)管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。本實(shí)驗(yàn)?zāi)康氖峭ㄟ^(guò) 請(qǐng)求頁(yè)式存儲(chǔ)管理中頁(yè)面置換算法的模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)， 掌握請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法。二、相關(guān)背景知識(shí)1隨機(jī)數(shù)產(chǎn)生辦法 關(guān)于隨機(jī)數(shù)產(chǎn)生辦法， Linux 或 UNIX 系統(tǒng)提供函數(shù) srand()和 rand()， 分別進(jìn)行初始化和產(chǎn)生隨機(jī)數(shù)。三、實(shí)驗(yàn)內(nèi)容(1)通過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列， 共 320 條指令。指令的地址按下述原則生成：1. 50%的指令是順序執(zhí)行的；2. 25%的指令是均勻分布在前地址部分；3

2、. 25%的指令是均勻分布在后地址部分； 具體的實(shí)施方法是：1. 在0， 319的指令地址之間隨機(jī)選取一起點(diǎn) m；2. 順序執(zhí)行一條指令，即執(zhí)行地址為 m+1 的指令；3. 在前地址 0， m+1中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為 m；4. 順序執(zhí)行一條指令，其地址為 m+1；5. 在后地址 m +2, 319中隨機(jī)選取一條指令并執(zhí)行；6. 重復(fù)上述步驟 15，直到執(zhí)行 320 次指令。 (2)將指令序列變換成頁(yè)地址流，設(shè)1. 頁(yè)面大小為 1K；2. 用戶內(nèi)存容量為 4頁(yè)到 32 頁(yè)；3. 用戶虛存容量為 32K。在用戶虛存中，按每 K 存放 10 條指令排列虛存地址，即 320 條指令

3、在虛 存中存放的方式為：第 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)存容量下的命中率。1. 先進(jìn)先出頁(yè)面淘汰算法( FIFO)2. 最近最久未使用頁(yè)面淘汰法( LRU ) 命中率=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ù)。四、關(guān)鍵數(shù)據(jù)

4、結(jié)構(gòu)與函數(shù)的說(shuō)明ty： 頁(yè)地址流長(zhǎng)度。int d320 ：裝指令序列。int page320：裝頁(yè)地址流。int p32 ：內(nèi)存頁(yè)面。que：記錄缺頁(yè)次數(shù)。time32 ：記錄頁(yè)面距離上次被訪問(wèn)的時(shí)間。creat()：對(duì)內(nèi)存頁(yè)面進(jìn)行初始化FIFO()：先進(jìn)先出頁(yè)面淘汰算法。LRU() ： 最近最久未使用算法。srand(10*getpid():每次運(yùn)行時(shí)進(jìn)程號(hào)不同，用來(lái)作為初始化隨機(jī)數(shù)隊(duì)列的 種子。rand()： 可以生成 0RAND_MAX 之間的一個(gè)隨機(jī)數(shù)。五、編譯與執(zhí)行過(guò)程截圖rootl ocalhost:|文件(巳編垣(曰查看(V)挾素Q)終端(工)幫助(H)rootlocalhost

5、./a.outPAGEFIFOLRU40.5120.51250.5190.51260.5470.54470.5620.56980.5880.57890.5910.594100.5940.603110.6130.622120.6220.637130.6340.656140.6440.662150.6620.662160.6810.678170.7130.688180.7190.703190.7340.725200.7440.738210.7720.756220.7840.775230.8090.787240.8220.809250.8250.834260.8340.847270.8500.866

6、280.8590.869290.8630.878300.8910.884310.9000.891320.9000.900rootlocalhostT# 1六、實(shí)驗(yàn)結(jié)果與分析運(yùn)行結(jié)果： FIFO 算法與 LRU 算法的命中率相差不大，一般在 0.03 以內(nèi)，隨 著內(nèi)存頁(yè)面的增加，命中率上升， 4 頁(yè)時(shí)一般在 50%左右， 32頁(yè)一般在 90% 左右。分析： FIFO 算法是以先進(jìn)內(nèi)存先替換而 LRU 是以最久沒(méi)訪問(wèn)先替換，當(dāng)內(nèi) 存中頁(yè)面數(shù)量增加時(shí)，訪問(wèn)的內(nèi)容在內(nèi)存的概率會(huì)越高。七、調(diào)試時(shí)遇到的問(wèn)題及解決方法(提供 BUG 截屏)解決： linux 不支持頭文件 PROCESS.H，但是使用 sr

7、and()需要 用該頭文件，于是用支持 srand() 的頭文件 unistd.h 替代 PROCESS.H 。解決后試調(diào)：八、調(diào)試后的程序源代碼#include#include#include #include #define NULL 10000 const int ty=320;int d320;/指令序列int page320; / 頁(yè)地址流int p32; / 內(nèi)存頁(yè)面int que; /缺頁(yè)次數(shù)int time32; /記錄頁(yè)面距離上次被訪問(wèn)的時(shí)間/* 初始化內(nèi)存頁(yè)面void creat(int leng)/leng 為內(nèi)存頁(yè)面數(shù)量int i;que=0;for(i=0;ileng

8、;i+)pi=NULL; /讓內(nèi)存頁(yè)面置空 timei=0;/* 先進(jìn)先出算法void FIFO(int leng) /leng 為內(nèi)存頁(yè)面數(shù)量int i,j,k;int n; /n 為要被替換的頁(yè)面號(hào)，按 0,1,2.leng,0,1,2.leng 循環(huán)變化 creat(leng); / 初始化內(nèi)存頁(yè)面n=0;for(i=0;ity;i+)k=0;for(j=0;jleng;j+)if(pj=NULL) break;else if(pj=pagei)/ 在內(nèi)存中有該頁(yè)k=1; break; if(k=0)que+;pn=pagei;n+; if(n=leng) n=0; printf(%-7

9、.3ft,1-(float)que/ty); /* 最近最久未使用算法void LRU(int leng) /leng 為內(nèi)存頁(yè)面數(shù)量 int i,j,k;int tmax;/ 存 time 的最大值int t;/t 為要被訪問(wèn)的頁(yè)面號(hào)creat(leng); / 初始化內(nèi)存頁(yè)面 for(i=0;ity;i+)k=0;for(j=0;jleng;j+) if(pj=NULL) break;else if(pj=pagei)/ 在內(nèi)存中有該頁(yè)k=1; t=j; break; if(k=0) que+; tmax=time0; t=0;for(j=0;jleng;j+) / 查找最久沒(méi)訪問(wèn)的頁(yè)面號(hào)

10、賦予 t if(tmaxtimej) tmax=timej; t=j; pt=pagei;for(j=0;jleng;j+)/ 將每個(gè)頁(yè)面 time 自增timej+;timet=0; /將這次被訪問(wèn)的頁(yè)面 time 清零 printf( %-7.3ft,1-(float)que/ty);void main( ) int m,i;srand(10*getpid(); / 用來(lái)作為初始化隨機(jī)數(shù)隊(duì)列的 種子 m=(int)(float)(ty-1)*(rand()/(RAND_MAX+1.0); / 選 0-319 中一數(shù)for (i=0; ity; i+=4) / 產(chǎn)生指令隊(duì)列di=m; / 任

11、選一指令訪問(wèn)點(diǎn) m di+1=di+1; /順序執(zhí)行一條指令 m+1 di+2=(int)(float)di*(rand()/(RAND_MAX+1.0); /* 執(zhí)行前地址指 令 m, 即選擇 (0，m+1) 之間的數(shù) */ di+3=di+2+1; /順序執(zhí)行一條指令m= (int)(float)(ty-1)-di+2)*(rand()/(RAND_MAX+1.0) + di+2; /選(m+2,319)之間數(shù) for(i=0;ity;i+) / 將指令序列變換成頁(yè)地址流pagei=di/10; printf(PAGEtFIFOt LRUtn); for(i=4;i=32;i+)/內(nèi)存從 4 頁(yè)到 32頁(yè)printf( %2dt,i); FIFO(i);LRU(i); printf(n);九、實(shí)驗(yàn)體會(huì) 這一次實(shí)驗(yàn)是對(duì)請(qǐng)求頁(yè)式存儲(chǔ)管理的一次模擬實(shí)驗(yàn)，設(shè)計(jì)和