连续内存分配 _内存分配

文章插图

内存必须容纳操作系统和各种用户进程，因此应该尽可能有效的分配内存的各个部分。

内存通常分为两个区域，一个用于驻留操作系统，另一个用于用户进程。操作系统可以位于低内存，也可以位于高内存，影响这一决定的主要因素是中断向量的位置，由于中断向量通常位于低内存，因此程序员通常将操作系统页放在低内存。

内存映射与保护
在说内存分配之前，先说说内存映射与保护的问题，通过采用重定位寄存器和界限地址寄存器，可以实现这种保护。
重定位寄存器含有最小的物理地址值，界限地址寄存器含有逻辑地址的范围值(例如：重定位=100050，界限=74500) 。有了重定位寄存器和界限地址寄存器，每个逻辑地址必须小于界限地址寄存器。MMU动态的将逻辑地址加上重定位寄存器的值后映射成物理地址，映射后的物理地址再交送内存单元。
当CPU调度器选择一个进程来执行时，作为上下文切换工作的一部分，调度程序会用正确的值来初始化重定位寄存器和界限地址寄存器。由于CPU所产生的每一地址都需要与寄存器进行核对，所以可以保证操作系统和其他用户程序和数据不受该进程的运行所影响。
内存分配
现在我们就来讨论一下内存分配，最简单的内存分配方式之一就是将内存分为多个固定大小的分区(parttiion) 。每个分区只能容纳一个进程，因此，多道程序的程度会受到分区数所限制。如果使用这种多分区方法，当一个分区空闲的时候，可以从输入队列中选择一个进程，以调入到空闲分区，当进程终止时，其分区可以被其他进程所使用。这种方法最初为IBM OS/360 操作系统所使用，不过现在已经不再使用了。
下面来介绍可变分区方案。在可变分区方案里，操作系统有一个表,用于记录哪些内存可用和哪些内存已经被使用，在一开始，所有的内存都可用于用户进程，因此可以作为一大块可用内存，称为孔(hole) 。当有新进程需要内存时，为该进程查找足够大的孔，如果找到，可以从该进程分配所需的内存，孔内未分配的内存可以下次再用。
随着进程进入系统，它们将被加入到输入队列，操作系统根据所有进程的内存需要和现有可用内存情况来决定哪些进程可以分配内存。当进程分配到空间时，它就装入内存，并开始竞争CPU，当进程终止的时候，它将释放内存，该内存可以被操作系统分配给输入队列中的其他进程。
在任意的时候，有一组可用孔(块)大小列表和输入队列，操作系统根据调度算法来对输入队列进行排序，内存不断地分配给进程，直到下一个进程的内存需求不能满足为止，这时没有足够大的可用孔来装入进程。操作系统可以等到有足够大的空间。或者往下扫描输入队列以确定是否有其他内存需求较小的进程可以被满足。
通常，一组不同大小的孔分散在内存中，当新进程需要内存时，系统为该进程查找足够大的孔，如果孔太大，那么就分为两块：一块分配新进程，另一块还回到集合。当进程终止时，它将释放其内存，该内存将还给孔集合，如果新孔与其他孔相邻，那么将这些孔合并成大孔，这时，系统可以检查是否有进程在等待内存空间，新合并的内存空间是否满足等待进程。
分配方法
上面讲的这种方法是通用动态存储分配问题的一种情况(根据一组空闲孔来分配大小为 n 的请求) 。这个问题有许多解决方法，从一组可用孔中选择一个空闲的最常用方法有首次适应(first-fit)、最佳适应(best-fit)、最差适应(worst-fit) 。

首席适应:分配第一个足够大的孔，查找可以从头开始，也可以从上次首次适应结束时开始，一旦找到足够大的空闲空间孔，就可以停止。
最佳适配: 分配最小的足够大的孔，必须查找整个列表，除非列表按大小排序，这种方法可以产生最小剩余孔。
最差适应: 分配最大的孔，同样，必须查找整个列表，除非列表按大小排序，这种方法可以产生最大剩余孔，该孔可能比最佳适应方法产生的比较剩余孔更为有用。

碎片
【连续内存分配】首次适应方法和最佳适应方法都有外部碎片问题,随着进程的装入和移出内存，空闲内存被分为小片段，当所有总的可用内存之和可以满足请求，但并不连续时，这就出现了外部碎片的问题。这个问题可能很严重。在最坏的情况下，每两个进程之间就有空闲块(或浪费) 。如果这些内存块是一整块，那么就可以再运行多个进程。