连续分配存储管理方式
目录
参考资料：
为了能将用户程序装入内存，必须为它分配一定大小的内存空间。连续分配方式是最早出现的一种存储器分配方式，曾被广泛应用于上世纪 60~80 年代的 OS 中，该分配方式为一个用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻。连续分配方式可分为四类：单一连续分配、固定分区分配、动态分区分配以及动态可重定位分区分配算法四种方式。
1 单一连续分配
在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提供给 OS 使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。
虽然在早期的单用户、单任务操作系统中，有不少都配置了存储器保护机构，用于防止用户程序对操作系统的破坏，但在 20 世纪 80 年代所产生的几种常见的单用户操作系统中，如 CP/M、MS-DOS 及 RT11 等，并未采取存储器保护措施。这是因为，一方面可以节省硬件，另一方面在单用户环境下，机器由一用户独占，不可能存在其他用户干扰的问题，因此这是可行的。即使出现破坏行为，也仅仅会是用户程序自己破坏操作系统，其后果并不严重，只会影响该用户程序的运行，且操作系统也很容易通过系统的再启动而重新装入内存。
- 单用户系统
2 固定分区分配
为了能在内存中装入多道程序，且使这些程序之间又不会发生相互干扰，于是将整个用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，这样就形成了最早的、也是最简单的一种可运行多道程序的分区式存储管理方式。如果在内存中有四个用户分区，便允许四个程序并发运行。当有一空闲分区时，便可以再从外存的后备作业队列中选择一个适当大小的作业，装入该分区。当该作业结束时，又可再从后备作业队列中找出另一作业调入该分区。
2.1 划分分区的方法
可用下述两种方法将内存的用户空间划分为若干个固定大小的分区：
- 分区大小相等（指所有的内存分区大小相等）。其缺点是缺乏灵活性，即当程序太小时，会造成内存空间的浪费。当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。尽管如此，对于利用一台计算机同时控制多个相同对象的场合，因为这些对象所需的内存空间大小往往相同，这种划分方式比较方便和实用，所以被广泛采用。例如，炉温群控系统就是利用一台计算机去控制多台相同的冶炼炉。
- 分区大小不等。为了增加存储器分配的灵活性，应将存储器分区划分为若干个大小不等的分区。最好能对常在该系统中运行的作业大小进行调查，根据用户的需要来划分。通常，可把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区，这样，便可根据程序的大小，为之分配适当的分区。
2.2 内存分配的方法
为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态（是否已分配）。当有一用户程序要装入时，由内存分配程序依据用户程序的大小检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为 “已分配”。若未找到大小足够的分区，则拒绝为该用户程序分配内存。//使用分区表来维护分区情况
固定分区分配是最早出现的、可用于多道程序系统中的存储管理方式，由于每个分区的大小固定，必然会造成存储空间的浪费，因而现在已很少将它用于通用的 OS 中。但在某些用于控制多个相同对象的控制系统中，由于每个对象的控制程序大小相同，是事先已编好的，其所需的数据也是一定的，故仍采用固定分区式存储管理方式。//固定分区分配方式存在内存浪费问题
3 动态分区分配
动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样三方面的问题。
3.1 动态分区分配中的数据结构
为了实现动态分区分配，系统中必须配置相应的数据结构，用以描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有以下两种形式：
空闲分区表：在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项。
空闲分区链：为了实现对空闲分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。为了检索方便，在分区尾部重复设置状态位和分区大小表目。当分区被分配出去以后，把状态位由 “0” 改为 “1”，此时，前、后向指针已无意义。//通过链表来管理分区
3.2 动态分区分配算法
为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。// 内存分配算法对系统性能有很大的影响，后续将详细介绍
3.3 分区分配操作
在动态分区存储管理方式中，主要的操作是分配内存和回收内存。
分配内存
系统应利用某种分配算法，从空闲分区链（表）中找到所需大小的分区。
设请求的分区大小为 u.size，表中每个空闲分区的大小可表示为 m.size。若 m.size - u.size <= size（size 是事先规定的不再切割的剩余分区的大小），说明多余部分太小，可不再切割，将整个分区分配给请求者。//当分区不能再切割时，分配整个分区
否则（即多余部分超过 size），便从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链（表）中。然后，将分配区的首址返回给调用者。
回收内存
当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链（表）中找到相应的插入点，此时可能出现以下四种情况之一：//回收操作就是把空闲内存重新放回空闲分区表的过程
- 回收区与插入点的前一个空闲分区 F1 相接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区 F1 的大小。
- 回收分区与插入点的后一空闲分区 F2 相接。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
- 回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并使用 F1 的表项和 F1 的首址，取消 F2 的表项，大小为三者之和。
- 回收区既不与 F1 邻接，又不与 F2 接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。
4 基于顺序搜索的动态分区分配算法
为了实现动态分区分配，通常是将系统中的空闲分区链接成一个链。所谓顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。基于顺序搜索的动态分区分配算法有如下四种：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法。//适用于分区不是很多的系统
4.1 首次适应（first fit，FF）算法
FF 算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已没有足够大的内存分配给该进程，内存分配失败，返回。
该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，称为碎片。而每次查找又都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销。
4.2 循环首次适应（next fit，NF）算法
为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。
为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。
4.3 最佳适应（best fit，BF）算法
所谓“最佳”是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区必然是最佳的。
孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的碎片。
4.4 最坏适应（worst fit，WF）算法
由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反：它在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。
实际上，这样的算法未必是最坏的，它的优点是可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利。同时，最坏适应分配算法查找效率很高，该算法要求，将所有的空闲分区，按其容量以从大到小的顺序形成一空闲分区链，查找时，只要看第一个分区能否满足作业要求即可。
5 基于引搜索的动态分区分配算法
基于顺序搜索的动态分区分配算法，比较适用于不太大的系统。当系统很大时，系统中的内存分区可能会很多，相应的空闲分区链就可能很长，这时采用顺序搜索分区方法可能会很慢。为了提高搜索空闲分区的速度，在大、中型系统中往往会采用基于索引搜索的动态分区分配算法，目前常用的有快速适应算法、伙伴系统和哈希算法。
5.1 快速适应（quick fit）算法
该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表。同时，在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。//就像一张 hash 表
空闲分区的分类是根据进程常用的空间大小进行划分的，如 2KB、4KB、8KB 等，对于其它大小的分区，如 7KB 这样的空闲区既可以放在 8KB 的链表中，也可以放在一个特殊的空闲区链表中。
该算法在搜索可分配的空闲分区时分为两步：
- 第一步是根据进程的长度，从索引表中去寻找到能容纳它的最小空闲区链表；
- 第二步是从链表中取下第一块进行分配即可。
另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。优点是查找效率高。
该算法的主要缺点在于为了有效合并分区，在分区归还主存时的算法复杂，系统开销较大。此外，该算法在分配空闲分区时，是以进程为单位的，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。这是典型的以空间换时间的做法。
5.2 伙伴系统（buddy system）
该算法规定，无论已分配分区或空闲分区，其大小均为 2 的 k 次幂（k 为整数）。假设系统的可利用空间容量为 2^m 个字，则系统开始运行时，整个内存区是一个大小为 2^m 的空闲分区。
在系统运行过程中，由于不断地划分，将会形成若干个不连续的空闲分区，将这些空闲分区按分区的大小进行分类。对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，这样，不同大小的空闲分区形成了 k 个空闲分区链表。// 一次分配要进行多次分割
当需要为进程分配一个长度为 n 的存储空间时，首先计算一个 i 值，使 2^(i-1) < n <= 2^i，然后在空闲分区大小为 2^i 的空闲分区链表中查找。
若找到，即把该空闲分区分配给进程。否则，表明长度为 2^i 的空闲分区已经耗尽，则在分区大小为 2^(i+1) 的空闲分区链表中寻找。若存在 2^(i+1) 的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为 2^i 的空闲分区链表中。
若大小为 2^(i+1) 的空闲分区也不存在，则需要查找大小为 2^(i+2) 的空闲分区，若找到则也对其进行两次分割：第一次，将其分割为大小为 2^(i+1) 的两个分区，一个用于分配，一个加入到大小为 2^(i+1) 的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为 2^i 的两个分区，一个用于分配，一个加入到大小为 2^i 的空闲分区链表中。
若仍然找不到，则继续查找大小为 2^(i+3) 的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对 2^k 的空闲分区进行 k 次分割才能得到所需分区。
与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为 2^i 的空闲分区时，若事先已存在 2i 的空闲分区，则应将其与伙伴分区合并为大小为 2^(i+1) 的空闲分区，若事先已存在 2^(i+1) 的空闲分区，又应继续与其伙伴分区合并为大小为 2^(i+2) 的空闲分区，依此类推。//如果有成对的相同空闲分区，那么进行合并
在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比快速适应算法差，但由于它采用了索引搜索算法，比顺序搜索算法好。而其空间性能，由于对空闲分区进行合并，减少了小的空闲分区，提高了空闲分区的可使用率，故优于快速适应算法，比顺序搜索法略差。
5.3 哈希算法
在上述的分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时需要在一张管理索引表中查找到所需空间大小所对应的表项，从中得到对应的空闲分区链表表头指针，从而通过查找得到一个空闲分区。如果对空闲分区分类较细，则相应索引表的表项也就较多，因此会显著地增加搜索索引表的表项的时间开销。
哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。//减少搜索索引表的表项的时间开销
当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。
6 动态可重定位区分配
6.1 紧凑
连续分配方式的一个重要特点是，一个系统或用户程序必须被装入一片连续的内存空间中。当一台计算机运行了一段时间后，它的内存空间将会被分割成许多小的分区，而缺乏大的空闲空间。即使这些分散的许多小分区的容量总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。
因为碎片过多，且无法连续，导致内存浪费
例如，在内存中现有四个互不邻接的小分区，它们的容量分别为 10 KB、30 KB、14 KB 和 26 KB，其总容量是 80 KB，但如果现在有一个作业到达，要求获得 40 KB 的内存空间，由于必须为它分配一个连续空间，故此作业无法装入。这种不能被利用的小分区即是前已提及的 “碎片”，或称为 “零头”。
若想把大作业装入，可采用的一种方法是：将内存中的所有作业进行移动，使它们全都相邻接。这样，即可把原来分散的多个空闲小分区拼接成一个大分区，可将一个作业装入该区。这种通过移动内存中作业的位置，把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。
虽然“紧凑”能获得大的空闲空间，但也带来了新的问题，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。为了提高内存的利用率，系统在运行过程中是经常需要进行“紧凑”的，每“紧凑”一次，就要对移动了的程序或数据的地址进行修改，这不仅是一件相当麻烦的事情，而且还大大地影响到系统的效率。那么，使用动态重定位方法将能很好地解决此问题。
6.2 动态重定位
使用动态运行时装入的方式中，作业装入内存后的所有地址仍然都是相对(逻辑)地址。而将相对地址转换为绝对(物理)地址的工作被推迟到程序指令要真正执行时进行。
为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。//相对地址+重定位寄存器地址
地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位。当系统对内存进行了“紧凑”，而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址去置换原来的起始地址即可。//动态重定位的实现原理
6.3 动态重定位分区分配算法
动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。
通常，当该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这时便须对内存进行“紧凑”，将经“紧凑”后所得到的大空闲分区分配给用户。如果所有的小的空闲分区的容量总和仍小于用户的要求，则返回分配失败信息。
如果内存不够，触发一次紧凑，Java 虚拟机的内存回收就是这一原理