虛擬存儲(chǔ)器管理方案試驗(yàn)報(bào)告

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

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

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

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

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

6、參數(shù)輸入模塊開 始是*打開w accept窗口關(guān)閉w input窗口算法實(shí)現(xiàn)模塊始開擊取消按打開w input窗口關(guān)閉w accept窗口否用FCFS算用SSTF算用SCAN算用CSCAN算調(diào)用FCFS算法顯不結(jié)果是 調(diào)用SSTF算法,顯示結(jié)果是 調(diào)用SCAN算法”顯示結(jié)果是 調(diào)用CSCAN法顯示結(jié)果四、主要程序清單模塊之間的調(diào)用關(guān)系登錄模塊點(diǎn)擊確定按參數(shù)輸入模塊IF*1 町、算法實(shí)現(xiàn)模塊F點(diǎn)擊返回按錨I點(diǎn)擊確定按鈕#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ù)組的橫坐標(biāo)為進(jìn)程序列，縱坐標(biāo)為每個(gè)進(jìn)程的頁號(hào)int processallotment6;/存儲(chǔ)每個(gè)進(jìn)程已經(jīng)分配的塊數(shù)int finishp6;/標(biāo)志進(jìn)程是否完成(1完成0不完成)int finishprocess=0;/進(jìn)程完成的個(gè)數(shù)int findpage6;/每個(gè)進(jìn)程命中的個(gè)數(shù)struct linknode *plinkhead6;struct linknode *plink

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

10、);choicestey();int re=allotment(head);if(re=0)printf(內(nèi)存分配出現(xiàn)問題。);system(pause);chosedisplace();recovermemory();system(pause);void recovermemory()int n=0;printf(是否回收全部已分配的內(nèi)存空間？n回收輸入1,不回收輸入2n);scanf(%d,&n);if(n=1)for(int i=1;iused=0;head=head-processnext;void choicestey()printf(請(qǐng)選擇置換算法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(輸入錯(cuò)誤，t#重新輸入 n);void chosedisplace() 選擇置換算法struct

12、 linknode *head;int randcount;/ 進(jìn)程序號(hào)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)/如果在鏈表中沒找到當(dāng)前的頁數(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(進(jìn)程執(zhí)行完后內(nèi)存分配情況：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)/ 為進(jìn)程分配內(nèi)存int allotsum=0;/已經(jīng)分配完進(jìn)程的個(gè)數(shù)int randprocess;/當(dāng)前要分配內(nèi)存的進(jìn)程標(biāo)號(hào)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( 內(nèi) 存 塊 號(hào)： %dt 進(jìn) 程 號(hào)： dt 頁號(hào)：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( 內(nèi) 存 塊 號(hào)： %dt 進(jìn) 程 號(hào)： 號(hào)：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(進(jìn)程 %d 分配失敗 n,randprocess);return 0;)if(head=0)(printf(進(jìn)程 %d 分配失敗 n,randprocess);return 0;)if(processallotmentrandprocess=processrandprocess0)(p

25、rintf(進(jìn)程 %d 分配成功 n,randprocess);allotsum+;boolallotrandprocess=true;finishprocess+;finishprandprocess=1;)elseif(memoryallotmentrandprocess=4)allotsum+;boolallotrandprocess=true;printf(進(jìn)程 %d 分配成功 n,randprocess);)struct linknode *p;printf(初始內(nèi)存分配情況：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+)/ 假設(shè)有 5 個(gè)進(jìn)程perrandcount=producerand(10);/每個(gè)進(jìn)程產(chǎn)生的頁面?zhèn)€數(shù)processi0=perrandcount;for(int j=1;j=perrandcount;j+)processij=producerand(20);/為第i個(gè)進(jìn)程產(chǎn)生0至U 19之間的頁面順序)for(int i=1;i=5;i+)printf(進(jìn)程序列 d,i);printf(該進(jìn)程的調(diào)用頁號(hào)順序)；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)生隨機(jī)數(shù)(int randcount;randcount=(rand()+(unsigned)time(NULL)%remainder+1;return randcount;五、程序運(yùn)行結(jié)果負(fù)C：D octi menti and Settings Md min istratortgl面匕uoycl桌面1131由咨表實(shí)廉的存禽管整+先出項(xiàng)面看A251-3 I346 6 11S 3213 529 21 180 9 78 112 1向Is恢RE用用用用用mm 一E1 二Irt，JTT b/Vt US fifififi進(jìn)注工 、tB-1-t、Tl- V r V 171 該該該該該算ria 12315 羽Fotiu 冽列列列7J置FIFoptLRU 示示示 程程程程程選表表a勝芹請(qǐng)L21