蘭州大學操作系統(tǒng)實驗八存儲管理模擬題目和答案,實驗報告.docx

實驗報告 實驗八 實驗名稱：存儲管理模擬實驗目的：1. 掌握請求分頁存儲管理系統(tǒng)的基本原理2. 實現一個模擬的虛擬分頁存儲管理系統(tǒng)實驗要求: 編寫一個程序，模擬一個虛擬分頁存儲管理系統(tǒng)。其中，由系統(tǒng)隨機產生進程；進程大小、進程到達次序、時間、進程執(zhí)行軌跡（頁面訪問順序）也隨機生成，但進程之間必須有并發(fā)存在，進程執(zhí)行時間需有限，進程調度采用時間片輪轉算法（以頁面模擬）；rss駐留集大小物理塊分配策略采取固定分配局部置換；分配算法采用按比例分配算法；調頁采用請求調頁方式；置換分別采用FIFO、LRU(一直沒用) 訪問次數 和簡單CLOCK算法（循環(huán)鏈表）標志 有沒有被訪問； 駐留集大小可調，觀察駐留集大小對缺頁率的影響。算法思想:FIFO 先進先出法LRU 最久未使用算法CLOCK 簡單時鐘算法命中率頁面失效次數頁地址流(序列)長度駐留集大小可調，觀察駐留集大小對缺頁率的影響。結構體定義頁面控制表表結構 頁面號指針頁面控制結構單位時間訪問次數頁框號上次訪問時間頁面序號頁面頁框號包含鏈表：空閑頁面表 忙頁面表 包含數組：進程數組 頁面號數組 開始流程圖：引用塊編號大于物理塊？分配物理塊為其分配頁號隨機得到進程指令序列 否頁號在物理塊內？是是是否完成？選擇FIFO LRU CLOCK 置換算法置換是結束實驗結果分析：觀察數據可看出：橫向：三種替換算法的命中率由高到底排列應該是LRU>CLOCK>FIFO。 縱向：進程的駐留級越大，其缺頁率就越低。實驗體會：1. 內存中進程的多少會影響駐留集大小和缺頁中斷率。如果內存中進程太多，將導致每個進程的駐留集太小，發(fā)生缺頁中斷的概率很大。相應地，系統(tǒng)發(fā)生抖動的可能性就會很大。如果在內存中保持太少的活動進程，那么所有活動進程同時處于阻塞狀態(tài)的可能性就會很大，從而降低處理機的利用率。2. 置換算法的好壞將直接影響系統(tǒng)的性能，不適當的置換算法可能導致系統(tǒng)出現“抖動”現象。常用的頁面置換算法：最佳置換算法、最近最少使用算法、先進先出算法和時鐘算法等。最佳置換算法難以實現但可以成為核對其他算法的標準。3. 也應注意負載問題，解決系統(tǒng)應當保持多少個活動進程駐留在內存的問題，即控制多道程序系統(tǒng)的度。當內存中的活動進程數太少時，負載控制將增加新進程或激活一些掛起進程進入內存；反之，當內存中的進程數太多時，負載控制將暫時掛起一些進程，減少內存中的活動進程數。實驗代碼：#include <stdio.h>#include <stdlib.h>#include <unistd.h> #include <string.h>#define TRUE 1#define FALSE 0#define INVALID -1#define total_instruction 320 /指令流長#define total_vp 32 /頁長#define clear_period 50 typedef struct /頁面結構 int pn,/頁面序號 pfn,/頁面所在內存區(qū)的頁框號counter,/單位時間內訪問次數time;/上次訪問的時間pl_type;pl_type pltotal_vp; /頁面結構數組struct pfc_struct /頁面控制結構 int pn,/頁面號 pfn;/內存區(qū)頁面的頁框號 struct pfc_struct *next;/頁面指針，用于維護內存緩沖區(qū)的鏈式結構;typedef struct pfc_struct pfc_type; /主存區(qū)頁面控制結構別名pfc_type pfctotal_vp, /主存區(qū)頁面控制結構數組*freepf_head, /主存區(qū)頁面控制結構的空閑頁面頭指針*busypf_head, /主存區(qū)頁面控制結構的忙頁面頭指針*busypf_tail; /主存區(qū)頁面控制結構的忙頁面尾指針int diseffect; /頁錯誤計數器，初次把頁面載入主存時也當做頁錯誤int atotal_instruction; /隨即指令流數組int pagetotal_instruction; /指令對應的頁面號int offsettotal_instruction; /指令所在頁面中的偏移量int initialize(int);/初始化頁面結構數組和頁面控制結構數組int FIFO(int);/先進先出算法int LRU(int);/最近最久未使用算法int CLOCK(int);/簡單時鐘(鐘表)算法int main( ) int s;/隨機數 int i; srand(10*getpid(); /*每次運行時進程號不同，用來作為初始化隨機數隊列的"種子"*/ s = (int)(float)(total_instruction-1)*(rand()/(RAND_MAX+1.0);printf("n-rand instructions queue-n"); for (i=0; i<total_instruction; i+=4) /產生指令隊列 ai=s; /任選一指令訪問點m ai+1=ai+1; /順序執(zhí)行一條指令 ai+2=(int)(float)ai*(rand()/(RAND_MAX+1.0); /執(zhí)行前地址指令m ai+3=ai+2+1; /順序執(zhí)行一條指令 printf("%6d%6d%6d%6dn", ai,ai+1,ai+2,ai+3); s = (int)(float)(total_instruction-1)-ai+2)*(rand()/(RAND_MAX+1.0) + ai+2; printf("-n");for (i=0;i<total_instruction;i+) /將指令序列變換成頁地址流 pagei=ai/10; offseti=ai%10; printf("compare the three methods:");printf("n-n"); printf(" Rsst FIFOt LRUt CLOCKn"); for(i=4;i<=32;i+) /用戶內存工作區(qū)從4個頁面到32個頁面 printf(" %2d t",i); FIFO(i); LRU(i);CLOCK(i); printf("n"); return 0;/初始化頁面結構數組和頁面控制結構數組/total_pf; 用戶進程的內存頁面數int initialize(int total_pf) int i; diseffect=0; for(i=0;i<total_vp;i+)pli.pn=i;pli.pfn=INVALID; /置頁面所在主存區(qū)的幀號為-1.表示該頁不在主存中pli.counter=0;/置頁面結構中的訪問次數為0pli.time=-1;/置頁面結構中的上次訪問的時間為-1for(i=0;i<total_pf-1;i+)pfci.next=&pfci+1; /建立pfci-1和pfci之間的鏈接pfci.pfn=i; /初始化主存區(qū)頁面的頁框號pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/主存區(qū)頁面控制結構的空閑頁面頭指針指向pfc0return 0;/最近最久未使用算法/int total_pf; 用戶進程的內存頁面數int LRU (int total_pf) int MinT;/最小的訪問時間，即很久沒被訪問過int MinPn;/擁有最小的訪問時間的頁的頁號int i,j;int CurrentTime;/系統(tǒng)當前時間 initialize(total_pf);/初始化頁面結構數組和頁面控制結構數組 CurrentTime=0;diseffect=0;for(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID) /頁面失效diseffect+;/頁錯誤次數加 if(freepf_head=NULL) /無空閑頁面 MinT=100000; for(j=0;j<total_vp;j+) /找出time的最小值，表明該頁很久沒被訪問過 if(MinT>plj.time&&plj.pfn!=INVALID) MinT=plj.time; MinPn=j; freepf_head=&pfcplMinPn.pfn; /最久沒被訪問過的頁被釋放 plMinPn.pfn=INVALID; /最久沒被訪問過的頁被換出主存 plMinPn.time=-1;/最久沒被訪問過的頁的訪問時間置為無效 freepf_head->next=NULL; plpagei.pfn=freepf_head->pfn; /有空閑頁面,把相應的頁面換入主存，并把pfn改為相應的頁框號 plpagei.time=CurrentTime;/令訪問時間為當前系統(tǒng)時間 freepf_head=freepf_head->next; /減少一個空閑頁面elseplpagei.time=CurrentTime; /命中則刷新該單元的訪問時間CurrentTime+; /系統(tǒng)當前時間加 printf("%6.3ft",1-(float)diseffect/320);return 0;/簡單時鐘算法/int total_pf; 用戶進程的內存頁面數int CLOCK(int total_pf)int i;int usetotal_vp; /使用位int swap;swap=0; /發(fā)生替換initialize(total_pf);pfc_type *pnext; /時鐘指針pfc_type *head; /隊列頭指針pnext=freepf_head;head=freepf_head;for(i=0;i<total_vp;i+)usei=0; /初始化使用位為diseffect=0;for(i=0;i<total_instruction;i+)if (plpagei.pfn=INVALID) /頁面失效,不在主存中diseffect+;/頁錯誤次數加if(freepf_head=NULL) /無空閑頁面while(usepnext->pfn=1) /若時鐘指針指向的頁的使用位為，則改為并跳過usepnext->pfn=0;pnext=pnext->next;if(pnext=NULL) pnext=head; /如果時鐘指針到達隊列尾部，重新返回頭部/換出被替換的頁plpnext->pn.pfn=INVALID;swap=1;if(usepnext->pfn=0) /如果使用位為，則換入相應的頁plpagei.pfn=pnext->pfn; /頁面結構中要標記頁框號pnext->pn=pagei; /頁面控制結構中要標記頁號usepnext->pfn=1;/重置使用位為pnext=pnext->next;/時鐘指針下移if(pnext=NULL) pnext=head;/如果時鐘指針到達隊列尾部，重新返回頭部if(swap=0) freepf_head=freepf_head->next;else/頁面在主存中useplpagei.pfn=1; /刷新使用位為printf("%6.3ft",1-(float)diseffect/320);return 0;/先進先出算法版本/int total_pf; 用戶進程的內存頁面數/實現細節(jié)由CLOCK算法退化而來，與FIFO同效果int FIFO(int total_pf)int i;int usetotal_vp;int swap=0;initialize(total_pf);pfc_type *pnext,*head;pnext=freepf_head;head=freepf_head;for(i=0;i<total_vp;i+)usei=0;diseffect=0;for(i=0;i<total_instruction;i+)if (plpagei.pfn=INVALID) /頁面失效,不在主存中diseffect+;if(freepf_head=NULL) /無空閑頁面while(usepnext->pfn=1)usepnext->pfn=0;pnext=pnext->next;if(pnext=NULL) pnext=head;/換出被替換的頁plpnext->pn.pfn=INVALID;swap=1;if(usepnext->pfn=0) /如果使用位為，則換入相應的頁plpagei.pfn=pnext->pfn; /頁面結構中要標記頁框號pnext->pn=pagei; /頁面控制結構中要標記頁號usepnext->pfn=1;/重置使用位為pnext=pnext->next;if(pnext=NULL) pnext=head;if(swap=0) freepf_head=freepf_head->next;printf("%6.3ft",1-(float)diseffect/320);return 0;