Skip to main content

内存管理

功能​

内存管理的主要功能有：

  1. 内存的分配与回收，使程序员免除分配内存的麻烦；
  2. 地址转换，多道程序环境下，逻辑地址与物理地址不一致，操作系统通过内存管理单元 MMU 进行转换；
  3. 内存扩充，通过虚拟化技术或自动覆盖技术，从逻辑上扩充内存；
  4. 内存共享，允许多个进程访问同一内存部分；
  5. 存储保护，保证各作业在各自存储空间运行，互不干扰。

程序的链接和装入​

创建进程首先要将程序和数据装入内存，流程为：

  1. 编译，由编译程序将源代码编译为若干目标模块；
  2. 链接，将目标模块与其需要的库函数链接，形成完整的装入模块；
  3. 装入，装入内存。
tip

链接一般有三种方式：

  1. 静态链接，程序运行前，链接为一个完整的装入模块，不再拆开，但要解决两个问题：
    1. 修改相对地址，编译后的所有目标模块都是从 0 开始；
    2. 变换外部调用符号，也变换为相对地址；
  2. 装入时动态链接，便于修改和更新，实现对目标模块的共享；
  3. 运行时动态链接，加快装入过程，节省大量内存。

装入也有三种方式：

  1. 绝对装入，只适用于单道程序，逻辑地址与物理地址相同，甚至可以由程序员给出；
  2. 可重定位装入，多道程序环境下，起始地址通常是 0，程序中的其他地址则是相对于 0 的相对地址，装入时需要进行 重定位，静态 修改所有地址为实际物理地址；
  3. 动态运行时装入，程序若在内存中发生移动，则需要 动态 装入，将地址转换推迟到程序执行，需要一个重定位寄存器；便于将程序分配到不连续的存储区，并且只装入部分代码就可以运行，也有利于程序段的共享。

进程的内存映像​

  1. 代码段，程序的二进制代码，只读，可被多个进程共享；
  2. 数据段，包括全局变量和静态变量；
  3. 进程控制块（PCB），存放在系统区；
  4. 堆，存放动态分配的变量，从低地址向高地址；
  5. 栈，实现函数调用等，从高向低。

代码段和数据段装入时就指定了大小，而堆和栈不同，会动态收缩和扩张。

内存保护​

为了确保进程都有单独的内存空间，有两种方法：

  1. CPU 中设置上下限寄存器，判断有无越界；
  2. 采用 重定位寄存器（又称基地址寄存器）和界地址寄存器（又称限长寄存器），分别包含最小的物理地址值和逻辑地址最大值，判断有无越界。

内存共享​

tip

只有只读区域才可以共享，实际执行时，也可以为每个进程分配局部数据区，将可能改变的部分复制过去，这样就不需要修改共享代码。

覆盖与交换​

早期计算机系统中，主存容量很小，当主存不够时，可以采用覆盖技术，将用户空间分为固定区和若干覆盖区，活跃部分放置于固定区，其余部分按照调用关系分段，运行时调入覆盖区即可；该技术对用户和程序员不透明；

交换是指将处于等待状态（阻塞态）程序由主存移到辅存，再将就绪的程序移入主存；几个需要注意的点：

  1. 辅存空间要大，并提供对内存映像的直接访问；
  2. 为了提高 CPU 利用率，需要使进程的执行时间大于交换时间；
  3. 换出进程须保证进程完全空闲；
  4. 交换空间独立于文件系统，使用起来很快；
  5. 通常在系统负荷低时暂停使用；

连续分配管理​

指为用户程序分配一个连续的内存空间，方式有：

  1. 单一连续分配，内存分为系统区和用户区，仅有一道用户程序，独占用户区；无碎片、无须内存保护、仅适于单道程序系统；
  2. 固定分区分配，用户空间划分为若干固定大小的区域，每个分区一道作业，分区大小可相同可不同，通常建立分区表，回收内存时只要标记未分配即可；当分区大小不够时，需要采用覆盖技术，容易形成 内部碎片，空间利用率低；
  3. 动态分区分配，又称可变分区分配，装入时动态分配分区大小，刚好合适程序大小；刚开始时无内存碎片，当运行一段时间后会产生很多 外部碎片，不在分区之中，而是处于分区之间，无法被分配；可以采用 紧凑技术，移动分区，但是开销大。
