1 背景
内存是现代计算机运行的中心，内存由很大一组字或字节组成，每个字或字节都有它们自己的地址，CPU根据程序计数器的值从内存中读取指令，这些指令可能会引起进一步对特定内存地址的读取和写入。一个典型的指令执行周期，首先从内存中读取指令，接着该指令被解码，且可能需要从内存中读取操作数，在指令对操作数执行后，其结果可能被存回到内存。
CPU能直接访问的存储器只有内存和处理器内的寄存器，机器指令可以用内存地址作为参数，而不能用磁盘地址作为参数。因此，执行指令以及指令使用的数据必须在这些直接可访问的存储设备上。如果数据不在内存中，那么在使用CPU前必须先把数据移到内存中。
CPU内置寄存器通常可以在一个CPU时钟周期内访问完成，完成对内存的访问可能需要多个CPU时钟周期，而且通常会出现等待的情况。由于内存访问频繁，这种情况难以忍受，解决方法是在CPU与内存之间增加高速内存，成为高速缓存（cache）。
为了确保操作系统不被用户进程所访问，以及确保用户进程不被其他用户进程访问，需要确保每个进程都有独立的内存空间。这种保护通过两个寄存器实现，即基地址寄存器和界限地址寄存器。基地址寄存器含有最小的合法物理内存地址，而界限地址寄存器决定了范围的大小。
通常程序以二进制可执行文件的形式存储在磁盘上，为了执行，程序被调入内存并放在进程空间内。根据所使用的内存管理方案，进程在执行时可以在磁盘和内存之间移动，在磁盘上等待调入内存以便执行的进程形成输入队列。许多系统允许用户进程放在物理内存的任意位置，源程序中的地址的通常是用符号来表示的，编译器通常将这些符号地址绑定在可重定位的地址，链接程序或加载程序再将这些可重定位的地址绑定成绝对地址，每次绑定都是从一个地址空间到另一个地址空间的映射。
通常，将指令与数据绑定到内存地址有以下三种情况：编译时可以生成绝对代码；加载时必须生成可重定位代码；执行时是绝大多数通用计算机操作系统采用的方法。
CPU所生成的地址通常称为逻辑地址（logical address），而内存单元所看到的地址通常称为物理地址。将逻辑地址映射成物理地址的是内存管理单元(memory management unit),逻辑地址的意义在于让每个用户进程都拥有独立的地址空间。编译和加载时的地址绑定方法生成相同的逻辑地址和物理地址，执行时的地址绑定方案导致不同的逻辑地址和物理地址。基地址寄存器在这里称为重定位寄存器，用户进程所生成的地址在送交内存之前，都将加上重定位寄存器的值，如下图所示。
2 交换
进程需要在内存中以便执行，不过，进程可以暂时从内存中交换到备份存储上，当需要再次执行时再调回到内存中。当每个进程用完时间片，它将与另一进程进行交换，在理想情况下，内存管理器可以足够快的速度交换进程，以便当CPU调度器需要调度CPU时，总有进程在内存中可以执行。除此之外，时间片必须足够大，以保证交换之间可以进行一定量的计算。
这种交换策略的变种被用在基于优先级的调度算法中，当更高优先级的进程执行完后，低优先级进程可以交换回内存以继续执行。交换需要备份存储，备份存储通常是快速磁盘。系统有一个就绪队列，它包括在备份存储或在内存中准备运行的所有进程。交换系统的上下文切换时间比较长，为了有效使用CPU，需要使每个进程的执行时间比交换时间长，交换时间的主要部分是转移时间。
3 连续内存分配
内存通常分为两个区域：一个用于驻留操作系统，另一个用于用户进程。通常需要将多个进程同时放在内存中，因此需要考虑如何为输入队列中需要调入内存的进程分配内存空间。
在分配内存时，需要考虑到内存映射与保护问题，这种保护通过重定位寄存器和界限地址寄存器实现，MMU动态地将将逻辑地址加上重定位寄存器值后映射成物理地址，映射后的物理地址再送给内存单元，如图所示。
最为简单的内存分配方法之一就是将内存非为多个固定大小的分区，每个分区只能容纳一个进程。当一个分区空闲时，可以从输入队列中选择一个进程，调入到空闲分区。现在使用更多的是可变分区，在该方案中，操作系统有一个表，用于记录哪些内容可用和哪些内存一杯占用。
在任意时候，有一组可用内存大小列表和输入队列，操作系统根据调度算法来对输入队列进行排序，并不断给进程分配内存。通常，存在一组不同大小的内存，如果内存太大，那么就分为两块：一块分配给进程，另一块返回给内存集合。从一组可用内存中选择一个空闲内存的方法有：首次适应、最佳适应和最差适应，除此之外，还有一种伙伴系统（buddy system）。
| 匹配算法 | 思路 | 优点 | 缺点 |
|---|---|---|---|
| 首次适应匹配 | 分配第一个足够大的内存块 | 管理简单，倾向于保留高地址空间的内存给后期的大作业 | 低地址部分不断被划分，变成很多小的空闲块，加大了查找的开销 |
| 最佳适应匹配 | 分配最小的足够大的内存块 | 碎片达到最小 | 需要将所有的空闲内存块管理起来，带来了一定的开销，同时会产生很多的小块的难以利用的内存碎片 |
| 最差适应匹配 | 分配最大的内存块 | 寻找内存块的速度非常快，同时内存碎片往往较大 | - |
| 伙伴系统 | 将内存每次对半分，直到恰好大于需要分配的大小 | 极大的解决了内存的外碎片问题 | 一个很小的块可能就会阻止一个大块的回收，对内存块的分配和释放开销也比较大 |
首次适应和最佳适应方法都有外部碎片问题，该问题是指当所有总的内存之和可以满足请求但并不连续。内存碎片可以是外部的，也可以是内部的。通常将内存以固定大小的块为单位来分配，可能导致分配的内存比内存需要的大，多出来内存在分区内，但是并不能使用，成为内部碎片。
一种解决外部碎片问题的方法是紧缩,思路是移动内存内容，以便所有空闲空间合并成一整块，但这种方法并非总是可能的，而且有可能开销巨大。另一种方法是允许物理地址空间为非连续，只要有物理内存就可为进程分配，这种方案有两种互补的技术：分页和分段。
小结：
连续分配的缺点：
- 分配给程序的物理内存必须是连续的很难做到
- 存在外部内存碎片和内部内存碎片
- 内存分配的动态修改困难
非连续内存分配的目标：提高内存利用率和管理灵活性
- 允许一个进程使用非连续的物理地址空间爱你
- 允许共享代码与数据
- 支持动态加载和动态链接
4 分页
分页（paging）内存管理方案允许进程的物理地址空间可以是非连续的，避免了将不同大小的内存块匹配到交换空间上的麻烦。当位于内存中的代码或数据需要换出时，必须现在备份存储上找到空间。各种形式的分页由于其优越性，因此通常为绝大多数操作系统所采用。
实现分页的基本方法是将物理内存分为固定大小的块，成为帧（frame）；而将逻辑内存也分为同样大小的块，称为页（page）。当需要执行进程时，其页从备份存储中调入到可用的内存帧中。备份存储也分为固定大小的块，其大小与内存帧一样。
分页硬件支持如下图所示，有CPU生成的每个地址分为两个部分：页号（p）和页偏移（d）。页号作为页表（page table）中的索引，包含每页所在物理内存的基地址，这些基地址与页偏移的组合就是物理地址，可以送交内存单元。
分页技术不会产生外部碎片：每个帧都可以分配给需要的进程。但是会产生内部碎片，如果进程所要求的内存并不是页的倍数，那么最后一个帧就用不完。通常，页的大小为4～8KB。分页的一个重要特点是用户视角的内存和实际的物理内存的分离，两者之间的差异是通过地址转换硬件协调的。
操作系统使用帧表（frame table）管理物理内存，每个条目对应着一个帧，表示该帧是否被占用，被哪个进程占用。操作系统为每个进程维护一个页表的副本，用来将逻辑地址映射成物理地址。当进程分配到CPU时，CPU调度程序可以根据该页表副本定义硬件页表，因此分页增加了切换时间。
页表的硬件实现有多种方法，最简单的是将页表作为一组专用寄存器来实现，如果页表比较小，该方法是可行的。所以需要将页表放在内存中，并将页表基寄存器（page-table base register， PTBR）指向页表。采用这种方案访问一个字节需要两次内存访问，一次用于页表条目，一次用于字节。
这一问题的解决方法是采用小但专用且快速的硬件缓冲，称为转换表缓冲区（translation look-aside buffer， TLB）。TLB与页表一起使用的方法如下：TLB只包含页表中的一小部分条目，当CPU产生逻辑地址后，页号提交给TLB。如果找到页号，也就得到了帧号；如果找不到，那么就需要访问页表，同时将页号和帧号添加到TLB中。如下图所示。
分页的优点之一在于可以共享公共代码，如果代码是可重用的，则可以共享。可重用代码是不能自我修改的代码，不会在执行期间改变，因此两个或更多的进程可以在相同的时间执行相同的代码。
5 分段
采用分页内存管理有一个不可避免的问题：用户视角的内存和实际物理内存的分离。用户通常不愿意将内存看做一个线性字节数组，而是一组不同长度的段的集合，这些段之间没有一定的顺序。段（segment）表示访问方式和存储数据等属性相同的一段地址空间，对应一块连续的内存块，若干个段组成进程的逻辑地址空间。用户通过段名称和偏移来实现对段的访问。
用户通过二维地址来访问内存中的字节，但物理内存是一维的，两者之间的映射方式是段表（segment table）。段表的每个条目都有段基地址和段界限，段基地址包含该段在内存中的开始物理地址，而段界限制定该段的长度。段表的使用如下所示。
