基本原理

静态页式管理(内存页面分配与回收 分配算法 地址变换)

动态页式管理

请求页式管理中的置换算法(随机淘汰算法 轮转法和先进先出算法 最近最久未使用页面置换算法 理想型淘汰算法)

存储保护

页式管理的优缺点(优点： 缺点：)

页式管理是一种内存空间存储管理的技术，页式管理分为静态页式管理和动态页式管理。

基本原理

将各进程的虚拟空间划分成若干个长度相等的页(page)，页式管理把内存空间按页的大小划分成片或者页面（page frame），然后把页式虚拟地址与内存地址建立一一对应页表，并用相应的硬件地址变换机构，来解决离散地址变换问题。页式管理采用请求调页或预调页技术实现了内外存存储器的统一管理。

静态页式管理

内存页面分配与回收

静态分页管理的第一步是为要求内存的作业或进程分配足够的页面。系统通过存储页面表、请求表以及页表来完成内存的分配工作。

页表：内存中的一块固定存储区。页式管理时每个进程至少有一个页表。

请求表：用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置；

存储页面表：整个系统有一个存储页面表，其描述了物理内存空间的分配使用状况。

存储页面表有两种构成方法：

1、位示图法

2、空闲页面链表发

分配算法

首先，请求表给出进程或作业要求的页面数。然后，由存储页面表检查是否有足够的空闲页面，如果没有，则本次无法分配。如果有则首先分配设置页表，并请求表中的相应表项后，按一定的查找算法搜索出所要求的空闲页面，并将对应的页好填入页表中。

地址变换

首先，需要有一个装置页表始址和页表长度用的控制寄存器。系统所调度执行的进程页表始址和长度从请求表中取出送入控制寄存器中。然

后，由控制寄存器页表始址可以找到页表所在位置。

静态页式管理解决了分区管理时的碎片问题。但是，由于静态页式管理要求进程或作业在执行前全部装入内存，如果可用页面数小于用户要求时，该作业或进程只好等待。而且作业和进程的大小仍受内存可用页面数的限制。

动态页式管理

动态页式管理是在静态页式管理的基础上发展起来的。它分为请求页式管理和预调入页式管理。请求页式管理和预调入页式管理在作业或进程开始执行之前，都不把作业或进程的程序段和数据段一次性地全部装入内存，而只装入被认为是经常反复执行和调用的工作区部分。其它部分则在执行过程中动态装入。请求页式管理与预调入页式管理的主要区别在它们的调入方式上。请求页式管理的调入方式是，当需要执行某条指令而又发现它不在内存时或当执行某条指令需要访问其它的数据或指令时．这些指令和数据不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。

预调入方式是，系统对那些在外存中的页进行调入顺序计算。估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序将它们顺次调入和调出内存。除了在调入方式上请求页式管理和预调入管理有些区别之外，其它方面这两种方式基本相同。因此，下面我们主要介绍请求页式管理。

请求页式管理的地址变换过程与静态页式管理时的相同，也是通过页表查出相应的页面号之后，由页面号与页内相对地址相加而得到实际物理地址，但是，由于请求页式管理只让进程或作业的部分程序和数据驻留在内存中，因此，在执行过程中，不可避免地会出现某些虚页不在内存中的问题。怎样发现这些不在内存中虚页以及怎样处理这种情况．是请求页式管理必须解决的两个基本问题。

第一个问题可以用扩充页表的方法解决。即与每个虚页号相对应，除了页面号之外，再增设该页是否在内存的中断位以及该页在外存中的副本起始地址。关于虚页不在内存时的处理，涉及到两个问题。第一，采用何种方式把所缺的页调入内存。第二，如果内存中没有空闲页面时，把调进来的页放在什么地方。也就是说，采用什么样的策略来淘汰已占据内存的页。还有，如果在内存中的某一页被淘汰，且该页曾因程序的执行而被修改，则显然该页是应该重新写到外存上加以保存的。而那些未被访问修改的页、因为外存已保留有相同的副本，写回外存是没有必要的。因此，在页表中还应增加一项以记录该页是否曾被改变。

