长篇预警

一、内存管理背景

内存是现代计算机运行的中心，它是由字或字节组成，每个字或字节都有自己的地址。

基本硬件

程序必须装入内存才能被执行；
CPU可以直接访问的存储器只有主存、高速缓存和寄存器；
寄存器通常可在1个（或少于1个）CPU时钟周期内完成访问，完成主存访问可能需要多个CPU时钟周期；
CPU暂停（Stall）：在读取内存数据时，CPU空闲；
在内存和CPU之间，增加高速内存，来协调速度差异，这种内存缓冲区称为高速缓存Cache；
内存保护需要保证正确的操作。

独立运行内存空间

确保进程可访问的合法地址范围，并确保进程只访问其合法地址。
两个寄存器实现进程保护：

• 基址寄存器（Base）
  进程最小的合法物理内存地址
• 界限寄存器（Limit）
  进程地址的长度
• CPU在执行指令时，需要进行地址合法性检验
  
  合法的地址应该是大于等于基址寄存器的值，小于基址与界限寄存器的值之和。

指令和数据绑定到内存

程序以二进制可执行文件的形式存储在磁盘上，为了执行，程序被调入内存并放在进程空间内。

地址绑定（重定位）：在秩序装入内存时，把程序中的相对地址转换为内存中的绝对地址的过程。

指令和数据绑定到内存地址可在三个不同阶段：

1. 编译时期（Compile time）
   如果内存位置已知，可生成绝对代码；
   如果开始位置改变，需要重新编译代码
2. 加载时期（Load time）
   如果存储位置在编译时不知，则必须生成可重定位（relocatable）代码
3. 执行时期（Execution time）
   如果进程执行时可在内存移动，则地址绑定可延迟到运行时；
   需要硬件对地址映射的支持（例如基址和限长寄存器）
   

逻辑地址和物理地址

逻辑地址：
由CPU产生，在进程内的相对地址，也称虚拟地址、相对地址、程序地址；
物理地址：
内存地址，所有内存统一编址，也称绝对地址、实地址。

编译和加载时的地址绑定生成相同的逻辑地址和物理地址，此时重定位是静态的；但执行时的地址绑定导致不同的逻辑地址和物理地址，此时的重定位称为动态重定位。
由程序所生成的所有逻辑地址的集合称为逻辑地址空间，与这些逻辑地址所对应的所有物理地址的集合称为物理地址空间。
逻辑地址空间绑定到物理地址空间这一概念至关重要，是正确进行内存管理的中心。

内存管理单元（MMU）

运行时，从虚拟地址到物理地址的映射是由一个硬件设备来完成的。该硬件称为内存管理单元（简称MMU）。它是CPU用来管理内存的控制线路。

实现地址映射，在MMU策略中，这里的基址寄存器称为重定位寄存器，这里的重定位就是指从逻辑地址转化为物理地址的过程。逻辑地址在送入内存之前要加上重定位寄存器的值。用户程序所对应到的是逻辑地址，物理地址从来都不可见。

动态加载

为了获得更好的内存空间使用率，可以使用动态加载。
一个子程序只有在被调用时才会加载；
不需要操作系统的特别支持，通过程序设计实现。

优点：

• 更好的内存空间利用率
• 没有被使用的例程不被载入
• 当需大量代码来处理不经常使用的功能时非常有用
  操作系统可以提供子程序库来帮助加载，如Windows的动态链接库。

动态链接

• 和各种库文件的链接被推迟到执行时期
• 需要动态装载技术支持
• 一小段代码即存根。用来定位合适的保留在内存中的库程序
• 存根用例程地址来替换自己，并开始执行例程
• 操作系统需要检查例程是否在进程的内存空间，所以需要操作系统支持

二、连续内存分配

为一个用户程序分配一个连续的内存空间。
早期内存分配模式：应用于内存较小的系统

三种类型：

1. 单一连续分配
2. 固定分区分配
3. 可变分区分配

主存通常被分为两部分：

• 操作系统（通常驻留在低端，因为中断矢量保存在低端）
• 用户进程（保存在内存高端）

1. 单一连续分配

