操作系统之存储管理详细知识点

存储管理所研究的内容包括三个方面：取（Fetch）、放（Placement）、替换（Replacement）。

• “取”是研究该将哪个进程（或进程的某些部分）从辅存调入主存。调入进程占用主存或有资格占用主存是中级调度的工作。在主存资源有限的情况下，也可以调入进程的某些部分占用主存，它一般有请调（Demand Fetch）和预调（Anticipatory Fetch）之分。前者按照进程运行需要来确定调入进程的某一部分；后者是采用某种策略，预测出即将使用的进程的某部分并调入到主存。

• “放”则是研究将“取”来的某进程（或进程的某部分）按何种方式放在主存的什么地方。

• “替换”是研究将哪个进程（或进程的某部分）暂时从主存移到辅存，以腾出主存空间供其他进程（或进程的某部分）占用。

在这三个方面中，“放”是存储管理的基础。目前“放”的技术可归结成两类：一类是连续的，即运行的程序和数据必须放在主存的一片连续空间中（单道连续分配、多道固定分区和多道可变分区方法均属此类）；另一类是不连续的，即运行的程序和数据可以放在主存的多个不相邻的块中（页式管理、段式管理和段页式管理即属此类）。下面详细介绍：

一、连续空间管理

1. 单道连续分配

系统只有单道用户程序，单道用户程序连续存放于主存中。

2. 多道固定分区法

单道管理过于简单，主存中只能存放一道作业。多道固定分区法将用户空间分成如大小固定的几块，各块大小的选取很重要。系统初启时，可根据系统中常运行的作业的大小来划分各块。以后在系统运转过程中不断收集统计信息，再重新修订各块的大小。
在多道固定分区法下，存储调度（即中级调度）一般分为多队列法和单队列法。多队列法是指每个存储区对应一个作业队列，在作业到达后，按该作业的大小在对应的队列中排队。单队列法是指系统中仅保持一个作业队列。
多道固定分区法虽比单道连续分配法提高了空间利用率，但对空间的利用仍不充分。进入各存储块的作业长度往往短于该块的长度，因而存在一些未加利用的存储空间。另外，若大作业较多，小存储块就常处于空闲状态而形成浪费。这些未得到利用的空间称为存储碎片。

3. 多道可变分区法

这种方法对用户存储实施动态分割，从而改善了空间的利用效果。系统设置一张表（多道可变连续分区法一般用数组或链表管理可用空间），登记主存空间用户区域未占用的块（空闲块）。当作业到达后，即可在空闲块中分配空间。如果满足作业要求的可用快可能有多个，那么应该选择哪一块分给作业呢，有以下三种选择方案：
① 首次满足法（First Fit）。搜索F时，选择所碰到的第一个满足作业存储量要求的块分配给用户。
② 最佳满足法（Best Fit）。在F中选出所有满足作业要求的存储块中最小的一块分给用户。
③ 最大满足法（Largest Fit）。在F中选出满足作业要求的最大块分给用户。
下面两张图展示了多道可变分区的一个实例。


采用可变分区，没有内部碎片（一般不把小于基本存储分配单位的未利用的空间看成碎片）。但是有外部碎片，并且外部碎片现象经常很严重。这可以用紧致（Compact）空间的方法予以消除。紧致的基本思想是，通过移动主存中的作业位置，使可用空间连成一片。实现紧致必须要求作业代码是动态重定位的。（精致虽然可以达到较好的效果但是实施复杂）
连续空间管理总结：

二、不连续空间管理

1.页式管理

逻辑地址与物理地址：用户程序目标代码所设想的空间和所用地址称为逻辑空间和逻辑地址。所占主存空间称为物理空间，对应的地址称为物理地址。在页式系统中，逻辑空间、物理空间均以相同长度为单位进行等分。逻辑空间所划分出的每个区域称为页（Page）；物理空间所划分出的每个区域称为页帧（Page Frame）。页和页祯大小一致。
逻辑地址和物理地址的动态地址转换过程如下图所示：首先把页号送到快表中去匹配。若匹配成功，则形成物理地址，否则到主存页表中查找页表项来形成物理地址。如果快表不满，则将新页表项加入快表，否则从快表中淘汰一项后再加入新项。
快表：为了减少内存的访问次数，将页表中经常用的页表项置于快速存储器（即快变，又称为联想存储器）。

