操作系统之 内存

内存的基础知识

内存相当于硬盘和CPU之间的中间件。CPU只能处理内存当中的数据，而程序运行需要将数据从硬盘移动到内存。

内存地址

CPU访问数据是通过内存地址来找到数据的。每个地址代表着一个存储单元。我们只需要知道，通过地址，能够访问内存中特定的位置即可。

内存地址的编址方式有以下两种：

• 按字节编址：每个地址代表了一字节的数据。即8bit。

• 按字编址：字长为16的计算机编址，每个地址有16位，即2字节，其余同理。

指令

我们编写的代码，在经过编译器编译后，将转换成机器能读懂的指令。在这个指令中，可能需要我们操作内存中的数据。那么就需要我们在指令中添加某个数据的内存地址。

编译后的指令是不变的，但在不同时间不同机器上运行，地址是会变的。一味的执行指令中的地址是不可取的。因此这里引出两个概念：

• 逻辑地址是程序在运行时生成的地址，也称为虚拟地址。它是由程序员编写的代码或编译器生成的地址，表示程序中变量和数据的相对位置。

• 物理地址是实际的内存地址，指向计算机硬件中的内存单元。它是内存芯片上物理存储位置的真实地址。

在现代计算机系统中，逻辑地址和物理地址之间的转换通常通过内存管理单元（MMU）完成。MMU使用页表或段表等数据结构来管理逻辑地址与物理地址之间的映射。

因此，我们执行程序时，操作系统会将编译好的逻辑地址映射到物理地址，完成了数据的读取和修改。

装入、地址转换

在程序执行时，需要将程序放入内存中进行执行。这时候会发生地址的转换，下面三种装入方式对应的转换规则不尽相同：

绝对装入

编译时程序知道这个程序将会放到内存的某个位置，那么编译程序直接生成绝对地址的目标指令。装入后执行指令，不需要进行地址转换，就可以直接使用。

用于单道程序阶段，没有操作系统（地址从0开始）。整个内存只能放一个程序。

可重定位装入

编译后指令使用的地址都是相对地址（相对于起始地址而言），程序装入时，需要将逻辑地址转换为物理地址，但是这次转换只需要一次，即装入时进行转换即可。

程序在内存中的位置在之后不能发生变化。

用于早期多到批处理阶段。

动态运行时装入

编译后指令使用的是相对地址，装入时不会立即把逻辑地址转换成物理地址。只有执行这条指令时才会转换成物理地址。

这种方式的转换需要重定位寄存器的支持。程序在内存中的位置可以发生变化，只需要更新重定位寄存器即可。

现代操作系统使用的装入方式。

链接

链接是编译过程中的一个概念。我们的程序引入了一个模块，如何把这个模块集成在程序之中？可以是把整个模块拷贝一份到程序中？还是不拷贝，在装入时寻找这个模块一起放到内存中？还是使用时才链接？这就引出了三种链接方式：

静态链接

程序运行之前，把目标模块和所需的库函数连接成一个完整的可执行文件，之后不再拆开。

装入时动态链接

又称动态链接，是在程序运行时加载所需的库，而不是在编译时将其包含在可执行文件中。

运行时动态链接

在程序执行过程中需要该目标模块才进行链接，其优点是便于修改和更新，便于实现对目标模块的共享。

内存保护

假设在内存中，某个进程的寻址范围是100-289；如何确保该进程不会访问到寻址范围之外的地址？内存保护可以采取两种方法：

• 设置一对上下限寄存器，例如本例中，上下限寄存器应该被设置为100和289。如果访问到了上下限之外的地址，CPU应该引发中断。

• 设置重定位寄存器和界地址寄存器（又称基址寄存器和限长寄存器），重定位寄存器存放进程的起始物理地址，界地址寄存器存放进程的最大逻辑地址。例如本例中，两个寄存器应该被设置为100和189。

内存空间扩充

