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

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

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

3、的詳細設(shè)計1）系統(tǒng)設(shè)計在進程運行過程中，若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進程能正常運行，系統(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頁面置換算法計算缺頁次數(shù)和缺頁率結(jié)束開始主流程圖3）先進先出(FIFO)頁面置換算

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

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

6、長時間未被訪問，則它在最近一段時間不會被訪問。算法流程圖： 入口初始化數(shù)據(jù)i指向下一個頁面頁面是否存在物理塊是否有空閑選擇最近最久未使用的頁面作為淘汰頁計算缺頁率，并輸出數(shù)據(jù) 結(jié)束輸出當前頁,i+將頁面放到空閑的物理塊處i<頁面長度YYYNNNLRU頁面置換算法四、源程序代碼#include"stdio.h"#include"malloc.h"#define N 20#define num 3/*進程分配物理塊數(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() /*進程分配物理塊*/ 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;/*默認鏈表填滿*/ 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)/*計算距離*/ 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+)/*計算最

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;/默認隊列已滿 page *p,*delect; p=head->next; w

12、hile(p) if(p->address=-1)/隊列未滿 flag=0; p->address=n; printf("Change the page %dn",i+1); break; p=p->next; i+; if(flag)/隊列已滿 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;/*默認為已滿*/ 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-)/*向前計算距離*/ if(q->address=Ai) distancetotal=position-i; break; total+; q=q->next; MAX=distance0; for(i=0; i<num; i+)/*計算最遠距離*/ 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)建進程*/ if(choice=1)/*采用OPT算法置換*/ percent=OPT();/*計算OPT時的缺頁率*/ printf("The percent of OPT is %fn",percent); else if(choice=2)/*采用LRU算法置換*/ percent=LRU