原文：http://www.cnitblog.com/tarius.wu/articles/322.html

现代操作系统及CPU硬件中，都会提供内存管理单元（memory management unit，MMU）来进行内存的有效管理。内存管理算法有许多，从简单的裸机方法到分页和分段策略。各种算法都有其优缺点，为特定系统选择内存管理算法依 赖于很多因素，特别是系统的硬件设计。

1 内存管理的目的

内存管理的目的是为了更好的使用内存。 内存是现代操作系统运行的中心。操作系统中任何一个进程的运行都需要内存，但是，操作系统中的内存是有限的；另一方面，从安全的角度出发，进程都需要有自 己的内存空间，其他的进程都不能访问这个私有的空间；同时，内存的分配会导致内存碎片问题，严重影响计算机的性能。以上这三个问题就是一般内存管理算法所 需要处理的目标。

• 交换
• 内存保护
• 碎片问题
  

2 交换

进程需要在内存中执行，但进程可以暂时从内存中交换（swap）出去到备份存储上，当需要时再调回到内存中去。

在基于优先级的交换调度算法中，如果一个更高优先级的进程来了且需要服务，内存管理可以交换出低优先级的进程，以便装入和执行更高优先级的进程。当高优先级的进程执行完毕之后，低优先级的进程可以交换回内存继续执行。这种交换有时被称之为滚出(roll out)、滚进(roll in)。

通常一个交换出的进程需要交换回它原来的内存空间。这一限制是由地址捆绑方式决定的。如果捆绑是在汇编时或加载时决定的，那么就不可以移动到不同的位置。如果捆绑是在运行时决定，由于物理地址是在运行时才确定，那么进程可以移到不同的地址空间。

交换的代价：交换时间

交换时间主要是指转移时间，总的转移时间和所交换的内存空间成正比。交换不需要或只需要很少的磁头移动，简单的说，交换空间通常作为磁盘的一整块，且独立于文件系统（如Linux的swap空间），因此使用就有可能很快。

交换需要花很多时间，而且进程执行时间却很少，故交换通常不执行，但只有在许多进程运行且内存吃紧时，交换才开始启动。

3 分页

3.1内存保护和内存碎片的背景

内存保护是指操作系统进程不受用户进程的影响，保护用户进程不受其他用户进程的影响。内存保护最基本的思路是进程使用逻辑地址空间，而内存管理单元所看的是物理地址。操作系统将逻辑地址分配给进程，MMU负责逻辑地址到物理地址的映射（转换，捆绑）。

值得注意的是对于指令（程序）和数据映射到内存地址可以在以下步骤地任意一步执行：

• 编译时：如果编译时就知道进程将在内存中的驻留地址，那么就可以生成绝对代码。如MS-DOS的COM格式程序。
• 加载时：如果编译时不知道程序将驻留在何处，那么编译器就必须要生成可重定位代码(relocatable code )。这种情况下，最后地址映射会延迟到加载时才确定，如果开始地址发生变换，必须重新加载程序，以引入新值。
• 执行时：如果进程在执行时可以从一个内存段移到另一个内存段，那么映射必须延迟到执行时才进程。采用这种方法需要硬件的支持，目前绝大多数操作系统采用这种方法（基于分页、分段等）。

内存碎片是操作系统内存分配的产物。最初操作系统的内存是连续分配的，即进程A需要某一大小的内存空间，如200KB，操作系统就需要找出一块至少200KB的连续内存空间给进程A。随着系统的运行，进程终止时它将释放内存，该内存可以被操作系统分配给输入队列里的其他等待内存资源的进程。

可以想象，随着进程内存的分配和释放，最初的一大块连续内存空间被分成许多小片段，即使总的可用空间足够，但不再连续，因此产生的内存碎片。

一 个办法是不再对内存空间进行连续分配。这样只要有物理内存就可以为进程进行分配。而实际上，不进行连续分配只是相对的，因为完全这样做的代价太大。现实 中，往往定出一个最小的内存单元，内存分配是这最小单元的组合，单元内的地址是连续的，但各个单元不一定连续。这样的内存小单元有页和段。

当然，分段和分页也会产生碎片，但理论上每个碎片的大小不超过内存单元的大小。

3.2 分页

分页时一种内存管理方案，同时也提供了内存保护机制。它允许分配的物理内存地址可以是非连续的。

逻辑内存分为大小相等块的组合，这个块称之为页；物理内存则分为固定大小的帧(frame)。页大小应和帧大小相同，这是由硬件决定的。通常是2的幂，这样可以方便地将逻辑地址映射到物理地址。

基于分页的逻辑地址到物理地址的映射

考虑32位地址。如果页大小是4KB，则需要12位来表示每一页中的某个具体地址，因此32位的逻辑地址中需要12位来对某一页中的具体地址寻址。这12位叫做页偏移。剩下的20位可以作为页码，可以有1M的页。逻辑地址可以表示为：

寻址时，根据页码P查页表，找到该页对应的帧，将帧号与页偏移（也是帧偏移）组合即得到物理地址。这样也说明了为什么页大小要等于帧大小，因为页数要等于帧数。

例如，页大小为4K，页码11对应的帧码是10，即表示是第10块物理帧，也偏移为5，则逻辑地址0X0000b 005对应的物理地址是0X0000a 005。

3.3 分页的内存保护

基于分页的操作系统在分配内存时分给进程所需要的页数，其对应物理内存的帧号同时装入该MMU的页表。同时页表上有一个标记为，指明该页是属于哪个进程的。甚至可以定义该页对于某个进程的读写权限。非法的读写操作会产生硬件陷阱（或内存保护冲突）。

3.4 分页的代价

由上一节可知分页是基于查找表的，而在内存中存储这个1M个项目的页表本身就带来了内存消耗和查找速度问题。于是，页表通常需要硬件的支持，即将页表写在硬件MMU的寄存器中。

如果页表比较小，那么页表写在寄存器中可以加快查找速度。但绝大多数当代的计算机页表都非常大。对于这些页表，采用快速寄存器来实现页表就不太合理了。

一种办法是使用TLB（translation look-aside buffer）。TLB是关联的寄存器，TLB条目由两部分组成：页号和帧号。

TLB只包含页表中的一小部分条目，整个页表还是保存在内存中。当CPU产生逻辑地址后，其页号提交给TLB。如果找到了页号，那同时也就找到了帧号，就可以访问物理内存；如果页号不在TLB中（称为TLB失效），那就需要访问页表。在页表中找到帧号后，把页号和帧号增加到TLB中，这样下次再用时可以很快找到。如果TLB中条目已满，则操作系统会根据一个替换策略来替换条目。替换策略有很多，从最近最小使用替换到随机替换等。另外，有的TLB允许某些条目不被替换，如内核代码的条目。

有的TLB还在条目中保存地址空间保护标志符，用来唯一标志进程，以提供进程内存保护。

3.5 页表结构

对于32位以及64位逻辑地址的计算机来说，其页表实在太过庞大。为了压缩页表，一个简单的方法是使用层次化分页算法，就是将页表再分页。（这实际上是一种索引的方法）

即将2^20个页表项分为2^10个组，每个组里面有2^10项。这样只需要2K*4=8K的页表空间，且查找速度也有很大提升。例如原先最坏情况下要查2^20次，现在最坏只要2*2^10次。