tip

动态分区的分配方法被称为 适应方法，我写了一个可视化工具 MemAlloc，一些方法如下：

  1. 首次适应，选择第一个能满足要求的分区；
  2. 邻近适应，从上次分配结束的地方开始首次适应；
  3. 最佳适应，空闲分区按照容量递减形成 空闲分区连，找到第一个能满足要求且最小的空闲分区；
  4. 最坏适应，与最佳适应相反；
  5. 伙伴算法，Linux 内核中针对大内存的分配，比较复杂，将内存分为多个内存块，每个内存块都有 2k2^k 个页框，如分为 11 个内存块，则每块页框数量为 1,2,4,8…1024，每个页框大小一般为 4KB，TODO

分页存储管理​

将主存分为大小相同的内存块，作为基本单位，进程也以块为单位划分；不会产生外部碎片，，并且只有进程最后一块才会产生非常小的内部碎片。具体见计算机组成原理。

分段存储管理​

见计算机组成原理

虚拟内存​

部分内容见计算机组成原理

基本概念​

tip

上述讨论的内存管理策略都是为了将多个进程保留在内存中，允许多道程序设计，有以下两个特征：

  1. 一次性，必须全部装入才能开始运行；这导致过大的作业不可运行，只有少量作业可驻留内存；
  2. 驻留性，作业装入一直在内存中，直到结束。

程序运行中许多不需要使用的内存长时间占据了大量的内存空间，导致多道性下降。

基于局部性原理，可以只将部分程序装入，因此操作系统为用户提供了比实际内存大得多的吸你存储器，具体转换功能对用户透明。

分页管理​

页表：包括页号、物理块号、状态位、访问字段、修改位和外存地址；其中状态位表示该页是否调入内存，访问字段表示一段时间内被访问的次数，修改位标志是否被修改。

缺页中断：当要访问的页不存在内存中，产生缺页中断，请求操作系统调入对应页；其本身作为中断，需要经过 保护 CPU 环境、分析中断原因、转入缺页中断处理程序、恢复 CPU 环境等，与一般中断相比，有两个明显区别：指令执行期间的内部中断；一条指令执行过程中可能产生多次缺页中断。

页框分配​

驻留集

给一个进程分配的物理页框大小就是驻留集，需要考虑以下几点：

  1. 驻留集越小，内存中留存的进程数就越多，有利于提高 CPU 利用率；
  2. 驻留集过小，可能导致缺页率提高；

内存分配策略

  1. 固定分配局部置换：每个进程固定分配页框数，缺页是从所分配页框中置换；难以确定分配页框数，太少会提高缺页率，太多降低资源利用率；
  2. 可变分配全局置换：分配页框数量可在执行过程中变化，全局置换是指可分配内存中的空闲页框；但是如果盲目给进程增加物理块，会导致多道程序并发能力下降；
  3. 可变分配局部置换：若缺页率高，则增加分配页框数量，反之可以减少；实现更复杂，开销也更大，但是小于频繁的页置换。
tip

采用固定分配时，分配内存中的空闲页框有几种算法：

  1. 平均分配；
  2. 按比例分配；
  3. 优先权分配。

通常是将空闲页框分为两部分，一部分按比例分配，一部分按优先权分配；

调入页面时机

  1. 预调页策略，根据局部性原理，可以一次调入相邻的若干页；但准确率不高，主要用于进程的首次调入；
  2. 请求调页策略，进程提出调页请求，每次仅调入一页，会增加磁盘 I/O 开销。

从何处调页