分析下面一个情景：某程序需要10GB的内存空间，而我们的物理内存只有8GB。那么怎样操作我们才能运行这个程序呢？想一想现实生活中，假如我们要运行一个100GB的游戏，物理内存只有16GB的电脑也可以正常运行。这其中必然是用到了某种方式将内存空间进行了扩充。

覆盖

早期操作系统，引入了名为覆盖的技术。覆盖技术的核心思想就是将程序分为多个段，常用的段常驻内存，不常用的段在需要时调入内存。内存则分为一个固定区和若干个覆盖区。

如上图，程序被分成了多个段，只有执行到某个段时，内存对应覆盖区存入该段的相应数据。

覆盖结构必须由程序员显性的进行分配，再有操作系统完成自动覆盖。这增加了用户的编程负担，现在已经不再使用。

交换

交换技术和核心思想就是当内存空间紧张时，系统将内存中的某些进程暂时放到外存中。将外存中符合运行条件的进程换入内存。

在上一章介绍调度时，中级调度就是做这样工作的。被放在外存的进程称为挂起进程。

挂起进程的PCB还是在内存中的。

所有的挂起进程都被放到了硬盘中的对换区。对换区采用连续的分配方式，其换入和换出速度更快。这部分内容会在文件管理章节详细阐述。

交换常发生在许多进程执行且内存吃紧的状态下。如果系统负荷降低就可以换入一些进程。

换出进程可以选择阻塞进程、优先级较低的进程。为了换入后快速被换出，系统还会考虑进程在内存中的驻留时间。

虚拟内存

虚拟内存是一种内存管理技术，它允许计算机使用硬盘空间来扩展可用的内存容量，使得程序可以使用比实际物理内存更大的地址空间。

传统存储的问题

• 一次性：在传统的存储管理方式中，作业会被一次性装入内存之后才能运行。如果作业很大，可能无法装入内存。如果大量作业并发运行，内存可能无法满足所有作业。

• 主流行：内存装入作业后，进程会一直留在内存，直到作业结束。即使某一时间段只需要访问很小的一个数据就能运行，但大量无用数据还是留在了内存中。

局部性原理

• 时间局部性：如果程序执行了某条指令，那么这条指令很有可能再次执行。如果访问了某个数据，那么该数据很可能在不久之后再次被访问。

• 空间局部性，程序访问了某存储单元，不久之后其附近的存储单元也有可能被访问到。

基于局部性原理，在程序装入时，先将很快能用到的部分装入内存，其余部分暂时留在外存。程序执行过程中访问的数据不在内存中，则再从外存调入内存。若内存空间不够，操作系统将内存中暂时用不到的信息换出外存。

通过这样的管理，在用户层面好像实际的内存比物理内存要打，这就是虚拟内存。

虚拟内存的三个特征

• 多次性：作业运行无需一次性全部装入内存，可以多次装入内存。

• 对换性：作业运行无需一直常驻内存，允许在作业运行过程中，将作业换入和换出。

• 虚拟性：错逻辑上扩充了内存的容量，使用户看的到的内存容量远大于实际的容量。

虚拟内存的分配基于离散分配，如下文中的分页、分段和段页式管理。

内存的分配和回收

内存的分配分为连续分配管理方式和非连续管理方式。所谓连续分配指为用户进程分配的必须是一个连续的内存空间。

连续分配管理

连续分配管理分为三种：单一连续分配、固定分区分配和动态分区分配。

单一连续分配

在单一连续分配方式中，内存分为系统区和用户区。系统区位于内存的低地址部分，用户存放操作系统相关数据。用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。

• 优点：实现简单，无外部碎片。

• 缺点：只能用于单用户，单任务操作系统，有内部碎片，存储器利用率极低。

内部碎片是指分配给进程的内存块中，实际使用的内存与分配的内存之间的差额。换句话说，当分配的内存块大于实际需要的内存时，未使用的部分就会形成内部碎片。

外部碎片是指在内存中存在多个小的未分配内存块，这些块虽然总和足够满足新的内存请求，但由于它们不连续，无法被有效利用。

固定分区分配

为了支持多道程序，将用户空间划分为固定大小的分区，每个分区只装入一道作业。

