虛擬存儲器管理方案試驗報告

1、淮海工學院計算機科學系實驗報告書課程名： 操作系統(tǒng)題 目：虛擬存儲器管理頁面置換算法模擬實驗班 級：學 號：姓 名：評語:成績： 指導教師： 批閱時間:、實驗目的與要求.目的：請求頁式虛存管理是常用的虛擬存儲管理方案之一。通過請求頁式虛存管理中對頁面置換算法的模擬，有助于理解虛擬存儲技術的特點，并加深對請求頁式虛存管理的頁面調度算法的 理解。. 要求：本實驗要求使用 C語言編程模擬一個擁有若干個虛頁的進程在給定的若干個實頁中運行、并在缺頁中斷發(fā)生時分別使用FIFO和LRU算法進行頁面置換的情形。其中虛頁的個數(shù)可以事先給定（例如10個），對這些虛頁訪問的頁地址流（其長度可以事先給定，例如20次虛

2、頁訪問）可以由程序隨機產(chǎn)生，也可以事先保存在文件中。要求程序運行時屏幕能顯示出置換過程 中的狀態(tài)信息并輸出訪問結束時的頁面命中率。程序應允許通過為該進程分配不同的實頁數(shù)， 來比較兩種置換算法的穩(wěn)定性。二、實驗說明.設計中虛頁和實頁的表不本設計利用C語言的結構體來描述虛頁和實頁的結構。實頁結構在虛頁結構中，pn代表虛頁號，因為共10個虛頁，所以pn的取值范圍是09。pfn代表實頁號，當一虛頁未裝入實頁時，此項值為-1 ;當該虛頁已裝入某一實頁時，此項值為所裝入的實頁的實頁號pfn o time項在FIFO算法中不使用，在 LRU中用來存放對該虛頁的最近訪問時間。在實頁結本中中，pn代表虛頁號，表

3、示pn所代表的虛頁目前正放在此實頁中。pfn代表實頁號,取值范圍（0n-1 ）由動態(tài)指派的實頁數(shù) n所決定。next是一個指向實頁結構體的指針，用于多個 實頁以鏈表形式組織起來，關于實頁鏈表的組織詳見下面第4點。.關于缺頁次數(shù)的統(tǒng)計為計算命中率，需要統(tǒng)計在20次的虛頁訪問中命中的次數(shù)。為此，程序應設置一個計數(shù)器count ,來統(tǒng)計虛頁命中發(fā)生的次數(shù)。每當所訪問的虛頁的 pfn項值不為-1 ,表示此虛頁已被裝入某實頁內，此虛頁被命中，count加1。最終命中率 =count/20*100% 。. LRU算法中“最近最久未用”頁面的確定為了能找到“最近最久未用”的虛頁面，程序中可引入一個時間計數(shù)器

4、countime ,每當要訪問一個虛頁面時，countime的值加1,然后將所要訪問的虛頁的time項值設置為增值后的當前LRU算法需要置換時，從所有已分配實頁的虛countime值，表示該虛頁的最后一次被訪問時間。當頁中找出time值為最小的虛頁就是“最近最久未用”的虛頁面，應該將它置換出去。.算法中實頁的組織因為能分配的實頁數(shù) n是在程序運行時由用戶動態(tài)指派的，所以應使用鏈表組織動態(tài)產(chǎn)生的多個實頁。為了調度算法實現(xiàn)的方便，可以考慮引入free和busy兩個鏈表：free鏈表用于組織未分配出去的實頁，首指針為free_head ,初始時n個實頁都處于free鏈表中；busy鏈表用于組織已分配

5、出 去的實頁，首指針為 busy_head ,尾指針為busy_tail ,初始值都為null。當所要訪問的一個虛頁 不在實頁中時，將產(chǎn)生缺頁中斷。此時若free鏈表不為空，就取下鏈表首指針所指的實頁，并分配給該虛頁。若free鏈表為空，則說明 n個實頁已全部分配出去，此時應進行頁面置換：對于 FIFO 算法要將busy_head所指的實頁從busy鏈表中取下，分配給該虛頁，然后再將該實頁插入到busy鏈表尾部；對于LRU算法則要從所有已分配實頁的虛頁中找出time值為最小的虛頁，將該虛頁從裝載它的那個實頁中置換出去，并在該實頁中裝入當前正要訪問的虛頁。三、程序流程圖三個模塊的流程圖1登錄模塊

