操作系統(tǒng)頁(yè)面置換算法

1、 操作系統(tǒng)課程設(shè)計(jì)報(bào)告院 （系）： 信息與數(shù)學(xué)學(xué)院 專 業(yè)： 信息與計(jì)算科學(xué) 姓 名: 張三 班 級(jí)： 信計(jì)11402 學(xué) 號(hào): 12 29 14 題 目： 頁(yè)面置換算法 指導(dǎo)教師: 孫慶生 2017年5月27日一、課程設(shè)計(jì)目的Linux操作系統(tǒng)課程設(shè)計(jì)是在學(xué)完操作系統(tǒng)課程之后的實(shí)踐教學(xué)環(huán)節(jié)，是復(fù)習(xí)和檢驗(yàn)所學(xué)課程的重要手段。通過(guò)實(shí)驗(yàn)環(huán)節(jié)，加深學(xué)生對(duì)操作系統(tǒng)基本原理和工作過(guò)程的理解，提高學(xué)生獨(dú)立分析問(wèn)題、解決問(wèn)題的能力，增強(qiáng)學(xué)生的動(dòng)手能力。二、課程設(shè)計(jì)的任務(wù)和要求由于具體的操作系統(tǒng)相當(dāng)復(fù)雜，不可能對(duì)所有管理系統(tǒng)進(jìn)行詳細(xì)地分析。因此，選擇了操作系統(tǒng)中最重要的管理之一存儲(chǔ)器管理，作為本設(shè)計(jì)的任務(wù)。頁(yè)

2、面置換算法是虛擬存儲(chǔ)管理實(shí)現(xiàn)的關(guān)鍵，要求在充分理解內(nèi)存頁(yè)面調(diào)度機(jī)制的基礎(chǔ)上，模擬實(shí)現(xiàn)OPT、FIFO、LRU幾種經(jīng)典頁(yè)面置換算法，比較各種置換算法的效率及優(yōu)缺點(diǎn)，從而了解虛擬存儲(chǔ)實(shí)現(xiàn)的過(guò)程。具體任務(wù)如下：1) 分析設(shè)計(jì)內(nèi)容，給出解決方案要說(shuō)明設(shè)計(jì)實(shí)現(xiàn)的原理；采用的數(shù)據(jù)結(jié)構(gòu)：定義為進(jìn)程分配的物理塊；定義進(jìn)程運(yùn)行所需訪問(wèn)的頁(yè)面號(hào)；定義頁(yè)的結(jié)構(gòu)；2）模擬三種頁(yè)面置換算法；3）比較各種算法的優(yōu)劣。4）對(duì)程序的每一部分要有詳細(xì)的設(shè)計(jì)分析說(shuō)明。5）源代碼格式要規(guī)范。6） 設(shè)計(jì)合適的測(cè)試用例，對(duì)得到的運(yùn)行結(jié)果要有分析。任務(wù)要求：Linux平臺(tái)下實(shí)現(xiàn)（Windows+ VMware+ Ubuntu） 三、課程

3、的詳細(xì)設(shè)計(jì)1）系統(tǒng)設(shè)計(jì)在進(jìn)程運(yùn)行過(guò)程中，若其所要訪問(wèn)的頁(yè)面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送磁盤(pán)的對(duì)換區(qū)中。但應(yīng)將哪 個(gè)頁(yè)面調(diào)出，須根據(jù)一定的算法來(lái)確定。通常，把選擇換出頁(yè)面的算法稱為頁(yè)面置換算法。 一個(gè)好的頁(yè)面置換算法，應(yīng)具有較低的頁(yè)面更換頻率。從理論上講，應(yīng)將那些以后不再會(huì)訪問(wèn)的頁(yè)面換出，或?qū)⒛切┰谳^長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問(wèn)的頁(yè)面調(diào)出。2）主程序流程圖輸入頁(yè)面序列輸入物理塊數(shù)調(diào)用各種置換算法，OPT，LRU，F(xiàn)IFO頁(yè)面置換算法計(jì)算缺頁(yè)次數(shù)和缺頁(yè)率結(jié)束開(kāi)始主流程圖3）先進(jìn)先出(FIFO)頁(yè)面置換算

