操作系统4-存储管理

本文介绍操作系统另一个重要功能：存储管理。包括存储管理的基本功能，以及分区、页式、段式与段页式三种存储管理方法的具体细节。

首先记住，用户程序生成的每个地址都是虚拟地址，只有进程执行时，才会把这些虚拟地址转换为真实的物理地址。

1. 存储管理的功能

指的是进行存储管理时涉及的一些技术和必须完成的工作，包括虚存、地址变换技术、内外存数据传输的控制、内存的分配与回收、内存信息的共享与保护五部分。

1.1 虚存

计算机中的存储器可以分为几个层次：外存—>内存—>高速缓存—>寄存器。这个顺序是容量由大到小，但访问速度由快到慢的。划分为多个层次的原因是计算机的各部分，从 CPU 到外设，处理的速度是不同的，使用这种分层结构可以使各部分处于均衡的繁忙状态。

进程在执行时访问的是内存中的指令与数据，但由于内存的容量较小，一些进程的内存需求甚至可能超过内存的实际容量，即使是可容纳的进程，计算机也难以支撑多个并发进程的同时执行。解决办法是将一些不常访问的数据和程序段存放在外存中，需要时再调入内存。这种情况下，需要统一管理内外存进程所需的程序和数据，使用内存实际物理地址的方法变得不再可行，因此操作系统使用了一种名为虚拟内存的技术。

虚拟内存，也叫做虚拟存储器，可以简称为虚存。其原理是使用一个一维或多维的虚拟地址空间存放进程所需的所有资源的方法，不论指令和数据是位于内存还是外存，它们在虚拟地址空间中都有一个确定的地址，称为虚拟地址。虚拟地址与实际物理地址有一个确定的变换关系，进程运行时，可以主动将虚拟地址变换为实际物理地址，然后对指令和数据进行操作。

每个进程都拥有这样一个虚拟地址空间，这个虚拟地址空间就叫做虚存（进程管理中我们也将其称作进程空间）。虚存不考虑内存大小，因为使用虚存技术时进程所需容量理论上只受内外存容量之和限制；虚存也不考虑信息的实际存储位置，只关注每个进程相关的指令和数据的相对位置。

虚存的实际大小仅与处理器的位数有关，以 x86 体系 32位 Linux 为例，其虚存为 $2^{32} = 4G$。

实际上，虚存在使用时会划分为不同的区域，分布存放程序、数据、堆栈、控制信息等，以上面提到的 32位 Linux 的 4G 虚存为例，空间划分的方式如下：

首先，整体将虚存划分位了内核空间和用户空间两部分，这是由于某些指令比较危险，错用会导致系统崩溃，某些数据也需要限制访问权限，因此不同的进程限制在不同的空间进行，而且，当进程运行在内核空间时就称其处于内核态，当进程运行在用户空间时则处于用户态。上图中，内核空间是高地址的 1G 字节（从虚拟地址 0xC0000000 到 0xFFFFFFFF），用户空间是较低的 3G 字节。

注意，低地址的 3G 字节用户空间每个进程是独立的，而高地址的 1G 字节内核空间是所有进程共享的。

用户空间的不同部分说明如下

1. .text段（代码段）存放程序运行时产生的指令和只读数据（read only data）
2. .data存放了初始化了的且初始化的值不为0的数据
3. .bss存放未初始化及初始化为0的数据
4. 堆由编程语言分配，由低地址向高地址增长
5. 栈由操作系统分配，由高地址向低地址增长

1.2 地址变换技术

采用虚存后面临的一个重要问题就是进行虚拟地址和物理地址的变换。

我们把内存的每一个存储单元用一个编号标识，这一编号就是物理地址，也叫做内存地址。内存地址的集合就叫做内存空间，或者叫做物理地址空间。

虚拟地址向物理地址的变换就叫做地址重定位，主要分为静态地址重定位和动态地址重定位两种。

静态地址重定位指的是在程序执行前由装配程序完成地址映射，不需要硬件支持，但程序一旦装入内存就不能再移动，并且必须在程序执行前全部装入，这种方法无法实现虚存。

