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

1、精選文庫操作系統(tǒng)課程設(shè)計報告院（系）：信息與數(shù)學(xué)學(xué)院專 業(yè)：信息與計算科學(xué)姓 名：張三班 級：信計11402學(xué) 號:12 29 14題 目：頁面置換算法指導(dǎo)教師：孫慶生2017年5月27日一、課程設(shè)計目的Linux操作系統(tǒng)課程設(shè)計是在學(xué)完操作系統(tǒng)課程之后的實踐教學(xué)環(huán)節(jié)，是復(fù)習(xí)和檢驗所學(xué)課程的重要手段。通過實驗環(huán)節(jié)，加深學(xué)生對操作系統(tǒng)基本原理和工作過程的理解，提高學(xué)生獨立分析問題、解決問題的能力，增強學(xué)生的動手能力。二、課程設(shè)計的任務(wù)和要求由于具體的操作系統(tǒng)相當(dāng)復(fù)雜，不可能對所有管理系統(tǒng)進(jìn)行詳細(xì)地分析。因此，選擇了操作系統(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)：定義為進(jìn)程分配的物理塊；定義進(jìn)程運行所需訪問的頁面號；定義頁的結(jié)構(gòu)；2）模擬三種頁面置換算法；3）比較各種算法的優(yōu)劣。4）對程序的每一部分要有詳細(xì)的設(shè)計分析說明。5）源代碼格式要規(guī)范。6）設(shè)計合適的測試用例，對得到的運行結(jié)果要有分析。任務(wù)要求：Linux 平臺下實現(xiàn)（ Windows+ VMware+ Ubuntu ）三、課程的詳細(xì)設(shè)計1）系統(tǒng)設(shè)計在

3、進(jìn)程運行過程中， 若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進(jìn)程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)中。但應(yīng)將哪 個頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換 算法。一個好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不再-2精選文庫會訪問的頁面換出，或?qū)⒛切┰谳^長時間內(nèi)不會再訪問的頁面調(diào)出2）主程序流程圖主流程圖3）先進(jìn)先出（FIFO）頁面置換算法算法的基本思想：該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面

4、，按先后次序存入一個時間數(shù)組，并將其中時間值最大的頁面進(jìn)行淘汰，并替換入新的頁面就可以實現(xiàn)。算法流程圖：FIFO置換算法4）最佳頁面置換置換算法（ OPT）算法的基本思想： 其所選擇的被淘汰頁面，將是永不使用的， 或者是在最長時間內(nèi)不再被訪問的頁面?？杀ＷC獲得最低的缺頁率。但由于人們目前還無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法也是無法實現(xiàn)的。但是可利用該算法去評價其它算法。算法流程圖：OPT頁面置換算法5）最近最久未使用頁面置換算法LRU算法的基本思想：當(dāng)需要淘汰某一頁時，選擇離當(dāng)前時間最近的一段時間內(nèi)最久沒有使用過 的頁先淘汰。該算法的主要出

5、發(fā)點是，如果某頁被訪問了，則它可能馬上還被訪問。或者反過來 說，如果某頁很長時間未被訪問，則它在最近一段時間不會被訪問。算法流程圖：四、源程序代碼#includestdio.h#includemalloc.h#define N 20#define num 3/*進(jìn)程分配物理塊數(shù)目*/int AN尸7。1,2,0,3。423。321,2。1,7。1;typedef struct page /* 頁表映像 */int address; /* 頁面地址 */struct page *next;page;struct page *head,*run,*rear;void initial。/*進(jìn)程分配物

6、理塊*/int i=1;page *p,*q;head=(page *)malloc(sizeof(page);p=head;for(i=1; inext=q;q-address=-1;q-next=NULL;p=q；rear=p;void print()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-nex

7、t-address=n)printf(Get it at the page %dn,i+1);run=p;return 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; iaddress=-1)flag=0;break;p=p-next;i+;if(用ag)/*鏈表沒有填

8、滿的情況*/p-address=n;printf(Change the page %dn,i+1);else /*鏈表已經(jīng)填滿的情況*/while(q) /*計算距離*/for(i=position+1; iaddress=Ai) distancetotal=i-position; break;total+;q=q-next;MAX=distance0;for(i=0; iMAX)MAX=distancei;order=i; /*記錄待替換的頁面的位置*/printf(Change the page %dn,order+1);i=0;p=head-next; while(p) /*頁面替換*/

9、 if(i=order) p-address=n; i+； p=p-next;void changeFIFO(int n,int position)int i=0;int flag=1;默認(rèn)隊列已滿page *p,*delect;p=head-next;while(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;p

10、rintf(Delect from the head, and add new to the end.n); rear-next=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; iaddress=-1)flag=0;break;p=p-next;i+;if(用ag)/*鏈表沒

11、有滿的情況*/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; iMAX) MAX=distancei;order=i;printf(Change the page %dn,order+1);i=0;p=head-next;while(p) /*頁面替換*/if

12、(i=order)p-address=n;i+；p=p-next;float OPT()int i;int lose=0;float losef;float percent;for(i=0; iN; i+)if(search(Ai)=0)lose+;changeOPT(Ai,i);print();losef=(float)lose;percent=1-(losef/N);return percent;float LRU()int i;int lose=0;float losef;float percent;for(i=0; iN; i+)if(search(Ai)=0)lose+;change

13、LRU(Ai,i);print();losef=(float)lose;percent=1-(losef/N);return percent;float FIFO()int i;int lose=0;float losef;float percent;page *p;for(i=0; inext;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 m

14、ain()/*主函數(shù)部分*/float percent;int choice;printf(Select the arithmetic:nOPTn(2)LRUn(3)FIFOn your choice is:); scanf(%d,&choice);/*選擇頁面置換算法*/initial。;/* 創(chuàng)建進(jìn)程 */if(choice=1)/* 采用 OPT 算法置換 */ percent=OPT();/*計算OPT時的缺頁率*/printf(The percent of OPT is %fn,percent);else if(choice=2)/* 采用 LRU 算法置換 */ percent=L

15、RU();/*計算LRU時的缺頁率*/printf(The percent of LRU is %fn,percent);else if(choice=3)/* 采用 FIFO 算法置換 */percent=FIFO();/* 計算 FIFO 時的缺頁率 */ printf(The percent of FIFO is %fn,percent);else printf(Your choice is invalid.);14五、調(diào)試結(jié)果顯示331123235 Q.55OaQ0your choice ls:iChange the page 1 7Change the page 27flChange

16、 the page 3 7 fl 1Change the page 1 291Get it at the page 2Z01the page 3.20iGet it at the page 2201Change the page 2 24iGet it at the page 1243Get it at the page 243Change the 口己ge 2 203Get It at the pagp 203Get it at the pdge 263Change the page 3 201Get it at the page 2G1Get It at the page 201Get I

17、t at the pag 201Change the page 1 761Get it at the page 701Get it at the page 7G1The percent of OPT(1)OPT置換算法(2)LRU置換算法your choice vs：2Change th? page 1 1ChanRu the page 2 7 eChange the page 3 761Change the page 1 21Get it at the page 2 201Change the page 3 i2 e 3Get it at the page 2 2fl3107Get it a

18、t the page 1 107The percent of LRU is 0,400000Change the p白ge 1 403Change the page 3 462Change the page 2 432Change the pdge 1 -)32Gf七 It 七 thp pgu 2your choice is i S Change the page主文件夷 口叫e2 70Change the page 3 701Delect from the head, and 912Get it at the page 1 Move It to end of queue- 120Oelect from the head, and Z03Get tt at the page 2 Move ittoend