4、法算法的基本思想：該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序存入一個(gè)時(shí)間數(shù)組，并將其中時(shí)間值最大的頁(yè)面進(jìn)行淘汰，并替換入新的頁(yè)面就可以實(shí)現(xiàn)。算法流程圖： 入口初始化數(shù)據(jù)i指向下一個(gè)頁(yè)面頁(yè)面是否存在物理塊是否有空閑選擇最先進(jìn)入的頁(yè)面作為淘汰頁(yè)計(jì)算缺頁(yè)率，并輸出數(shù)據(jù) 結(jié)束輸出當(dāng)前頁(yè),i+將頁(yè)面放到空閑的物理塊處i<頁(yè)面長(zhǎng)度YYYNNNFIFO置換算法4）最佳頁(yè)面置換置換算法（OPT）算法的基本思想：其所選擇的被淘汰頁(yè)面，將是永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面?？杀ＷC獲得最低的缺頁(yè)率。但由于人

5、們目前還無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的，因而該算法也是無(wú)法實(shí)現(xiàn)的。但是可利用該算法去評(píng)價(jià)其它算法。算法流程圖： 入口初始化數(shù)據(jù)i指向下一個(gè)頁(yè)面頁(yè)面是否存在物理塊是否有空閑選擇以后最長(zhǎng)時(shí)間內(nèi)（未來(lái)）不在被訪問(wèn)的頁(yè)面作為淘汰頁(yè)計(jì)算缺頁(yè)率，并輸出數(shù)據(jù) 結(jié)束輸出當(dāng)前頁(yè), i+將頁(yè)面放到空閑的物理塊處i<頁(yè)面長(zhǎng)度YYYNNNOPT頁(yè)面置換算法5）最近最久未使用頁(yè)面置換算法LRU算法的基本思想：當(dāng)需要淘汰某一頁(yè)時(shí)，選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒(méi)有使用過(guò)的頁(yè)先淘汰。該算法的主要出發(fā)點(diǎn)是，如果某頁(yè)被訪問(wèn)了，則它可能馬上還被訪問(wèn)?；蛘叻催^(guò)來(lái)說(shuō)，如果某頁(yè)很

6、長(zhǎng)時(shí)間未被訪問(wèn)，則它在最近一段時(shí)間不會(huì)被訪問(wèn)。算法流程圖： 入口初始化數(shù)據(jù)i指向下一個(gè)頁(yè)面頁(yè)面是否存在物理塊是否有空閑選擇最近最久未使用的頁(yè)面作為淘汰頁(yè)計(jì)算缺頁(yè)率，并輸出數(shù)據(jù) 結(jié)束輸出當(dāng)前頁(yè),i+將頁(yè)面放到空閑的物理塊處i<頁(yè)面長(zhǎng)度YYYNNNLRU頁(yè)面置換算法四、源程序代碼#include"stdio.h"#include"malloc.h"#define N 20#define num 3/*進(jìn)程分配物理塊數(shù)目*/int AN=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1;typedef struct page

