實(shí)驗(yàn)4內(nèi)存管理

1、實(shí)驗(yàn) 4 內(nèi)存管理學(xué)校： FJUT 學(xué)號(hào)： 3131903229 班級(jí)：計(jì)算機(jī) 1302 姓名：姜峰注：其中 LFU 和 NRU 算法運(yùn)行結(jié)果可能與其他人不同， 只是實(shí)現(xiàn)方式不同， 基本思路符合就可以。一 . 實(shí)驗(yàn)學(xué)時(shí)與類型學(xué)時(shí)： 2，課外學(xué)時(shí)：自定 實(shí)驗(yàn)類型：設(shè)計(jì)性實(shí)驗(yàn)二 . 實(shí)驗(yàn)?zāi)康哪M實(shí)現(xiàn)請(qǐng)求頁式存儲(chǔ)管理中常用頁面置換算法，理會(huì)操作系統(tǒng)對(duì)內(nèi)存的調(diào)度管理。三 . 實(shí)驗(yàn)內(nèi)容 要求：各算法要給出詳細(xì)流程圖以及執(zhí)行結(jié)果截圖。 假設(shè)有一程序某次運(yùn)行訪問的頁面依次是： 0,1,2,4,3,4,5,1,2,5,1,2,3,4,5,6 ，請(qǐng)給 出采用下列各頁面置換算法時(shí)頁面的換進(jìn)換出情況，并計(jì)算各調(diào)度算

2、法的命中率(命中率 非缺頁次數(shù)/總訪問次數(shù))，初始物理內(nèi)存為空，物理內(nèi)存可在420頁中選擇。(1) FIFO ：最先進(jìn)入的頁被淘汰；(2) LRU ：最近最少使用的頁被淘汰；(3) OPT ：最不常用的頁被淘汰； ( 選做)(4) LFU ：訪問次數(shù)最少的頁被淘汰 (LFU) 。 ( 選做) 源代碼：#include #include #include #include #define MAXNUM 100struct Phy_Memory/定義一個(gè)物理內(nèi)存結(jié)構(gòu)體char Page;int time;char *OutPut;struct Phy_Memory *Phy_Page;void P

