系统设计硬核知识(3)——操作系统的存储管理

存储器是计算机系统中最重要的资源之一。因为任何程序和数据以及各种控制用的数据结构都必须占有一定的存储空间，因此，存储管理直接影响系统性能。

存储器由内存和外存组成。内存是由系统实际提供的存储单元（常指字节）组成的一个连续地址空间，处理器可直接存取。外存（辅存）是指软盘、硬盘、光盘和磁带等一些外部存储部件，常用来存放暂不执行的程序和数据。处理器不能直接访问外存，需通过启动 I/O（Input/Output，输入/输出）设备才能进行内存、外存交换，其访问速度慢，但价格便宜， 常用作内存的后援设备。

内存大小由系统硬件决定，存储容量受到实际存储单元的限制。虚拟存储器（简称虚存）不考虑实际内存的大小和数据存取的实际地址，只考虑相互有关的数据之间的相对位置，其容量由计算机地址的位数决定。

系统中内存的使用一般分成两部分，一部分为系统空间，存放操作系统本身及相关的系统程序；另一部分为用户空间，存放用户的程序和数据。

存储管理主要是指对内存储器的管理，负责对内存的分配和回收、内存的保护和内存的扩充。

存储管理的目的是尽量提高内存的使用效率。

1 地址变换

由进程中的目标代码 、 数据等的虚拟地址组成的虚拟空间称为虚拟存储器，虚拟存储器允许用户用比内存容量大得多的地址空间来编程，以运行比内存实际容量大得多的程序。用户编程所用的地址称为逻辑地址 ( 虚地址 ) ，而实际的内存地址则称为物理地址 ( 实地址 ) 。每次访问内存时都要进行逻辑地址到物理地址的转换，这种转换是由硬件完成的，而内存和外存之间的信息动态调度是由硬件和操作系统两者配合完成的。

1. 静态重定位 : 静态重定位是在虚空间程序执行之前由装配程序完成地址映射工作。静态重定位的优点是不需要硬件的支持。 缺点是无法实现虚拟存储器，必须占用连续的内存空间，且难以做到程序和数据的共享。
2. 动态重定位 : 动态重定位是在程序执行过程中，在 CPU 访问内存之前，将要访问的程序或数据地址转换为内存地址。动态重定位依靠硬件地址变换机构完成，其优点主要有 : 可以对内存进行非连续分配，提供了虚拟存储器的基础，有利于程序段的共享 。

2 存储组织

虚拟存储器可以分为单一连续分区 、 固定分区 、 可变分区 、 可重定位分区 、 页式 、 段式 、 段页式 7 种 。

1. 单一连续分区。把所有用户区都分配给唯一的用户作业，当作业被调度时，进程全部进入内存，一旦完成，所有内存恢复空闲，因此，它不支持多道程序设计 。
2. 固定分区。这是支持多道程序设计的最简单的存储管理方法，它把内存划分成若干个固定的和大小不同的分区，每个分区能够装入一个作业，分区的大小是固定的，算法简单，但是容易生成较多的存储器碎片 。
3. 可变分区。引入可变分区后虽然内存分配更灵活，也提高了内存利用率，但是由于系统在不断地分配和回收中，必定会出现一些不连续的小的空闲区，尽管这些小的空闲区的总和超过某一个作业要求的空间，但是由于不连续而无法分配， 产生了碎片解决碎片的方法是拼接 ( 紧凑 ) ，即向一个方向 ( 如向低地址端 ) 移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面是要求能够对作业进行重定位，另一方面系统在拼接时要耗费较多的时间。
4. 可重定位分区。这是克服固定分区碎片问题的一种存储分配方法，它能够把相邻的空闲存储空间合并成一个完整的空区，还能够整理存储器内各个作业的存储位置，以达到消除存储碎片和紧缩存储空间的目的。紧缩工作需要花费大量的时间和系统资源。

另外还有三种存储组织方式：页式 、 段式 、 段页式，下面我们将详细解读段页式存储管理。

