北郵大三上-操作系統(tǒng)-存儲(chǔ)管理實(shí)驗(yàn)報(bào)告

操作系統(tǒng)實(shí)驗(yàn)三存儲(chǔ)管理實(shí)驗(yàn)班級(jí)：學(xué)號(hào)：姓名：schnee目 錄1.實(shí)驗(yàn)?zāi)康?2.實(shí)驗(yàn)內(nèi)容2(1) 通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令2(2) 將指令序列變換成為頁地址流2(3) 計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率23.隨機(jī)數(shù)產(chǎn)生辦法3環(huán)境說明34.程序設(shè)計(jì)說明34.1.全局變量34.2.隨機(jī)指令序列的產(chǎn)生44.3.FIFO算法44.4.LRU算法44.5.OPT算法55.編程實(shí)現(xiàn)（源程序）：56.運(yùn)行結(jié)果及分析116.1.運(yùn)行（以某兩次運(yùn)行結(jié)果為例，列表如下：）116.2.Beladys anomaly111. 實(shí)驗(yàn)?zāi)康拇鎯?chǔ)管理的主要功能之一是合理地分配空間。請(qǐng)求頁式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。本實(shí)驗(yàn)的目的是通過請(qǐng)求頁式存儲(chǔ)管理中頁面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁式存儲(chǔ)管理的頁面置換算法。2. 實(shí)驗(yàn)內(nèi)容(1) 通過隨機(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í)行一條指令，其地址為m+1;e) 在后地址m+2，319中隨機(jī)選取一條指令并執(zhí)行;f) 重復(fù)上述步驟a)f)，直到執(zhí)行320次指令。(2) 將指令序列變換成為頁地址流設(shè)：a) 頁面大小為1K；b) 用戶內(nèi)存容量為4頁到32頁；c) 用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條第9條指令為第0頁（對(duì)應(yīng)虛存地址為0，9）；第10條第19條指令為第1頁（對(duì)應(yīng)虛存地址為10，19）；第310條第319條指令為第31頁（對(duì)應(yīng)虛存地址為310，319）。按以上方式，用戶指令可以組成32頁。(3) 計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率a) 先進(jìn)先出的算法（FIFO）；b) 最近最少使用算法（LRU）；c) 最佳淘汰算法（OPT）；命中率=1-頁面失效次數(shù)/頁地址流長(zhǎng)度在本實(shí)驗(yàn)中，頁地址流長(zhǎng)度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時(shí)，該指令所對(duì)應(yīng)的頁不在內(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ù)。例如：srand();語句可以初始化一個(gè)隨機(jī)數(shù)；a0=10*rand()/32767*319+1;a1=10*rand()/32767*a0;語句可以用來產(chǎn)生a0與a1中的隨機(jī)數(shù)。環(huán)境說明此實(shí)驗(yàn)采用的是Win7下Code:blocks 10.05編譯器編程。此word實(shí)驗(yàn)文檔中采用notepad+的語法高亮。4. 程序設(shè)計(jì)說明4.1. 全局變量const int maxn = 320; /序列個(gè)數(shù)const int max = maxn +20;/數(shù)組大小const int maxp = max/10; /最大頁數(shù)int instmax;/指令序列int pagemax;/頁地址流int size; /內(nèi)存能容納的頁數(shù)bool inmaxp; /該頁是否在內(nèi)存里，提高效率int pinmaxp; /現(xiàn)在在內(nèi)存里的頁其中in數(shù)組是為了方便直接判斷該頁是否在內(nèi)存里，而不用遍歷內(nèi)存里所有頁來判斷。fault_n用來記錄缺頁次數(shù)。4.2. 隨機(jī)指令序列的產(chǎn)生按照實(shí)驗(yàn)要求的寫了，但是由于沒有考慮細(xì)節(jié)，開始時(shí)出了點(diǎn)問題。（1） 當(dāng)m=319時(shí)，我們順序執(zhí)行m+1會(huì)產(chǎn)生第32頁的頁地址，從而使頁地址沒能按要求限制在0, 31之間。解決方法：采用循環(huán)模加來避免超出范圍。（2） 但是這樣之后有可能出現(xiàn)模0的問題。所以我索性將等于0的模數(shù)都賦值為160.最后的程序如下。void produce_inst() int m, n; int num = 0; while(num maxn) m = rand() % maxn; instnum+ = (m+1)%maxn; if(num = maxn) break; m = (m+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; instnum+ = m; 4.3. FIFO算法定義變量ptr。一開始先預(yù)調(diào)頁填滿內(nèi)存。在這一部分，ptr指向下一個(gè)要存放的位置。之后繼續(xù)執(zhí)行剩下的指令。此時(shí)，ptr表示隊(duì)列最前面的位置，即最先進(jìn)來的位置，也就是下一個(gè)要被替換的位置。ptr用循環(huán)加，即模擬循環(huán)隊(duì)列。4.4. LRU算法定義數(shù)組ltu,即last_time_use來記錄該頁最近被使用的時(shí)間。定義變量ti模擬時(shí)間的變化，每執(zhí)行一次加一。這個(gè)算法，我沒有預(yù)調(diào)頁，而是直接執(zhí)行所有指令。若當(dāng)前需要的頁沒在內(nèi)存里，就尋找最近最少使用的頁，也就是ltu最小的頁，即最近一次使用時(shí)間離現(xiàn)在最久的頁，然后替換掉它?；蛘咴趦?nèi)存還未滿時(shí)，直接寫入，這個(gè)我以初始化內(nèi)存里所有頁為-1來實(shí)現(xiàn)。若已經(jīng)在內(nèi)存里了，則只遍歷內(nèi)存內(nèi)的頁，把當(dāng)前頁的最近使用時(shí)間改一下即可。4.5. OPT算法定義數(shù)組ntu, 即next_time_use來記錄下一次被使用的時(shí)間，即將來最快使用時(shí)間。初始化為-1.開始時(shí)預(yù)調(diào)頁填滿內(nèi)存里的頁。同樣利用變量ptr來表示下一個(gè)要存放的位置從而控制預(yù)調(diào)頁的過程。接著初始化ntu數(shù)組為-1。然后求出每一頁下一次被使用的指令號(hào)，以此代替使用時(shí)間。如果所有剩下的序列都沒有用該頁時(shí)，則還是-1.這種值為-1的頁顯然是最佳替換對(duì)象。然后執(zhí)行所有剩下的指令。當(dāng)該頁不在內(nèi)存里時(shí)，遍歷ntu數(shù)組，遇到-1的直接使用該頁，沒有則用ntu值最大的，也就是最晚使用的。無論該頁在不在內(nèi)存里，因?yàn)檫@一次已經(jīng)被使用了，所以都應(yīng)該更新這個(gè)頁的ntu，只需往前看要執(zhí)行的頁流，記錄下第一個(gè)遇到的該頁即可。如果沒有找到同樣添-1即可。5. 編程實(shí)現(xiàn)（源程序）：#include #include #include #include using namespace std;const int maxn = 320; /序列個(gè)數(shù)const int max = maxn +20;/數(shù)組大小const int maxp = max/10; /最大頁數(shù)int instmax;/指令序列int pagemax;/頁地址流int size; /內(nèi)存能容納的頁數(shù)bool inmaxp; /該頁是否在內(nèi)存里，提高效率int pinmaxp; /現(xiàn)在在內(nèi)存里的頁void welcome() printf(*n); printf(* By schnee On2011-12-06 *n); printf(* 班級(jí): 班內(nèi)序號(hào)：30 *n); printf(*nn);void input_hint() printf(n1-create new instruction sequence 2-set memory page number(4 to 32)n); printf(3-solve by FIFO algorithm 4-solve by LRU algorithmn); printf(5-solve by OPT algorithm 0-exitn); printf(*Please input Your choice: );/*通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令*/void produce_inst() int m, n; int num = 0; while(num maxn) m = rand() % maxn; instnum+ = (m+1)%maxn; if(num = maxn) break; m = (m+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; instnum+ = m; /*將指令序列變換成為頁地址流*/void turn_page_address() for(int i=0; imaxn; i+) pagei = insti/10;void FIFO_solve() memset(in, false, sizeof(in); int fault_n = 0;/缺頁率 int ptr, i;/預(yù)調(diào)頁填滿空間 ptr = 0; /下一個(gè)要放的位置 for(i=0; imaxn & ptrsize; i+) if(!inpagei) pinptr+ = pagei; inpagei = true; fault_n+; /繼續(xù)執(zhí)行剩下的指令 ptr = 0;/隊(duì)列里最先進(jìn)來的位置，即下一個(gè)要被替換的位置 for(; imaxn; i+) if(!inpagei) inpinptr = false; inpagei = true; pinptr = pagei; fault_n+; ptr = (ptr+1) % size; printf(nBy FIFO algorithm, the fault-page number is: %dn, fault_n); printf( the hit ratio is : %.2lfn, (1-(fault_n+0.0)/320.0);void LRU_solve() int ltumaxp; /last_time_useint ti = 1; /模擬時(shí)間 int fault_n = 0; memset(ltu, 0, sizeof(ltu); memset(in, false, sizeof(in); memset(pin, -1, sizeof(pin); int min, ptr, i, j; for(i=0; imaxn; i+) if(!inpagei) /尋找lru min=; ptr=0; for(j=0; jsize; j+) if(ltuj min) min = ltuj; ptr = j; /替換或?qū)懭?if(pinptr != -1) inpinptr = false; inpagei = true; pinptr = pagei; fault_n+; ltuptr = ti+; else/已經(jīng)在內(nèi)存里則只需更改最近使用時(shí)間 for(j=0; jsize; j+) if(pinj = pagei) ltuj = ti+; break; printf(nBy LRU algorithm, the fault-page number is: %dn, fault_n); printf( the hit ratio is : %.2lfn, (1-(fault_n+0.0)/320.0);void OPT_solve() int ntumaxp;/next_time_use int fault_n = 0; int i, j; memset(in, false, sizeof(in); memset(ntu, -1, sizeof(ntu); /預(yù)調(diào)頁填滿 int ptr = 0; for(i=0; imaxn & fault_nsize; i+) if(!inpagei) inpagei = true; pinptr = pagei; fault_n+; ptr+; /初始化ntu數(shù)組 ptr = 0; for(j=i; jmaxn & ptr32; j+) if(ntupagej = -1) ntupagej = j; ptr+; int max; for(; imaxn; i+) if(!inpagei) max = 0;ptr = 0; for(j=0; j max) max = ntupinj; ptr = j; inpinptr = false; inpagei = true; pinptr = pagei; fault_n+; ntupagei = -1; for(j=i+1; jmaxn; j+) if(pagej = pagei) ntupagei = j; break; printf(nBy OPT algorithm, the fault-page number is: %dn, fault_n); printf( the hit ratio is : %.2lfn, (1-(fault_n+0.0)/320.0);int main() srand(time(NULL); welcome(); int choice; while(1) input_hint(); scanf(%d, &choice); printf(n); if(choice = 0) printf(BYE-BYE!n); break; if(choice = 1) produce_inst(); turn_page_address(); printf(New page address sequence is set OK!n); else if(choice