1、頁面置換算法的演示一題目要求：設計一個虛擬存儲區和內存工作區，編程序演示下述算法的具體實現過程，并計算訪問命中率：要求設計主界面以靈活選擇某算法，且以下算法都要實現1) 最佳置換算法(OPT)：將以后永不使用的或許是在最長(未來)時間內不再被訪問的頁面換出。2) 先進先出算法(FIFO)：淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的頁面。4) 最不經常使用算法(LFU)二實驗目的：1、用C語言編寫OPT、FIFO、LRU，LFU四種置換算法。2、熟悉內存分頁管理策略。3、了解頁面置換的算法。4、掌握一般常用的調度算

2、法。5、根據方案使算法得以模擬實現。6、鍛煉知識的運用能力和實踐能力。三相關知識：1虛擬存儲器的引入： 局部性原理：程序在執行時在一較短時間內僅限于某個部分；相應的，它所訪問的存儲空間也局限于某個區域，它主要表現在以下兩個方面：時間局限性和空間局限性。2虛擬存儲器的定義： 虛擬存儲器是只具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的一種存儲器系統。3虛擬存儲器的實現方式： 分頁請求系統，它是在分頁系統的基礎上，增加了請求調頁功能、頁面置換功能所形成的頁面形式虛擬存儲系統。 請求分段系統，它是在分段系統的基礎上，增加了請求調段及分段置換功能后，所形成的段式虛擬存儲系統。4頁面分配：

3、平均分配算法，是將系統中所有可供分配的物理塊，平均分配給各個進程。 按比例分配算法，根據進程的大小按比例分配物理塊。 考慮優先的分配算法，把內存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據個進程的優先權，適當的增加其相應份額后，分配給各進程。5頁面置換算法：常用的頁面置換算法有OPT、FIFO、LRU、Clock、LFU、PBA等。四設計思想： 選擇置換算法，先輸入所有頁面號，為系統分配物理塊，依次進行置換：OPT基本思想：是用一維數組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數組nextmSIZE記錄物理塊中對應頁面的最

4、后訪問時間。每當發生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調出該頁，換入所缺的頁面。【特別聲明】若物理塊中的頁面都不再使用，則每次都置換物理塊中第一個位置的頁面。FIFO基本思想：是用隊列存儲內存中的頁面，隊列的特點是先進先出，與該算法是一致的，所以每當發生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁。或者借助輔助數組timemSIZE記錄物理塊中對應頁面的進入時間，每次需要置換時換出進入時間最小的頁面。LRU基本思想：是用一維數組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數組flag10標記頁面的訪問時間。每當使用頁面時，刷新訪問時間。發生缺頁

5、時，就從物理塊中頁面標記最小的一頁，調出該頁，換入所缺的頁面。五流程圖：如下頁所示將頁號放入物理塊中，編號加1引用串編號大于物理塊數?載入頁號序列，從第0個得到頁號開始頁號在物理塊中?根據選擇的置換算法完成置換頁號序列載完?結束是否是是是是六源代碼：如下頁所示【使用C語言】#include <stdio.h>#include <stdlib.h>/*全局變量*/int mSIZE; /*物理塊數*/int pSIZE; /*頁面號引用串個數*/static int memery10=0; /*物理塊中的頁號*/static int page100=0; /*頁面號引用串

6、*/static int temp10010=0; /*輔助數組*/*置換算法函數*/void FIFO();void LRU();void OPT();/*輔助函數*/void print(unsigned int t);void designBy();void download();void mDelay(unsigned int Delay);/*主函數*/void main() int i,k,code;system("color 0A");designBy();printf("請按任意鍵進行初始化操作. n");printf("n&q

7、uot;);printf(" >>>");getch();system("cls");system("color 0B");printf("請輸入物理塊的個數(M<=10)：");scanf("%d",&mSIZE);printf("請輸入頁面號引用串的個數(P<=100)：");scanf("%d",&pSIZE);puts("請依次輸入頁面號引用串(連續輸入，無需隔開)：");for(i

8、=0;i<pSIZE;i+) scanf("%1d",&pagei);download();system("cls");system("color 0E"); do puts("輸入的頁面號引用串為：");for(k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)printf("%dn",pa

9、gei);elseprintf("%d ",pagei);printf("* * * * * * * * * * * * * * * * * * * * * * *n"); printf("* 請選擇頁面置換算法：ttt *n");printf("* - *n"); printf("* 1.先進先出(FIFO) 2.最近最久未使用(LRU) *n");printf("* 3.最佳(OPT) 4.退出 *n");printf("* * * * * * * * * *

10、* * * * * * * * * * * * *n"); printf("請選擇操作： bb"); scanf("%d",&code); switch(code) case 1: FIFO(); break; case 2: LRU(); break; case 3: OPT(); break; case 4:system("cls");system("color 0A");designBy(); /*顯示設計者信息后退出*/printf("謝謝使用頁面置換算法演示器! 正版授權 n&

11、quot;);printf("n"); exit(0);default:printf("輸入錯誤，請重新輸入："); printf("按任意鍵重新選擇置換算法：>>>");getch();system("cls"); while (code!=4);getch();/*載入數據*/void download()int i;system("color 0D");printf("n");printf("正在載入數據，請稍候 !n");prin

