页面置换算法（FIFO、LRU）用C++实现

为了使大的作业(其地址空间超过主存可用空间)或多个作业的地址空间之和超过实际主存空间时，仍能运行，引入了虚拟存储器的概念。使运行作业的一部分地址空间在主存,另一部分地址空间在辅存，由操作系统实现多级存储器的自动管理，实现主存空间的自动覆盖。要求学生通过本实验，对请求分页管理有一个清楚的概念。

(1)在分页虚拟存储系统中，当硬件发出缺页中断后转操作系统处理缺页中断。查主存分块表看有无可用空闲块。若有，则为进程分配-块。如果主存中已无空闲块,当采用先进先出算法时，已进人的各页排成一个FIFO队列,其头部放在变量K中。淘汰时，淘汰最先进人主存的一页。若该页修改过，还要存入磁盘。然后再把当前要访问的页装人该块,并修改页表和存储分块表。恢复中断现场，继续执行被中断的指令。 数组P中各个元素为作业已在主存的页号。假定作业最多可分配m块,且该作业的装人情况如图10-2所示。当淘汰一页时，总是淘汰P[K]所指页。之后调整数组P: -----P[K]=要装入的页 -----K=(K+1)mod m 先进先出(FIFO)淘汰算法框图如图10-2所示。 (2)当采用LRU算法时，则淘汰最近很少访问的页。 该算法也可采用一个数组P记录该作业已在主存的页。假定分给该作业4个空闲块。 为了模拟LRU算法,将数组P设计成一个能含有4个元素的堆栈,栈指针用HEAD 表示。假定开始时，堆栈为空。HEAD的初值为0。当调一个页时，按P[HEAD]-调入的页号,HEAD=(HEAD+1) mod m。当访问的页在主存时，将该页调整到栈顶:首先找到该页在P中的位置A.若A≠HEAD,则将该页放栈顶，其他页依次向下移，以反映该页是最近访问的页。 最近很少访问(LRU)淘汰算法框图如图10-3所示。 （3）FIFO和LRU算法使用的指令序列如表10-3所示。