【概述】
连续分配方式是最早出现的一种存储器分配方式，曾被广泛应用于上世纪 60~80 年代的 OS 中，该分配方式为一个用户分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻
连续分配方式根据发展，可分为四类：
- 单一连续分配：将内存分为用户区和系统区，同一时刻下只允许一个程序在用户区运行
- 固定分区分配：将整个用户空间划分为若干固定大小的区域，在每个区域中只装入一道作业
- 动态分区分配：根据进程的实际需要，动态地为之分配内存空间
- 动态可重定位分区分配：在动态分区分配的基础上，加了紧凑功能，且设置重定位寄存器，在程序执行期间，随着对每条指令或数据的访问自动执行重定位
【单一连续分配】
在单道环境下，存储器的管理方式是将内存分为系统区和用户区两部分：
- 系统区：放在内存的低址部分，仅提供给 OS 使用
- 用户区：除系统区外的全部内存空间，提供给用户使用
值得注意的是，在单一联系分配方式中，用户区一般仅装有一道用户程序，即同一时刻，只有一个程序占用内存用户区的全部空间
单一连续分配方式是最简单的一种存储管理方式，只能用于单用户、单任务的 OS 中，其优点是便于管理，缺点是对要求内存很少的程序造成了极大的内存浪费
【固定分区分配】
基本原理
为能在内存中装入多道程序，且这些程序之间又不会发生干扰，于是将整个用户空间划分为若干固定大小的区域，在每个区域中只装入一道作业，这就形成了最早的、可运行多道程序的分区式存储管理方式
固定分区分配方式的分区总数是固定的，这就限制了并发执行的程序数目，此外，由于内存分配是固定的，可能会出现内碎片而造成浪费，即一个分区内分配程序后存在剩余空间
分区
在固定分区分配中，将内存的用户空间划分为若干固定大小的分区有以下两种方式：
- 分区大小相等：适用于多个相同程序的并发执行，缺乏灵活性
- 分区大小不等：划分为多个小分区、适量的中等分区、少量的大分区，根据程序的大小，分配当前空闲的、大小适当的分区
进行分区划分时，需要建立一个记录相关信息的分区表，表项值随着内存的分配和释放而动态进行改变，表项有：
- 起始位置：分区地址的开始位置
- 分区大小：分区的大小
- 分区状态：是否已分配
分配过程
为简化分配过程，常将分区表根据分区状态分为两张表：空闲分区表、占用分区表
在进行分配时，检索空闲分区表，寻找一个满足要求且尚未分配的分区，并分配给请求程序，若未找到大小足够的分区，则拒绝为该用户程序分配内存
空闲分区表可能按照不同的分配算法而采用不同方式对表象进行排序
【动态分区分配】
基本原理
动态分区分配又称可变分区分配，其是根据进程的实际需要，动态地为之分配内存空间
该方式的并发进程数没有固定的限制，因此不会产生内碎片，但由于动态分区分配算法的设计，存在外碎片，即分区之间无法利用的空间
数据结构
在实现动态分区分配时，要配置相应的数据结构，来描述空闲分区和已分配分区的情况，为分配提供依据，常用的数据结构有以下两种：
- 空闲分区表：记录每个空闲分区的情况，每个空闲分区占一个表目，表目中包括分区号、分区大小、分区起始位置
- 空闲分区链表：为实现对空闲分区的分配、链接，在每个分区的起始位置设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针、后向指针，通过前、后向链接指针，将所有的空闲分区链成一双向链表
动态分区分配算法
首次适应算法
首次适应（First Fit，FF）算法是一种顺序搜索算法，其要求空闲分区链以地址递增的次序链接
在分配内存时，首先从链首开始顺序查找直至找到一个大小能满足要求的空闲分区，然后从该分区中划出一块作业要求大小的内存空间分配给请求者，余下的空闲分区大小改变仍留在空闲链中
若从链表到链尾都检索不到满足要求的分区，则分配失败
该算法优先利用内存低址部分，而保留了高地址部分的大空闲区，但随着低址部分不断划分，会产生外碎片，而且每次查找从低址部分开始，会逐渐增加查找开销
循环首次适应算法
循环首次适应（Next Fit，NF）算法是一种顺序搜索算法，其要求空闲分区链以地址递增的次序链接
在分配内存时，不再是每次从链首开始寻找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区
为实现该算法，应设置一起始查找指针，用于指示下一次起始查找的空闲分区，同时采用循环查找方式
该算法能使内存中的空闲分区分布更加均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区
最佳适应算法
最佳适应（Best Fit，BF）算法是一种顺序搜索算法，其要求空闲分区按容量从小到大排成空闲分区表
在分配内存时，从分区表的头部开始检索，找到的第一个满足大小的空闲分区就进行分配
宏观上来看最佳适应算法是最佳的，但每次找到最合适大小的分区割下的空闲区也总是最小的，这就会产生外碎片
最坏适应算法
最坏适应（Worst Fit，WF）算法是一种顺序搜索算法，其要求空闲分区按容量从大到小排成空闲分区表
在分配内存时，从分区表的头部开始检索，总是选择一个最大的空闲区，从中割一部分存储空间给作业使用
该算法与最佳适应算法正好相反，其能使得剩下的空闲区不至于太小，产生外碎片的可能性也就变小，对中、小型作业较为有利，但会出现缺乏较大的空闲分区的情况
快速适应算法
快速适应算法（Quick Fit，QF）算法是一种基于索引搜索算法，其是将空闲分区根据容量大小进行分类，对于每一类具有相同容量的空闲分区，单独设立一个空闲分区链表
同时，在内存中设立一张管理索引表，其中的每一个索引表项都对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针
在分配内存时，首先根据进程长度从索引表中去寻找容纳它的最小空闲分区链表，然后从链表中取下第一块进行分配
该算法在进行空闲分区分配时，不会对任何分区产生分割，因此能保留大分区，也不会产生内存碎片，但分区归还时算法较为复杂，系统开销较大
伙伴系统
伙伴系统规定，无论是已分配分区还是空闲分区，其大小均为 $2$ 的 $k$ 次幂，且 $1 \leq k \leq m$，通常 $2^m$ 为可分配内存的大小，即最大分区大小
在系统运行过程中，内存被不断划分，形成若干不连续的空闲分区，对每一类具有相同大小的空闲分区设置一双向链表，会有 $k$ 个链表，链表中的分区大小都是 $2^m$
当进程申请 $n$ 个大小的空间时，计算一个 $i$ 值，使得 $2^{i-1} < n \leq 2^i$，然后在空闲分区大小为 $2^i$ 的空闲分区链表中查找
若找到，则将空闲分区分配给进程，否则表明长度为 $2^i$ 的空闲分区已耗尽，则在分区大小 $2^{i+1}$ 的空闲分区链表中查找
若存在 $2^{i+1}$ 的一个空闲分区，则将该空闲分区化为两个大小相等的 $2^i$ 的空闲分区，这两个分区称为一对伙伴，其中一个用于分配，另一个加入分区大小为 $2^i$ 的空闲分区链表中
若 $2^{i+1}$ 大小的空闲分区不存在，则去寻找 $2^{i+2}$ 大小的空闲分区，若找到则将其进行两次分割，若找不到继续寻找 $2^{i+3}$ 大小的空闲分区，以此类推
哈希算法
哈希算法，是利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一表项记录了一个对应的空闲分区链表表头指针
当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略
分区分配操作
分配内存
分配内存是指利用某种分配算法，从空闲分区表中找到所需大小的分区
设请求分区大小为 u.size，表中每个分区大小为 m.size，则流程如下：
回收内存
当进程运行完毕释放内存时，系统根据回收区的首地址，从空闲分区表中找到相应的插入点，此时可能会出现以下四种情况：
- 回收分区上邻接一个空闲分区：合并后首地址为空闲分区首地址，大小为二者之和
- 回收分区下邻接一个空闲分区：合并后首地址为回收分区首地址，大小为二者之和
- 回收分区上下邻接空闲分区：合并后首地址为上空闲分区首地址，大小为三者之和，删除下邻
- 回收分区不邻接空闲分区：在空闲分区表新建一表项，并填写分区大小等信息
【动态可重定位分区分配】
紧凑
当使用连续分配方式一段时间后，内存空间会被分割成多个小分区，从而缺乏大的空闲空间，此时这些分散的小分区的容量总和要大于要装入的程序，但由于这些分区不邻接，因此无法装入
若想将大作业装入，常用的一种方法是紧凑：将内存中所有作业进行移动，让他们全部邻接，使得原来分散的多个空闲小分区拼接成一个大分区，从而可以将作业装入
虽然紧凑可以获得大的空闲空间，但经过紧凑后的用户程序在内存中的地址发生了变换，此时需要对程序和数据的地址进行修改
为了提高内存的利用率，系统在运行过程中需要经常紧凑，而每紧凑一次，就要对移动了的程序和数据的地址进行重定位，这极大的影响了系统效率
动态重定位
在动态分区分配的方式中，作业装入内存后的所有地址仍是逻辑地址，而将逻辑地址转为物理地址的工作被推迟到程序指令要真正执行时进行
为使地址的转换不影响指令的执行速度，动态可重定位分区分配在动态分区分配的基础上，加了紧凑功能
同时，在系统中设置一个重定位寄存器，作为硬件地址变换机构，即用来存放程序或数据在内存中的起始地址，在程序执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而成的
地址变换过程是程序执行期间，随着对每条指令或数据的访问自动执行的，因此称为动态重定位
动态重定位分区分配算法与动态分区分配算法基本相同，差别在于增加了紧凑的功能
动态重定位能较好的解决紧凑的问题，当系统对内存进行了紧凑，使得若干程序从内存的某处移动到另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址去置换原来的起始地址即可
