内存管理

存储器管理的主要对象是内存，在多道程序设计系统中，必须在内存中进一步细分出“用户”部分，以满足多个进程的需求，称为内存管理

内存管理的需求

编译→链接→装入程序→内存

• 逻辑组织（logical organization）：程序被组织成模块
• 共享：允许多个进程访问内存的同一部分（受控访问）
• 保护：进程应避免被其他进程干扰，编译阶段无法确定程序加载时的绝对地址，因此必须进行地址安全检查（保护内存由处理器满足而不是操作系统，因为OS无法预测程序可能产生的所有内存访问）
• 重定位（relocation）：当程序员不知道某个程序执行时存放在内存的位置，或者进程被挂起后返回硬盘，之后又回到内存，地址发生变化；需要把进程重定位到内存的不同区域

为实现内存地址重定位，必须有硬件地址变换机构的支持，即需要在系统中增加一个重定位寄存器，存放程序或数据在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的

• 物理组织：内存提供快速访问和保存当前使用的程序和数据、外存提供长期存储程序和数据

供程序和数据使用的内存可能不足，此时需要采用覆盖（overlaying）技术来组织程序和数据，使不同的模块被分配到内存中的同一块区域（已经退出历史，呵呵）

内存分区（memory partitioning）

固定分区

• 大小相等：

  • 小于等于分区大小的进程可以被装入
  • 若分区全满，且没有进程处于就绪态或运行态，换出一个进程的所有分区
  • 难点：程序太大装不下、内存利用率低（装入数据块小于分区大小，但占用整个分区，存在空间浪费，称为内部碎片internal fragmentation）

• 大小不等

  • 可以减缓分区大小相等时的难点，但无法真正解决

放置算法

对于分区大小相等放置无所谓

对于分区大小不等：

• 把每个进程分配到能容纳它的最小分区中：每个分区需要维护一个调度队列，保存分区换出的进程，优点是可以使分区内部浪费的空间（内部碎片）最少
• 为所有进程只提供一个队列：当需要一个进程装入内存时，选择可以容纳的最小可用分区，若所有分区都已被占据，则必须进行交换，一般优先考虑换出能容纳新进程的最小分区中的进程

动态分区

分区长度和数量可变。进程装入内存时，会被分配一块与其所需容量相等的内存空间

缺点：最终会产生外部碎片；解决方法：采用压缩技术（compaction），操作系统不时地移动进程，使得进程占用的空间连续，并使所有空闲空间连成一片(但费时，需要动态重定位的能力)

放置算法

• 最佳适配：选择与要求大小最接近的块（最差）
• 首次适配：从头开始扫描内存，选择大小足够的第一个可用的块（最好最快）
• 下次适配：从上一次放置的位置开始扫描内存，选择下一个大小足够的可用块

伙伴系统

固定分区：限制了活动进程的数量，内存利用率可能较低

动态分区：维护复杂，可能会引入压缩的额外开销

折中方案：伙伴系统，可用内存块大小$2^{K}$个字，L≤K≤U，$2^{L}$表示分配的最小块的尺寸，$2^{U}$表示分配的最大块的尺寸

分配过程：若有$2^{U-1}\lt s\le 2^{U}$，则分配整个空间；否则该块分为两个大小等大的伙伴。大小均为$2^{U-1}$；持续这个过程直到产生大于等于s的最小块，并分配给该请求。这个过程中随时对空闲空间进行分裂或合并

二叉树分配：若两个伙伴都是叶结点，则至少分配出去一个，否则将合并为一个更大的块

重定位

首次加载一个进程时，代码中的相对内存访问被绝对内存地址替代，这个绝对地址由进程被加载到的基地址确定

• 逻辑地址：与当前数据在内存中的物理分配地址无关的访问地址，在执行对内存的访问前必须转为物理地址
• 相对地址：相对于某些已知点（通常是程序开始处）的存储单元
• 物理/绝对地址：数据在内存中的实际位置

进程装入时设置基址和界限寄存器的值，并计算基址寄存器的值加上相对地址产生一个绝对地址，并于界限寄存器的值进行比较，在范围内继续执行指令；否则向操作系统发出中断信号，操作系统做出相应响应

分页/分段

计组和下一单元虚拟内存讲的更详细，此处不再赘述，只简单记下比较重要的

• 和前面的内存分配不同在于增加了对进程的分块
• 进程页面与页框号一一对应
• 每个进程维护一个页表，包含页号和对应页框号