动态地址重定位指的是在程序执行过程中，在 CPU 访问时完成地址映射。该工作需要硬件的支持，主要是基地址寄存器 BR 和程序虚拟地址寄存器 VR，BR 存放程序或数据在内存的首地址，VR 由虚存得到的相对地址，因此，实际的物理地址与它们的关系为 $MA = BR + VR$。只需要使用多个 BR 存储不同区域的首地址，就可以实现对内存进行非连续的分配。动态地址重定位可以实现虚存。

1.3 内外存数据传输

实现虚存时，需要经常进行内外存之间的数据交换，比如将即将执行的程序和数据段调入内存，将处于等待状态的程序和数据段调出内存。

控制这种数据交换的方法有两种，用户程序自己控制和操作系统控制。

用户程序自己控制使用的技术叫覆盖。覆盖技术将程序划分为若干个功能相对独立的程序段，然后让那些不会同时执行的程序段共享同一块内存区域，假如程序段 A 正在运行，和它共享内存的程序段 B 开始调度时， A 一定已经执行完毕，那么 B 就可以调度到 A 原本占用的内存区域。这一，用户看起来，就好像内存扩大了。

操作系统控制又可以进一步分为两种方式：交换、请求调入和预调入。

• 交换技术考虑到内存中的进程可能处于执行、就绪或等待状态，处于等待状态的进程驻留内存会造成存储空间的浪费，因此由操作系统将处于等待状态的进程换出内存，而将那些等待事件已经发生、处于就绪态的进程换入内存。
• 请求调入是在程序执行时，如果所要求访问的程序段或数据段不在内存中，由操作系统自动从外存调入的方式；预调入是由操作系统预测在不远的将来会访问到的程序段和数据段，并在它们被访问前寻找合适的时机调入内存的方式。

请求调入和预调入是唯一可以实现虚存的控制方法。

1.4 内存分配与回收

内存分配与回收是内存管理的主要功能之一，为了将外存中的程序和数据调入内存，需要事先为它们分配内存空间，进程执行结束时，还要及时地回收进程所占用的内存空间。

内存分配与回收算法的涉及要考虑如下的事情：

1. 分配结构：登记内存使用情况，提供分配程序使用的数据结构
2. 放置策略：确定调入内存的程序和数据在内存中的位置
3. 交换策略：在需要将某个程序段和数据调入内存时，若内存无足够空间，使用交换策略
4. 调入策略：决定外存中程序段和数据段调入的时间和控制方式
5. 回收策略：回收的时机和空闲区的调整

1.5 内存信息保护

进程执行时要保护系统程序区不被用户侵犯（有意或无意的），也不应该允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间），这就是内存信息的保护。

常用的内存信息保护方法有三种：硬件法、软件法和软硬结合法。

• 硬件法指的是使用寄存器保持程序段或数据段的起始和终止地址，进程访问前进行合法性检查
• 软件法指的是为每个存储区域设置一个标志位，不同的标志代表不同的读写权限的方法
• 软硬结合指用户态进程只能访问寄存器限制的内存，而核心态进程可以访问整个内存空间

1.6 存储管理方法

介绍分区、页式、段式与段页式三种存储管理方法，每种包括虚存的划分方式、页面置换算法、内存分配与回收算法等内容。不过，由于分区管理存在很多缺点，而且不被当前系统普遍使用，下面不进行介绍，仅在最后总结时放入表中。

2. 页式管理

2.1 基本原理

页式管理的基本原理是将虚存划分为若干长度相等的页（page），页长与内外存数据传输的速度和内存大小有关，一般约 1K~4K。经过页划分后，进程的虚拟地址就变成了页号 P 和页内地址 W 的组合，地址的高位部分是页号，低位部分是页内地址。

此外，页式管理还把内存空间也按页的大小划分为片或页面（page frame），操作系统为进程分配内存时，是以页面为单位的，页面内的地址连续，但不同的页面间不一定连续。

2.2 地址变换

地址的转换和内存页面的分配使用页表、请求表和存储页面表三种表完成。

页表存放页号和与之对应的页面号，每个进程都有一个页表，对于一个大小为 20K，页长为 1K 的进程而言，只需要存放二十个页表项即可。页表在内存中有一块固定的存储区。

请求表描述系统内各进程的页表起始地址和长度，用来进行内存分配和地址转换。整个系统只需要一张请求表。页表和请求表的一个示例如下

