《请求页式存储管理的页面置换算法》由会员分享，可在线阅读，更多相关《请求页式存储管理的页面置换算法（7页珍藏版）》请在金锄头文库上搜索。
1、 请求页式存储管理的页面置换算法实验环境Linux 2.6.24实验内容设计一个虚拟存储区和内存工作区,并使用下列算法计算页面失效次数.（1） 进先出的算法（FIFO）（2） 最近最少使用的算法（LRU）（3） 最佳淘汰算法(OPT)在本实验中，页地址流长度为 320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。算法描述及实验步骤实验步骤（1）通过随机数产生一个指令序列，共 320 条指令。指令的地址按下述原则生成：50%的指令是顺序执行的；50%的指令是均匀分布在前地址部分；50%的指令是均匀分布在后地址部分。具体的实施方法是：在 0，319 的指令之间随即选取一起点
2、m;顺序执行一条指令，即执行地址为 m+1 的指令；在前地址0，m+1中随机选取一条指令并执行，该指令的地址为 m；顺序执行一条指令，其地址为 m+ 1；在后地址m+ 2，319中随机选取一条指令并执行；重复上述步骤-，直到执行 320 次指令。（2）将指令序列变换为页地址流设：页面大小为 1k；用户内存容量为 4 页到 32 页；用户虚存容量为 32k。在用户虚存中，按每 k 存放 10 条指令排在虚存地址，即 320 条指令在虚存中的存放方式为：第 0 条-第 9 条指令为第 0 页（对应虚存地址为0 ，9） ；第 10 条-第 19 条指令为第一页（对应虚存地址为 10， 19） ； 第
3、 310 条第 319 条指令为第 31 页（对应虚地址为310，319 ） 。按以上方式，用户指令可组成 32 页。（3）计算并输出下述各种算法在不同内存容量下的页面失效次数。先进先出的算法（FIFO） ；最近最少使用算法（LRU)；最佳淘汰算法（OPT）先淘汰最不常用的页地址；随机数产生办法，Linux 或 UNIX 系统提供函数 strand()和 rand(),分别进行初始化和产生随机数。例如：strand (); 语句可初始化一个随机数；a0=10*rand()/65535*319+1; a1=10*rand()/65535*a0;语句可用来产生 a0与 a1中的随机数实验指导本实验
4、的程序设计基本上按照实验内容进行。即首先用 srand()和 rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。相关定义如下：1 数据结构(1)页面类型typedef structint pn,pfn,counter,time;pl-type;其中 pn 为页号,pfn 为面号, counter 为一个周期内访问该页面的次数, time 为访问时间.(2) 页面控制结构pfc-structint pn,pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_t
5、ype pfc_structtotal_vp,*freepf_head,*busypf_head;pfc_type *busypf_tail;其中 pfctotal_vp定义用户进程虚页控制结构,*freepf_head 为空页面头的指针,*busypf_head 为忙页面头的指针 ,*busypf_tail 为忙页面尾的指针.2函数定义（1）Void initialize( ): 初始化函数 ,给每个相关的页面赋值 .（2）Void FIFO( ):计算使用 FIFO 算法时的页面失效次数 .（3）Void LRU( ):计算使用 LRU 算法时的页面失效次数.（4）Void OPT( ):
6、计算使用 OPT 算法时的页面失效次数.3. 变量定义(1)int atotal_instruction: 指令流数据组.(2)int pagetotal_instruction: 每条指令所属的页号.(3)int offsettotal_instruction: 每页装入 10 条指令后取模运算页号偏移值.(4)int total_pf: 用户进程的内存页面数 .(5)int disaffect: 页面失效次数4. 程序参考源码及结果#include #include #include #define TRUE 1#define FALSE 0#define INVALID -1#defin
7、e NUL 0#define total_instruction 320 /*指令流长*/#define total_vp 32 /*虚页长*/#define clear_period 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 pfct
8、otal_vp,*freepf_head,*busypf_head,*busypf_tail;int diseffect,atotal_instruction;int pagetotal_instruction, offsettotal_instruction;void initialize();void FIFO();void LRU();void OPT();int main()int S,i;srand(int)getpid();S=(int)rand()%390;for(i=0;inext;plbusypf_head-pn.pfn=INVALID; /*释放忙页面队列中的第一个页面*/
9、freepf_head=busypf_head;freepf_head-next=NUL;busypf_head=p;p=freepf_head-next; /*按方式调新页面入内存页面*/freepf_head-next=NUL;freepf_head-pn=pagei;plpagei.pfn=freepf_head-pfn;if(busypf_tail=NUL)busypf_head=busypf_tail=freepf_head;elsebusypf_tail-next=freepf_head;busypf_tail=freepf_head;freepf_head=p;printf(FI
10、FO:%d,diseffect);void LRU(total_pf)int total_pf;int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;iplj.time&plj.pfn!=INVALID)min=plj.time;minj=j;freepf_head=plminj.pfn=INVALID;plminj.time=-1;freepf_head-next=NUL;plpagei.pfn=freepf_head-pfn;plpagei.time=present_time;freepf_hea
11、d=freepf_head-next;elseplpagei.time=present_time;present_time+;printf(LRU:%d,diseffect);void OPT(total_pf) /*OPT(Optimal Replacement)ALGORITHM*/int total_pf;int i,j,max,maxpage,d,disttotal_vp;pfc_type *t;initialize(total_pf);for(i=0;inext=NUL;plmaxpage.pfn=INVALID;plpagei.pfn=freepf_head-pfn;freepf_
12、head=freepf_head-next;printf(OPT:%d,diseffect);void initialize(total_pf) /*初始化相关数据结构 */int total_pf; /*用户进程的内存页面数 */int i;diseffect=0;for(i=0;itotal_vp;i+)pli.pn=i;pli.pfn=INVALID; /*置页面控制结构中的页号，页面为空*/pli.counter=0;pli.time=-1; /*页面控制结构中的访问次数为 0，时间为 -1*/for(i=1;itotal_pf;i+)pfci-1.next=/*建立 pfci-1和 pfci之间的连接*/pfctotal_pf-1.next=NUL;pfctotal_pf-1.pfn=total_pf-1;freepf_head= /*页面队列的头指针为 pfc0*/