动态分区分配

动态分区分配又称为可变分区分配。进程在装入内存中时，根据进程的大小动态的建立分区。

实现动态分配，可以使用空闲分区表和空闲分区连来记录内存中所有空闲的内存信息。以下是一个示例空闲分区表：

空闲分区链是一个双向链表，其数据部分可以记录分区大小信息。动态分配有四种算法：首次适应算法、最佳适应算法、最坏适应算法和邻近适应算法。

当发生装入时，需要对内存进行分配，分配后需要更新空闲分区表。释放也同理。

• 优点：没有内部碎片

• 缺点：有外部碎片

处理外部碎片可以使用紧凑技术，将不同的进程在内存中移动，将其紧密排列，从而减少外部碎片。

基本分页存储管理

页框、页面、页表

我们将内存大小分成一个个大小相等的块，将其命名为页框（也称页帧、内存块、物理块等）。每个页框有一个编号，称作为页框号。页框号从0开始。

然后，我们将要装入的进程分成一个个同样大小的块，将其命名为页。每个页也有一个编号，称作页号。页号也是从0开始。

这时候我们将进程装入内存，就可以将一个一个页面装入页框之中。这些页面不必连续存储，我们用一个简单的数据结构就可以记录页号和页框号的对应关系了。

记录页号和页框号的数据结构称作页表。页表的数据结构可以看作下表。

假设一个物理内存大小为4GB，页面大小为4KB，页表项应该为多少字节？

我们可以计算块号的最大值：4GB/4KB = 2^(20)个，至少需要20位来保存页表项，至少应该3字节。实际上，根据操作系统架构的不同，页表项的大小也不同。

地址转换

现在我们知道了逻辑地址A，如何定位物理地址呢？想要访问到物理地址，分为以下三个步骤：

1. 找到A对应的页号；

2. 找到页号对应页面的物理起始地址；

3. 确定A的页内偏移量，将物理起始地址加上页内偏移量得到物理地址。

页号的计算如下：逻辑地址/页面长度向下取整；页内偏移量计算如下：逻辑地址和页面长度取余。这样就完成了逻辑地址和物理地址的转换。

页面大小为50B，逻辑地址为110。页号为：110/50 = 2，页内偏移量为110%50=10。通过查询页表，得到页框号，页框号*页面大小为页面的起始物理地址，加上页内偏移量就得到了物理地址。

在计算机中，所有的无符号整数可以由二进制串表示，假设页面大小为2^12B，某逻辑地址为：

00000000000000000001000000100100

计算机通过移动操作很容易计算出页内偏移量和页号，上面加粗的部分就是页内偏移量，不加粗的部分就是页号。通过页号得出页框号，也是相同大小的二进制串，将这个二进制串和页内偏移量拼接就是物理地址。假设上面页号对应的页框号对应的物理起始地址为：

00000011110000100001

将页内偏移量拼接上去得到物理地址：

00000011110000100001000000100100

通过二进制串我们也能得出一些隐含的信息。比如说页面大小：页内偏移量数字个数为K，则一个页面的大小为2^K个内存单元。页面数：页号的数字个数为P，进程被允许的最大页面数为2^P个内存单元。

快表 TLB

快表又称为联想寄存器，是比内存访问快得多的高速缓存。可以用来存放一定量页表项的副本。内存中的页表称作慢表。

为什么会出现快表这个东西呢？假设我们想要访问内存的某个数据，需要查询慢表，得到起始物理地址，然后再次访问该数据。这个过程访问了两次内存。有了快表，我们查询物理起始地址就可以避免访问内存，只需一次访问高速缓存和一次内存。加快了运行速度。

然而，访问速度快的代价时其容量非常小。因此快表只能存储页表的一部分数据，如果命中了，数据访问就会很快，如果没有命中，则还需再次查询慢表，并且将页表项复制到快表中。如果下次还查询该页则会很快。

复制页表项可能会导致覆盖原来快表中的页表项。所以我们需要一种算法，决定应该覆盖哪一个页表项，从而提升我们的命中率。