有些处理机设计是匹配快表和查找页表同时进行，如果快表匹配成功则查找页表逻辑终止。
页式存储可用空间管理
页式系统把所有可用页帧或组成一个链表，或将它们登记在数组中。当按调度原则选中某作业（进程）进入主存时，首先检查现有的可用页帧总数是否大于或等于作业（进程）的总页数，否则不能分配。此时，需从可用队列中取出满足作业（进程）要求的若干页帧分给该作业（进程）。分配时须将页中内容抄到对应的页帧中，并填写对应的页表项，使二者互为对应。可用空间管理工作如下：
① 若可用页帧总数小于作业（进程）总页数，则拒绝分配，结束。
② 取作业（进程）的下一页P，分配一可用页帧f，并将P的内容抄到f中。
③ 将f抄到页P的页表项中。
④ 若所有页已处理完，则结束，否则转到②。
当作业（进程）撤离或出交换时，根据页表项中记录的页帧号，回收页帧到可用队列中。

2.段式管理

页式管理虽具有空间利用好、管理方法简单的特点，但是将空间按页划分就用户而言显得极不自然。用户看待程序是以自然段为单位的，如主程序段、子程序段、数据段等。若用户要求保护，那么受到保护的基本单位也是自然段。
段式系统的地址转换与页式系统基本相同。首先需要一张逻辑空间与主存空间对照的段表，若作业被划分成n段，段表就应该有n项。作业控制块（或PCB）保存段表起始地址和段表长度。系统还设置段表起始地址寄存器及段表长度寄存器，低调选中某个进程后就将该进程的段表起始地址与长度装入这对寄存器中。

地址转换的过程是，将段号与快表中的各个关键字进行比较，若匹配成功，则检查段内位移d是否在该说明的长度内，同时检查保护码与本次操作的一致性，若这些比较结果都正常，则输出该段的起始物理地址，并与d相加得到物理地址。若在快表中匹配不成功，则将S与段表长度寄存器的内容进行比较。若没有越界，则将S与段表始地址相加，得到段表项的物理地址，查段表项，检查d是否越界，操作码是否与保护码一致。最后用该段起始地址与d相加得到物理地址，同时更换快表的内容。
附保护码：操作访问保护的一般方法是，在页表项中增设一个存储保护域。保护的项目一般有读、写、执行，分别用R，W，E来表示。每个保护项目用一位表示，该位为1表示可以进行这种操作，为0表示不可以进行这种操作。R，W，E各位的不同取值形成表5.3的8种保护模式。

硬件在进行地址转换的同时，将该次访问要进行的操作与页表项中的保护码进行匹配。若访问不合法则报访问权限错，系统产生异常，异常处理将终止作业的运行。例如，若页表项中的保护码为101，而访问该页是取其指令执行则为合法。若是欲修改该页面（即进行写操作），则访问不合法。故页表项中除含有页帧号外，还包含保护码，段表中也是如此。

3.段页式管理

段页式系统对物理空间的管理、安排与页式系统相同，而对逻辑空间则先进行段的划分，然后在每一段内再进行页的划分。
其逻辑地址由三部分组成：段号、页号、页内位移，分别记为S，P，d。当地址转换时，首先向快表输入S，P，而S，P同时与各个关键字比较。若匹配成功，则进行操作保护检查。若操作合法，则输出对应的页帧号，合成物理地址。若匹配不成功，则将S与段表长度进行比较，查看是否越界。若正常，则将段表始地址与S相加，到主存查找对应的段表项。将段表长度与P比较，若没有越界，则将段表始地址与P相加得到页表项地址，同时进行操作保护检查。最后查页表项，得到f，将f与d合成物理地址，并用S，P，f替换快表中的一项。

总结各种存储管理方法，“放”可归纳为连续存放与不连续存放这两类。前者包括单道连续分区、多道连续固定分区和多道连续可变分区。后者包括页式、段式和段页式系统。对连续存放的管理方法，硬件只提供越界保护措施，但是这类方法不能较好地利用存储空间（多道可变分区法虽可用紧致消除碎片，但耗费巨大）且无法实现共享。非连续存放的管理方法均要求硬件提供动态地址转换机制，能实现共享。页式系统管理方法简单，能很好地利用存储空间，但不利于共享与保护。段式系统有利于共享和保护，但空间利用差，管理复杂。改进的段页式管理结合了两者的优点。

