OS之内存管理 ---基本的内存管理策略（一）

基本概念

基本硬件

CPU可以直接访问的通用存储只有内存和处理器的内置的寄存器。机器指令可以用内存地址作为参数，而不能用磁盘地址作为参数。所以执行指令以及指令使用的数据，应在这些可执行访问的存储设备上，如果数据不在内存中，那么在CPU使用他们之前应把数据移到内存上。

CPU内置寄存器通常可以在一个CPU时钟周期内完成访问，但是对于内存，完成内存的访问可能需要多个CPU时钟周期，这种结果造成的影响就是如果没有数据用于完成正在执行的指令，那么CPU可能将会多次中断(暂停)。所以需要在CPU和内存之间增加一个高速缓存。

为了确保进程的执行正确，需要为每个进程分配一块单独的内存空间，从而使进程内存空间保护进程而互相不受到影响。通过两个寄存器，通常为基地址寄存器和界限地址寄存器。基地址寄存器中含有最小的合法的物理内存大小；界限地址寄存器中指定了进程范围的大小。内存空间的保护实现是通过在CPU硬件对在用户模式下产生的地址和寄存器的地址进行比较来完成的。也只有操作系统可以通过特殊的特权指令，才能加载基地址寄存器和界限地址寄存器，因为特权指令只能在内核模式下执行，所以只有操作系统可以加载基地址寄存器和界限地址寄存器。

地址绑定

通常程序是作为二进制可执行文件存放在磁盘上的，如果需要执行的话，首先要将程序调入内存并放在进程中。在磁盘上等待调入内存以便执行的进程形成了输入队列。

大多数情况下，用户程序在执行前，需要经过好几个步骤，在这些步骤中，地址可能会有不同的表示形式。源程序中地址通常使用符号表示，编译器通常将这些符号地址绑定到可重定位的地址。链接程序或加载程序在将这些可重定位的地址绑定到绝对地址。每次绑定都是从一个地址空间到另一个地址空间的映射。

通常，指令和数据绑定到存储器地址可在沿途的任何一步中进行：

编译时：如果编译时就已经知道进程将在内存中的驻留地址，那么就可以生成绝对代码，如果将来开始地址发生变化，那么就有必要重新编译代码。
加载时：如果在编译时不知道进程将驻留在何处，那么编译器就应生成可重定位代码。对这种情况，最后绑定会延迟到加载时才进行。如果开始地址发生变化，那么只需要重新加载用户代码以合并更改的值。
执行时：如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定应延迟到执行时才进行。大多数通用操作系统就是采用这种方式的。

逻辑地址空间和物理地址空间

CPU生成的地址通常称为逻辑地址，而内存单元看到的地址(即加载到内存地址寄存器的地址)通常是物理地址。编译时和加载时的地址绑定方法生成相同的逻辑地址和物理地址，但是执行时的地址绑定方案生成不同的逻辑地址和物理地址。在这种情况下，通常成逻辑地址为虚拟地址。

从虚拟地址到物理地址的运行时映射是由**内存管理单元(MMU)**的硬件设备来完成。用户进程所生成的地址在送交到内存之前，都将加上重定位寄存器的值(基地址寄存器)。而用户程序不会看到真实的物理地址。

动态加载

在之前的进程加载到内存中，是将进程的整个程序和所有数据都加载到物理内存当中，所以进程的大小受限于内存的大小，为了获得内存空间利用率，可以采用动态加载。采用动态加载时，一个程序只有在调用时才会加载，所有程序都以可重定位加载格式保存在磁盘中。主程序被加载到内存并执行，当一个程序需要调用另一个程序时，调用程序首先检查另外一个程序是否已经加载到内存中。如果没有，可重定位链接程序会加载所需的程序到内存中，并更新程序的地址表以反映这个变化，接着控制传递给新加载的程序。所以，动态加载的好处就是，只有一个程序需要时才会被加载。

动态链接

动态链接库是系统库，可链接到用户程序，以便运行。

如果是静态链接的话，它的系统库与其他目标模块一样，通过加载程序被合并到二进制程序映像。但是动态链接库类似动态加载(注意在这里不是加载而是链接)，会延迟到运行时。