假设查询一次内存为100us，查询快表1us，命中率为90%，则访问一个地址的平均耗时为：(1 + 100)\times0.9+(1+100+100)\times0.1=111\mu s 。假设同时进行查询，则为(1 + 100)\times0.9+(100+100)\times0.1=110.9\mu s

两级页表

假设一个物理内存大小为4GB，页面大小为4KB，页表项应该为3字节。假设我有2^11个页面需要存放在页表中，页表的大小为6KB。这个页表大小超出了页面的大小，我们应该保证页表的大小小于页面的大小。

上面这种情况意味着我们需要将页表再分成两个块，存放在不同的页框中。假设我们还想正常进行上面所讲的地址转换，则会引申出两个问题：

1. 存放页表的页框应该是连续的。

2. 整个页表需要常驻内存，即使进程在一段时间内只访问了几个特定的页面。

解决这两个问题的方法也很简单：给页表上在嵌套一个页表。不过这个嵌套的页表不叫作页表了，我们称作页目录表或是外层页表、顶层页表。

在地址的二进制串中，结构就很清晰了：

0000000000 0000000001 000000100100

从左往右，分别为页目录表号、页表号偏移量、页内偏移量。页目录表和页表只能存放2^10=1024个项，我们先通过页目录表号查到某一块页表的起始物理地址，加上页表号偏移量得出页号的物理起始地址，再加上页内偏移量得到物理地址。

二级页表会导致3次访存，降低了运行效率。

假设逻辑地址的位数更长，我们就再嵌套一个表，直到表项总和不能超过一个页面的大小。

基本分段存储

在之前我们在覆盖那一部分提到了段。段还可以应用在非连续的存储管理方式中。一个进程被拆分出几个段，将不同的段放在内存之中。这种方式类似于连续分配方式的动态分配。但是动态分配内存分配的是整个进程，而这里分配的是段。

分段分配也需要一个数据结构保存每个段的地址信息。和分页类似，该数据结构存储了段名、段长和基址信息。段名在编译时会被生成为无重复的整数，作为索引。该数据结构称作段表，段表的结构类似于下表：

将逻辑地址转换为物理地址的阶段中，我们不能单单只提供逻辑地址了。需要提供段号和段内地址两个信息。通过查表，基址和段内地址相加，就能找到对应的物理地址。

分段和分页各具优劣：

• 页是信息的的物理单位，其目的是为了实现离散分配，提高内存利用率。分页是系统行为，对用户不可见。用户无法决定怎么分页。

  • 内存空间利用率高，不会产生外部碎片，会产生少量的内部碎片；

  • 不方便按照逻辑实现信息保护。

• 段是信息的逻辑单位，目的是更好的满足用户的需求。分段对用户是可见的，用户编程时需要显式的给出段名。

  • 分段和分页更容易实现信息的共享和保护；

  • 如果段长过大，分配连续的内存空间会很不方便，段式管理会产生外部碎片。

分段和分页都需要两次访存。

段页式管理方式

段页式将分段和分页结合了起来，先对某进程分段，然后再对段进行分页。将不同的页分散到内存的页框中。

段页式的逻辑地址结构分为短号、页号和页内地址（偏移量）组成。

在地址转换过程中，需要同时维护段表和页表两个数据结构：段表由段号、页表长度和页表存放块号组成。用户给出段号和段内地址，先计算出对应的页号，查页表，再查询出内存起始地址，加上段内地址，就能得出的对应的物理地址。

请求分页管理模式

基本分页方式要求所有的信息都存放在内存之中。如果说我们想要实现虚拟内存的外存调入内存的功能，或是将用不到的信息调出外存的功能，基本分页管理模式需要改进。

我们需要对页表进行改造，每个页表项需要增加以下信息：

• 状态位：这个页面是否已经装入内存。

• 访问字段：记录最近被访问了几次，或是记录上次访问的时间，供置换算法选择换出页面时参考。

• 修改位：页面调入内存后是否被修改过。

• 外存地址：该页面存放在外存的地址。

