本章主要总结操作系统中的内存管理

  • 随着技术的发展，内存的容量再不断增大，但是也不能把所有用户数据和程序一起装入内存，因此操作系统需要对内存空间进行合理的划分和有效的动态分配，从而提高系统的资源利用率。对内存的合理划分以及有效的动态划分就是内存管理的概念。

程序执行过程

  • 每段程序执行前大致需要经过三个过程：编译 -> 链接 -> 装入
    1. 编译：将源代码通过编译器编译为一个个目标模块。
    2. 链接：将每个目标模块和所需库函数链接起来，形成一个完整的装入模块。
      1. 静态链接（装入前链接），即在装入内存之前把所有的模块和对应的库函数进行链接从而形成一个可执行程序，以后不会再拆开。
      2. 装入时动态链接，即在装入内存时，一边装入一边链接。
      3. 运行时动态链接，即在执行对应模块代码时，实时链接。
    3. 装入：将链接后形成的模块装入内存中。
      1. 绝对装入 => 程序相对地址和实际装入的物理地址相同。
      2. 可重定位装入 => 程序相对地址加一个重定位地址形成实际的物理地址。
      3. 动态运行时装入 => 在执行对应的模块时，才开始执行地址转换，地址转换的偏移量则从重定位寄存器中取出。

内存分配管理方式

连续分配方式：用户程序被分配进一个连续的内存空间

  1. 单一连续分配方式: 整个内存中只运行一道用户程序。
  2. 固定分区分配
    • 内存被划分为若干个固定大小的区域。当有程序需要装入内存时，从分区说明表上寻找合适的内存区域并分配给它。
  3. 动态分区分配 => 不预先对内存进行分区，而是等程序装入内存时动态分区。
    1. 首次适应算法
    2. 最佳适应算法
    3. 最坏适应算法
    4. 邻近适应算法（首次适应算法的改进，即下一次分配内存是从上一次分配内存结束位置开始）

区分内部碎片还是外部碎片的关键在于：内存分区是提前分好还是运行时实时分配的。

对于前者，很容易理解每个内存分区就可以称之为“内”，所以就有了内部碎片的说话。

对于后者，由于没有提前分区，所以自然没有“内”的概念，那么所有的内存都是“外”，所以此时产生的碎片也称为外部碎片。

即固定分区会产生内部碎片，动态分区会产生外部碎片。

非连续分配方式

  1. 基本分页存储管理方式 => 一维表示即可，即给定一个地址，便可以算出它的页号以及偏移地址（因为页的大小是确定的）
  2. 基本分段存储管理方式 => 二维表示，因为每段的大小不同，导致一个地址无法算出其它信息，段号和段内位移地址要显式给出
  3. 段页式存储管理方式 => 对代码分段，对内存分页。

  • 分页系统和分段系统的共同之处：

    1. 它们都有对应的“表”，分页系统是页表，分段系统是段表。当然对于表来说也有对应的寄存器（页表/段表寄存器）
    2. 它们都可以加入**快表（联想存储器 TLB）**来提高地址转移效率。

  • 不同之处：

    1. 分页系统的地址可以进行一维表示，而分段系统的地址需要二维表示。
    2. 分段系统中的每段是具有一定逻辑意义的代码集合（比如一块函数定义），方便代码共享。

虚拟内存

局部性原理 => 高速缓存技术依赖的原理

  1. 时间局部性：程序中的某条指令一旦执行，不久后该指令可能再次执行；某数据被访问，不久后该数据可能再次被访问。产生时间局部性的原因是程序中往往含有大量的循环操作
  2. 空间局部性：一旦程序访问了某个存储单元，不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在某个区域。

虚拟存储器

  • 根据局部性原理，程序装入时，可以只将程序的部分装入，其余部分留在外存。程序执行过程中，若程序不在内存中，则从外存中调入对应部分的程序代码，然后继续执行程序。另一方面，操作系统也把不再执行的代码重新换出到外存（实际情况是如果代码段没有被修改，则直接丢弃）。这样，系统好像就为用户提供了一个比内存大的多的存储器，称其为虚拟存储。

  • 实现方式

    1. 请求分页存储管理
    2. 请求分段存储管理
    3. 请求段页式存储管理

  • 它们都需要的硬件支持：

    1. 一定的内外存。

    2. 地址转换机构。

    3. 中断机构（程序访问部分不在内存时，发生缺页/段中断）

    4. 页表（段表）机制。

      • 特别说明下页表机制（这里以页表存储管理为例），由于程序在运行时有部分在外存（不像之前直接全部调入），于是需要标记外存的程序段的地址。

      • 另一方面，为了分辨对应页的代码是否在内存中，还需要一个状态位来进行说明。除此之外，为了优化调入换出次数，提高执行效率，则还需要设置访问字段以及修改位。

      • 那么上述的字段设置在哪里设置比较好呢？显而易见页表是最适合的位置，即给页表增加几个状态位专门安放上述的几种状态字。

页面置换算法

  1. 最佳置换算法（OPT）
  2. 先进先出算法（FIFO）=> 可能会出现Belady异常，即分配物理块数越多，缺页次数反而越大。
  3. 最近最久未使用（LRU）置换算法
  4. 时钟（CLOCK）置换算法 => 最近未使用算法（NRU）
  5. 改进型CLOCK算法
    • 改进型CLOCK算法主要是增加了修改位的判断，即优先换出没有修改的内存页（可以直接扔掉而不是写回外存）

页面分配策略

  • 系统必须考虑给特定的进程分配几个页框比较合适。
分配算法
  1. 固定分配局部置换
  2. 可变分配全局置换
  3. 可变分配局部置换
从何处调入页面

  • 在外存上分为文件区（存放文件）和对换区（存放对换页面）。

  • 文件区：采用离散分配方式，读写速度相对较慢。

  • 对换区：采用连续分配方式，读写速度相对较快。

  1. 如果对换区足够大，则操作系统在程序执行之前把需要调入的页面从文件区复制到对换区。
  2. 如果对换区大小有限，则不会修改的文件都从文件区调入（因为不用写回），可能会被修改的则复制到对换区。这样可以提高写回速度。

抖动： 进程执行过程中，如果换页的时间超过了执行时间，则判断其发生了抖动。

  • 抖动的解决方法：工作集。