存储页面表也是整个系统一张，它指出内存各页面是否已被分配出去，以及未分配页面的总数。它有两种表示方法

1. 位示图法：在内存划分一块固定的区域，每个单元的比特代表一个页面，页面已分配则对应比特位置1，否则置0；
2. 空闲页面链：队首页面第一个单元和第二个单元分别放入空闲页面总数和指向下一个空闲页面的指针，其它页面的第一个单元放入指向下一个页面的指针。

根据页号和页内相对地址变换得到内存物理地址的方法如下。

以一个例子来说明，设一个3页长的进程具有页号0、1、2，但其对应的页面号为2、3、8。设每个页面长度为1K，指令 LOAD 1，2500 的虚地址为100，地址转换过程为：

1. 系统将所调度进程的页表始址和页表长度从请求表取出放入控制寄存器；
2. 根据控制寄存器中的页表始址找到页表所在的位置，并由虚地址 100 得知指令在第 0 页的第 100 单元；
3. 查页表得知第 0 页与 第 2 个页面对应，因此该指令在内存中的地址为 2048 + 100 = 2148；
4. 当执行到第 2148 单元的指令，也就是 LOAD 1，2500，需要从有效地址 2500 中取数据放入 1 号寄存器。地址变换机构可以将 2500 转换为页号 2 和页内相对地址 452；
5. 查页表得知第 2 页和第 8 个页面对应，因此数据在内存中的地址为 1024*8+452 = 8644.

整个变换的过程可以总结如下图

上述地址变换过程全部由硬件地址变换机构自动完成。另外，由于页表位于内存的某个固定区域，而取数据或指令又必须经过查询页表才能得到物理地址，因此取一个数据或指令至少要访问内存两次以上。

2.3 页面置换算法

动态的页面管理使用前面提到的请求调入和预调入的办法，当硬件变换机构发现所要求的页不在内存时，产生缺页中断信号，有中断处理程序做出相应的处理。而如果内存没有空闲的页面还需要选择一定的置换算法淘汰已占据内存的页面。页面置换算法的选择直接影响内存利用率和系统效率。

页面置换算法的实质是将访问概率低的页面移出内存，常用算法有

• 随机淘汰算法：无法确定哪些页面访问概率较低，则随机选择一个页面淘汰；
• 轮转法：循环换出内存可用区内一个可以被换出的页，无论该页是刚被换进或已换进内存很长时间；
• 先入先出：总是选择在内存驻留时间最长的一页将其淘汰；
• 最近最久未使用：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的出发点是：如果某页被访问了，那么它可能马上还要被访问；
• 最不经常使用：最近最久未使用算法实现比较困难，因为要维护每个页面的访问记录，最不经常使用是一种简化，思路是淘汰到当前为止被访问次数最少的那一个，只需要在页表为每一页增加一个访问计数器即可；
• 最近没有使用：也是最近最久未使用的简化，思路是从最近一个时期内未被访问的页中随机选择一页淘汰，只需要在页表中增加一个访问标志即可。
• 理想算法：最理想的算法是淘汰再也不会出现或在离当前最远位置上的页，但这种无法实现。

2.4 存储保护

页式管理可以为内存提供两种方式的保护。

地址越界保护可由地址变换机构中的控制寄存器的值—页表长度和所要访问的虚地址进行比较完成；

存取控制保护通过在页表中增加相应的保护位完成。

3. 段式管理

分区式和页式的虚存结构都是一维线性的，对程序或数据段的共享不友好，程序链接时 CPU 和 存储空间的开销也比较大，因此提出了段式管理。

3.1 基本原理

段式管理的基本思路是：将程序的地址空间按内容或函数关系划分为若干个段(segment) ，每段有自己的名字。段与段之间没有顺序关系，也不要求连续，每一段的长度都是不固定的。

常见的逻辑段有四种，如下表

程序的指令代码必须存放在代码段，否则将无法正常执行。程序利用代码段寄存器 CS获得当前代码段的段基地址，指令指针寄存器IP保存代码段中指令的偏移地址。处理器利用CS:IP取得下一条要执行的指令。

程序使用的堆栈（临时存放数据的区域）一定在堆栈段。程序利用SS获得当前堆栈段的段基地址，堆栈指针寄存器SP保存堆栈栈顶的偏移地址。处理器利用SS:SP操作堆栈数据。