一个示例页表如下：

访问数据的步骤如下：

1. 首先确定逻辑地址，比如说我们想要获取页号、页内偏移量为(0, 1024)的数据；

2. 通过状态位判断该数据是否在内存中，如果在内存中，则直接根据地址访问；

3. 如果该数据不在内存中（缺页中断），通过外存地址找到数据在外存的存放位置，准备放入内存。

4. 如果内存中有空闲块（页框），则放入空闲块中，如果没有，则通过页面置换算法选择一个页框进行覆盖。

5. 覆盖时通过修改位判断该数据是否被修改，如果被修改，则将新数据还要写回外存中。

请求分页管理方式也可以使用快表来提高性能。需要注意的是：当慢表中某一页被换出了外存，那么快表中相应的那一页也应该被删除。页面调入内存，需要将页表项复制到快表当中。

页面置换算法

前面我们提到了什么时候需要用到页面置换算法：当内存块满时，需要再次放入新的页面时，需要覆盖某个页面。如何决定覆盖某个页面就是本节的重点。页面置换算法的指标是追求最小的缺页率。

最佳置换算法 OPT

最佳置换算法的思想是向后查找。当要覆盖时，往后查看寻找到在内存中最远要使用的页面进行覆盖。这样就能保证最低的缺页率。

假设某进程分配了三个内存块，依次访问以下页面：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。请问缺页率是多少？每次访问在内存块中的页面编号分别是什么？

在第四次选择要被覆盖的页面时，我们需要查看7、0、1这三个页面在之后谁才是最远被访问到的页面。发现7是最远的页面，因此就把7替换掉，以下以此类推。

最终得出缺页率为45%。

但是，在实际应用中，我们无法确定具体的访问序列是什么，我们知道的只有之前访问了哪些页面。因此OPT算法是无法实现的。

先进先出置换算法 FIFO

先进先出置换算法每次淘汰的页面是最早进入内存的页面。

假设系统为某进程分配了三个内存块，页面的访问顺序为3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4。

这种置换方式最为简单，实现起来较为容易。假设我们把上个例子改成4个内存块，那么表格更新为：

内存块更多了，但是缺页次数相比于三个内存块却增加了。这称为Belady异常。

Belady异常（Belady's Anomaly）是指在某些页面置换算法（例如FIFO，即先进先出算法）中，增加内存块的数量反而导致缺页率上升的现象。这一现象与直觉相反，因为通常我们认为增加内存块的数量应该减少缺页率。

这种算法的性能很差，一般不使用。

最近最久未使用置换算法 LRU

LRU算法每次淘汰的页面都是最近最久未使用的页面。比如说我们可以查询页表当中的访问字段t，表示自上次被访问所经历的时间。选择t最大的进行淘汰。

假设系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1, 8, 1, 7, 8, 2, 7, 2, 1, 8, 3, 8, 2, 1, 3, 1, 7, 1, 3, 7

每次需要替换时，你想查找谁是最早被访问的内存块，然后进行替换即可。

这种算法性能好，但是要求专门的硬件支持，开销也比较大。

时钟置换算法 CLOCK

时钟置换算法又称为最近未用算法（NRU），通过维护页表中一个访问位来判断是否覆盖页表项。

CLOCK算法的思想如下：将内存中的页面通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1.当要淘汰一个页面时，检查页中的访问位，如果是0则换出该页。如果是1，则将其置为0，检查下一个页面。若第一轮扫描所有都是1，那么再进行第二轮扫描，一定会有访问位为0的页面。

改进型的时钟置换算法

改进型的时钟置换算法引入了是否修改来决定是否覆盖。为了方便讨论用（访问位、修改位）的形式表示各页面状态。规则如下：

1. 从当前状态开始扫描第一个（0，0）的帧用于替换。本轮扫描不修改标志位。

2. 若第一轮扫描失败，则重新扫描。查找第一个（0，1）的帧用于替换。本轮扫描将所有的被访问位设为0。

3. 若第二轮扫描失败，则重新扫描。查找第一个（0，0）的帧用于替换。本轮扫描不修改标志位。

