請求頁式存儲管理中常用頁面置換算法模擬

1、計算機操作系統(tǒng)實 驗 報 告課程名稱計算機操作系統(tǒng)實驗項目名稱請求頁式存儲管理中常用頁面置換算法模擬學號20111214034班級計1103姓名韓瑤專業(yè)計算機科學與技術實驗地點12J-661實驗室 濟南大學信息科學與技術學院2013年xx月xx日一、實驗概述1. 實驗名稱 請求頁式存儲管理中常用頁面置換算法管理2. 實驗目的（1）了解內(nèi)存分頁管理策略（2）掌握調(diào)頁策略（3）掌握一般常用的調(diào)度算法 （4）學會各種存儲分配算法的實現(xiàn)方法。（5）了解頁面大小和內(nèi)存實際容量對命中率的影響3. 實驗內(nèi)容（1）采用頁式分配存儲方案，通過分別計算不同算法的命中率來比較算法的優(yōu)劣，同時也考慮頁面大小及內(nèi)存實際

2、容量對命中率的影響；（2）實現(xiàn)OPT 算法 (最優(yōu)置換算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 (First IN First Out)的模擬；（3）使用某種編程語言模擬頁面置換算法。二、實驗環(huán)境C語言三、實驗過程1. 設計思路和流程圖選擇置換算法，先輸入所有頁面號，為系統(tǒng)分配物理塊，依次進行置換將頁號放入物理塊中，編號加1引用串編號大于物理塊數(shù)?載入頁號序列，從第0個得到頁號開始頁號在物理塊中?根據(jù)選擇的置換算法完成置換頁號序列載完?結(jié)束是否是是是是2. 算法實現(xiàn)（1）OPT基本思想：是用一維數(shù)組pagepSIZE存儲頁面號序列，mem

3、erymSIZE是存儲裝入物理塊中的頁面。數(shù)組nextmSIZE記錄物理塊中對應頁面的最后訪問時間。每當發(fā)生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調(diào)出該頁，換入所缺的頁面。（2）FIFO基本思想：是用隊列存儲內(nèi)存中的頁面，隊列的特點是先進先出，與該算法是一致的，所以每當發(fā)生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁?；蛘呓柚o助數(shù)組timemSIZE記錄物理塊中對應頁面的進入時間，每次需要置換時換出進入時間最小的頁面。(3)LRU基本思想：是用一維數(shù)組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數(shù)組flag10標記頁面的訪問時間。每當使用頁面時，

4、刷新訪問時間。發(fā)生缺頁時，就從物理塊中頁面標記最小的一頁，調(diào)出該頁，換入所缺的頁面。3.源程序并附上注釋#include <stdio.h>#include <stdlib.h>/*全局變量*/int mSIZE; /*物理塊數(shù)*/int pSIZE; /*頁面號引用串個數(shù)*/static int memery10=0; /*物理塊中的頁號*/static int page100=0; /*頁面號引用串*/static int temp10010=0; /*輔助數(shù)組*/*置換算法函數(shù)*/void FIFO();void LRU();void OPT();/*輔助函數(shù)*/

5、void print(unsigned int t);void designBy();void download();void mDelay(unsigned int Delay);/*主函數(shù)*/void main() int i,k,code;system("color 0A");designBy();printf("請按任意鍵進行初始化操作. n");printf("n");printf(" >>>");getch();system("cls");system("

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

7、);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",pagei);elseprintf("%d ",pagei);printf("* * * * * * * * * * * * * * * * *

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

9、;,&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");printf("n"); exit(0);default:printf("輸入錯誤，請重新輸入："); printf

10、("按任意鍵重新選擇置換算法：>>>");getch();system("cls"); while (code!=4);getch();/*載入數(shù)據(jù)*/void download()int i;system("color 0D");printf("n");printf("正在載入數(shù)據(jù)，請稍候 !n");printf("n");printf("Loading.n");printf(" O");for(i=0;i<5

11、1;i+)printf("b");for(i=0;i<50;i+)mDelay(pSIZE+mSIZE)/2);printf(">");printf("nFinish.n載入成功，按任意鍵進入置換算法選擇界面：>>>");getch();/*設置延遲*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay>0;Delay-) for(i=0;i<124;i+) printf(" b"); /*顯示設計者信息*/

12、 void designBy()printf("n");printf(" 課題三：頁面置換算法 n");printf(" 學號：20111214034 n");printf(" 姓名：韓瑤 n");printf("n");void print(unsigned int t)int i,j,k,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=

13、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(" |%d|",tempij);elseprintf(" | |");for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1);

14、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");printf("-n");printf("缺頁次數(shù)：%dtt",t+mSIZE);printf("缺頁率：%d/%dn",t+mSIZE,pSIZE);p

15、rintf("置換次數(shù)：%dtt",t);printf("訪問命中率：%d%n",(pSIZE-(t+mSIZE)*100/pSIZE);printf("-n");/*計算過程延遲*/void compute()int i;printf("正在進行相關計算，請稍候");for(i=1;i<20;i+)mDelay(15);if(i%4=0)printf("bbbbbb bbbbbb");elseprintf("");for(i=0;i+<30;printf(&qu

16、ot;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; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; timei=i; for(j=0;j<mSIZE;

17、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<mSIZE;m+)if(timem<timemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁進入物理塊的時間*/ for(j=0;j<mSIZE;j+)tempi

18、j=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; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/ for(i=0;i<mSIZE;i+) memeryi=pagei; flagi=i; for(j=0;j<mSIZE;j+)tempij=meme

19、ryj; 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(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; /*記錄置換次數(shù)*/