我们可以看出上面的所有存储管理方式有两个特征：

1. 作业必须一次性全部装入内存后，方能开始运行。这会导致两种情况发生：

• 当作业很大，不能全部被装入内存时，将使该作业无法运行；
• 当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序度的下降。

2. 作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。运行中的进程，会因等待I/O而被阻塞，可能处于长期等待状态。

由以上分析可知，许多在程序运行中不用或暂时不用的程序（数据）占据了大量的内存空间，而一些需要运行的作业又无法装入运行，显然浪费了宝贵的内存资源。基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。下面再看引入了虚拟存储之后的内存管理。

三、虚拟内存管理

现在，软硬件都有了较大的发展，特别是硬件价格大幅度降低，主存已做得很大。但是虚存技术并未因此而遭淘汰，因为采用虚存技术仍有重要意义，除了能给用户进程一个足够大的虚空间外，还能提高系统的吞吐率。因为它只把运行程序在最近一段时间里活跃的那一部分放进主存，而这一部分往往只占整个程序空间的少数，于是主存中能同时存在的进程道数明显增多，为提高系统的吞吐量奠定了基础。
页式管理、段式管理、段页式管理和虚存技术的结合分别称为页式虚存系统、段式虚存系统、段页式虚存系统。下面详细介绍页式虚存系统，段式虚存系统和段页式虚存系统实现和页式虚存系统类似。
实现页式虚拟空间的基本方法是，在页式存储管理的基础上，仅把进程的一部分页放在主存中。页表项中注明对应的页是在主存还是在辅存。程序在执行时，当访问的页不在主存时，根据页表项的指引，从辅存将其调入主存。如果这时已无可用的物理空间，则从主存淘汰若干页。其页表项的结构如下：

① 合法位：置上表示该页在主存中。
② 修改位：置上表示该页在上次调入主存后被修改过，在淘汰时应回写辅存。
③ 页类型：零页时，表示该页在分配物理页帧时应清0页帧空间；回写Swap文件页时，表示在回写时必须分配Swap空间（用于存放那些可读写的进程页面），并回写到Swap空间；没有设置页类型时，表示按正常方式处理。
零页表示该页的初始值是0，为这种页面分配主存页帧时，不必从辅存获得初始数据，只要在分配页帧时，将页帧清0即可。当回写时，也需要分配交换空间，然后回写到交换空间中。
④ 保护码：说明许可对该页的读/写或执行操作。
⑤ 辅存块号：该页所在辅存的块号，用于页面的调入和回写。
⑥ 页帧号：当合法位置上时，代表该页所在主存的页帧号。
动态地址转换过程： 当CPU执行访存操作时，首先从快表查找要访问地址的逻辑页号对应的物理页帧号。注意，快表中的项都是合法页的页表项，在进程被调度运行时由操作系统置入。若能够在快表中获得要访问页的页帧号，则合成物理地址并进行访问。若要查页表，须先检查该页页表项的合法性。若合法位已被置上，则从页表项中获得页帧号，合成物理地址并进行访问。若合法位未被置上，则马上产生一个页故障（Page Fault）或称为缺页异常。进入操作系统核心，马上进行页面调入处理。操作系统处理完成后，返回刚产生页故障的指令运行现场，重新执行访存指令。这时，访存指令可以合成物理地址并进行访存。由此可见，页故障的开销会非常大，如何减少页故障，是操作系统虚存管理面临的挑战。
当硬件执行访存指令时，若要访问的页面不在主存则会发生缺页异常。发生缺页异常后，硬件会马上转到操作系统中断/例外入口，进行现场保护，判断是缺页异常，并进行如下处理：
① 根据发生页故障的虚地址得到对应页的页表项。
② 申请一个可用的页帧（根据所采用的页面替换策略，可能需要淘汰某一页，即将某页的主存空间释放）。
③ 检查发生页故障页的页类型。若为零页，则将刚申请到的页帧清0，将页帧号填入页表项，置合法位为1。否则，则调用I/O子系统将页表项中辅存块号所指的页面读到页帧中，将页帧号填入页表项，将合法位置1，结束缺页异常的处理，转中断/例外处理公共出口，恢复现场，重新执行访存指令。
页面替换策略
采用虚存技术能较好地解决空间不足的矛盾并提高系统的效率。解决空间不足的效果一般较明显，而提高系统效率的实现是有条件的。因为采用虚存技术后，常会出现页故障，解决页故障需要与辅存打交道，耗时较多。如果系统不能有效地将页故障控制在一定范围内，则会使系统陷于页故障的频繁处理，很少做有用工作。影响页故障数的首要因素是页面替换策略。主要分为驻留集固定的替换策略和驻留集可变的替换策略。