4. 若第三轮扫描失败，则重新扫描。查找第一个（0，1）的帧用于替换。

对比

页面分配策略

驻留集

驻留集指请求分页存储管理中给进程分配物理块的集合。例如驻留集的大小为4，那么该进程同一时刻只能存储4个页面在内存中。

• 驻留集太小，会导致频繁缺页，操作系统需要花费大量的时间来处理缺页。

• 驻留集太大，多道程序的并发度下降，资源利用率降低。

分配策略

• 固定分配：操作系统为进程分配的驻留集大小固定；

• 可变分配：先为进程分配一定数量的物理块，之后根据情况适当的增加和减少。

• 局部置换：缺页时，只能用进程自己的物理块进行置换

• 全局置换：操作系统可以将空闲的物理块分配给缺页进程，或是将别的进程的物理块分配给缺页进程。

页面分配就有以下三种分配方式：

1. 固定分配局部置换：一开始为进程分配确定的物理块，在缺页时，只能用自己的物理块进行置换。这种方式并不灵活，因为我们并不知道给进程分配多少个物理块才合理。

2. 可变分配全局置换：一开始分配一定数量的物理块，但是操作系统会在进程发生缺页时给其分配空闲的物理块。仅当空闲物理块用完，系统才会选择未锁定的页面调出。被选择调出的页可能是任意一个页，导致这个进程缺页率可能会增加。

3. 可变分配局部置换：一开始分配一定数量的物理块，缺页时将自己的物理块进行置换。如果频繁缺页，才会多分配几个物理块。反之缺页率过少，则会减少分配给进程的物理块。

何时调入

• 预调页策略：预测不久之后可能访问到的页面，将它们预先调入内存。但是这种预测成功率较低。这种调入策略称为运行前调入，可以由程序员指出操作系统应该一开始调入哪些部分。

• 请求调页策略：一开始并不调入页面。只有当发生缺页才调入内存。这种方式对于IO消耗较大，也被称为运行时调入。

何处调入

• 如果系统有充足的对换区空间，页面调入和调出都是在内存和对换区进行。在进程开始时，需要将相关数据从文件区复制到对换区。

• 如果系统缺少对换区空间，不会被修改的文件从文件区调入，换出不必写入磁盘。对可能被修改的部分，换出写回对换区。下次使用从对换区调入。

• UNIX方式，运行之前所有文件都在文件区。页面换出放在对换区，换入则从对换区放入。

上图中的虚拟内存选项的大小，就是对换区的大小。

抖动（颠簸）

刚刚换出的页面很快被换入，或者刚刚换入的页面很快被换出。这种现象称为抖动。产生抖动的主要原因时频繁访问的页面数目高于驻留集大小。

工作集

指的是一个进程在某一时刻所需要的内存页面集合，这些页面是进程在运行时频繁访问的部分。

工作集通常通过以下方式计算：

• 时间窗口: 在一定的时间窗口内（例如过去的 10 秒），记录进程访问的所有页面。

• 访问频率: 统计在这个时间窗口内访问的页面，形成工作集。

操作系统可以根据工作集的大小来动态分配物理内存，确保活跃进程有足够的内存，以减少缺页的发生。

内存映射文件

内存映射文件（Memory-Mapped Files）是操作系统提供的一种机制，允许将文件的内容映射到进程的地址空间中，使得进程可以像访问内存一样访问文件。

1. 直接内存访问: 内存映射文件将文件内容直接映射到进程的虚拟地址空间中，进程可以通过指针直接访问文件数据，而不需要使用读取和写入函数。

2. 共享内存: 多个进程可以映射同一个文件，从而实现进程间通信（IPC）。当一个进程修改映射的内容时，其他进程也能看到这些变化。

3. 延迟加载: 只有在实际访问时，文件的内容才会被加载到内存中，这有助于节省内存资源。

4. 自动同步: 内存映射文件的修改可以自动同步到磁盘，减少了显式的文件写入操作。

与传统方式进行对比