实验3虚拟存储器管理 (2).pdf

"实验三虚拟存储器管理" 虚拟存储器管理是操作系统中的一种重要机制，它允许一个进程使用超过物理内存大小的虚拟内存。为实现虚拟存储器管理，需要设计虚拟页和实页的结构，并实现页面置换算法。 虚拟页和实页的结构 在设计中，虚页和实页的结构可以使用 C/C++ 语言的结构体来描述。虚页结构包括虚页号 pn、实页号 pfn 和时间项 time。其中，pn 代表虚页号，pfn 代表实页号，time项在 FIFO 算法中不使用，在 LRU 中用来存放对该虚页的最近访问时间。实页结构包括虚页号 pn 和实页号 pfn，next 是一个指向实页结构体的指针，用于多个实页以链表形式组织起来。 缺页次数的统计 为计算命中率，需要统计在 20 次的虚页访问中命中的次数。可以设置一个计数器 count，来统计虚页命中发生的次数。每当所访问的虚页的 pfn 项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count 加 1。最终命中率=count/20*100%。 LRU 算法中“最近最久未用”页面的确定 为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器 countime，每当要访问一个虚页面时，countime 的值加 1，然后将所要访问的虚页的 time 项值设置为增值后的当前 countime 值，表示该虚页的最后一次被访问时间。当 LRU 算法需要置换时，从所有已分配实页的虚页中找出 time 值为最小的虚页就是“最近最久未用”的虚页面，应该将它置换出去。 算法中实页的组织 为了实现虚拟存储器管理，需要使用链表组织动态产生的多个实页。可以引入 free 和 busy 两个链表：free 链表用于组织未分配出去的实页，busy 链表用于组织已分配出去的实页。当所要访问的一个虚页不在实页中时，将产生缺页中断。此时若 free 链表不为空，就取下链表首指针所指的实页，并分配给该虚页。若 free 链表为空，则说明 n 个实页已全部分配出去，此时应进行页面置换。 页面置换算法 有两种页面置换算法：FIFO 和 LRU。FIFO 算法将 busy_head 所指的实页从 busy 链表中取下，分配给该虚页，然后再将该实页插入到 busy 链表尾部。LRU 算法则要从所有已分配实页的虚页中找出 time 值为最小的虚页，将该虚页从装载它的那个实页中置换出去，并在该实页中装入当前正要访问的虚页。 实验步骤 1. 理解相关实验说明。 2. 根据实验说明，画出相应的程序流程图。 3. 按照程序流程图，用 C/C++/Java 语言编程并实现。 4. 通过实验结果，比较两种算法的稳定性和差异。