6、參數(shù)輸入模塊開 始是*打開w accept窗口關閉w input窗口算法實現(xiàn)模塊始開擊取消按打開w input窗口關閉w accept窗口否用FCFS算用SSTF算用SCAN算用CSCAN算調用FCFS算法顯不結果是 調用SSTF算法,顯示結果是 調用SCAN算法”顯示結果是 調用CSCAN法顯示結果四、主要程序清單模塊之間的調用關系登錄模塊點擊確定按參數(shù)輸入模塊IF*1 町、算法實現(xiàn)模塊F點擊返回按錨I點擊確定按鈕#include#include#includeint producerand(int remainder);void initprocess();void chosedispla

7、ce();struct linknode * fifo(struct linknode *head,int randcount);void Optimal(struct linknode*head,int randprocess);struct linknode* LRU(struct linknode *head,int randprocess);struct linknode* initlink();void choicestey();int allotment(struct linknode *head);bool checkfifooptimal(struct linknode* he

8、ad,int checkpage);void recover(struct linknode *head,int randprocess);void recovermemory();int process1020;/數(shù)組的橫坐標為進程序列，縱坐標為每個進程的頁號int processallotment6;/存儲每個進程已經(jīng)分配的塊數(shù)int finishp6;/標志進程是否完成(1完成0不完成)int finishprocess=0;/進程完成的個數(shù)int findpage6;/每個進程命中的個數(shù)struct linknode *plinkhead6;struct linknode *plink

9、6;int memoryallotment6;int stey=0;struct linknode(struct linknode *linkper;/ 空鏈表的前驅指針int page;int processpage;int used;int memorypage;struct linknode *linknext; 空鏈表的后繼指針struct linknode *processper;/ 進程的前去指針struct linknode *processnext; 進程的后繼指針;int main()(struct linknode *head=initlink();initprocess(

10、);choicestey();int re=allotment(head);if(re=0)printf(內存分配出現(xiàn)問題。);system(pause);chosedisplace();recovermemory();system(pause);void recovermemory()int n=0;printf(是否回收全部已分配的內存空間？n回收輸入1,不回收輸入2n);scanf(%d,&n);if(n=1)for(int i=1;iused=0;head=head-processnext;void choicestey()printf(請選擇置換算法n);printf(1 表示 FI

11、FOn2 表示 Optimaln3 表示 LRUn);bool flag=true;while(flag)scanf(%d,&stey);switch(stey)(case 1:printf(您選擇的是 FIFO 替換算法 n);flag=false; break;case 2:printf(您選擇的是 Optimal 替換算法 n);flag=false;break;case 3:printf(您選擇的是 LRU 替換算法 n);flag=false;break; default :printf(輸入錯誤，t#重新輸入 n);void chosedisplace() 選擇置換算法struct

12、 linknode *head;int randcount;/ 進程序號bool find;while(finishprocess5)randcount=producerand(5);while(processallotmentrandcountprocessrandcount0)find=false;head=plinkheadrandcount;if(stey=1|stey=2)find=checkfifooptimal(head,processrandcountprocessallotmentrandcount+1);if(find=true)findpagerandcount+;)if

13、(find=false)/如果在鏈表中沒找到當前的頁數(shù)(switch(stey)(case 1:(plinkheadrandcount=fifo(plinkheadrandcount,randcount);break;)case 2:Optimal(plinkheadrandcount,randcount);break;)case 3:plinkheadrandcount=LRU(plinkheadrandcount,randcount);break;)processallotmentrandcount+;)if(finishprandcount=0)finishprocess+;finish

14、prandcount=1;)struct linknode *p;printf(進程執(zhí)行完后內存分配情況：n);for(int i=1;imemorypage,p-processpage,p-page);p=p-processnext;)for(int i=1;ipage=checkpage)return true;else(head=head-processnext;)return false;)struct linknode* LRU(struct linknode *head,int randprocess) (struct linknode *bhead;bhead=head;whil

15、e(head-processnext!=0)(if(head-page=processrandprocessprocessallotmentrandprocess+1) break;else head=head-processnext;)if(head-page!=processrandprocessprocessallotmentrandprocess+1) 沒找至U(bhead-page=processrandprocessprocessallotmentrandprocess+1;head-processnext=bhead;bhead-processper=head;bhead=bhe

16、ad-processnext;bhead-processper=0;head=head-processnext;head-processnext=0;plinkrandprocess=plinkrandprocess-processnext;return bhead;)else/俄到了 if(head=bhead)/ 頭head-processper=plinkrandprocess;plinkrandprocess-processnext=head;plinkrandprocess=plinkrandprocess-processnext;head=head-processnext;head

17、-processper=0;plinkrandprocess-processnext=0;findpagerandprocess+;return head;)elseif(head-processnext=0)/ 尾findpagerandprocess+;return bhead;)else/中間head-processnext-processper=head-processper;head-processper-processnext=head-processnext;head-processnext=0;head-processper=plinkrandprocess;plinkrand

