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

實用標準文案操作系統(tǒng)課程設(shè)計報告院（系）： 信息與數(shù)學學院專 業(yè)： 信息與計算科學姓 名: 張三班 級：＿ 信計11402學 號: 122914題 目： 頁面置換算法指導教師: 孫慶生2017年5月27日精彩文檔實用標準文案精彩文檔實用標準文案一、課程設(shè)計目的《Linux 操作系統(tǒng)課程設(shè)計》是在學完《操作系統(tǒng)》課程之后的實踐教學環(huán)節(jié)，是復習和檢驗所學課程的重要手段。 通過實驗環(huán)節(jié)， 加深學生對操作系統(tǒng)基本原理和工作過程的理解， 提高學生獨立分析問題、解決問題的能力，增強學生的動手能力。二、課程設(shè)計的任務(wù)和要求由于具體的操作系統(tǒng)相當復雜，不可能對所有管理系統(tǒng)進行詳細地分析。因此，選擇了操作系統(tǒng)中最重要的管理之一存儲器管理， 作為本設(shè)計的任務(wù)。 頁面置換算法是虛擬存儲管理實現(xiàn)的關(guān)鍵，要求在充分理解內(nèi)存頁面調(diào)度機制的基礎(chǔ)上，模擬實現(xiàn) OPT、FIFO、LRU幾種經(jīng)典頁面置換算法，比較各種置換算法的效率及優(yōu)缺點，從而了解虛擬存儲實現(xiàn)的過程。具體任務(wù)如下：分析設(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 ）精彩文檔實用標準文案三、課程的詳細設(shè)計）系統(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)出。）主程序流程圖開始輸入頁面序列輸入物理塊數(shù)調(diào)用各種置換算法， OPT，LRU，F(xiàn)IFO頁面置換算法計算缺頁次數(shù)和缺頁率結(jié)束主流程圖3）先進先出(FIFO)頁面置換算法精彩文檔實用標準文案算法的基本思想：該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。 該算法實現(xiàn)簡單只需把一個進程已調(diào)入內(nèi)存的頁面， 按先后次序存入一個時間數(shù)組，并將其中時間值最大的頁面進行淘汰，并替換入新的頁面就可以實現(xiàn)。算法流程圖：入口初始化數(shù)據(jù)指向下一個頁面Y頁面是否存在N 輸出當前頁,i++Y物理塊是否有空閑N將頁面放到空選擇最先進入的頁面閑的物理塊處作為淘汰頁Yi<頁面長度N計算缺頁率，并輸出數(shù)據(jù)結(jié)束FIFO置換算法4）最佳頁面置換置換算法（ OPT）算法的基本思想：其所選擇的被淘汰頁面，將是永不使用的，或者是在最長時間內(nèi)不再被訪問的頁面?？杀ＷC獲得最低的缺頁率。但由于人們目前還無法預知一個進程在內(nèi)存的若干個頁面精彩文檔實用標準文案中，哪一個頁面是未來最長時間內(nèi)不再被訪問的， 因而該算法也是無法實現(xiàn)的。 但是可利用該算法去評價其它算法。算法流程圖：入口初始化數(shù)據(jù)指向下一個頁面Y頁面是否存在N 輸出當前頁,Y物理塊是否有空閑N

i++將頁面放到空閑 的選擇以后最長時間內(nèi)（未來） 物理塊處不在被訪問的頁面作為淘汰頁i<頁面長度YN計算缺頁率，并輸出數(shù)據(jù)結(jié)束OPT頁面置換算法5）最近最久未使用頁面置換算法 LRU算法的基本思想：當需要淘汰某一頁時，選擇離當前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰。該算法的主要出發(fā)點是，如果某頁被訪問了，則它可能馬上還被訪問?；蛘叻催^來說，如果某頁很長時間未被訪問，則它在最近一段時間不會被訪問。精彩文檔實用標準文案算法流程圖：入口初始化數(shù)據(jù)指向下一個頁面Y頁面是否存在N 輸出當前頁,i++Y物理塊是否有空閑N將頁面放到空選擇最近最久未使用閑的物理塊處的頁面作為淘汰頁Yi<頁面長度N計算缺頁率，并輸出數(shù)據(jù)結(jié)束LRU頁面置換算法四、源程序代碼#include"stdio.h"#include"malloc.h"#defineN20#definenum3精彩文檔實用標準文案/*進程分配物理塊數(shù)目 */intA[N]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};typedefstructpage /*頁表映像*/{intaddress;/* 頁面地址*/structpage*next;}page;structpage*head,*run,*rear;voidinitial()/* 進程分配物理塊 */{inti=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;}voidprint(){page*p=head->next;while(p){if(p->address!=-1) /*避免輸出-1*/printf("%d\t",p->address);p=p->next;}printf("\n");}intsearch(intn) /*判斷鏈表中是否有 n*/{page*p;inti=0;p=head;while(p->next){if(p->next->address==n)精彩文檔實用標準文案{printf("Getitatthepage%d\n",i+1);run=p;return1;}p=p->next;i++;}return0;}voidchangeOPT(intn,intposition){inti;inttotal=0;intflag=1; /*默認鏈表填滿 */intdistance[num];/*用于存放距離*/intMAX;intorder=0;page*p,*q;p=head->next;q=head->next;for(i=0;i<num;i++)/*初始化距離*/{精彩文檔實用標準文案distance[i]=100;}i=0;while(p)/* 判斷鏈表中是否填滿 */{if(p->address==-1){flag=0;break;}p=p->next;i++;}if(!flag) /*鏈表沒有填滿的情況 */{p->address=n;printf("Changethepage%d\n",i+1);}else/*鏈表已經(jīng)填滿的情況 */{while(q)/* 計算距離*/{for(i=position+1;i<N;i++)精彩文檔實用標準文案{if(q->address==A[i]){distance[total]=i-position;break;}}total++;q=q->next;}MAX=distance[0];for(i=0;i<num;i++)/* 計算最大距離*/{if(distance[i]>MAX){MAX=distance[i];order=i; /*記錄待替換的頁面的位置 */}}printf("Changethepage%d\n",order+1);i=0;p=head->next;while(p)/* 頁面替換*/精彩文檔實用標準文案{if(i==order){p->address=n;}i++;p=p->next;}}}voidchangeFIFO(intn,intposition){inti=0;intflag=1; //默認隊列已滿page*p,*delect;p=head->next;while(p){if(p->address==-1) //隊列未滿{flag=0;p->address=n;精彩文檔實用標準文案printf("Changethepage%d\n",i+1);break;}p=p->next;i++;}if(flag) //隊列已滿{delect=head->next;delect->address=n;head->next=delect->next;printf("Delectfromthehead,andaddnewtotheend.\n");rear->next=delect;rear=delect;rear->next=NULL;}}voidchangeLRU(intn,intposition){inti;inttotal=0;intflag=1; /*默認為已滿*/intdistance[num];精彩文檔實用標準文案intMAX;intorder=0;page*p,*q;p=head->next;q=head->next;for(i=0;i<num;i++){distance[i]=100;}i=0;while(p)/* 判斷鏈表是否已滿 */{if(p->address==-1){flag=0;break;}p=p->next;i++;}if(!flag) /*鏈表沒有滿的情況 */{p->address=n;精彩文檔實用標準文案printf("Changethepage%d\n",i+1);}else/*鏈表已滿的情況 */{while(q){for(i=position-1;i>=0;i--) /*向前計算距離 */{if(q->address==A[i]){distance[total]=position-i;break;}}total++;q=q->next;}MAX=distance[0];for(i=0;i<num;i++)/* 計算最遠距離*/{if(distance[i]>MAX){MAX=distance[i];精彩文檔實用標準文案order=i;}}printf("Changethepage%d\n",order+1);i=0;p=head->next;while(p)/* 頁面替換*/{if(i==order){p->address=n;}i++;p=p->next;}}}floatOPT(){inti;intlose=0;floatlosef;floatpercent;精彩文檔實用標準文案for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeOPT(A[i],i);}print();}losef=(float)lose;percent=1-(losef/N);returnpercent;}floatLRU(){inti;intlose=0;floatlosef;floatpercent;for(i=0;i<N;i++){if(search(A[i])==0){精彩文檔實用標準文案lose++;changeLRU(A[i],i);}print();}losef=(float)lose;percent=1-(losef/N);returnpercent;}floatFIFO(){inti;intlose=0;floatlosef;floatpercent;page*p;for(i=0;i<N;i++){if(search(A[i])==0){lose++;changeFIFO(A[i],i);}精彩文檔實用標準文案else{p=run->next;run->next=p->next;rear->next=p;rear=p;rear->next=NULL;printf("Moveittoendofqueue.\n");}print();}losef=(float)lose;percent=1-(losef/N);returnpercent;}voidmain()/* 主函數(shù)部分*/{floatpercent;intchoice;printf("Selectthearithmetic:\n(1)OPT\n(2)LRU\n(3)FIFO\nyourchoiceis:");scanf("%d",&choice);/* 選擇頁面置換算法 */initial();/* 創(chuàng)建進程*/if(choice==1)/* 采用OPT算法置換*/精彩文檔實用標準文案{percent=OPT();/* 計算OPT時的缺頁率*/printf("ThepercentofOPTis%f\n",percent);}elseif(choice==2)/* 采用LRU算法置換*/{percent=LRU();/* 計算