7.4 页式存储管理

7.4.1 分区式存储管理的局限及对策

1、分区式作业必须连续存储。
2、分区式方式下当作业的地址空间大于内存可用分区空间时，作业不能马上运行，必须等到空闲分区和其他分区释放后融合成为更大的空闲分区后才能全部载入内存。
针对这些局限性，提出分页式存储管理，可以解决作业的非连续存储和部分调入问题。
分页式应解决的问题：1、动态地址映射；2、调入策略；3、淘汰策略；4、放置策略。

1、“页”与“块”具有相等的大小，只是为区别起见，对虚存的划分单位称为“页”，对主存的划分单位称为“块”。
2、主存“块”及虚存“页”的大小一般为2的次幂，多为1至4K；
3、主存碎片大量减少；碎片最多出现在最后一个主存块中；
4、实现了连续存储到非连续存储的飞跃；

7.4.2 页式地址变换

（一）页表
OS为每个进程建立的一张表，存放在主存的固定区域中，也有可能放在高速缓冲存储器，或部分放在主存，部分放在高速缓存中，最简单的页表只包含两方面的信息：页号、页面对应的块号。
页表可由高速缓冲存储器组成，这样做的结果是，地址变换速度快，但成本较高。然而，在现代的计算机系统中，往往采用硬件作为地址变换机构。另一个办法是，在主存固定区域内，拨出一些存储单元来存放页表。图7.15给出三个作业分页映像存储的情况。从图中可以看出每个作业有一张页表表。对于实现地址变换而言，页表需两个信息，一为页号，二为页面对应的块号。

  　　　　　　　　　　图7.15  分页映像存储

页表始址寄存器
用于记录页表存放在内存中的起始地址；

（二）虚地址结构
如何利用页表来进行地址变换，这和计算机所采用的地址结构有关，而地址结构又与选择的页面尺寸有关。比如，当CPU给出的虚地址长度为32位，页面大小为4KB时，在分页系统中地址结构的格式如图7.16所示。
在这种情况下，若页面大小确定为4KB，机器的地址长度为32位，则每当CPU给出一个虚地址（指令地址或操作数地址）时，这个进址中的高20位（12位～31位）一定表示这个地址所在的页号，而12位（0～11位）一定表示该地址在这页内的相对位称量。分页系统中具有这种特征的地址结构称为页机构。
（三）页式地址变换
下面以图7.17中所示的作业2程序中的一条指令的执行过程来说明页式系统的地址变换过程。程序地址空间中第100号单元处有一条指令为“mov r1,[2500]”。这条指令在主存中的实际位置为2148号单元（第2块100号单元），而这条指令要取的数123在程序地址空间中位于2500号单元（第2页的452号单元）处，它在主存中存于7620号单元（第7块452号单元）。假定页面大小为1KB，机器的地址长度为16位。
 　　　　　　　　　 图7.17  页式系统地址变换过程

当作业2的相应进程在CPU上运行时，操作系统负责把该作业的页表在主存中的起始地址（a）送到页表起始地址寄存器中，以便在进程运行过程 进行地址变换时由它控制找到该作业的页表。
当作业2的程序执行到指令“mov r1,[2500]”时，CPU给出的操作数地址为2500，首先由分页机构自动地把它分为两部分，得到页号p=2，页内相对位移w=452。然后，根据页表始址寄存器指示的页表始地址，以页号为索引，找到第2页所对庆的块号为7。最后，将块号7和页内位移量w拼接在一起，就形成了访问主存的物理地址7620。这正是所取的数123所在主存的实际位置。图7.17说明了这个过程。

7.4.3 请调策略