• 驻留集固定的替换策略
  （1）FIFO（First In First Out）
  这是一种最简单的替换策略。例如，驻留集大小为三个页帧，在FIFO策略控制下，对于访问串7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，驻留集的变化过程如下图所示，出现12次页故障（X表示产生一次页故障）。
  
  实现FIFO策略无需硬件提供新的帮助。但是FIFO策略的实际效果不好，并且伴有一种称为Belady奇异的现象。Belady奇异是指替换策略不符合随着驻留集大小的增大，页故障数一定减少的规律。
  （2）OPT（OPTional replacement）
  它淘汰距离下次访问最远的页。例如，驻留集大小为三个页帧，访问串为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。在OPT策略控制下，驻留集变化过程如图5.41所示，共出现8次页故障。例如，要访问访问串的第四个时（即2），当前存在内存的页式7，0、1，通过查看后续访问串，可以得知再访问7的距离是最远的（在这个例子中是不访问了），所以淘汰7。
  
  OPT虽被誉为驻留集固定策略中的最优策略，但由于用以控制页面替换时需预先得知整个访问串，故难以付诸实用，仅能将其作为一种标准，用以测量其他可行策略的性能。
  （3）LRU（Least Recently Used）
  LRU策略淘汰上次使用距当前最远的页。例如，驻留集大小为三个页帧，访问串为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。在LRU控制下，驻留集的变化过程如下图所示，共出现11次页故障。
  
  LRU没有Belady奇异。
  （4）CLOCK
  CLOCK策略是一种基于LRU思想的简化算法。页表项需要增加一个访问位，硬件访问页面时置上访问位，进程所有驻留页形成一个类似钟面的环形链表，如下图所示，有一指针指向当前欲淘汰页。当需要淘汰页面时，如果指针指向的页访问位是0，则将其淘汰，指针顺时针方向转一格；如果指针指向的页访问位是1，则将访问位清0，指针顺时针方向转一格，……，直到找到访问位是0的页，将其淘汰。该算法既考虑了最近被访问的因素，清除访问位代价也较小，是一种比LRU更实用的算法。
  
  （5）NRU（Not Recently Used）
  每页设表示其被使用的访用位，每访问一页就置对应的访用位为1，页管理软件则定时地把所有的访用位重新置0。当必须淘汰页时，任选一访用位为0（可能不唯一，但表明该页最近没有被访问）的页。若所有页的访用位都为1，则按FIFO规则淘汰。
  为减少淘汰页的回写时间可增设修改位。因此在选择淘汰页时，总尽量避免首先淘汰被修改过的页，因为这种页被淘汰时需要写回辅存。若将访用位与修改位结合起来，则可制定如下的淘汰顺序：先选择访用位和修改位为0的页作为淘汰对象。若无这种页，则选择未使用但被修改过的页，然后选择使用过但未被修改过的页，最后再按FIFO规则选择二者均为1的页淘汰。
• 驻留集可变的替换策略
  （1）WS（Working Set）
  这是一种为顺应程序的局部性行态而制定的策略，在驻留集中只放置当前活跃的局部集（我们把活跃的局部集叫做工作集Working Set）中的页。WS需要一个控制参数，记为Δ。若某页在驻留集中有Δ个时间单位（访存间隔）未被引用，则将其淘汰。例如，取Δ＝5，访问串为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。驻留集的变化见下表，其中共产生了7次页故障。驻留集的评论大小为3.5。
  
  （2）SWS（Sampled Working Set）
  在实际系统中，常用的是SWS策略，它近似WS。在WS策略的控制下，每过τ个时间单位（如取τ＝10000）检查一次计数器，将计数器值大于等于Δ的页淘汰。这样做耗费仍很大，可用硬件时钟计数来进一步降低耗费。每访问一页，同时将当前时钟值记录在页表项中，经τ时间单位后便检查驻留集，将当前时钟值与记录在页表项中的值相减，淘汰差值大于等于Δ的页。

参考资料：
操作系统（第三版），罗宇等编著。