实验三虚拟存储器管理
一、实验目的
为了使大的进程(其地址空间超过主存可用空间)或多个进程的地址空间之和超过实际主存空间时，仍能运行，引入了虚拟存储器的概念。

使进程的一部分地址空间在主存，另一部分在辅存，由操作系统实现多级存储器的自动管理，实现主存空间的自动覆盖。

模拟请求分页虚拟存储器管理技术中的硬件地址变换、缺页中断以及页式置换算法，处理缺页中断。

通过本实验，使学生对请求分页存储管理的概念有一个清楚的理解。

二、实验内容
1、模拟请求分页存储管理中的硬件地址变换的过程
(1)请求分页虚拟存储器管理技术是把进程地址空间的全部信息存放在磁盘对换区上。

当进程被选中运行时，先把进程的开始几页装入主存并启动运行。

为此在为进程建立页表时，应说明哪些页已在主存，哪些页不在主存。

页表的格式如表1 所示。

在表1中
①"标志位"表示对应页是否已经装入主存的标志: "0"表示对应页未装入主存;"1"表示对应页已装入主存。

②"主存块号"表示该页对应的主存块号。

③"修改位"指示该页进主存后是否修改过的标志。

④"外存地址"表示该页所在的外存地址。

设计一个主存分块表，假定分配给进程的主存块数为M，且该进程开始的M页已装入主存。

(2)进程执行时，指令中的逻辑地址指出指令或操作数的地址中的页号和页内地址。

硬件地址转换机构按页号查页表。

①若该页的有效位为"1" ，表示该页已在主存，从而找到该页对应的主存块号。

根据如下的关系式，计算出欲访问的主存地址:
绝对地址=块号×块的长度+页内地址
由于页的大小为2 的整次幕，所以只要将块号与页内地址相拼接，放入主存地址寄存器，形成绝对地址。

不去模拟指令的执行，而是输出被转换的地址即可。

②若该页的有效位为"0" ，对应的页不在主存，由硬件产生缺页中断，转操作系统处理。

这里不去设计缺页处理程序，仅输出"*该页号的页不在主存，产生缺页中断"即可，以表示产生了一次缺页中断。

假定主存的每块长度为128个字节。

现有一个具有8页的进程，系统为它分配了4 个主存块(即m=4)。

其中第0~3页已经装入主存。

该进程的页表如表2 所示，进程执行的指令序列如表3 所示，地址变换算法流程如图1所示。

图1 地址变换算法流程
运行自己设计的地址变换程序，显示或打印运行结果。

因为只是模拟地址变换，并不模拟指令的执行，故不考虑上述指令的操作结果。

2、采用先进先出(或LRU)算法实现分页管理的缺页中断处理
在请求分页存储管理系统中，当硬件发出缺页中断后转操作系统处理缺页中断。

如果主存中已无空闲块，采用适当算法(FIFO 或LRU) 进程缺页处理。

(1)当采用先进先出算法时，用一个数组P构成先进先出(FIFO) 队列，数组中各个元素为进程已在主存的页号，其队列头指针放在HEAD变量中，初始化为0 。

假定分配给每个进程的内存块数固定不变，为M。

当队列满需淘汰时，掏汰最先进入主存的一页。

若该页修改过，还要存入磁盘。

然后再把当前要访问的页装入该块，并修改页表和存储分块表中的对应标志。

采用先进先出(FIFO) 置换算法的流程如图2 所示。

每一次调整，要求输出队列中的元素。

(2)当采用LRU 算法时，用一个数组P构成堆栈，堆栈中各个元素为进程已在主存的页号，为了进行页面置换，可设置一个栈指针HEAD ，初始化为0。

假定分配给每个进程的内存块数固定不变，为M。

当队列满需淘汰时，操作系统选择栈底的元素淘汰，其他元素向下移一个位置，将新调入页放HEAD指示的钱顶。

当访问的页在栈中时，还应调整页号从当前位置到栈顶。

采用LRU 置换算法的流程如图3 所示。

每一次调整，要求输出栈中的元素。

图2 FIFO置换算法流程
图3 LRU置换算法流程。