| 在多道程序操作系统当中，同时有多个任务在系统中运行，每个任务都有各自的地址空间。为了实现这种多道程序系统，在存储管理上，最简单的做法就是采用分区存储管理。它的基本思路是：把整个内存划分为两大区域，即系统区和用户区，然后再把用户区划分为若干个分区，分区的大小可以相等，也可以不等，每个任务占用其中的一个分区。这样，就可以在内存当中同时保留多个任务，让它们共享整个用户区，从而实现多个任务的并发运行。在具体实现上，分区存储管理又可以分为两类：固定分区和可变分区。
|
|
|
|
|
| 固定分区存储管理的基本思路是：各个用户分区的个数、位置和大小一旦确定后，就固定不变，不能再修改了。例如，在系统启动时，由管理员来手工划分出若干个分区，并确定各个分区的起始地址和大小等参数。然后，在系统的整个运行期间，这些参数就固定下来，不再改变。另外，为了满足不同程序的存储需要，各个分区的大小可以是相等的，也可以是不相等的。
|
|
|
| 当一个新任务到来时，需要根据它的大小，把它放置到相应的输入队列中去，等待合适的空闲分区。在具体的实现上，主要有两种实现方式，即多个输入队列和单个输入队列。
|
|
|
| 下图（a）是多个输入队列的一个例子。整个内存被分成五个区，包括四个用户分区和一个系统分区。操作系统放在内存地址低端，占用了100KB。分区1、分区2和分区3的大小分别是100KB、200KB和300KB，分区4的大小是100KB。在多个输入队列的方式下，对于每一个用户分区，都有一个相应的输入队列。在分区1的输入队列中有三个任务在等待，在分区2的输入队列中有一个任务在等待。分区3的输入队列是空的，而分区4的输入队列中有两个任务在等待。当一个新任务到来时，就把它加入到某一个输入队列中去。要求这个输入队列所对应的分区，是能够装得下该任务的最小分区。例如，假设现在又来了一个新任务，它的大小是180KB，那么应该把它加入到分区2的输入队列中去。因为在当前情形下，能够装得下该任务的只有分区2和分区3，而分区2比分区3要小，所以它更合适。
|
|
|
|
|
|
|
| 这种为每一个分区都设置一个输入队列的做法，有一个很大的缺点，它可能会出现内存利用率不高的问题，即小分区的输入队列是满的，而大分区的输入队列却是空的。例如，在上图（a）的这个例子中，在分区1的输入队列中，有3个任务在等待，而分区3的输入队列却是空的。也就是说，一方面，有很多小任务在等着进入内存；而另一方面，在内存中却存在着大量的空闲空间。事实上，如果把这300KB的空闲空间平均分给这三个任务，那么它们就都能进入内存了。
|
|
|
| 为了解决这个问题，人们又提出了单个输入队列的方法。它的基本思路是：对于所有的用户分区，只设置一个统一的输入队列。当一个新任务到来时，就把它加入到这个输入队列当中。然后当某个分区变得空闲的时候，就从这个队列中选择合适的任务去占用该分区。在任务的选择上，可以有两种方法。第一种方法是选择离队首最近的、能够装入这个分区的任务。如果选中的是一个比较小的任务，那么就会浪费大量的内存空间。第二种方法是先搜索整个队列，从中选择能够装入这个分区的最大任务，这样就能尽可能地减少所浪费的空间。
|
|
|
| 对于固定分区的存储管理方法，它的优点是易于实现，系统的开销比较小。无论是空闲空间的管理，还是内存的分配和回收算法，都非常简单。算法的时间复杂度和空间复杂度也比较低。因此，系统的管理开销比较小。但是它也有两个主要的缺点：第一，内存的利用率不高，内碎片会造成很大的浪费。所谓的内碎片，就是在任务所占用的分区内部，未被利用的空间。第二，分区的总数是固定的，这就限制了并发执行的程序个数。如果一开始只分了N个分区，那么最多只能有N个任务在同时运行，不够灵活。
|
|
|
|
|
| 可变分区的基本思路是：分区不是预先划分好的固定区域，而是动态创建的。在装入一个程序时，系统将根据它的需求和内存空间的使用情况来决定是否分配。具体来说，在系统生成后，操作系统会占用内存的一部分空间，这一般是放在内存地址的最低端，其余的空间则成为一个完整的大空闲区。当一个程序要求装入内存运行时，系统就会从这个空闲区当中划出一块来，分配给它，当程序运行结束后会释放所占用的存储区域。随着一系列的内存分配和回收，原来的一整块的大空闲区就会形成若干个占用区和空闲区相间的布局。
|
|
|
| 下图是一个可变分区的例子。在系统当中，整个内存区域有1024KB。如下图（a）所示，在初始化的时候，操作系统占用了内存地址最低端的128KB。剩下的空间就成为一个完整的大空闲区，总共是896KB。然后，任务1进入了内存，它需要的内存空间是320KB，因此紧挨着操作系统，给它分配了一块大小为320KB的内存，也就是说，创建了一个新的用户分区，该分区的起始地址是128KB，大小是320KB。此时，剩余的内存空间还有576KB，而且还是连续的一整块。接下来，任务2和任务3先后进入内存，它们需要的内存空间分别是224KB和288KB，因此紧挨着任务1，给它们分配了两块内存空间，大小分别是224KB和288KB，也就是说，又创建了两个新的用户分区。此时，在内存中总共有3个任务，连同操作系统，总共占用了960KB的内存空间。因此，在地址空间的最高端，只剩下一小块64KB的空闲区域，如下图（b）所示。接下来，任务2运行结束，系统回收了它所占用的内存分区。然后任务4进入内存，它的大小为128KB，因此就把刚才存放任务2的那个分区，一分为二，一部分用来存放任务4，另一部分是96KB的空闲区。接下来，任务1也运行结束，系统回收了它所占用的分区。因此，内存空间的最后状态如下图（c）所示。从图中可以看出，随着系统不断运行，空闲区就变得越来越小，越来越碎了，它们被分隔在内存的不同位置，形成了占用区和空闲区交错在一起的局面。
|
|
|
|
|
|
|
| 可变分区存储管理的优点是：与固定分区相比，在可变分区当中，分区的个数、位置和大小都是随着任务的进出而动态变化的，非常灵活。当一个任务要进入内存的时候，就在空闲的地方创建一个分区，把它装进来；当任务运行结束后，就把它所占用的内存分区给释放掉。这样，就避免了在固定分区当中由于分区的大小不当所造成的内碎片，从而提高了内存的利用效率。在可变分区的存储管理当中，不会出现内碎片的现象，因为每个分区都是按需分配的，分区的大小正好等于任务的大小，因此不会有内碎片。
|
|
|
| 可变分区存储管理的缺点是：可能会存在外碎片。所谓的外碎片，就是在各个占用的分区之间，难以利用的一些空闲分区，这通常是一些比较小的空闲分区。例如，在上图（c）当中，对于64KB这个空闲区，它只能分配给那些不超过64KB的任务，如果所有的任务都大于64KB的话，那么它就用不上了，变成了一个外碎片。另外，这种可变分区的办法，使得内存的分配、回收和管理变得更加复杂了。
|
|
|
| 在具体实现可变分区存储管理技术的时候，需要考虑三个方面的问题：内存管理的数据结构、内存的分配算法以及内存的回收算法。
|
|
|
| 在内存管理的数据结构上，系统会维护一个分区链表，来跟踪记录每一个内存分区的情况，包括该分区的状态（已分配或空闲）、起始地址、长度等信息。具体来说，对于内存当中的每一个分区，分别建立一个链表结点，记录它的各种管理信息。然后，将这些结点按照地址的递增顺序进行排列，从低到高，从而形成一个分区链表。
|
|
|
| 在内存的分配算法上，当一个新任务来到时，需要为它寻找一个空闲分区，其大小必须大于或等于该任务的要求。若是大于要求，则将该分区分割成两个小分区，其中一个分区为要求的大小并标记为“占用”，另一个分区为余下部分并标记为“空闲”。选择分区的先后次序一般是从内存低端到高端。通常的分区分配算法有：最先匹配法、下次匹配法、最佳匹配法和最坏匹配法。
|
|
|
| .最先匹配法：假设新任务对内存大小的要求为M，那么从分区链表的首结点开始，将每一个“空闲”结点的长度与M进行比较，看是否大于或等于它，直到找到第一个符合要求的结点。然后把它所对应的空闲分区分割为两个小分区，一个用于装入该任务，另一个仍然空闲。与之相对应，把这个链表结点也一分为二，并修改相应内容。
|
|
|
| .下次匹配法：与最先匹配法的思路是相似的，只不过每一次当它找到一个合适的结点（分区）时，就把当前的位置记录下来。然后等下一次新任务到来的时候，就从这个位置开始继续往下找（到链表结尾时再回到开头），直到找到符合要求的第一个分区。而不是像最先匹配法那样，每次都是从链表的首结点开始找。
|
|
|
| .最佳匹配法：将申请内存的任务装入到与其大小最接近的空闲分区当中。算法的最大缺点是分割后剩余的空闲分区将会很小，直至无法使用，从而造成浪费。
|
|
|
| .最坏匹配法：每次分配时，总是将最大的空闲区切去一部分分配给请求者，其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区，从而避免了空闲区越分越小的问题。这种算法基本不留下小的空闲分区，但较大的空闲分区也不被保留。
|
|
|
| 在内存的回收算法上，当一个任务运行结束并释放它所占用的分区后，如果该分区的左右邻居也是空闲分区，则需要将它们合并为一个大的空闲分区。与此相对应，在分区链表上，也要将相应的链接结点进行合并，并对其内容进行更新。
|
|
|
|
|
| 下图是一个嵌入式系统的内存布局，主要是堆空间的管理。如下图所示，整个堆空间被划分为两部分：一部分是内存块池；一部分是字节池。前者即为固定分区的存储管理方式，后者即为可变分区的存储管理方式。需要说明的是，这里的分区存储管理讨论的并不是各个任务的地址空间，而是系统的堆空间，即各个任务在运行的时候，如果它们需要使用动态内存，就会通过类似于malloc的函数提出申请，系统就会从堆当中分配相应的空间，满足任务的动态内存请求，而不是把整个任务装进来。
|
|
|
|
|
|
|
| 下图（a）是内存块池的具体分布。该区域总的大小为1408KB，被划分为不同大小的块。例如，大小为64B的块有1024个，共64KB；大小为512B的块有32个，共16KB，等等。最大的块为512KB，只有一个。另外，当任务去申请一块内存空间时，其大小并不一定与某个块的大小正好相同。例如，假设任务申请的对象大小为9KB，系统只能将一个16KB的块分配给它，所以内碎片为7KB。
|
|
|
|
|
|
|
| 上图（b）是字节池的示意图，任务可以申请一块任意大小的内存空间。在当前状态下，如果下一次请求的大小不超过段1，就会把它一分为二，满足此次请求。另外，虽然在系统中有四块空闲分区，但它们并没有连接在一起。因此，当任务在提出内存申请的时候，能够满足的最大请求为段5和段6这两块分区之和。实际上，在内存回收算法当中，应该会把这两个相邻的分区进行合并，合成一个大的空闲分区。
|
|
|