一个程序可以使用多个数据段，便于安全有效地访问不同类型的数据。例如，程序的主要数据存放在一个数据段，只读的数据存放在另一个数据段，动态分配的数据安排在第3个数据段。

下面是一个简单的图示

每个段是一个首地址为零的，连续的一维线性空间，根据需要，段长可动态增长。对段式虚地址空间访问包括两个部分：段名（段号）和段内地址。

3.2 地址变换

段式管理进行地址变换时，需要将段号和段内地址变换为实际物理地址，一般使用一种名为段表的数据结构。

一个考虑了缺段处理和段式访问控制的段表包括：段号、始址（段基址）、长度、存取方式、内外和访问位。其中段号与用户指定的段名对应，段基址是该段在内存的起始地址，长度是该段在外存的实际长度，存取方式用来进行存取保护，内外指该段出现在内存还是外存，访问位用于最近没有使用置换算法。

根据上图，过程可以描述如下

1. 在内存分配一段固定的区域存放段表；
2. 进程开始执行时，管理程序首先将该进程的段表始址放入段表地址寄存器，通过访问该寄存器开始访问段表；
3. 由虚地址中的段号 1 查段表，得知该段在内存，然后判断存取控制方式是否匹配；
4. 从段表中查到段基址位 3400，然后和段内地址 120 相加，得到实际内存地址 3520；

如果该段不在内存，就会产生缺段中断，将 CPU 交给内存分配程序。内存分配程序检查空闲区链，确定是否有足够长的空闲区来装入所需的段，如果不够，检查段表中的访问位，利用最近没有使用置换算法淘汰访问概率低的段，然后将需要的段调入。

和页式管理一样，由于段表的存在，也需要两次以上内存访问。

3.3 段的共享与保护

段式管理可以方便的实现内存信息的共享与保护，因为段是按逻辑意义划分的，可以根据段名访问。

很多程序段和数据是被多个进程共享的，如果每个进程都保留它们的一个副本，就会造成极大的浪费，最好的办法就是只保留一个副本，供多个进程使用。这种共享在段式管理中可以很容易的使用相同的段名实现，在段表中填入已存在内存中的段的起始地址，并赋给适当的读写控制权，就可以共享该段的内容，而不是创建一个新的副本。注意，段式管理中有一部分段是共享的。

但是，共享段会面临进程同时执行该段的情况和置换到外存的需求，这两种情况通过设置相应的共享位实现。

段式管理对内存的保护和页式相同，也是使用地址越界保护法和存取方式控制保护法。

4. 段页式

段页式是将页式和段式管理相结合，充分利用它们的优点，不过，系统开销也更大。

4.1 基本原理

段页式使用和段式相同的分段方式，但是，对每个段内的程序和数据按一定的大小划分成页。因此，段页式管理进程的虚地址由三部分组成：段号 s、页号 p 和页内相对地址 d。

段页式中，程序员可见的只有段号 s 和段内相对地址 w，p 和 d 是地址变换结构把 w 的高几位解释成页号 p，把剩下的低位解释成页内地址 d 而得到的。

由于虚存的最小单位是页而不是段，因此，内存的划分是以页为单位的。

4.2 地址变换

段页式同时使用段表和页表，不过，页表不再归属某个进程，而是属于某个段。地址变换时，首先根据段表地址寄存器得到段表始址去访问段表，取出相应段的页表地址；然后访问页表得到所要访问的物理地址，最后才能访问真正的物理单元。因此，段页式存取内存中的指令和数据需要访问3次以上内存。

5. 局部性原理和抖动

程序的局部性原理：在一定时间内，进程集中在一组子程序或循环中执行，导致所有的存储器访问局限于进程地址空间的一个固定子集

• 时间局部性：一条指令的一次执行和下次执行以及一个数据的一次访问和下次访问都集中在一个较短的时间内
• 空间局部性：在一段时间内，程序和数据的访问都集中在一个较小区域内

抖动：置换算法选择不当，刚被调出内存的段或页马上又被调入内存，调入内存不久又被调出，如此反复。这使得整个系统的调度非常频繁，以致大部分时间都花费在内外存之间的来回调入调出上，这种现象被称为抖动。

6. 总结