实验3+虚拟存储器管理

实验3 虚拟存储器管理

实验说明(一)实验目的 请求页式虚存管理是常用的虚拟存储管理方案之 一。通过请求页式虚存管理中对页面置换算法的 模拟，有助于理解虚拟存储技术的特点，并加深 对请求页式虚存管理的页面调度算法的理解。 实验环境 Turbo C 2.0/3.0或VC++6.0 实验学时 4学时，必做实验

实验内容本设计的内容是要求使用C语言编写一个页面调 度算法模拟程序，模拟一个拥有10个虚页的进程 在给定的若干个实页中运行、并形成一个长度为 20的页地址流的情形。 本设计的具体要求是所编写的程序能随机产生页 地址流中对虚页的访问次序，并动态指派所用的 实页数n;使用FIFO和LRU算法调度页面，程序 运行时屏幕能显示出调度过程中的状态信息并输 出访问结束时的页面命中率；文档中包含两种算 法的程序流程图，内容准确、详尽。

算法数据结构说明——虚页的表示 虚页的表示pn pfn time pn代表虚页号，因为共10个虚页， 所以pn的取值范围是0—9。 pfn代表实页号，当一虚页未装 入实页时，此项值为-1;当该虚 页已装入某一实页时，此项值为 所装入的实页的实页号pfn。 time项在FIFO算法中不使用，在 LRU中用来存放对该虚页的最近 访问时间。

虚页结构

算法数据结构说明——实页的表示 实页的表示pn pfn next pn代表虚页号，表示pn所 代表的虚页目前正放在此 实页中。 pfn代表实页号，取值范围 (0—n-1)由动态指派的 实页数n所决定。 next是一个指向实页结构 体的指针，用于多个实页 以链表形式组织起来

实页结构

缺页次数的统计为计算命中率，需要统计在20次的页面访问 中缺页的次数。为此，程序应设置一个计数 器count,来统计缺页中断发生的次数。 每当所访问的虚页的pfn项值为-1,表示此时 它尚未被装入内存中的实页内，缺页中断就 发生了，count加1。最终命中率 命中率=1命中率 count/20。

LRU算法中“最近最久未用” 算法中“最近最久未用” 算法中 页面的确定为了能找到“最近最久未用”的虚页面，程序中 可引入一个时间计数器countime,每当要访问一 个虚页面时，countime的值加1,然后将所要访问 的虚页的time项值设置为增值后的当前countime 值，表示该虚页的最后一次被访问时间。 当LRU算法需要置换时，从所有已分配实页的虚页 中找出time值为最小的虚页就是“最近最久未用” 的虚页面，应该被置换出去。

算法中虚页和页地址流的组织可以使用有10个元素的数组保存10个虚 页。数组中元素的类型就是前述的虚页 结构。 可以使用有20个元素的数组保存页地址 页地址 流。

算法中实页的组织 (一)因为能分配的实页数n

是在程序运行时由用户动态 指派的，所以应使用链表组织动态产生的多个实页。 为了调度算法实现的方便，可以考虑引入free和 busy两个链表：free链表用于组织未分配出去的实 页，首指针为free_head,初始时n个实页都处于 free链表中；busy链表用于组织已分配出去的实页， 首指针为busy_head,尾指针为busy_tail,初始值 都为null。

算法中实页的组织( 算法中实页的组织(二)当所要访问的一个虚页不在实页中时，将产生缺页 中断。 此时若free链表不为空，就取下链表首指针所指的 实页，并分配给该虚页。 若free链表为空，则说明n个实页已全部分配出去， 此时应进行页面置换。 对于FIFO算法要将busy_head 所指的实页从busy链 表中取下，分配给该虚页，然后再将该实页插入到 busy链表尾部。 对于LRU算法则要从所有已分配实页的虚页中找出 time值为最小的虚页，将该虚页从装载它的那个实 页中置换出去，并在该实页中装入当前正要访问的 虚页。