在动态页管理的流程中，有关地址变换部分是由硬件自动完成的。当硬件变换机构发现所要求的页不在内存时，产生缺页中断信号，由中断处理程序做出相应的处理。中断处理程序是由软件实现的。除了在没有空闲页面时要按照置换算法选择出被淘汰页面之外，还要从外存读入所需要的虚页。这个过程要启动相应的外存和涉及到文件系统。因此，请求页式管理是一个十分复杂的处理过程，内存的利用率的提高是以牺牲系统开销的代价换来的。

请求页式管理中的置换算法

功能：需要调入页面时，选择内存中哪个物理页面被置换。称为replacement policy。

出发点：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测。

页面锁定(frame locking)：用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现方法为在页表中加上锁定标志位(lock bit)。

随机淘汰算法

随机淘汰算法(random golongram):在系统设计人员认为无法确定哪些页被访问的概率较低时，随机地选择某个用户的页面并将其换出将是一种明智的作法。

轮转法和先进先出算法

轮转法(RR,round robin)和先进先出算法(FIFO,first in first out):轮转法循回换出内存可用区内一个可以被换出的页，无论该页是刚被换进或已换进内存很长时间。FIFO算法总是选择在内存驻留时间最长的一员将其淘汰。

FIFO算法认为先调入内存的页不再被访问的可能性要比其它页大，因而选择最先调入内存的页换出。实现FIFO算法需要把各个已分配页面按分配时间顺序链接起来，组成FIFO队列，并设置一置换指针指向FIFO队列的队首页面。这样，当要进行置换时，只需把置换指针所指的FIFO队列前头的页顺次换出，而把换入的页链接在FIFO队尾即可。

由实验和测试发现FIPO算法和RR算法的内存利用率不高。这是因为，这两种算法都是基于CPU按线性顺序访问地址空间这一假设。事实上，许多时候．CPU不是按线性顺序访问地址空间的。

Belady现象:一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。在极限情况下，这个推论是成立的。因为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。但是，使用FIFO算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。

最近最久未使用页面置换算法

最近最久未使用页面置换算法(LRU, Least Recently Used):

选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。硬件机构如：

(1) 一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。

(2) 每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。

比较常用的近似算法有：

(a) 最不经常使用页面淘汰算法(LFU, Least Frequently Used)

(b) 最近没有使用页面淘汰(NRU, Not Recently Used)

理想型淘汰算法

理想型淘汰算法（OPT,Optimal Replacement Algorithm）

该算法淘汰在访问串中将来再也不出现的或是离当前最远的位置上出现的页。它是一种理想化的算法，性能最好，但在实际上难于实现。

存储保护

页式管理可以为内存提供两种方式的保护。一种是地址越界保护，另一种是通过页表控制对内存信息的操作方式以提供保护。

地址越界保护可由地址变换机构中的控制寄存器的值一一页表长度和所要访问的虑地址相比较完成。

存取控制保护的实现则是在页表中增加相应的保护位即可。

页式管理的优缺点

优点：

1、由于它不要求作业或进程的程序段和数据在内存中连续存放，从而有效地解决了碎片问题。

2、动态页式管理提供了内存和外存统一管理的虚存实现方式，使用户可以利用的存储空间大大增加。这既提高了主存的利用纽，又有利于组织多道程序执行。

缺点：

1、要求有相应的硬件支持。例如地址变换机构，缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。这增加了机器成本。

2、增加了系统开销，例如缺页中断处理机，

3、请求调页的算法如选择不当，有可能产生抖动现象。

4、虽然消除了碎片，但每个作业或进程的最后一页内总有一部分空间得不到利用果页面较大，则这一部分的损失仍然较大。