实验3虚拟存储器管理

淮海工学院计算机科学系实验报告课程名称：操作系统原理主题：实验3虚拟内存管理等级：z软件52学校编号：2017140595姓：郭文静评论：成绩：讲师：审批时间：年、月、日操作系统原理实验报告1.实验的目的和要求本实验模拟请求页面虚拟内存管理系统的页面替换。实验程序可以模拟具有多个虚拟页面的进程在给定数量的真实页面中运行的情况，并在出现分页时分别使用先进先出和LRU算法进行页面替换。当程序运行时，要求屏幕显示替换过程中的状态信息，并在访问结束时输出页面命中率。通过给进程分配不同的实际页面来比较几种算法的稳定性。2、实验内容或题目该实验需要使用C/C语言编程来模拟在给定数量的真实页面中运行多个虚拟页面的过程，并在发生分页时使用先进先出和LRU算法来分别替换页面。虚拟页面的数量可以预先给定(例如，10)，并且访问这些虚拟页面的页面地址流(其长度可以预先给定，例如，20次虚拟页面访问)可以由程序随机生成或者预先存储在文件中。当程序运行时，要求屏幕显示替换过程中的状态信息，并在访问结束时输出页面命中率。程序应该允许通过给进程分配不同的实际页面来比较两个替换算法的稳定性。实验表明：(1)虚拟页面和真实页面在设计中的表现本设计使用C/C /Java语言结构来描述虚拟页面和真实页面的结构。期票pfn时间期票pfn然后虚拟页面结构在虚拟页面结构中，pn代表虚拟页面号，因为总共有10个虚拟页面，所以pn的取值范围是0-9。Pfn代表真实的页码。当虚拟页面未加载到真实页面时，该值为-1；当虚拟页面加载到真实页面时，该值是加载的真实页面的真实页码pfn。时间项不在先进先出算法中使用，而是在LRU用于存储对虚拟页面的最新访问时间。在真实页面结构中，pn表示虚拟页面号，这意味着pn表示的虚拟页面当前被放置在这个真实页面中。Pfn代表实际页码，数值范围(0-n-1n-1)由动态分配的实际页码n决定。下一步是指向实际页面结构的指针。它用于组织链接列表中的多个真实页面。有关实际页面链接列表的组织的详细信息，请参见下面的第4点。(2)缺页次数统计为了计算命中率，需要计算20次虚拟页面访问的命中次数。因此，程序应该设置计数器计数来计算虚拟页面的点击次数。每当被访问的虚拟页面的pfn条目值不是-1时，这意味着虚拟页面已经被加载到真实页面中，并且虚拟页面被命中，计数加1。最终命中率=计数/20*100%。(3)在3)LRU算法中确定“最近和最长未使用的”页面为了找到“最近未使用的”虚拟页面，可以在程序中引入时间计数器计数时间。每当要访问虚拟页面时，countime的值递增1，然后要访问的虚拟页面的时间项值被设置为递增后的当前countime值，指示虚拟页面的最后访问时间。当LRU算法需要替换时，从所有分配的真实页面的虚拟页面中找出时间值最小的虚拟页面，即“最近最长未使用”的虚拟页面，并进行替换。(4)算法中真实页面的组织因为当程序运行时，可以分配的实际页面数n是由用户动态分配的，所以应该使用链表来组织动态生成的多个实际页面。为了便于调度算法的实现，可以考虑空闲和忙碌两种链表：空闲链表用于组织未分配的实页，第一个指针是free_head，最初n个实页都在空闲链表中；繁忙链表用于组织分配的实际页面。第一个指针是busy_head，最后一个指针是busy_tail，初始值为空。当要访问的虚拟页面不在真实页面中时，会发生缺页中断。此时，如果空闲链表不为空，则链表的第一个指针所指向的真实页面被移除并分配给虚拟页面。如果空闲链表为空，那么所有n个实页都已被分配，此时应该进行页替换：对于先进先出算法，busy_head引用的实页应该从繁忙链表中删除，分配给虚拟页，然后实页应该插入繁忙链表的尾部；对于LRU算法，从分配的真实页面的所有虚拟页面中找出时间值最小的虚拟页面，从加载虚拟页面的真实页面中替换虚拟页面，并将当前正在访问的虚拟页面加载到真实页面中。3.实验步骤(1)了解相关实验说明。(2)根据实验说明画出相应的程序流程图。(3)根据程序流程图，使用C/C /Java语言进行编程和实现。4.流程图主页先进先出算法OPT算法LRU算法开始提取指令记下说明书中的页码页面查找表页面标志=1？形成一个绝对地址输出绝对地址还有后续的说明输出*页码表示缺少页面中断Y出现n个分页下一条指令Y目标N5、源代码和测试数据以及实验结果(可以捕捉和粘贴)#包括 iostream.h 常量int DataMax=100const int BlockNum=10int数据显示块号数据最大值；/用于存储要显示的数组bool DataShoweableBlockNumDataMax；/用于存储数组中的数据是否需要显示/int数据DataMax=4，3，2，1，4，3，5，4，3，2，1，5，6，2，3，7，1，2，6，1 ；/测试数据/int N=20；/输入页数内部数据数据最大值；/保存数据内部块块号；/物理块整数计数块数；/计数器整数；/页数整数M；/最小物理块数int ChangeTimesvoid DataInput()；/输入数据的功能void DataOutput()；无效先进先出法()；/先进先出功能void Optimal()；/最佳函数void LRU()；/LRU函数/*int main(int argc，char* argv)数据输入()；/DataInput()；/先进先出()；/最优()；/LRU()；/返回0；int菜单；而(真的)coutmenu。开关(菜单)判例1:(先进先出)；休息；案例2:最优()；休息；判例3: LRU()；休息；默认值breakif(菜单！=1menu！=2menu！=3)中断；/*/void DataInput()“计数”请输入最小物理块数：“；cinM而(M块数)/大于数据数 Cout 物理块数超过预定值，请重新输入：；cinM“Cout”请输入页数：“；cinN而(N个数据最大值)/大于数据数量 Cout 页数超过预定值，请重新输入：；cinN“Cout”请输入页面访问顺序：“数据i”;void DataOutput()int i，j；对于(I=0；如果i=3，更换后计数值设置为1。/同时，将其他块计数值加1形成(1 3 2)。参见下面的先进先出程序部分对于(