2.1 页式存储管理

分页的基本思想是把程序的逻辑空间和内存的物理空间按照同样的大小划分成若干页面，并以页面为单位进行分配。在页式存储管理中，系统中虚地址是一个有序对（页号，位移）。系统为每一个进程建立一个页表，其内容包括进程的逻辑页号与物理页号的对应关系、状态等。

页式系统的动态地址转换是这样进行的：当进程运行时，其页表的首地址已在系统的动态地址转换机构中的基本地址寄存器中。执行的指令访问虚存地址（ p， d）时，首先根据页号 p 查页表，由状态可知，这个页是否已经调入内存。若已调入内存，则得到该页的内存位置 p2，然后，与页内相对位移 d 组合，得到物理地址 r。如果该页尚未调入内存，则产生缺页中断，以装入所需的页，如图 1 所示。

页式虚拟存储管理是在页式存储管理的基础上实现虚拟存储器的。首先把作业信息作为副本存放在磁盘上，作业执行时，把作业信息的部分页面装入内存储器，作业执行时若所访问的页面已在内存中，则按页式存储管理方式进行地址转换，得到欲访问的内存绝对地址，若欲访问的页面不在内存中，则产生一个“缺页中断”，由操作系统把当前所需的页面装入内存。

为此，在装入作业时，就应在该作业的页表中指出哪些页已在内存中，哪些页还没有装入内存。可用一个标志位来指示对应页是否在内存中，比如假设标志位为 1 表示该页在内存，而标志位为 0 表示该页尚未装入内存。为了能方便地从磁盘上找到作业信息的副本，故在页表中还可指出每一页副本在磁盘上的位置。

当要装入一个当前需要的页面时，如果内存储器中无空闲块，则可选择一个已在内存中的页面，把它暂时调出内存。若在执行中该页面被修改过，则把该页信息重新写回到磁盘上，否则不必重新写回磁盘。当一页被暂时调出内存后，让出的内存空间用来存放当前需要使用的页面。以后再使用被调出的页面时，可用同样的方法调出另一个页面而将其再装入内存。页面被调出或装入之后都要对页表中的相应表目做修改。

2.2 段式存储管理

段式存储管理与页式存储管理类似。分段的基本思想是把用户作业按逻辑上有完整意义的段来进行划分，并以段为单位作为内外存交换的空间尺度。

一个作业是由若干个具有逻辑意义的段（如主程序、子程序、数据段等）组成。分段系统中，容许程序（作业）占据内存中许多分离的分区。每个分区存储一个程序分段。这样，每个作业需要几对界限地址寄存器来判定访问地址是否越界，实现复杂。在分段存储系统中常常利用存储保护键实现存储保护。分段系统中虚地址是一个有序对（段号，位移）。系统为每个作业建立一个段表，其内容包括段号、段长、内存起始地址和状态等。状态指出这个段是否已调入内存，即内存起始地址指出这个段，状态指出这个段的访问权限。

分段系统的动态地址转换是这样进行的：进程执行时，其段表的首地址已在基本地址寄存器中，执行的指令访问虚存（s， d）（取指令或取操作数）时，首先根据段号 s 查段表，若段已经调入内存，则得到该段的内存起始地址，然后与段内相对地址（段内偏移量 d）相加，得到实际地址。如果该段尚未调入内存，则产生缺段中断，以装入所需要的段。段式存储与页式存储的地址转换方式类似。

段式虚拟存储管理仍然以段式存储管理为基础，为用户提供比内存实际容量大的虚拟空间。段式虚拟存储管理把作业中的各个分段信息都保留在磁盘上，当作业可以投入执行时，做如下操作：

1. 首先把当前需要的一段或几段装入内存。
2. 作业执行时，如果要访问的段已经在内存，则按照“段式存储管理” 中的方式进行地址转换；如果要访问的段不在内存中，则产生一个“缺段中断”，由操作系统把当前需要的段装入内存。