3、rint(char *PageStr,int Phy_PageNum,int absence)/打印圖解函數(shù)int i,j;for(i=0;istrlen(PageStr);i+)printf(%c ,*(PageStr+i);printf(n); for(i=0;istrlen(PageStr);i+)printf(-);printf(n);for(i=0;iPhy_PageNum;i+) for(j=0;jstrlen(PageStr);j+) printf(%c ,*(OutPut+i*strlen(PageStr)+j);printf(n);printf( 缺頁數(shù)為 :%dn,abse

4、nce);printf( 總訪問次數(shù)為 :%dn,strlen(PageStr);printf( 缺頁率為 %.2fn,(double)absence/strlen(PageStr);int IsExist(char *Temp,int Phy_PageNum)/判斷某頁面是否存在于物理內(nèi)存中int i;for(i=0;iPage!=*Temp;i+);if(iPhy_PageNum) return i+1;/ 找到返回此頁面位置加 1return 0;void FIFO(char *PageStr,int Phy_PageNum) / 利用時(shí)間計(jì)數(shù)器方式，還可以用棧來實(shí)現(xiàn) char *Tem

5、p=PageStr;/定義 Temp 指針指向 PageStr 首地址int i,num,location,absence=0;int Flag=0;/定義一個(gè)標(biāo)記變量，標(biāo)記插入位置while(*Temp!=0) / 頁面未訪問完 num=0;if(FlagPage=*Temp;Flag+;absence+;/若物理內(nèi)存已滿/若此頁面未被訪問 /找到駐留時(shí)間最長的頁 else if(!IsExist(Temp,Phy_PageNum) for(i=0;iFlag;i+)if(numtime)location=i;num=(Phy_Page+i)-time;(Phy_Page+location)

6、-Page=*Temp;(Phy_Page+location)-time=0;absence+;for(i=0;itime+;*(OutPut+i*strlen(PageStr)+(Temp-PageStr)=(Phy_Page+i)-Page;Temp+;Print(PageStr,Phy_PageNum,absence);void LRU(char *PageStr,int Phy_PageNum)/ 依舊利用計(jì)數(shù)器方式，也可用棧來實(shí)現(xiàn)char *Temp=PageStr;/定義 Temp 指針指向 PageStr 首地址int i,num,location,absence=0;int F

7、lag=0;/定義一個(gè)標(biāo)記變量，標(biāo)記插入位置while(*Temp!=0)/ 頁面未訪問完num=0;if(Flagtime=0;else/ 若此頁面未被訪問(Phy_Page+Flag)-Page=*Temp;Flag+;absence+;else/若物理內(nèi)存已滿if(location=IsExist(Temp,Phy_PageNum)/若此頁面已被訪問(Phy_Page+location-1)-time=0;else/若此頁面未被訪問for(i=0;iFlag;i+)/ 找到最近最久未使用的頁if(numtime) location=i;num=(Phy_Page+i)-time;(Phy

8、_Page+location)-Page=*Temp;(Phy_Page+location)-time=0;absence+;for(i=0;itime+; *(OutPut+i*strlen(PageStr)+(Temp-PageStr)=(Phy_Page+i)-Page;Temp+;Print(PageStr,Phy_PageNum,absence );int Distance(char *PageStr,char *Temp,char Now) /計(jì)算距離函數(shù)( OPT 算法中使用)int i;for(i=1;*(Temp+i)!=0&*(Temp+i)!=Now;i+);if(*(T

9、emp+i)!=0)return i;return INT_MAX;void OPT(char *PageStr,int Phy_PageNum) / 實(shí)際中無法實(shí)現(xiàn)，知道訪問串后順序遍歷 char *Temp=PageStr;/定義 Temp 指針指向 PageStr 首地址int i,num,Size,location,absence=0;int Flag=0;/定義一個(gè)標(biāo)記變量，標(biāo)記插入位置while(*Temp!=0) / 頁面未訪問完 num=0;if(FlagPage=*Temp;Flag+;absence+;/若物理內(nèi)存已滿/若此頁面未被訪問/淘汰在訪問串中將來再也不會(huì)出現(xiàn)的或e

10、lseif(!IsExist(Temp,Phy_PageNum)for(i=0;iPage);/調(diào)用 distance函數(shù)返回值為與當(dāng)前位置物理頁面相同頁號(hào)的距離if(numPage=*Temp;absence+;for(i=0;iPage;Temp+;Print(PageStr,Phy_PageNum,absence);char *Create(char *PageStr)/根據(jù)訪問串建立計(jì)數(shù)字符數(shù)組( LFU 算法使用)int i,j,Size,Num=0;char *Temp1,*Temp2;int length=strlen(PageStr);char *NowPage=(char *

11、)malloc(length);for(i=0;ilength;i+) *( NowPage + i ) = *( PageStr + i );Temp1 = Temp2 = NowPage; while(Temp1-NowPage)=length+1) / 去除訪問串中重復(fù)串 if(*Temp1!=0) for(Temp2=Temp1+1;(Temp2-NowPage)=length+1;Temp2+) if(*Temp1=*Temp2)*Temp2=0;Num+;Temp1+;Size=length-Num;char *Count=(char *)malloc(Size*2);for(i=

12、0;ilength;i+) if(*(NowPage+i)!=0) *(Count+Size-1)=*(NowPage+i); Size-;Size=length-Num;for(i=Size;i2*Size;i+)*(Count+i)=0;return Count;void Add(char *Ptr,char Str,int Size)int i;for(i=0;*(Ptr+i)!=Str;i+);*(Ptr+i+Size)+=1;int Find(char *Ptr,char Str,int Size)(LFU 算法使用)int i;for(i=0;*(Ptr+i)!=Str;i+);r

13、eturn (*(Ptr+i+Size)-0);void Zero( char *Ptr, int Size )int i; for(i=Size;i2*Size;i+) *(Ptr+i)=0;void LFU(char *PageStr,int Phy_PageNum) 器，每次選出最小的淘汰char *Temp=PageStr;char *Count=Create(PageStr);/將不重復(fù)的訪問頁置于計(jì)數(shù)器中/計(jì)數(shù)位置零/ 相應(yīng)計(jì)數(shù)器加一（ LFU 算法使用）/在計(jì)數(shù)器中找到相應(yīng)頁面并返回其計(jì)數(shù)值/ 將所有計(jì)數(shù)器清零（ LFU 算法使用）/對(duì)每一頁面設(shè)置一個(gè)計(jì)數(shù)/定義 Temp 指針指

14、向 PageStr 首地址int i,Size,time,num,location,absence=0;int Flag=0;/定義一個(gè)標(biāo)記變量，標(biāo)記插入位置Size=strlen(Count)/2;while(*Temp!=0) / 頁面未訪問完 num=INT_MAX;if(FlagPage,Size);else/若此頁面未被訪問(Phy_Page+Flag)-Page=*Temp;Flag+;absence+;else/ 若物理內(nèi)存已滿if(location=IsExist(Temp,Phy_PageNum)/若此頁面已被訪問Add(Count,(Phy_Page+location-1)

15、-Page,Size);else/ 若此頁面未被訪問for(i=0;iPage,Size);if(numtime)location=i;num=time;(Phy_Page+location)-Page=*Temp;Zero(Count,Size);absence+;for(i=0;iPage;Temp+;int j;/ 打印每次訪問后的計(jì)數(shù)器值for(i=0;i2;i+)for(j=0;jSize;j+)printf(%c ,*(Count+i*Size+j);printf(n);printf(n);Print(PageStr,Phy_PageNum,absence);void NRU(ch

16、ar *PageStr,int Phy_PageNum)/ 對(duì)每個(gè)物理頁設(shè)置一個(gè)標(biāo)識(shí)(0/1)，用指針循環(huán)訪問淘汰標(biāo)識(shí)為零的頁面char *Temp=PageStr;/定義 Temp 指針指向 PageStr 首地址int i,location,absence=0;int Flag=0;/定義一個(gè)標(biāo)記變量，標(biāo)記插入位置struct Phy_Memory *Clock = Phy_Page; / 定義一個(gè)結(jié)構(gòu)體指針指向物理內(nèi)存首地址while(*Temp!=0)/頁面未訪問完if(Flagtime=1; else/若此頁面未被訪問(Phy_Page+Flag)-Page=*Temp;(Phy_P

17、age+Flag)-time=1;Flag+;absence+;Clock+;if(Clock-Phy_Page)=Phy_PageNum) Clock=Phy_Page;elseif(location=IsExist(Temp,Phy_PageNum)/若物理內(nèi)存已滿/若此頁面已被訪問(Phy_Page+location-1)-time=1; else/若此頁面未被訪問while(Clock-time)Clock-time=0;Clock+; if(Clock-Phy_Page)=Phy_PageNum) Clock=Phy_Page;Clock-Page=*Temp;Clock-time=

18、1;Clock+; if(Clock-Phy_Page)=Phy_PageNum) Clock=Phy_Page;absence+;for(i=0;iPage;Temp+;Print(PageStr,Phy_PageNum,absence );int main()char *Str;int i,n,Num;Str=(char*)malloc(MAXNUM);printf( 輸入程序運(yùn)行時(shí)訪問的頁面次序以及物理內(nèi)存的分頁數(shù) :n); scanf(%s%d,Str,&Num);/初Phy_Page=(struct Phy_Memory*)malloc(Num*sizeof(struct Phy_M

19、emory); 始化物理內(nèi)存結(jié)構(gòu)體OutPut=(char*)malloc(Num*strlen(Str); for(i=0;itime=0; printf( 選擇置換算法 :n1.FIFO 2.LRU 3.OPT 4.LFU 5.NRUn); scanf(%d,&n);switch (n)case 1:printf(n 以下為 FIFO 算法圖解:n”);FIFO(Str,Num);break;case 2:printf(n 以下為 LRU 算法圖解:n);LRU(Str,Num);break;case 3:printf(n 以下為 OPT 算法圖解:n);OPT(Str,Num);brea

20、k;case 4:printf(n以下為 LFU 算法圖解:n 各時(shí)期計(jì)數(shù)器女口下:n );LFU(Str,Num);break;case 5:printf(n 以下為 NRU 算法圖解:n);NRU(Str,Num);break;free(Phy_Page);free(OutPut);return 0;注：這里只對(duì)分頁數(shù)為4進(jìn)行運(yùn)行截圖實(shí)驗(yàn)截圖：輸入程序運(yùn)行時(shí)訪間的頁面次序以及做理內(nèi)存的分頁蛛312434512512345 4選擇置換算法：l.FIFO 2.LRU 3-OPT 4,LFU 5川刑罠下為F】FO算法圖解；01243451251234S6 00303333333334441111

21、15555SSS556 22222111111111 4444422222222獻(xiàn)頁率為日-殆Process returned S execution tine : l?+706 s Press anu key to continue輸人程序運(yùn)行時(shí)訪間的頁面次序以及物理內(nèi)存的分頁數(shù),M12434512S123456 4選擇置換算送：1.FIFO 2.LHU 3,OPT 4-LFU 5,NRU2以下為LRU算法圖解；B 1243451251234564衣為 數(shù)問率 K誼貞612 加75:1數(shù)乩2忘142 2 2 25 E S G11114 4 4 32 2 64 4 415 53 3 3*irp

22、cess returned u execut ion tine - 2tf - 015 s *r-ess any key to continue.5 15 15 13 13 10 10 10 10222222222222224I 4P 3 4 07- 6 皿:1魏0 九務(wù)為 數(shù)間率 頁訪頁 缺ln-礁LErncess returned U execut ion t line - 24.149 s LPi*ess any key t-D continue -輸入程序云行吋訪問的頁面次序以及物理內(nèi)存的分頁數(shù):B12434512512345G 4選擇萱換算法二1.F1FO 2.LRU 3.OPT 4

23、.LFU 5.NRU5認(rèn)下為麗U算袪圉解：012434S12512345nJ4 4 45 5 51162 2 23 3 3 3 %石“ 11112 2 2 2Ln-3 0 4Z6 :1數(shù)n. 凄為 數(shù)冋率 頁訪頁 缺總?cè)盤rocess returned 0 execut:lon tlne - 16 .34? s Press any key to continue.FIFO算法流程圖:LRU算法流程圖:OPT算法流程圖:LFU算法流程圖:NRU算法流程圖:開始四.思考與總結(jié)(1) 針對(duì)上述頁面訪問順序，請(qǐng)比較上述各頁面置換算法的性能。對(duì)于訪問順序 0,1,2,4,3,4,5,125,1,2,3,

24、4,5,6當(dāng)分頁數(shù)為4時(shí)： 隨著分頁數(shù)增加它們的缺頁數(shù)均降低。FIFO算法對(duì)此訪問串無Belady現(xiàn)象。OPT算法表現(xiàn)最好，實(shí)際上我們將OPT算法當(dāng)做最優(yōu)的評(píng)判標(biāo)準(zhǔn)。LRU算法理論上是優(yōu)于 FIFO算法的，但此時(shí)缺頁率卻高于 FIFO算法，主要是受訪問串以及 分頁數(shù)的影響。只能說此訪問串更適合FIFO算法。所以在實(shí)際中，我們要選擇最適合的算法考慮。當(dāng)分頁數(shù)為5時(shí)，各算法情況：觸入程序運(yùn)行時(shí)訪間的頁面枕序以及物理內(nèi)存的分頁數(shù)匕 陸擇置換算法：1,FIFO 2.LRU OPT 4-LFM 5.MRU以下為麗疇袪圖解;124J451251234b6aRnnE5弓弓555g511111111111111622222222222222444444444444433333333333輸入程序運(yùn)行時(shí)訪問的頁面試序嘆及物理內(nèi)存的分頁數(shù);012434512512M