分配方式：单道程序环境下，仅装有一道用户程序，即整个内存的用户空间由该程序独占。

• 内存分配管理十分简单，内存利用率低
• 适用于单用户、单任务OS
• CP/M、MS-DOS、RT11

未采取存储器保护措施

• 节省硬件
• 方案可行

2. 固定分区分配

最早的、也是最简单的一种可运行多道程序的存储管理方式；
预先把可分配的主存空间分割成若干个连续区域，称为一个分区；
每个分区的大小可以相同也可以不同。但分区大小固定不变，每个分区装一个且只能装一个程序；
内存分配：如果有一个空闲分区，则分配给进程。

划分分区的方法：

1. 分区大小一样
   缺乏灵活性。程序太小：浪费内存；程序太大：装不下。
   有些场合适用，如利用一台计算机同时控制多个相同对象。

2. 分区大小不等

• 多个小分区
• 适量中分区
• 少量大分区

3. 可变分区分配

• 分区（孔、Hole）-可用的内存块，不同大小的分区分布在整个内存中；
• 当一个进程到来的时候，它将从一个足够容纳它分区中分配内存。
• 操作系统包含以下信息：
  a）已分配的分区-已分配分区表
  b）空的分区-空闲分区表
  具体实现的数据结构可以是线性表或链表

从图上可以看到，进程8终止，所占内存被释放，进程9,10占用了部分内存。

可变分区分配是动态存储分配问题的一种情况。

存储分配算法

1. 首次适应（First-fit）：分配最先找到的合适的分区；
2. 最佳适应（Best-fit）：搜索整个列表，找到适合条件的最小的分区进行分配；
3. 最差适应（Worst-fit）：搜索整个列表，寻找最大的分区，进行分配。

现有一进程请求分配110K内存，首次适应、最佳适应、最差适应的分配方法如下：

在速度和存储空间的利用上，首次适应法和最佳适应法要好于最差适应法，首次适应法和最佳适应法在空间利用上差不多，但首次适应法更快些。

内存回收

可变分区分配方案的内存回收存在4种情况：
a. 回收内存块前后无空闲块
b. 回收内存块前有后无空闲块
c. 回收内存块前无后有空闲块
d. 回收内存块前后均有空闲块

碎片

随着进程颁繁的装入和移出内存，空闲内存空间中可能被分成小的片段。

• 外碎片——整个可用内存空间可以用来满足一个请求，但它不是连续的
  首次适应法和最佳适应法都有这个问题，这个问题可能很严重，最坏情况下，每两个进程之间都有空闲块被浪费。
• 内碎片——分配的内存可能比申请的内存大一点，这两者之间的差别是在分区内部，但又不被使用。
  可通过紧缩来减少外碎片：把一些小的空闲内存结合成一个大的块。只有重定位是动态的时候，才有可能进行紧缩，紧缩在执行时期进行。

最简单的合并算法是简单地将所有进程移动到内存的一端，而所有空闲分区移到另一端，这种方法的开销较大，所以为减少开销，应选择移动内容最小的一种。

紧缩例子：
右边3个是紧缩之后的内存空间，分别移动600K,400K,200K。

三、分页内存管理

解决外碎片的方案：允许物理地址空间非连续。

离散内存管理方案

1. 分页内存管理方案——现代操作系统常用方案
2. 分段内存管理方案
3. 段页式内存管理方案

分页

内存管理方案允许进程的物理地址空间可能不连续。只要有可用的物理内存，就可以分配给进程。

基本方法：

将物理内存分成大小固定的块，称为帧（frame）。也可以简单称为内存块，又称为页框；
把逻辑内存也分为同样大小的块，称为页。

帧和页的大小是由硬件来决定的，通常为2的幂。根据计算机结构的不同，大小不同。
早期为512字节至8K字节。现在为4K-64K。

系统保留所有空闲帧的记录。运行一个有N页大小程序，需要找到N个空帧来装入程序。
系统将建立一张页表，记录页与帧之间的映射关系。进程运行时，通过查找页表，实现逻辑地址转换为物理地址。