7、/*頁(yè)表映像*/ int address; /*頁(yè)面地址*/ struct page *next; page;struct page *head,*run,*rear;void initial() /*進(jìn)程分配物理塊*/ int i=1; page *p,*q; head=(page *)malloc(sizeof(page); p=head; for(i=1; i<=num; i+) q=(page *)malloc(sizeof(page); p->next=q; q->address=-1; q->next=NULL; p=q; rear=p;void print

8、()page *p=head->next;while(p)if(p->address!=-1)/*避免輸出-1*/printf("%dt",p->address);p=p->next;printf("n");int search(int n)/*判斷鏈表中是否有n*/ page *p; int i=0; p=head; while(p->next) if(p->next->address=n) printf("Get it at the page %dn",i+1); run=p; retur

9、n 1; p=p->next; i+; return 0;void changeOPT(int n,int position) int i; int total=0; int flag=1;/*默認(rèn)鏈表填滿*/ int distancenum;/*用于存放距離*/ int MAX; int order=0; page *p,*q; p=head->next; q=head->next; for(i=0; i<num; i+)/*初始化距離*/ distancei=100; i=0; while(p)/*判斷鏈表中是否填滿*/ if(p->address=-1) f

10、lag=0; break; p=p->next; i+; if(!flag)/*鏈表沒(méi)有填滿的情況*/ p->address=n; printf("Change the page %dn",i+1); else/*鏈表已經(jīng)填滿的情況*/ while(q)/*計(jì)算距離*/ for(i=position+1; i<N; i+) if(q->address=Ai) distancetotal=i-position; break; total+; q=q->next; MAX=distance0; for(i=0; i<num; i+)/*計(jì)算最

11、大距離*/ if(distancei>MAX) MAX=distancei; order=i;/*記錄待替換的頁(yè)面的位置*/ printf("Change the page %dn",order+1); i=0; p=head->next; while(p)/*頁(yè)面替換*/ if(i=order) p->address=n; i+; p=p->next; void changeFIFO(int n,int position) int i=0; int flag=1;/默認(rèn)隊(duì)列已滿 page *p,*delect; p=head->next; w

12、hile(p) if(p->address=-1)/隊(duì)列未滿 flag=0; p->address=n; printf("Change the page %dn",i+1); break; p=p->next; i+; if(flag)/隊(duì)列已滿 delect=head->next; delect->address=n; head->next=delect->next; printf("Delect from the head, and add new to the end.n"); rear->next=

13、delect; rear=delect; rear->next=NULL; void changeLRU(int n,int position) int i; int total=0; int flag=1;/*默認(rèn)為已滿*/ int distancenum; int MAX; int order=0; page *p,*q; p=head->next; q=head->next; for(i=0; i<num; i+) distancei=100; i=0; while(p)/*判斷鏈表是否已滿*/ if(p->address=-1) flag=0; break

14、; p=p->next; i+; if(!flag)/*鏈表沒(méi)有滿的情況*/ p->address=n; printf("Change the page %dn",i+1); else/*鏈表已滿的情況*/ while(q) for(i=position-1; i>=0; i-)/*向前計(jì)算距離*/ if(q->address=Ai) distancetotal=position-i; break; total+; q=q->next; MAX=distance0; for(i=0; i<num; i+)/*計(jì)算最遠(yuǎn)距離*/ if(dis

15、tancei>MAX) MAX=distancei; order=i; printf("Change the page %dn",order+1); i=0; p=head->next; while(p)/*頁(yè)面替換*/ if(i=order) p->address=n; i+; p=p->next; float OPT() int i; int lose=0; float losef; float percent; for(i=0; i<N; i+) if(search(Ai)=0) lose+; changeOPT(Ai,i); print

16、(); losef=(float)lose; percent=1-(losef/N); return percent;float LRU() int i; int lose=0; float losef; float percent; for(i=0; i<N; i+) if(search(Ai)=0) lose+; changeLRU(Ai,i); print(); losef=(float)lose; percent=1-(losef/N); return percent;float FIFO() int i; int lose=0; float losef; float perce

17、nt;page *p; for(i=0; i<N; i+) if(search(Ai)=0) lose+; changeFIFO(Ai,i); else p=run->next; run->next=p->next; rear->next=p; rear=p; rear->next=NULL; printf("Move it to end of queue.n"); print(); losef=(float)lose; percent=1-(losef/N); return percent;void main()/*主函數(shù)部分*/ fl

18、oat percent; int choice; printf("Select the arithmetic:n(1)OPTn(2)LRUn(3)FIFOn your choice is:"); scanf("%d",&choice);/*選擇頁(yè)面置換算法*/ initial();/*創(chuàng)建進(jìn)程*/ if(choice=1)/*采用OPT算法置換*/ percent=OPT();/*計(jì)算OPT時(shí)的缺頁(yè)率*/ printf("The percent of OPT is %fn",percent); else if(choice=2)/*采用LRU算法置換*/ percent=LRU