1、实验三 内存管理一、 实验目的 n 理解内存页面调度的机理。n 掌握几种理论页面值换算法的实现方法n 通过实验比较各种调度算法的优劣。二、 实验内容 随机给出一个页面执行序列，如：1,5,3,4,2,1,3,4,5,7,9,。要求计算以下几种置换算法的缺页数、缺页率和命中率。u 最佳置换算法OPT（Optimal）u 先进先出算法FIFO（First In First Out）u 最近最少使用算法LRU（Least Recently Used）三、 实验环境n PC + Linux Red Hat操作系统 + GCCn 或 Windows xp + VC四、 实验中遇到的主要问题及其解决方式
2、这次实验其实不一定要在linux操作系统下做，在windows操作系统一样可以实现，只要把头文件稍作修改即可。一开始做这个实验时，首先是看书，先把书上的替换算法知识点弄明白，要明白各种算法的优缺点和相互之间衍生互补关系。这四个算法中，难以实现的是LRU算法，因为它涉及到访问时间的计算，而且它的开销也比较大。OPT算法次难，它需要计算最近访问时间，并替换最近访问时间最大的页。而FIFO和CLOCK实现起来比较容易，FIFO算法的实现和CLOCK算法的实现很相似，FIFO可视为CLOCK的退化版。我先写了CLOCK算法，再删去一些约束条件就退化为FIFO算法。这就是两者的相同之处。理论上，CLOC
3、K算法需要维持一个循环的主存缓冲区，需要一个循环队列去实现，并且，FIFO算法保持先进先出，因此需要一个先进先出队列。五、 源代码#include #include #include /在window操作系统下要屏蔽此条指令#include #ifndef _UNISTD_H#define _UNISTD_H#include #include #endif#define TRUE 1#define FALSE 0#define INVALID -1#define total_instruction 320 /指令流长#define total_vp 32 /虚页长#define clear_p
4、eriod 50 /清周期typedef struct /页面结构 int pn,/页面序号pfn,/页面所在内存区的帧号counter,/单位时间内访问次数time;/上次访问的时间pl_type;pl_type pltotal_vp; /页面结构数组struct pfc_struct /页面控制结构 int pn,/页面号 pfn;/内存区页面的帧号 struct pfc_struct *next;/页面指针，用于维护内存缓冲区的链式结构;typedef struct pfc_struct pfc_type; /主存区页面控制结构别名pfc_type pfctotal_vp, /主存区页面
5、控制结构数组*freepf_head, /主存区页面控制结构的空闲页面头指针*busypf_head, /主存区页面控制结构的忙页面头指针*busypf_tail; /主存区页面控制结构的忙页面尾指针int diseffect; /页错误计数器，初次把页面载入主存时也当做页错误int atotal_instruction; /随即指令流数组int pagetotal_instruction; /指令对应的页面号int offsettotal_instruction; /指令所在页面中的偏移量int initialize(int);/初始化页面结构数组和页面控制结构数组int FIFO(int)
6、/先进先出算法int LRU(int);/最近最久未使用算法int OPT(int);/最佳置换算法int CLOCK(int);/简单时钟(钟表)算法int main( ) int s;/随机数inti; srand(10*getpid(); /*每次运行时进程号不同，用来作为初始化随机数队列的种子*/ s = (int)(float)(total_instruction-1)*(rand()/(RAND_MAX+1.0);printf(n-随机产生指令流-n); for (i=0; itotal_instruction; i+=4) /产生指令队列 ai=s; /任选一指令访问点m ai
7、1=ai+1; /顺序执行一条指令 ai+2=(int)(float)ai*(rand()/(RAND_MAX+1.0); /执行前地址指令m ai+3=ai+2+1; /顺序执行一条指令 printf(%6d%6d%6d%6dn, ai,ai+1,ai+2,ai+3); s = (int)(float)(total_instruction-1)-ai+2)*(rand()/(RAND_MAX+1.0) + ai+2; printf(-n);for (i=0;itotal_instruction;i+) /将指令序列变换成页地址流 pagei=ai/10; offseti=ai%10; pr
8、intf(n-不同页面工作区各种替换策略的命中率表-n); printf(Paget FIFOt LRUt OPTt CLOCKn); for(i=4;i=32;i+) /用户内存工作区从个页面到个页面 printf( %2d t,i); FIFO(i); LRU(i); OPT(i); CLOCK(i); printf(n); return 0;/初始化页面结构数组和页面控制结构数组/total_pf; 用户进程的内存页面数int initialize(int total_pf) int i; diseffect=0; for(i=0;itotal_vp;i+)pli.pn=i;pli.pf
9、n=INVALID; /置页面所在主存区的帧号为-1.表示该页不在主存中pli.counter=0;/置页面结构中的访问次数为pli.time=-1;/置页面结构中的上次访问的时间为-1for(i=0;itotal_pf-1;i+)pfci.next=&pfci+1; /建立pfci-1和pfci之间的链接pfci.pfn=i; /初始化主存区页面的帧号pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/主存区页面控制结构的空闲页面头指针指向pfc0return 0;/最近最久未使用算法/int tot
10、al_pf; 用户进程的内存页面数int LRU (int total_pf) int MinT;/最小的访问时间，即很久没被访问过int MinPn;/拥有最小的访问时间的页的页号int i,j;int CurrentTime;/系统当前时间 initialize(total_pf);/初始化页面结构数组和页面控制结构数组 CurrentTime=0;diseffect=0;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) /页面失效diseffect+;/页错误次数加 if(freepf_head=NULL) /无空闲页面 MinT
11、100000; for(j=0;jplj.time&plj.pfn!=INVALID) MinT=plj.time; MinPn=j; freepf_head=&pfcplMinPn.pfn; /最久没被访问过的页被释放 plMinPn.pfn=INVALID; /最久没被访问过的页被换出主存 plMinPn.time=-1;/最久没被访问过的页的访问时间置为无效 freepf_head-next=NULL; plpagei.pfn=freepf_head-pfn; /有空闲页面,把相应的页面换入主存，并把pfn改为相应的帧号 plpagei.time=CurrentTime;/令访问时间为
12、当前系统时间 freepf_head=freepf_head-next; /减少一个空闲页面elseplpagei.time=CurrentTime; /命中则刷新该单元的访问时间CurrentTime+; /系统当前时间加 printf(%6.3ft,1-(float)diseffect/320);return 0;/最佳置换算法/int total_pf; 用户进程的内存页面数int OPT(int total_pf)int i,j;int MaxD;/将来最近一次访问的距离的最大值（以时间单元度量）int MaxPn;/将来最近一次访问的距离的最大值的页号int dis;/距离计数器in
13、t disttotal_vp;/距离数组，保存距离上一次访问的时间差距个数initialize(total_pf);/初始化页面结构数组和页面控制结构数组diseffect=0;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)/页面失效diseffect+;/页错误次数加if(freepf_head=NULL)/无空闲页面for(j=0;jtotal_vp;j+)if(plj.pfn!=INVALID)/如果该页在主存中distj=100000;/ 该页关联的距离值改为最大值elsedistj=0;/如果不在该页主存中，该页关联的距离值
14、改为dis=1;/初始距离值为for(j=i+1;jtotal_instruction;j+) /从要替换的指令的下一条算起，if(plpagej.pfn!=INVALID &plpagej.counter=0)/如果该页在主存中,并且是将要最近访问的页/if(plpagej.pfn!=INVALID & distpagej=100000) /此条语句原理与上相同distpagej=dis;/距离值改为displpagej.counter=1;/使访问次数标志加，区别第一次访问和第二次访问dis+;MaxD=-1;for(j=0;jtotal_vp;j+)plj.counter=0;/重置访问
15、次数为if(MaxDnext=NULL;plMaxPn.pfn=INVALID;plpagei.pfn=freepf_head-pfn; /把当前页换入主存中，并且把当前页的pfn改为换入页的帧号，freepf_head=freepf_head-next; /减少一个空闲页面/if/forprintf(%6.3ft,1-(float)diseffect/320);return 0;/简单时钟算法/int total_pf; 用户进程的内存页面数int CLOCK(int total_pf)int i;int usetotal_vp; /使用位int swap;swap=0; /发生替换init
16、ialize(total_pf);pfc_type *pnext; /时钟指针pfc_type *head; /队列头指针pnext=freepf_head;head=freepf_head;for(i=0;itotal_vp;i+)usei=0; /初始化使用位为diseffect=0;for(i=0;ipfn=1) /若时钟指针指向的页的使用位为，则改为并跳过usepnext-pfn=0;pnext=pnext-next;if(pnext=NULL) pnext=head; /如果时钟指针到达队列尾部，重新返回头部/换出被替换的页plpnext-pn.pfn=INVALID;swap=1;
17、if(usepnext-pfn=0) /如果使用位为，则换入相应的页plpagei.pfn=pnext-pfn; /页面结构中要标记帧号pnext-pn=pagei; /页面控制结构中要标记页号usepnext-pfn=1;/重置使用位为pnext=pnext-next;/时钟指针下移if(pnext=NULL) pnext=head;/如果时钟指针到达队列尾部，重新返回头部if(swap=0) freepf_head=freepf_head-next;else/页面在主存中useplpagei.pfn=1; /刷新使用位为printf(%6.3ft,1-(float)diseffect/32
18、0);return 0;/先进先出算法版本/int total_pf; 用户进程的内存页面数/实现细节由CLOCK算法退化而来，与FIFO同效果int FIFO(int total_pf)int i;int usetotal_vp;int swap=0;initialize(total_pf);pfc_type *pnext,*head;pnext=freepf_head;head=freepf_head;for(i=0;itotal_vp;i+)usei=0;diseffect=0;for(i=0;ipfn=1)usepnext-pfn=0;pnext=pnext-next;if(pnext
19、NULL) pnext=head;/换出被替换的页plpnext-pn.pfn=INVALID;swap=1;if(usepnext-pfn=0) /如果使用位为，则换入相应的页plpagei.pfn=pnext-pfn; /页面结构中要标记帧号pnext-pn=pagei; /页面控制结构中要标记页号usepnext-pfn=1;/重置使用位为pnext=pnext-next;if(pnext=NULL) pnext=head;if(swap=0) freepf_head=freepf_head-next;printf(%6.3ft,1-(float)diseffect/320);return 0;六、 程序流程图总体流程图： OPT算法：FIFO算法：LRU算法：七、 实验总结从集中算法的命中率来看，opt是最高的，其次nur相对较高，fifo和lru相差无几，LFU最低，但每个页面执行结果会有所不同。