分页由硬件来处理的。然而，最新的设计是通过将硬件和操作系统相配合来实现的（尤其是在64位的微处理器上）。
采用分页技术不会产生外碎片，因为每个帧都可以分配给选程；分页有内碎片，进程请求的内存可能不是页的整数倍，因此最后一帧中可能存在多余的内存空间。

逻辑内存和物理内存的分页模型

地址转换机制

分页地址被分为：

• 页号（p）——它包含每个页在物理内存中的基址，用来为页表的索引；
• 页偏移（d）——同基址相结合，用来确定送入内存设备的物理内存地址。
  
  我们称上图的逻辑地址为线性地址。

分页的硬件支持

1）根据逻辑地址中的页号p，到页表中找到第p项，第p项内存储的f就是页框号；
2）页框号f和页内偏移d构成物理地址。

根据上图，页大小：4字节；
物理内存：32字节；
逻辑内存：4页。

通过查页表，
20 = 5*4+0，逻辑内存0映射为物理内存20；
25 = 6*4+1，逻辑内存1映射为物理内存25。

操作系统通过一个数据结构来管理物理内存中的空闲帧。这个结构称为空闲帧表，保存系统中所有的空闲帧。

空闲帧的分配：
当进程需要n页。如果系统有至少n帧，那么就分配给新进程。

页表的实现

页表的硬件实现：
当页表较小时，可放入专用寄存器。
将页表保存在内存中，并将页表基址寄存器（PTBR）指向页表，页表限长寄存器（PRLR）表明页表的长度。
在这个机制中，每一次的数据/指令存取需要两次内存存取，一次是存取页表，一次是存取数据/指令。这样内存访问速度会减半。
解决两次存取的问题，是采用小但专用且快速的硬件缓冲，这种缓冲称为转换表缓冲器（TLB）或联想寄存器。

TLB/联想寄存器的条目组成：
键、值实现并行查找。
这种查找方式比较快，但硬件也比较昂贵。所以通常TLB的条目数并不多，通常在64~1024之间。

使用TLB的分页硬件：

页号在TLB中被查找到的百分比称为命中率。这个比率与TLB的大小有关。

有效访问时间（EAT）：
根据概率对每种情况进行加权得到，类似于平均访问时间。
假设查找联想寄存器需要时间为a，内存一次存取时间为b，命中率为λ，则有效访问时间：
EAT=λ（a+b）+（1-λ)(a+2b)

例如，查找TLB需要20ns，访问内存需要100ns，命中率为80%，如果在TLB命中，那么需要120ns；如果未命中，那么需要2次内存访问时间加上TLB访问时间，所以一共需要220ns。
EAT = 0.8*120+0.2*220=140ns
内存访问速度从100ns到140ns，减慢了40%；
如果命中率为98%，可计算出EAT=122ns，内存访问速度只慢了22%。

内存保护

简单方法：把页号和页表限长寄存器值相比较；
细致方法：通过与每个帧相关联的保护位来实现的。

有效-无效位附在页表的每个表项中：

• “有效”表示相关的页在进程的逻辑地址空间，并且是一个合法的页；
• “无效”表示页不在进程的逻辑地址空间中。

通过有效-无效位可以捕捉到非法地址，操作系统可以通过对该位的设置来允许或不允许对某页的访问。

例如上图，有效地址空间为0~10468，如果页的大小为2KB。
页表的0-5是有效的，6,7无效，如果要访问这两页的地址，将产生非法操作。还有由于程序地址只到10468，所以超过该地址的引用都是非法的。但由于对页5的访问是有效的，因此到12287为止的地址都是有效的。这个问题是由页内碎片的存在而引起的。

分页的优点

可以共享公共代码，如果代码是可重入代码（或称为纯代码），则可以在进程间共享（如文本编辑器，编译器，数据库系统）。可重入代码是不可自我修改的代码，不会在执行期间改变。
共享代码必须出现在所有进程的逻辑地址空间的
相同位置。

每个进程单独保留一个代码和数据的副本，还可以有自己的私有代码和数据，存有这些数据的页能够出现在逻辑空间的任意位置。

下一篇 内存管理（二）