常用页面置换算法模拟实验-

内存管理常见页面替换算法的仿真实验实验目的通过模拟实现请求页面存储管理的几种基本页面替换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页面存储管理中几种基本页面替换算法的基本思想和实现过程，并对其效率进行比较。实验内容设计一个虚拟存储区和一个内存工作区，并使用以下算法计算访问命中率。1.最优消除算法2.先进先出算法3.最近最少使用的算法(LRU)4.最不常用的算法(LFU)5.最近未使用的算法命中率=1-页面失败次数/页面地址流长度实验准备本实验的程序设计基本上是根据实验内容进行的。首先，使用srand()和rand()函数定义和生成指令序列，然后将指令序列转换成相应的页面地址流，并为不同的算法计算相应的命中率。(1)通过随机数生成320条指令的序列。指令的地址是根据以下原则生成的：答：50%的指令是按顺序执行的B: 25%的指令平均分布在前端地址部分C: 25%的指令平均分布在后地址部分具体实现方法如下：答：在指令地址0，319之间随机选择一个点mb:依次执行一条指令，即执行地址为m 1的指令c:从前面的地址0，m 1中随机选择一条指令并执行，该指令的地址为m d:按地址m 1的顺序执行一条指令随机选择一条指令，并执行它重复步骤A-E，直到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页。实验指导语一、虚拟存储系统在UNIX中，为了提高内存利用率，提供了内部和外部内存进程之间的交换机制。内存空间的分配和回收是以页面为单位进行的。一个进程只能通过将它的一部分(段或页)转移到内存中来运行。它还支持请求分页的存储管理方法。当一个进程在运行过程中需要访问一些程序和数据时，它会发现它所在的页面不在内存中，并立即发出请求(向中央处理器发送一个默认中断)，系统会将它需要的页面转移到内存中。这种页面调入方法称为请求页面调入。为了请求分页，内核配置了四种数据结构：页表、页帧号、访问位、修改位、有效位、保护位等。第二，页面替换算法当中央处理器接收到缺页中断信号时，中断处理器首先保存场景，分析中断的原因，并切换到缺页中断处理器。程序通过查找页表获得存储在页外的物理块号。如果此时内存不足以容纳新页面，启动盘输入/输出将丢失的页面转移到内存中，然后修改页面表。如果内存已满，必须根据某个替换算法从内存中选择一个页面进行替换。是否重写磁盘由页表的修改位决定，然后将丢失的页转移到页表中进行修改。使用修改后的页表，形成要访问的数据的物理地址，然后访问存储器数据。整个页面转入过程对用户是透明的。常见的页面替换算法包括1.最优排列算法2.先进先出3.最近最不使用的4.最不常用的方法5.最近未使用的方法三。参考程序：#定义真1#定义FALSE 0#define INVALID -1#定义空值0#定义total_instruction 320 /*指令流长度*/# de pl _ typepl _类型pl总计_ VP；/*页面结构数组*/结构pfc_struct /*页面控制结构*/int pn，pfnstruct pfc _ struct * next；类型定义结构PFC _结构PFC _类型；pfc_type pfctotal_vp，*freepf_head，*busypf_head，* busypf _ tailint diseffect，atotal _ instruction；int页总计_说明，偏移量总计_说明；int初始化(int)；先进先出；LRU国际机场；LFU国际机场；int NUR(int)；int OPT(int)；int main()国际、国内、国际；srand(10 * getpid()；/*由于每次运行时进程号不同，故可用来作为初始化随机数队列的种子 */s=(float)319 * rand()/32767/32767/2 1；/对于(1=0；i319)printf(当i=%d，错误，s=%dn ，I，s)；退出(0)；aI=s；/*任选一指令访问点m*/aI 1=aI1；/*顺序执行一条指令*/一二=(浮动)一一*兰特()/32767/32767/2；/*执行前地址指令m */ai3=aI21；/*顺序执行一条指令*/s=(float)(318-aI2)* rand()/32767/32767/2 aI22；if(ai 2318)|(s319)printf(a%d 2，一个：%d且s=%dn ，I，ai 2，s)的数字。对于(1=0；不精确；plbusypf_head-pn.pfn=无效。freepf _ head=busypf _ head/*释放忙页面队列的第一个页面*/freepf _ head-next=空；繁忙pf _ head=p；p=freepf _ head-next；/*按先入先出方式调新页面入内存页面*/freepf _ head-next=空；freepf _ head-pn=第i页；pl第i页.pfn=freepf _ head-pfn；if(繁忙pf _ tail=空)busy pf _ head=busy pf _ tail=freepf _ head；其他busybf _ tail-next=freepf _ head；/*免费页面减少一个*/busypf _ tail=freepf _ headfreepf _ head=p；printf(FIFO:%6.4fn ，1-(float)diseffect/320)；返回0；LRU国际机场（总计_pf) /*最近最久未使用算法*/int total _ pf最小，最小，I，j，当前时间初始化（总计_ pf)；present _ time=0；对于(1=0；iplj.时间线j.pfn！=INVALID)min=plj.时间；minj=j；freepf_head=pfcplminj.pfn；/腾出一个单元plminj.pfn=无效。plminj.时间=-1；freepf _ head-next=空；pl第i页.pfn=freepf _ head-pfn；/有空闲页面，改为有效pl第i页.时间=当前时间；freepf _ head=freepf _ head-next；/减少一个自由的页面其他pl