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

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

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

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

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

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

6、長時間未被訪問，則它在最近一段時間不會被訪問。算法流程圖： 入口初始化數(shù)據(jù)i指向下一個頁面頁面是否存在物理塊是否有空閑選擇最近最久未使用的頁面作為淘汰頁計(jì)算缺頁率，并輸出數(shù)據(jù) 結(jié)束輸出當(dāng)前頁,i+將頁面放到空閑的物理塊處i<頁面長度YYYNNNLRU頁面置換算法四、源程序代碼#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、/*頁表映像*/ int address; /*頁面地址*/ 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)/*鏈表沒有填滿的情況*/ 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;/*記錄待替換的頁面的位置*/ printf("Change the page %dn",order+1); i=0; p=head->next; while(p)/*頁面替換*/ 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)/*鏈表沒有滿的情況*/ 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)/*頁面替換*/ 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);/*選擇頁面置換算法*/ initial();/*創(chuàng)建進(jìn)程*/ if(choice=1)/*采用OPT算法置換*/ percent=OPT();/*計(jì)算OPT時的缺頁率*/ printf("The percent of OPT is %fn",percent); else if(choice=2)/*采用LRU算法置換*/ percent=LRU