12、tf("n");printf("Loading.n");printf(" O");for(i=0;i<51;i+)printf("b");for(i=0;i<50;i+)mDelay(pSIZE+mSIZE)/2);printf(">");printf("nFinish.n載入成功，按任意鍵進入置換算法選擇界面：>>>");getch();/*設置延遲*/void mDelay(unsigned int Delay) unsigned in

13、t i; for(;Delay>0;Delay-) for(i=0;i<124;i+) printf(" b"); /*顯示設計者信息*/ void designBy()printf("n");printf(" 課題三：頁面置換算法 n");printf(" 學號：081001117 n");printf(" 姓名：邢磊 <Visual C+ 6.0>n");printf("n");void print(unsigned int t)int i,j,k

14、,l;int flag;for(k=0;k<=(pSIZE-1)/20;k+)for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1)printf("%dn",pagei);elseprintf("%d ",pagei);for(j=0;j<mSIZE;j+)for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i+)if(i>=j)printf("

15、; |%d|",tempij);elseprintf(" | |");for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1);i+)for(flag=0,l=0;l<mSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*頁面在物理塊中*/printf(" ");elseprintf(" |%d|",tempij);/*每行顯示20個*/if(i%20=0)continue;printf("n");pri

16、ntf("-n");printf("缺頁次數：%dtt",t+mSIZE);printf("缺頁率：%d/%dn",t+mSIZE,pSIZE);printf("置換次數：%dtt",t);printf("訪問命中率：%d%n",(pSIZE-(t+mSIZE)*100/pSIZE);printf("-n");/*計算過程延遲*/void compute()int i;printf("正在進行相關計算，請稍候");for(i=1;i<20;i+)mD

17、elay(15);if(i%4=0)printf("bbbbbb bbbbbb");elseprintf("");for(i=0;i+<30;printf("b");for(i=0;i+<30;printf(" ");for(i=0;i+<30;printf("b");/*先進先出頁面置換算法*/void FIFO() int memery10=0; int time10=0; /*記錄進入物理塊的時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ i

18、nt count=0; /*記錄置換次數*/*前mSIZE個數直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; timei=i; for(j=0;j<mSIZE;j+)tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計算換出頁*/ max=time0<time1?0:1;for(m=2;m<mSIZ

19、E;m+)if(timem<timemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁進入物理塊的時間*/ for(j=0;j<mSIZE;j+)tempij=memeryj; else for(j=0;j<mSIZE;j+)tempij=memeryj; compute();print(count);/*最近最久未使用置換算法*/void LRU() int memery10=0; int flag10=0; /*記錄頁面的訪問時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*

20、記錄置換次數*/*前mSIZE個數直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; flagi=i; for(j=0;j<mSIZE;j+)tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新該頁的訪問時間*/ if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計算換出頁*/ max=flag0<flag1?0:1;for

21、(m=2;m<mSIZE;m+)if(flagm<flagmax)max=m; memerymax=pagei; flagmax=i; /*記錄該頁的訪問時間*/ for(j=0;j<mSIZE;j+)tempij=memeryj; else for(j=0;j<mSIZE;j+)tempij=memeryj; compute();print(count);/*最佳置換算法*/void OPT() int memery10=0; int next10=0; /*記錄下一次訪問時間*/ int i,j,k,l,m; int max; /*記錄換出頁*/ int count=0; /*記錄置換次數*/*前mSIZE個數直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; for(j=0;j<mSIZE;j+)tempij=memer