Lab 2：物理内存管理

真实的物理内存通常是多种多样的，它们可能是互不连续且速度差异巨大的，操作系统需要为上层应用抽象出一个连续的 逻辑地址空间，逻辑地址空间到物理地址空间的映射则由 MMU（Memory Management Unit，内存管理单元）来负责。

逻辑地址空间与物理地址空间：

  • 逻辑地址空间（logical address space）：又称虚拟地址空间（virtual），在 CPU 运行的进程看到的地址，即可执行文件中的地址
  • 物理地址空间（physical）：由硬件直接支持的地址空间
  • 线性地址空间（linear）：

操作系统对内存的管理主要体现为 内存分配，内存分配又分为 连续内存分配 和 非连续内存分配，连续内存分配可以通过 重定位 实现，非连续内存分配可以通过 段机制 或 页机制 实现。

连续内存分配

连续内存分配是一种最简单的内存分配算法，指给进程分配一块不小于指定大小的连续的物理内存区域。值得注意的是，连续内存分配可能会产生空闲内存不能被利用的 碎片，碎片又分为外碎片和内碎片，外碎片 是指分配单元之间的未被使用内存，内碎片 是指分配单元内部的未被使用内存，内碎片的产生取决于分配单元大小是否要取整。

一个优秀的连续内存分配算法致力于减少这种碎片的产生，以下介绍一些常用的连续内存分配算法：

  • 最先匹配（First Fit Allocation）：空闲分区列表按地址顺序排序，分配过程时，搜索第一个合适的分区，释放分区时，检查是否可与临近的空闲分区合并。
    • 优点：简单；在高地址空间有大块的空闲分区。
    • 缺点：会产生外碎片；分配大块时较慢。
  • 最佳匹配（Best Fit Allocation）：空闲分区列表按由小到大排序，分配时，查找一个合适的分区，释放时，查找并且合并临近的空闲分区（如果找到）
    • 优点：大部分分配的尺寸较小时，效果很好
      • 可避免大的空闲分区被拆分
      • 可减小外碎片的大小
      • 相对简单
    • 缺点：会产生外碎片；释放分区较慢；容易产生很多无用的小碎片。
  • 最差匹配（Worst Fit Allocation）：空闲分区列表按由大到小排序，分配时，选最大的分区，释放时，检查是否可与临近的空闲分区合并，进行可能的合并，并调整空闲分区列表顺序。
    • 优点：中等大小的分配较多时，效果最好；避免出现太多的小碎片
    • 缺点：会产生外碎片；释放分区较慢；容易破坏大的空闲分区，因此后续难以分配大的分区

在连续内存分配中，当一个新进程需要内存空间，但却没有足够可使用的内存空间时，我们就需要碎片整理，碎片整理 是指通过调整进程占用的分区位置来减少或避免分区碎片。碎片整理进一步又分为：

  • 紧凑（compaction）：通过移动分配给进程的内存分区，以合并外部碎片。紧凑的条件是所有应用程序可动态重定位。通常来说会对等待态的进程进行移动。
  • 分区对换（swapping in/out）：通过抢占并回收处于等待态的进程的分区，以增大可用内存空间。

一个较好的连续内存分配的实现是 伙伴系统（buddy system）。

非连续内存分配

连续内存分配存在诸多缺点，因此我们需要非连续内存分配以提高内存利用效率和管理灵活性。具体而言，非连续内存分配 允许一个程序使用非连续的物理地址空间，允许共享代码与数据，支持动态加载和动态链接。根据非连续内存分配中的内存块的大小，我们可以将非连续内存分配分为 段式存储管理（segmentation）和 页式存储管理（paging），两者的区别是段式存储管理的内存块比较大，页式存储管理的内存块比较小。

段式存储管理

在段式存储管理中，段 表示访问方式和存储数据等属性相同的一段地址空间，其对应一个连续的内存“块”，若干个段组成进程逻辑地址空间。将逻辑地址空间映射为物理地址空间遵循如下步骤：

  1. 根据 段号 在 段表 中查找相应的 段基址 和 段长度
  2. 比较 段内偏移 是否小于等于段长度，若否，则抛出内存异常，若是，则进行下一步
  3. 根据段基址和段内偏移得到真实的物理地址

页式存储管理

在页式存储管理中，我们把物理地址空间划分为大小相同的基本分配单位 —— 帧，把逻辑地址空间也划分为相同大小的基本分配单位 —— 页，具体如下：

  • 帧（frame）：又称页帧（page frame）或物理页面，物理地址空间的基本单元，大小是 \(2^{n}\)，在 32 位系统中一般为 4K（4096，\(2^{12}\)）字节
  • 页（page）：又称页面或逻辑页面，逻辑地址空间的基本单元，大小和帧相同

将逻辑地址空间映射为物理地址空间遵循如下步骤：

  1. 根据 页号 在 页表 中查找相应的 帧号
  2. 根据帧号和 帧内偏移（或 页内偏移）得到真实的物理地址：\(s\times2^{n}+o\)

注意：一般来说，帧内偏移 = 页内偏移，帧号 != 页号。

每个进程都有一个页表，页表由一个个的 页表项 组成，页表的基址存储在 页表基址寄存器（PTBR，Page Table Base Register）中，页表项由以下内容组成：

  • 帧号
  • 页表项标志位：
    • 存在位（resident bit）：是否有帧号与此页号对应，若有，则为 1
    • 修改位（dirty bit）：表示在内存中的该页是否被修改过，用于虚拟页式存储中，回收该物理页面时，据此判断是否要把它的内容写回外存。
    • 引用位/访问位（clock/reference bit）：表示该页面是否被访问过（读或写），用于页面置换算法
    • 保护位：表示该页的允许访问方式，只读、可读写、可执行等，用于虚拟页式存储中。
    • 驻留位：表示该页是否在内存，用于虚拟页式存储中，1 表示该页位于内存中，该页表项是有效的，可以使用；0 表示该页当前在外存中，访问该页表项将导致缺页异常。

页式存储管理存在以下性能问题：

  • 内存访问性能：访问一个内存单元需要 2 次内存访问，第一次访问页表项，第二次才访问数据。
  • 页表大小问题：页表可能非常大

通过缓存（Caching）可以解决内存访问性能问题，通过间接（Indirection）访问可以解决页表大小问题。具体来说，通过快表（Translation Look-aside Buffer，TLB）缓存近期访问的页表项到 CPU 中；多级页表通过间接引用将页号分成 k 级，如果所有页表项都存在的话，使用多级页表实际上存储并没有减少，但实际中运行的进程，多数并不会用到整个所有的页表，在这种情况下，我们可以通过各级页表中的存在位把那些不存在的给省掉，这样可以节省空间。

此外，通过页寄存器和反置页表也可以解决上述的页表大小的问题。

段页式存储管理

段式存储在内存保护方面有优势，页式存储在内存利用和优化转移到后备存储方面有优势，段页式存储管理则是将这两者结合起来。

具体来说，在段式存储管理基础上，给每个段加一级页表。

在段页式存储管理中可以很方便的实现内存共享，即通过指向相同的页表基址，实现进程间的段共享。

实验

首先，在实模式下通过 BIOS 15 号中断来探测物理内存大小。

其次，实现连续内存分配算法：首次适配算法（First Fit）。

最后，建立分页机制。

具体而言，要建立二级页表