由前，从专门的交换分区（swap），不同于文件系统，其采用连续分配方式，速度更快，调页有三种情况：

  1. 系统有足够交换空间，全部从交换分区调入，并且进程运行前，将文件分区的文件调入交换分区；
  2. 没有足够交换空间，不会被修改的文件从文件区调入，可能修改的部分调出时换入交换分区；
  3. UNIX 方式，与进程有关的文件都放在文件分区，为运行的页面都从文件分区调入，被换出的页面调入交换分区；进程共享页面若被其他进程调入内存，则无须再从交换分区调入。

页面置换算法​

tip

置换算法发生在无可用空闲页面时，如前文的局部置换，就算内存中有空余空间，也有可能需要进行页面置换。

其指标是较低的页面更换频率。

最佳（OPT）

OPT 选择置换的页面是 以后永不使用 或者 最长时间内不再被访问的 页面，这要求我们知道进程所有的页面访问顺序，因此目前不能实现，主要用于评价其他算法。

先进先出（FIFO）

优先置换最早进入内存的页，可以通过队列实现，FIFO 可能出现所分配的物理块数增大，而缺页数不减反增的情况，称为 Belady 异常，LRU 和 OPT 不会。

最近最久未使用（LRU）

该算法认为过去一段时间内未被访问的页面，在一段时间的将来也可能不被访问，页面置换时选择之前最近没有访问的页换出；性能较好但是需要寄存器和栈的硬件支持。

时钟（CLOCK）

LRU 性能接近 OPT 但是实现开销大，因此有一些开销小且性能接近 LRU 的算法，大多是基于 CLOCK 算法的变体：

  1. 简单的 CLOCK，又称为最近未使用（NRU），其将内存中的所有页面练成一个循环队列，同时维护一个 替换指针，当某一页被替换时，则将其指向下一个页面；选择淘汰页面时，检查页的访问页，若为 0，则换出，若为 1，则置为 0，再给其一次驻留内存的机会；若某次缺页时，所有标志位都是 1，则其会不断向后扫描，将所有标志位置为 0，直到回到开始扫描的位置，换入页面后再置为 1；
  2. 改进型 CLOCK，页面换出时，若页面未被修改，实际上是无需写入磁盘的，因此进入了修改位，可以得到四种类型的页面：
    1. 未被访问和修改：最佳淘汰页面；
    2. 未被访问但被修改：不是很好的淘汰页面；
    3. 已被访问但未被修改：可能再被访问；
    4. 已被访问且已修改：可能再被访问。 算法执行过程如下：
    5. 寻找第一类页面作为淘汰页面，扫描期间不改变任何访问位；
    6. 若第一步失败，则寻找第二类页面，所有扫描过的页面访问位置为 0；
    7. 若第二步失败，则指针返回开始位置，将所有帧访问位置 0，重复第一步和第二步，此时一定能找到适合被淘汰的页。

抖动和工作集​

抖动

刚换出的页面马上又要换入，刚换入的页面又要换出，这种频繁地调度行为被称为抖动；其根本原因是因为系统中同时运行的进程太多，分配给每个进程的物理块太少，导致每个进程大部分时间都用于页面替换，进而导致 CPU 利用率急剧下降，因此提出了 工作集 的概念来解决这个问题。

工作集 是指在某段时间内进程要访问的页面集合，基于局部性原理，可以使用最近访问的页面来确定工作集，其可通过工作集窗口（过去的多少次调度）和时间（过去的一段时间内）确定，工作集小于等于工作集窗口，因为工作集窗口中会有重复的页面，而工作集窗口是唯一的。

操作系统跟踪每个进程的工作集，并为进程分配大于工作集的物理块，从而解决抖动。

内存映射文件​

将磁盘的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，这样就可以直接访问被映射的文件，而不必执行 I/O 操作，也无需对文件内容进行缓存处理，非常适合用于管理大尺寸文件。

对内存映射文件的任何操作都是在内存中完成的，进程解除文件映射时，所有改动的页面都会重新写回磁盘；多个进程允许并发的共享同一映射文件。

地址翻译​

见 计算机组成原理 TLB 等