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

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

3、t;struct Phy_Memory *Phy_Page;void Print(char *PageStr,int Phy_PageNum,int absence) /打印圖解函數(shù) int i,j; for(i=0;i<strlen(PageStr);i+)printf("%c ",*(PageStr+i);printf("n"); for(i=0;i<strlen(PageStr);i+)printf("-");printf("n"); for(i=0;i<Phy_PageNum;i+) fo

4、r(j=0;j<strlen(PageStr);j+) printf("%c ",*(OutPut+i*strlen(PageStr)+j); printf("n"); printf("缺頁數(shù)為:%dn",absence); printf("總訪問次數(shù)為:%dn",strlen(PageStr); printf("缺頁率為%.2fn",(double)absence/strlen(PageStr);int IsExist(char *Temp,int Phy_PageNum) /判斷某頁面

5、是否存在于物理內(nèi)存中 int i; for(i=0;i<Phy_PageNum&&(Phy_Page+i)->Page!=*Temp;i+); if(i<Phy_PageNum) return i+1; /找到返回此頁面位置加1 return 0;void FIFO(char *PageStr,int Phy_PageNum) /利用時間計數(shù)器方式，還可以用棧來實現(xiàn) char *Temp=PageStr; /定義Temp指針指向PageStr首地址 int i,num,location,absence=0; int Flag=0; /定義一個標(biāo)記變量，標(biāo)記插入

6、位置 while(*Temp!='0') /頁面未訪問完 num=0; if(Flag<Phy_PageNum) /若物理內(nèi)存未滿 if(!IsExist(Temp,Flag) /若此頁面未被訪問 (Phy_Page+Flag)->Page=*Temp; Flag+;absence+; else /若物理內(nèi)存已滿 if(!IsExist(Temp,Phy_PageNum) /若此頁面未被訪問 for(i=0;i<Flag;i+) /找到駐留時間最長的頁 if(num<(Phy_Page+i)->time) location=i;num=(Phy_P

7、age+i)->time; (Phy_Page+location)->Page=*Temp; (Phy_Page+location)->time=0; absence+; for(i=0;i<Flag;i+) /將當(dāng)前物理內(nèi)存數(shù)組列放入二維數(shù)組中 (Phy_Page+i)->time+; *(OutPut+i*strlen(PageStr)+(Temp-PageStr)=(Phy_Page+i)->Page; Temp+; Print(PageStr,Phy_PageNum,absence);void LRU(char *PageStr,int Phy_Pa

8、geNum) /依舊利用計數(shù)器方式，也可用棧來實現(xiàn) char *Temp=PageStr; /定義Temp指針指向PageStr首地址 int i,num,location,absence=0; int Flag=0; /定義一個標(biāo)記變量，標(biāo)記插入位置 while(*Temp!='0') /頁面未訪問完 num=0; if(Flag<Phy_PageNum) /若物理內(nèi)存未滿 if(location=IsExist(Temp,Phy_PageNum) /若此頁面已被訪問 (Phy_Page+location-1)->time=0; else /若此頁面未被訪問 (P

9、hy_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;i<Flag;i+) /找到最近最久未使用的頁 if(num<(Phy_Page+i)->time) location=i;num=(Phy_Page+i)->time; (Phy_Page+location)->Page=*Temp; (

10、Phy_Page+location)->time=0; absence+; for(i=0;i<Flag;i+) /將當(dāng)前物理內(nèi)存數(shù)組列放入二維數(shù)組中 (Phy_Page+i)->time+; *(OutPut+i*strlen(PageStr)+(Temp-PageStr)=(Phy_Page+i)->Page; Temp+; Print(PageStr,Phy_PageNum,absence );int Distance(char *PageStr,char *Temp,char Now) /計算距離函數(shù)（OPT算法中使用） int i; for(i=1;*(Tem

11、p+i)!='0'&&*(Temp+i)!=Now;i+); if(*(Temp+i)!='0')return i; return INT_MAX;void OPT(char *PageStr,int Phy_PageNum) /實際中無法實現(xiàn)，知道訪問串后順序遍歷 char *Temp=PageStr; /定義Temp指針指向PageStr首地址 int i,num,Size,location,absence=0; int Flag=0; /定義一個標(biāo)記變量，標(biāo)記插入位置 while(*Temp!='0') /頁面未訪問完 nu

12、m=0; if(Flag<Phy_PageNum) /若物理內(nèi)存未滿 if(!IsExist(Temp,Flag) /若此頁面未被訪問 (Phy_Page+Flag)->Page=*Temp; Flag+;absence+; else /若物理內(nèi)存已滿 if(!IsExist(Temp,Phy_PageNum) /若此頁面未被訪問 for(i=0;i<Flag;i+) /淘汰在訪問串中將來再也不會出現(xiàn)的或離當(dāng)前最遠(yuǎn)的位置上出現(xiàn)的頁 Size=Distance(PageStr,Temp,(Phy_Page+i)->Page); /調(diào)用distance函數(shù)返回值為與當(dāng)前位置

13、物理頁面相同頁號的距離 if(num<Size) location=i;num=Size; (Phy_Page+location)->Page=*Temp;absence+; for(i=0;i<Flag;i+) /將當(dāng)前物理內(nèi)存數(shù)組列放入二維數(shù)組中 *(OutPut+i*strlen(PageStr)+(Temp-PageStr)=(Phy_Page+i)->Page; Temp+; Print(PageStr,Phy_PageNum,absence);char *Create(char *PageStr) /根據(jù)訪問串建立計數(shù)字符數(shù)組（LFU算法使用） int i,

14、j,Size,Num=0; char *Temp1,*Temp2; int length=strlen(PageStr); char *NowPage=(char *)malloc(length); for(i=0;i<length;i+) *( NowPage + i ) = *( PageStr + i ); Temp1 = Temp2 = NowPage; while(Temp1-NowPage)<=length+1) /去除訪問串中重復(fù)串 if(*Temp1!='0') for(Temp2=Temp1+1;(Temp2-NowPage)<=length

15、+1;Temp2+) if(*Temp1=*Temp2) *Temp2='0'Num+; Temp1+; Size=length-Num; char *Count=(char *)malloc(Size*2); for(i=0;i<length;i+) /將不重復(fù)的訪問頁置于計數(shù)器中 if(*(NowPage+i)!='0') *(Count+Size-1)=*(NowPage+i); Size-; Size=length-Num; for(i=Size;i<2*Size;i+) /計數(shù)位置零 *(Count+i)='0' retur

16、n Count;void Add(char *Ptr,char Str,int Size) /相應(yīng)計數(shù)器加一（LFU算法使用） int i; for(i=0;*(Ptr+i)!=Str;i+); *(Ptr+i+Size)+=1;int Find(char *Ptr,char Str,int Size) /在計數(shù)器中找到相應(yīng)頁面并返回其計數(shù)值（LFU算法使用） int i; for(i=0;*(Ptr+i)!=Str;i+); return (*(Ptr+i+Size)-'0');void Zero( char *Ptr, int Size ) /將所有計數(shù)器清零（LFU算法使

17、用） int i; for(i=Size;i<2*Size;i+) *(Ptr+i)='0'void LFU(char *PageStr,int Phy_PageNum) /對每一頁面設(shè)置一個計數(shù)器，每次選出最小的淘汰 char *Temp=PageStr; /定義Temp指針指向PageStr首地址 char *Count=Create(PageStr); int i,Size,time,num,location,absence=0; int Flag=0; /定義一個標(biāo)記變量，標(biāo)記插入位置 Size=strlen(Count)/2; while(*Temp!='

18、;0') /頁面未訪問完 num=INT_MAX; if(Flag<Phy_PageNum) /若物理內(nèi)存未滿 if(location=IsExist(Temp,Phy_PageNum) /若此頁面已被訪問 Add(Count,(Phy_Page+location-1)->Page,Size); else /若此頁面未被訪問 (Phy_Page+Flag)->Page=*Temp; Flag+;absence+; else /若物理內(nèi)存已滿 if(location=IsExist(Temp,Phy_PageNum) /若此頁面已被訪問 Add(Count,(Phy_P

19、age+location-1)->Page,Size); else /若此頁面未被訪問 for(i=0;i<Flag;i+) /找到被訪問次數(shù)最少的一頁 time=Find(Count,(Phy_Page+i)->Page,Size); if(num>time) location=i;num=time; (Phy_Page+location)->Page=*Temp; Zero(Count,Size); absence+; for(i=0;i<Flag;i+) /將當(dāng)前物理內(nèi)存數(shù)組列放入二維數(shù)組中 *(OutPut+i*strlen(PageStr)+(Te

20、mp-PageStr)=(Phy_Page+i)->Page; Temp+; int j; /打印每次訪問后的計數(shù)器值 for(i=0;i<2;i+) for(j=0;j<Size;j+) printf("%c ",*(Count+i*Size+j); printf("n"); printf("n"); Print(PageStr,Phy_PageNum,absence);void NRU(char *PageStr,int Phy_PageNum) /對每個物理頁設(shè)置一個標(biāo)識（0/1），用指針循環(huán)訪問淘汰標(biāo)識為零的

21、頁面 char *Temp=PageStr; /定義Temp指針指向PageStr首地址 int i,location,absence=0; int Flag=0; /定義一個標(biāo)記變量，標(biāo)記插入位置 struct Phy_Memory *Clock = Phy_Page; /定義一個結(jié)構(gòu)體指針指向物理內(nèi)存首地址 while(*Temp!='0') /頁面未訪問完 if(Flag<Phy_PageNum) /若物理內(nèi)存未滿 if(location=IsExist(Temp,Phy_PageNum) /若此頁面已被訪問 (Phy_Page+location-1)->ti

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

23、ime=0;Clock+; if(Clock-Phy_Page)>=Phy_PageNum) Clock=Phy_Page; Clock->Page=*Temp; Clock->time=1;Clock+; if(Clock-Phy_Page)>=Phy_PageNum) Clock=Phy_Page; absence+; for(i=0;i<Flag;i+) /將當(dāng)前物理內(nèi)存數(shù)組列放入二維數(shù)組中 *(OutPut+i*strlen(PageStr)+(Temp-PageStr)=(Phy_Page+i)->Page; Temp+; Print(PageSt

24、r,Phy_PageNum,absence );int main() char *Str;int i,n,Num; Str=(char*)malloc(MAXNUM); printf("輸入程序運行時訪問的頁面次序以及物理內(nèi)存的分頁數(shù):n"); scanf("%s%d",Str,&Num); Phy_Page=(struct Phy_Memory*)malloc(Num*sizeof(struct Phy_Memory); /初始化物理內(nèi)存結(jié)構(gòu)體 OutPut=(char*)malloc(Num*strlen(Str); for(i=0;i<

25、;Num;i+)(Phy_Page+i )->time=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);break; case 4:printf("n以下為LFU算法圖解:n各時期計數(shù)器如下:n");LFU(Str,Num);b