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

10/10實驗報告實驗八實驗名稱：存儲管理模擬實驗?zāi)康模赫莆照埱蠓猪摯鎯芾硐到y(tǒng)的基本原理實現(xiàn)一個模擬的虛擬分頁存儲管理系統(tǒng)實驗要求:編寫一個程序,模擬一個虛擬分頁存儲管理系統(tǒng).其中,由系統(tǒng)隨機產(chǎn)生進程；進程大小、進程到達次序、時間、進程執(zhí)行軌跡〔頁面訪問順序〕也隨機生成,但進程之間必須有并發(fā)存在,進程執(zhí)行時間需有限,進程調(diào)度采用時間片輪轉(zhuǎn)算法〔以頁面模擬〕；rss駐留集大小物理塊分配策略采取固定分配局部置換；分配算法采用按比例分配算法；調(diào)頁采用請求調(diào)頁方式；置換分別采用FIFO、LRU<一直沒用>訪問次數(shù)和簡單CLOCK算法〔循環(huán)鏈表〕標志有沒有被訪問；駐留集大小可調(diào),觀察駐留集大小對缺頁率的影響.算法思想:FIFO先進先出法LRU最久未使用算法CLOCK簡單時鐘算法命中率＝１－頁面失效次數(shù)／頁地址流<序列>長度駐留集大小可調(diào),觀察駐留集大小對缺頁率的影響.結(jié)構(gòu)體定義頁面控制表表結(jié)構(gòu)頁面號指針頁面控制結(jié)構(gòu)單位時間訪問次數(shù)頁框號上次訪問時間頁面序號頁面控制表表結(jié)構(gòu)頁面號指針頁面控制結(jié)構(gòu)單位時間訪問次數(shù)頁框號上次訪問時間頁面序號頁面頁框號頁框號包含鏈表：空閑頁面表忙頁面表包含數(shù)組：進程數(shù)組頁面號數(shù)組開始流程圖：開始引用塊編號大于物理塊？分配物理塊為其分配頁號隨機得到進程指令序列引用塊編號大于物理塊？分配物理塊為其分配頁號隨機得到進程指令序列否頁號在物理塊內(nèi)？頁號在物理塊內(nèi)？是是是否完成？選擇FIFOLRUCLOCK置換算法置換是否完成？選擇FIFOLRUCLOCK置換算法置換是結(jié)束結(jié)束實驗結(jié)果分析：觀察數(shù)據(jù)可看出：橫向：三種替換算法的命中率由高到底排列應(yīng)該是LRU>CLOCK>FIFO.縱向：進程的駐留級越大,其缺頁率就越低.實驗體會：內(nèi)存中進程的多少會影響駐留集大小和缺頁中斷率.如果內(nèi)存中進程太多,將導(dǎo)致每個進程的駐留集太小,發(fā)生缺頁中斷的概率很大.相應(yīng)地,系統(tǒng)發(fā)生抖動的可能性就會很大.如果在內(nèi)存中保持太少的活動進程,那么所有活動進程同時處于阻塞狀態(tài)的可能性就會很大,從而降低處理機的利用率.置換算法的好壞將直接影響系統(tǒng)的性能,不適當?shù)闹脫Q算法可能導(dǎo)致系統(tǒng)出現(xiàn)"抖動"現(xiàn)象.常用的頁面置換算法：最佳置換算法、最近最少使用算法、先進先出算法和時鐘算法等.最佳置換算法難以實現(xiàn)但可以成為核對其他算法的標準.也應(yīng)注意負載問題,解決系統(tǒng)應(yīng)當保持多少個活動進程駐留在內(nèi)存的問題,即控制多道程序系統(tǒng)的度.當內(nèi)存中的活動進程數(shù)太少時,負載控制將增加新進程或激活一些掛起進程進入內(nèi)存；反之,當內(nèi)存中的進程數(shù)太多時,負載控制將暫時掛起一些進程,減少內(nèi)存中的活動進程數(shù).實驗代碼：#include<stdio.h>#include<stdlib.h>#include<unistd.h>#include<string.h>#defineTRUE1#defineFALSE0#defineINVALID-1#definetotal_instruction320//指令流長#definetotal_vp32//頁長#defineclear_period50typedefstruct//頁面結(jié)構(gòu){intpn, //頁面序號pfn, //頁面所在內(nèi)存區(qū)的頁框號 counter, //單位時間內(nèi)訪問次數(shù) time; //上次訪問的時間}pl_type;pl_typepl[total_vp];//頁面結(jié)構(gòu)數(shù)組structpfc_struct{//頁面控制結(jié)構(gòu)intpn, //頁面號 pfn; //內(nèi)存區(qū)頁面的頁框號structpfc_struct*next; //頁面指針,用于維護內(nèi)存緩沖區(qū)的鏈式結(jié)構(gòu)};typedefstructpfc_structpfc_type;//主存區(qū)頁面控制結(jié)構(gòu)別名pfc_typepfc[total_vp], //主存區(qū)頁面控制結(jié)構(gòu)數(shù)組*freepf_head, //主存區(qū)頁面控制結(jié)構(gòu)的空閑頁面頭指針*busypf_head, //主存區(qū)頁面控制結(jié)構(gòu)的忙頁面頭指針*busypf_tail; //主存區(qū)頁面控制結(jié)構(gòu)的忙頁面尾指針intdiseffect; //頁錯誤計數(shù)器,初次把頁面載入主存時也當做頁錯誤inta[total_instruction]; //隨即指令流數(shù)組intpage[total_instruction]; //指令對應(yīng)的頁面號intoffset[total_instruction]; //指令所在頁面中的偏移量intinitialize<int>; //初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組intFIFO<int>; //先進先出算法intLRU<int>; //最近最久未使用算法intCLOCK<int>; //簡單時鐘<鐘表>算法intmain<>{ints; //隨機數(shù)inti;srand<10*getpid<>>;/*每次運行時進程號不同,用來作為初始化隨機數(shù)隊列的"種子"*/s=<int><<float><total_instruction-1>*<rand<>/<RAND_MAX+1.0>>>; printf<"\nrandinstructionsqueue\n">;for<i=0;i<total_instruction;i+=4>//產(chǎn)生指令隊列{a[i]=s;//任選一指令訪問點ma[i+1]=a[i]+1;//順序執(zhí)行一條指令a[i+2]=<int><<float>a[i]*<rand<>/<RAND_MAX+1.0>>>;//執(zhí)行前地址指令m'a[i+3]=a[i+2]+1;//順序執(zhí)行一條指令printf<"%6d%6d%6d%6d\n",a[i],a[i+1],a[i+2],a[i+3]>;s=<int><<float><<total_instruction-1>-a[i+2]>*<rand<>/<RAND_MAX+1.0>>>+a[i+2];} printf<"\n">; for<i=0;i<total_instruction;i++>//將指令序列變換成頁地址流{page[i]=a[i]/10;offset[i]=a[i]%10;}printf<"parethethreemethods:">; printf<"\n\n">;printf<"Rss\tFIFO\tLRU\tCLOCK\n">;for<i=4;i<=32;i++>//用戶內(nèi)存工作區(qū)從4個頁面到32個頁面{printf<"%2d\t",i>;FIFO<i>;LRU<i>; CLOCK<i>;printf<"\n">;}return0;}//初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組//total_pf;用戶進程的內(nèi)存頁面數(shù)intinitialize<inttotal_pf>{inti;diseffect=0;for<i=0;i<total_vp;i++> { pl[i].pn=i; pl[i].pfn=INVALID;//置頁面所在主存區(qū)的幀號為-1.表示該頁不在主存中 pl[i].counter=0; //置頁面結(jié)構(gòu)中的訪問次數(shù)為0 pl[i].time=-1; //置頁面結(jié)構(gòu)中的上次訪問的時間為-1 } for<i=0;i<total_pf-1;i++> { pfc[i].next=&pfc[i+1]; //建立pfc[i-1]和pfc[i]之間的 pfc[i].pfn=i; //初始化主存區(qū)頁面的頁框號 } pfc[total_pf-1].next=NULL; pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; //主存區(qū)頁面控制結(jié)構(gòu)的空閑頁面頭指針指向pfc[0] return0;}//最近最久未使用算法//inttotal_pf;用戶進程的內(nèi)存頁面數(shù)intLRU<inttotal_pf>{intMinT; //最小的訪問時間,即很久沒被訪問過 intMinPn; //擁有最小的訪問時間的頁的頁號 inti,j; intCurrentTime; //系統(tǒng)當前時間initialize<total_pf>; //初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組CurrentTime=0; diseffect=0; for<i=0;i<total_instruction;i++> { if<pl[page[i]].pfn==INVALID>//頁面失效 { diseffect++; //頁錯誤次數(shù)加if<freepf_head==NULL>//無空閑頁面{MinT=100000; for<j=0;j<total_vp;j++>{//找出time的最小值,表明該頁很久沒被訪問過 if<MinT>pl[j].time&&pl[j].pfn!=INVALID> {MinT=pl[j].time;MinPn=j; } } freepf_head=&pfc[pl[MinPn].pfn];//最久沒被訪問過的頁被釋放 pl[MinPn].pfn=INVALID; //最久沒被訪問過的頁被換出主存 pl[MinPn].time=-1; //最久沒被訪問過的頁的訪問時間置為無效 freepf_head->next=NULL; }pl[page[i]].pfn=freepf_head->pfn;//有空閑頁面,把相應(yīng)的頁面換入主存,并把pfn改為相應(yīng)的頁框號pl[page[i]].time=CurrentTime; //令訪問時間為當前系統(tǒng)時間freepf_head=freepf_head->next;//減少一個空閑頁面 } else pl[page[i]].time=CurrentTime;//命中則刷新該單元的訪問時間 CurrentTime++;//系統(tǒng)當前時間加} printf<"%6.3f\t",1-<float>diseffect/320>; return0;}//簡單時鐘算法//inttotal_pf;用戶進程的內(nèi)存頁面數(shù)intCLOCK<inttotal_pf>{ inti; intuse[total_vp];//使用位 intswap; 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++>{use[i]=0;}//初始化使用位為 diseffect=0; for<i=0;i<total_instruction;i++> { if<pl[page[i]].pfn==INVALID>//頁面失效,不在主存中 { diseffect++; //頁錯誤次數(shù)加 if<freepf_head==NULL>//無空閑頁面 { while<use[pnext->pfn]==1>//若時鐘指針指向的頁的使用位為,則改為并跳過 { use[pnext->pfn]=0; pnext=pnext->next; if<pnext==NULL>pnext=head;//如果時鐘指針到達隊列尾部,重新返回頭部 } //換出被替換的頁 pl[pnext->pn].pfn=INVALID; swap=1; } if<use[pnext->pfn]==0>{//如果使用位為,則換入相應(yīng)的頁 pl[page[i]].pfn=pnext->pfn;//頁面結(jié)構(gòu)中要標記頁框號 pnext->pn=page[i];//頁面控制結(jié)構(gòu)中要標記頁號 use[pnext->pfn]=1; //重置使用位為 pnext=pnext->next; //時鐘指針下移 if<pnext==NULL>pnext=head; //如果時鐘指針到達隊列尾部,重新返回頭部 if<swap==0>{freepf_head=freepf_head->next; } } }else{//頁面在主存中 use[pl[page[i]].pfn]=1;//刷新使用位為 } } printf<"%6.3f\t",1-<float>diseffect/320>; return0;}//先進先出算法版本//inttotal_pf;用戶進程的內(nèi)存頁面數(shù)//實現(xiàn)細節(jié)由CLOCK算法退化而來,與FIFO同效果intFIFO<inttotal_pf>{ inti; intuse[total_vp]; intswap=0; initialize<total_pf>; pfc_type*pnext,*head; pnext=freepf_head; hea