页面置换算法模拟.pdfVIP

实验4 页面置换算法模拟 实验目的 通过请求页式存储管理中页面置换算法模拟设计，以便： 1、了解虚拟存储技术的特点 2 、掌握请求页式存储管理中页面置换算法 实验性质 验证性实验，必做，6 课时 实验程序说明 1、通过随机数产生一个指令序列，共320 条指令。指令的地址按下述原则生成： ①50%的指令是顺序执行的； ②25% 的指令均匀分布在前地址部分； ③25% 的指令均匀分布在后地址部分。 具体的实施方法： ①在[0，319]的指令地址之间随机选取一起点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 条指令为第1 页（对应虚存地址[10，19]） …… 第310~319 条指令为第31 页（对应虚存地址[310，319] ） 按以上方式，用户指令可组成32 页。 3、计算并输出下述各种算法在不同内存容量下的命中率 ①先进先出FIFO ②最近最少使用LRU ③最佳淘汰算法OPT （可选） ④最少访问LFU （可选） ⑤最近最不经常使用NUR （可选） 说明：命中率=1 －（页面失效次数/页地址流长度）。本实验中，页地址流长度是320， 页面失效次数为每次访问指令时，该指令所对应的页不在内存的次数。 实验内容 设计一个虚拟存储区和内存工作区，并使用FIFO 和LRU 算法计算机访问命中率。 程序设计 先用srand()函数和rand() 函数定义和产生指令序列，然后将指令序列变换成相应的页地 址流，并针对不同的算法计算相应的命中率。 程序1 #define TRUE 1 #define FALSE 0 #define INVALID -1 #define NULL 0 #define total_instruction 320/*共320 条指令*/ #define total_vp 32/*虚存页共32*/ #define clear_period 50 typedef struct{/*页面类型*/ int pn, pfn, counter, time;/*页号、页面号、一个周期内访问该页面的次数、访问时间*/ }pl_type; pl_type pl[32]; typedef struct pfc_struct{/*页面控制结构*/ int pn, pfn; struct pfc_struct *next; }pfc_type; pfc_type pfc[32]; pfc *freepf_head,*busypf_head,*busypf_tail;/*空闲页头指针，忙页头指针，忙页尾指针*/ int diseffect; /*缺页次数*/ int a[total_instruction];/*指令流数组*/ int page[total_instruction], offset[total_instruction];/*每条指令的页和页内偏移*/ void initialize( ); void FIFO( ); void LRU( ); /*void OPT( );根据需要可选*/ void main(){ int s,i,j; int s,i,j; srand(10*getpid());/*用进程号作为初始化随机数队列的种子*/ s=(float)319*rand()/32767/3267/2+1; for(i=0;itotal_instruction;i+=4){/*产生指令队列*/ if(s0||s319