1、分页式存储管理技术采用请求调入策略，页面根据请求而
被装入内存，这种页式系统也可称为请求分页式存储管理；
2、如何发现所要访问的页面不在主存中？——扩充页表；
图7.15中所示的页表结构只包含页号和块号两个信息，这是进行地址变换所必须的。为了能判断页面在不在主存，可在每个页表表中，除了登记虚页所在的主存块号外，再增加两个数据项。其一是中断位I，它用来标识该而是否在主存。若i=1。表示此页不在主存；若i=0，表示该页在主存。其二是该页面在辅存地位置。因此，扩充功能的页表格式应为图7.19所示。
页表中还必须包含关于页面的使用情况的信息，并增设专门的硬件和软件来考查和更新这些信息。于是，在页表中增加“引用位”和“改变位”。“引用位”是用业指示某页最近被访问过没有：为“0”表示没有被访问过；为“1”表示已被访问过。“改变位”是表示某页是否被修改过：为“1”表示已被修改过；为0表示未被修改过。这一信息是为了在淘汰一页时决定是否需要写回辅存而设置的。因此，这种情况下页表的一个表目通常在逻辑上至少应包括如图7.21所示的各数据项。

图7.21  完整的页表结构

7.4.4 淘汰策略

（一）置换算法
当要索取一页面并送入到全满的内存时，必须把已在主存中的某一页面淘汰到辅存，用来选择淘汰哪一页的规则称为置换策略。
置换算法可描述如下：当要索取一页面并送入到全满的主存中时，必须把已在主存中的某一页面淘汰掉。用来选择淘汰哪一面的规则就叫做置换算法。
（二）颠簸
颠簸（抖动）：导致系统效率急剧下降的主存和辅存之间的频繁的页面置换现象。
“抖动”现象花费了系统大量的开销，但收效甚微。因此，各种置换算法应考虑尽量减少和排除抖动现象的出现。

7.4.5 几种置换算法法

下面讨论几个常用的置换算法。讨论这些算法的前提是假定每道程序都给予固定数量的主存空间，即每道程序实际上占用的主存块数不允许页面调度算法来改变。
（一）先进先出算法（FIFO算法）
原理：总是选择在主存中停留时间最长的一页淘汰；
这种算法实现起来比较简单，只要系统保留一张次序表即可。该次序表记录了作业程序的各页面进入主存的先后次序。
在FIFO算法中，有时分配的内存块越多缺页中断率反而越高，这种现象称为陷阱现象。发生陷阱现象的原因在于：FIFO算法未考虑程序执行时的动态特征。
（二）最久未使用淘汰算法（LRU算法）
这原理：总是选择最长时间未被使用的一页进行淘汰。
LRU算法能够比较普遍地适用于各种类型的程序，但它同FIFO算法相比实现起来困难很多。因为，使用LRU算法必须在每次访问页面时都要修改有关信息，且需要做连续的修改，而对于FIFO算法，仅当往主存装入页面时才作修改。这种连续的修改如果完作由软件来做，其代价太高，但若由硬件完成，又要大大增加成本。由于以上原因，真正的LRU算法用得很少。实际得到推广的仅是一种简单而有效的LRU近似算法。
LRU似近算法，只要求每一个存储块有一位“引用位”（在逻辑上可以认为它在存储分块表中或在页表中）。当某块中的页面被访问时，这一位由硬件自动置“1”，而页面管理软件周期性（设周期为T）地将所有引用位重新置“0”。这样，在时间T内，某些被访问的页面，其对应的引用位为1，而未被访问过的页面，其相应的引用位为0。这样，在时间T内，某些被访问的页面，其对应的引用位为1，而未被访问过的页面，其相应的引用位为0。因此，可以根据引用位的状态来判断各个页面最近使用的情况。当需要置换一页时，选择引用位为0的页淘汰之。图7.25所示的算法就是查找引用位为0的块。在查找过程中，那些被访问过的页所对应的引用位重新被置为0。
  　　　　　　 图7.25  LRU近似算法

7.4.6 小结：页式管理的优缺点

优点：1、实现了作业或进程的非连续存放，有效解决了碎片问题；
            2、实现了内外存统一管理的虚存方式，用户可利用的存储空间大大增加；
缺点：1、硬件开销加大（地址变换，缺页中断等）；
            2、增加了系统开销（缺页中断处理）；
            3、抖动现象；
            4、每个作业或进程的最后一页总有一部分空间得不到利用。