18、process-processnext=head;plinkrandprocess=plinkrandprocess-processnext;findpagerandprocess+;return bhead;void Optimal(struct linknode*head,int randprocess)struct linknode *maxp;maxp=head;int max=1,i;while(head!=0)for(i=processallotmentrandprocess+1;ipage)break;if(imax)max=i;maxp=head;)head=head-proc

19、essnext;)maxp-page=processrandprocessprocessallotmentrandprocess+1;)struct linknode* fifo(struct linknode*head,int randprocess)struct linknode*phead;/ 改變后的頭指針phead=head;head-page=processrandprocessprocessallotmentrandprocess+1;while(head-processnext!=0)head=head-processnext;)head-processnext=phead;p

20、head-processper=head;phead=phead-processnext;head=head-processnext;head-processnext=0;phead-processper=0;return phead;)int allotment(struct linknode *head)/ 為進程分配內存int allotsum=0;/已經(jīng)分配完進程的個數(shù)int randprocess;/當前要分配內存的進程標號bool boolallot6;for(int i=1;i6;i+)(processallotmenti=0;boolalloti=false;memoryall

21、otmenti=0;while(allotsumused=0)(if(processallotmentrandprocess=0)(plinkheadrandprocess=head;plinkrandprocess=head;plinkrandprocess-processper=0;plinkrandprocess-processnext=0;head-processpage=randprocess;plinkrandprocess-page=processrandprocess1;head-used=1;printf( 內 存 塊 號： %dt 進 程 號： dt 頁號：dn,head-

22、memorypage,head-processpage,head-page);head=head- linknext;memoryallotmentrandprocess+;findpagerandprocess+;elseboolchecksame=checkfifooptimal(plinkheadrandprocess,processrandprocessprocessallotmentrandprocess+1);if(checksame=false)head-used=1;head-processnext=0;head-processper=plinkrandprocess;plin

23、krandprocess- processnext=head;head-processpage=randprocess;head-page=processrandprocessprocessallotmentrandprocess+1;plinkrandprocess=plinkrandprocess-processnext;%dt 頁printf( 內 存 塊 號： %dt 進 程 號： 號：dn,head-memorypage,head-processpage,head-page);head=head-linknext;memoryallotmentrandprocess+;findpag

24、erandprocess+;elseif(stey=3) plinkheadrandprocess=LRU(plinkheadrandprocess,randprocess);else findpagerandprocess+;)processallotmentrandprocess+;)else(printf(進程 %d 分配失敗 n,randprocess);return 0;)if(head=0)(printf(進程 %d 分配失敗 n,randprocess);return 0;)if(processallotmentrandprocess=processrandprocess0)(p

25、rintf(進程 %d 分配成功 n,randprocess);allotsum+;boolallotrandprocess=true;finishprocess+;finishprandprocess=1;)elseif(memoryallotmentrandprocess=4)allotsum+;boolallotrandprocess=true;printf(進程 %d 分配成功 n,randprocess);)struct linknode *p;printf(初始內存分配情況：n);for(int i=1;imemorypage,p-processpage,p-page);p=p-p

26、rocessnext;)return 1;)void initprocess()int perrandcount;for(int i=1;i=5;i+)/ 假設有 5 個進程perrandcount=producerand(10);/每個進程產(chǎn)生的頁面?zhèn)€數(shù)processi0=perrandcount;for(int j=1;j=perrandcount;j+)processij=producerand(20);/為第i個進程產(chǎn)生0至U 19之間的頁面順序)for(int i=1;i=5;i+)printf(進程序列 d,i);printf(該進程的調用頁號順序)；for(int j=1;j=p

27、rocessi0;j+)printf(%d ,processij);printf(n);)for(int i=1;iused=0;p-processnext=NULL;p-processper=NULL;p-linkper=q;p-linknext=NULL;p-memorypage=1;p-page=-1;for(int i=1;iused=0;p-processnext=NULL;p-processper=NULL;p-linkper=q;q-linknext=p;p-linknext=NULL;p-page=-1;p-memorypage=i+1;q=q-linknext;return

28、head;int producerand(int remainder)/ 產(chǎn)生隨機數(shù)(int randcount;randcount=(rand()+(unsigned)time(NULL)%remainder+1;return randcount;五、程序運行結果負C：D octi menti and Settings Md min istratortgl面匕uoycl桌面1131由咨表實廉的存禽管整+先出項面看A251-3 I346 6 11S 3213 529 21 180 9 78 112 1向Is恢RE用用用用用mm 一E1 二Irt，JTT b/Vt US fifififi進注工 、tB-1-t、Tl- V r V 171 該該該該該算ria 12315 羽Fotiu 冽列列列7J置FIFoptLRU 示示示 程程程程程選表表a勝芹請L21