如果有动态链接，在二进制映像中，每个库程序的引用都有一个存根。存根是一小段代码，用来支出如何定位适当的内存驻留库程序，或者在程序不在内存时应如何加载库。当执行存根时，他首先检查所需程序是否已经在内存中，如果不在，将程序加到内存中。存根会用程序地址来代替自己，并开始执行程序，所以下次在执行程序代码的时候，就可以直接进行，而不会因动态链接产生任何开销。

进程交换

进程必须在内存中以便执行，但是，进程可以短暂的从内存交换到备份存储，当再次执行时在调回到内存中。

标准交换

标准交换在内存和备份存储之间移动进程，备份存储通常是快速磁盘。备份存储应该足够的大，以容纳所有用户的所有内存映像的副本，并且应提供对这些存储器映像的直接访问。系统维护一个可运行的所有进程的就绪队列，他们的映像在备份存储和内存中，当CPU调度器决定要执行一个进程时，它调用分派器。分派器检查队列中的下一个进程是否在内存中，如果不在且没有空闲内存区域，那么分派器会换出当前位于内存的一个进程并换入所需进程，然后重新加载寄存器，并将控制权给所选进程。

移动系统的交换

移动系统通常不支持任何形式的交换，移动设备通常采用闪存，而不是空间更大的硬盘作为他的永久存储。苹果的IOS和谷歌的Android的具体交换策略可以自行百度。

连续内存分配

连续内存分配是早期OS所采用的一种内存分配策略，在采用连续内存分配时每个进程位于一个连续的内存区域，与包含下一个进程的内存相连。

内存保护

为了放置进程访问不属于他们的内存，依旧通过重定位寄存器和界限寄存器来实现保护，MMU通过动态的将逻辑地址加上重定位寄存器的值。当CPU调度器选择一个进程来执行时，作为上下文切换工作的一部分，分派器会用正确的值来加载重定位寄存器和界限寄存器。由于CPU所产生的每个地址都需要与这些寄存器进行核对，所以可以保证操作系统和其他用户的程序和数据不受该运行进程的影响。

内存分配

最简单的内存分配方法，就是将内存分为多个固定大小的分区。每个分区可以只包含一个进程。所以多道程序的程度受限于分区数。

对于可变分区方法，操作系统维护一张表，用于记录哪些内存可用和哪些内存已用。开始时所有内存都可用于用户进程，因此可以作为一大块的可用内存，称为孔。最后内存有一个集合，以包含各种大小的孔。

通常可用的内存块为分散在内存里的不同大小的孔的集合。当新进程需要内存时，系统为该进程查找足够大的孔。如果孔太大，那么就分为两块：一块分给进程，一块返回孔集合。这种方法是通用动态存储分配问题的一个例子。从一组可用孔中选择一个空闲孔的最常用方法有：

首次适应：分配首个足够大的孔，查找可以从头开始，也可以从上次首次适应结束时开始。一旦找到足够大的空闲孔，就可以停止.
最优适应：分配最小的足够大的孔。应查找整个列表，除非列表按大小排序。这种方法可以产生最小剩余孔
最差适应：分配最大的孔。同样应该查找整个列表，除非列表按大小排序这种方法可以产生最大剩余孔。

碎片

用于内存分配的首次适应和最优适应算法都会有外部碎片。对于内存的碎片可以是内部碎片，也可以是外部的。比如假设有一个18464字节大小的孔，有一个进程需要18462字节，如果只能分配所要求的块，那么还剩下2字节的孔。因此通常按固定大小的块为单位来分配内存，采用这种方法，进程所分配的内存可能比所需要的大，这两个数字之差称为内部碎片，这部分内存存在于分区内部，但是又不能用。

外部碎片的一种解决方法是紧缩，移动内存内容，以便将所有的空闲空间合并成一整块。但是紧缩并不是总是可能的。如果重定位是静态的，并且在汇编时或加载时进行的，那么就不能紧缩；只有重定位是动态的，且在运行时进行的，那么才可以采用紧缩。

巴特西