页面置换算法实验报告

页面替换算法实验报告一、实验目的：设计了最优的替换算法、随机替换算法、高级先进先进先出算法、最近的替换算法、简单的Clock替换算法和改进的Clock替换算法，以支持实现的页访问序列的随机生成，从而涉及该算法2、实验内容：l虚拟内存页的总数为n，页码为0到N-1l物理内存由m个物理块组成l页访问序列是整数序列，整数取N - 1范围内的值。 页面访问序列中的每个元素p表示对页面p的访问l页表由整数数组或结构数组表示一种适合q局部接入特征的随机生成算法1 .虚拟存储器的尺寸n、工作集的开始位置p、工作集中包括的页数e、工作集移动速率m (每次处理m页访问时的开始位置p 1)和介于0和1之间的值t2 .生成p和p e之间m个值范围内的随机数，并在页面访问序列上记录该随机数3 .生成随机数r，0 r 14 .对于rt，将生成p的新值。 否则，p=(p 1) mod N；5 .如果要进一步加长页面访问系列的长度，请返回步骤2。 否则就结束。3、实验环境：操作系统： windows 7软件： VC 6.04 .实验设计：本实验包括6种算法，基本内容差异不大，在实现方面不是统一的数据结构，而是根据不同算法的特征用不同的数据结构实现的1 .最佳置换和随机置换所需的操作较少，通过整数排列模拟存储器来实现2 .先进的先进先出和最近的未使用置换具有队列的特性，因此通过队列模拟内存来实现3、改进的CLOCK置换和改进的CLOCK置换具有循环队列的特性，以模拟循环队列中存储器的实现4 .所有算法都使用整数阵列模拟页面访问序列。5、数据结构设计：/页面访问序列数组：int refref_size；/内存数组：int phyphy_size；/队列数据结构定义：定义typedef struct QNode/队列数据结构装模作样int data；结构节点*下一步；QNode，*QueuePtr；typedef struct装模作样QueuePtr front； /头针QueuePtr rear； /尾部指针LinkQueue；/定义链表的数据结构定义typedef struct LNode/循环链接表的数据结构装模作样int data；int flag； /访问位int modify； /修改位结构节点*下一步；LNode、*LinkList；6 .主要函数说明：1、void set_rand_num()/生成具有局部特性的随机数序列2、int Exchange_LNode(LinkList L、int e、int i)/将链接表l的编号I的节点置换为内容e的节点3、bool Search_LinkList(LinkList L、int e、int i)/找到链表l的内容为e的节点，在I返回其位置，i=1表示最初的非开头节点，依次类推4、在void Search_LL_Flag(LinkList L，int i)/中第一个flag返回0个节点的位置，其中i=1表示第一个非开头节点，依此类推5、将void Set_LL_Flag(LinkList L、int i)/链接表l的编号为I的节点的flag标志设为16、intsearch _ ll _ modify clock (link list l，int modify_num)/找到改进的clock算法所需的丢弃页，并在modify_num中返回该位置该函数基于给出的原理，如果在第1次扫描中淘汰A=0且M=0的页，失败，在第2次扫描中扫描A=0且M=1的页，在第2次扫描中将访问的所有页的访问位置a设为0，则重复上述2部分7、void Set_LL_modify(LinkList L，int i)/链接表l的编号为I的节点的modify标志为18、bool SearchQueue(LinkQueue Q，int e，int i)/查找队列q的节点data域等于e的节点，并在I返回q的位置9、int getnum(int a，int b)/元素a引用的数列的下一个位置用b返回10、实现void ORA()/页面是否在内存中、页面是否在内存中、是否输出内存状态等最佳替换算法11、void RAND()/随机取代算法12、void FIFO()/高级先进先进先出算法13、void LRU()/最近没有使用算法实现最近最早未使用的算法的思想是确定要进入内存的页面，如果该页面与内存中的第一页相同，则删除该页面；如果该页面与内存中的第二页相同，则删除该页面；如果该页面与内存中的第一页相同，则删除该页面，并在队列的末尾添加相同元素，即最近使用的页面14、实现voidclock()/clock算法15、实现void Modified_Clock() /改进的CLOCK算法16、int main()/主函数调用实现各算法的6个主函数，并输出各算法的缺页率。7、实验问题的答复：1、FIFO算法是否优于随机置换算法？FIFO算法优于随机置换算法，但优势不明显。2、LRU算法比FIFO算法有多好？答： LRU算法FIFO算法的效率高达5%-10%，由于具有理论知识，页面访问序列具有局部性，但FIFO算法与实际情况不符。3、LRU算法与最佳算法有何不同？答： LRU算法是所有算法中效率最接近最优算法的算法，根据理论知识，最优算法是理想的算法，实际上是不可能实现的，只有一个评估标准，而LRU算法效率较高4、Clock算法和LRU算法有什么区别？答： clock算法和LRU算法的结果是差异较小，clock算法因为使用软件实现了LRU算法的硬件功能，所以执行效率稍差。8 .实验过程结果的截图：实验结果的屏幕截图评估1 :评估2 :评估3 :实验过程的截图(注意：只剪切第三次评估，蓝色字体表示发生页面用完)9 .实验结果分析：1 .最优置换算法的效果最好最佳替换算法的效果甚至在该组数据中也是最佳的，并且性能远远高于其他算法。 但是，通过在课堂上的学习，发现这是一种理想的算法，但实际上很难实现，因此主要用于算法评价的参考。2 .随机算法的性能总是最差的这是因为随机算法每次都被所有页面随机替换，但是访问页面的原理很局部，因为它不是随机的，所以性能很差。3、最近最早的未使用算法性能良好相较于先进的先入先出和两种clock算法，我们相信最近最早的未使用算法性能略好，我们测试的数据规模较小，如果采用更大规模的数据，其优势将更加明显。已发现，课堂上需要在实际应用中实现本算法、软件方法慢、影响程序执行效率的硬件实现时增加大量硬件设备。4 .先进先入先出和clock算法的性能基本相同这是因为与单纯的clock算法相比，改进的clock算法可以主要根据是否改变来选择，因为这两种clock算法遍历链路表并且采用FIFO方法10、实验总结：本次实验的整体难易度并不高，应该实现的算法的数量不少，但是由于基本的想法相似，实现也不太困难。 通过这次实验的完成，加深了我对一些策略的理解，锻炼了我的编程能力，另一大成就是理解了生成测试数据的方法。 为了使我们的测试数据接近现实，引入了工作集概念，根据实际使用情况的特点，设计了尽可能符合实际情况的随机数生成方案。 通过阅读教材加深自己的理解，我理解了老师设计的思维方式，这种思维方式非常巧妙，用于设计的方式表现出来的许多思想都值得我们学习。十一、程序清单：#include#include#include#include#include使用名称空间STD；定义ref _ size 20#define phy_size 3int refref_size；浮点interrupt 6=0.0；/int refref_size=0；int phyphy_size；我们可以看到它们的名字，例如，它们的名字，它们的名字，它们的名字，它们的名字，它们的名字，它们的名字，它们的名字，它们的名字void set_rand_num()/生成具有局部特性的随机数序列装模作样cout 页面访问程序： next=L；L-flag=0；return 1；以下称为int Exchange_LNode(LinkList L，int e，int i)/将链接表l的编号I的节点置换为内容e的节点装模作样if(L-next=L) exit(-1 )；LinkList p，q；int j=0；p=(link list ) malloc (sizeof (lnode ) )q=(link list ) malloc (sizeof (lnode ) )q-data=e；p=L；for(j=0； jnext；q-next=p-next-next；p-next=q；q-flag=1； /将新节点的访问位设置为1q-modify=0； /将新节点的修改位设置为0return 1；以下称为在int Insert_LNode(LinkList L，int e)/循环链路表中插入新节点，从l头节点开始依次向后插入装模作样LinkList p，q；p=(link list ) malloc (sizeof (lnode ) )q=(link list ) malloc (sizeof (lnode ) )q-data=e；q-flag=1； /将新节点的访问位设置为1q