因此，在段表中应增设段是否在内存的标志以及各段在磁盘上的位置，已在内存中的段仍要指出该段在内存中的起始地址和占用内存区长度。

作业执行要访问的段时，由硬件的地址转换模块查段表。若该段在内存中，则立即把逻辑地址转换成绝对地址；若该段不在内存中，则形成“缺段中断”，由操作系统处理这个中断。

处理的办法是，查内存分配表，找出一个足够大的连续区以容纳该分段，如果找不到足够大的连续区则检查空闲区的总和，若空闲区总和能满足该段要求，那么进行适当移动将分散的空闲区集中起来；若空闲区总和不能满足该段要求，可把内存中的一段或几段调出，然后把当前要访问的段装入内存中。段被移动、调出和装入后都要对段表中的相应属性进行修改。新的段被装入后应让作业重新执行被中断的指令，这时就能找到要访问的段，也可以继续执行下去。

2.3 段页式存储管理

段页式管理是段式和页式两种管理方法结合的产物，综合了段式组织与页式组织的特点，根据程序模块分段，段内再分页，内存被分划成定长的页。段页式系统中虚地址形式是（段号、 页号、页内偏移），如图 2 所示。系统为每个进程建立一个段表，为每个段建立一个页表。段页式管理采用段式分配、页式使用的方法，便于动态连接和存储的动态分配。这种存储管理能提高内存空间的利用率。

段式虚拟管理还是以段为单位分配内存空间，整段的调出、装入，有时还要移动，这些都增加了系统的开销。如果按段页式存储管理的方式，把每一段再分成若干页面，那么，每一段不必占用连续的存储空间；甚至当内存块不够时，可只将一段中的部分页面装入内存，这种管理方式称为“段页式虚拟存储管理”。

段页式虚拟存储管理为每一个装入内存的作业建立一张段表，还要为每一段建立页表。段表中指出该段的页表存放位置及长度，页表中应指出该段的各页在磁盘上的位置以及页是否在内存中。若在内存中，则填上占用的内存块号。作业执行时按段号查段表，找到相应的页表再根据页号查页表，由标志位判定该页是否已在内存，若是，则进行地址转换；否则进行页面调度。地址转换过程如图 3 所示。

段页式虚拟存储管理结合了段式和页式的优点，但增加了设置表格（段表、页表）和查表等开销，段页式虚拟存储器一般只在大型计算机系统中使用。

常见的虚存组织比较说明如下：

3 存储管理

在虚拟存储器的管理中，涉及载入 ( 调入 ) 、 放置 ( 放入分区 ) 和置换 ( swapping ) 等管理内容。

1. 调入策略 : 即何时将一页或一段从外存中调入内存，通常有两种策略，一种是请求调入法，即需要使用时才调入；另一种是先行调入法，即将预计要使用的页 / 段先行调入内存。
2. 放置策略 : 也就是调入后，放在内存中的什么位置，这与内存管理基本上是一致的。
3. 置换策略 : 由于实际内存是小于虚存的，因此可能会发生内存已满，但需要使用的页并不在内存中的情况 ( 称为缺页中断 ) 。这时就需要进行置换，即将一些内存中的某些页放到外存中，腾出空间。这一过程称为 swapping 。

当内存中无空闲块时，为了装入一个页面而必须按某种算法从已在内存的页中选择一页，将它暂时调出内存，让出内存空间以存放所需装入的页面，这个工作称为 “页面调度”。

如何选择调出的页面是很重要的，如果采用了一个不合适的算法，就会出现这样的现象：刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久又被装入，如此反复，使调度非常频繁。这种现象称为“抖动”。

一个好的调度算法应减少或避免抖动现象。常用的页面调度算法（置换算法）有：

1. 最优（OPT）算法。选择不再使用或最远的将来才被使用的页，这是理想的算法，但是难以实现。
2. 随机（RAND）算法。随机地选择需要被淘汰的页，开销小，但是可能选中立即就要访问的页。
3. 先进先出（FIFO ）算法。调出在内存驻留时间最长的页，但可能淘汰掉频繁使用的页。该算法简单，易实现。可以把装入内存的那些页的页号按进入的先后顺序排成队列，每次总是调出队首的页，当装入一个新页
   后，把新页的页号排到队尾。
4. 最近最少使用（Least Recently Used， LRU）算法。选择离当前时间最近的一段时间内使用得最少的页。这个算法的主要理论依据是，如果某个页被访问了，则它可能马上就要被访问；反之，如果某个页长时间未被访问，则它在最近一段时间也不会被访问。

另外，使用 FIFO 算法时，在未给予进程分配足够的页面时，有时会出现给予进程的页面数越多，缺页次数反而增加的异常现象，这称为 Belady 现象。例如，若某个进程访问页面的顺序 ( 称页面访问序列 ) 是 1,2,3,4,1,2,5,1,2,3,4,5，当进程拥有3个主存页面时，发生缺页率比拥有4个主存页面时要小。

具体分析如下：

1. 当要访问页面 1 时，发生缺页中断，系统载入页面 4；
2. 接着，当访问页面 2 与 3时，连续发生缺页中断，系统载入页面 2与页面 3；这时，进程所拥有的三个主存页都已占满。
3. 当要访问页面 4 时，应用 FIFO 算法，移除最先进入主存的页面 1，然后载入页面 4。
4. 之后的页面，都以 FIFO 算法为基础，进行类似处理。表 1 中的红色，就表示发生缺页中断时，载入主存的页号。

表 1 使用 FIFO 算法发生的缺页过程，进程拥有 3 个主存页

可以发现，访问 12 个页面时，共发生 9 次缺页中断，缺页率为 9/12=0.75。

如果进程拥有 4 个主存页，那么使用 FIFO 算法发生的缺页过程，分析方法与之前类似：

表 2 使用 FIFO 算法发生的缺页过程，进程拥有 4 个主存页

可以发现，访问 12 个页面时，共发生 10 次缺页中断，缺页率为 10/12=0.833。

也就是说，在这个示例中，给予进程的主存页面数越多，缺页中断次数反而会增加的异常现象。

Belady 现象的原因是 FIFO 算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的，因而 FIFO 并不是一个好的置换算法。

4 局部性原理

存储管理策略的基础是局部性原理，即进程往往会不均匀地高度局部化地访问内存。局部性分为时间局部性和空间局部性。

1. 时间局部性是指最近访问存储位置，很可能不久的将来还要访问 ；
2. 空间局部性是指存储访问有成组的倾向；当访问了某个位置后，很可能也要访问其附近的位置。

根据局部性原理的特征性， Denning 阐述了程序性能的工作集理论。工作集是进程频繁访问的页面的集合。工作集理论指出，为使进程有效地运行，它的页面工作集应驻留内存中。否则，由于进程频繁地从外存请求页面，而出现称为 “ 颠簸 ” ( 抖动 ) 的过度的页面调度活动。此时，处理页面调度的时间超过了程序的执行时间。显然，此时 CPU 的有效利用率会急速下降。

通常用两种等价的方法确定进程的工作集，一种是将工作集确定为在定长的页面访问序列 ( 工作集窗口 ) 中的页面集合；另一种是将工作集确定为在定长时间间隔中涉及页面的集合。

工作集的大小依赖于工作集窗口的大小，在进程执行时，工作集会发生变化。有时，当进程进入另一个完全不同的执行阶段时，工作集会出现显著的变化。不过在一个进程的执行过程中，工作集的大小处于稳定状态的时间基本上占绝大多数。

另一种控制抖动的技术是控制缺页率。操作系统规定缺页率的上下限，当一个进程的缺页率高于上限时，表明该进程需要更大的内存空间，则分配较多的内存页面给它，当进程的缺页率低于下限时，表明该进程占用的内存空间过大，可以适当地收回若干内存页面。

作者：deniro
链接：https://www.jianshu.com/p/5ea912e407dd
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。