《操作系统》知识点整理（八）分配存储管理方式

4-2 分配存储管理方式

（1）单一连续分配

内存分为 系统区和用户区两部分：

系统区：仅提供给OS使用，通常放在内存低址部分

用户区：除系统区以外的全部内存空间，提供给用户使用。

最简单的一种存储管理方式，只能用于单用户、单任务的操作系统中。

优点**：易于管理。**

缺点：针对那些仅需少量内存的程序而言，在运行过程中容易导致内存不足；将整个程序加载到内存中后，即便某些不常用的部分也会被加载占用。

（2）固定分区分配

将内存划分为若干个大小相等或不等的区域（partition），其中每个应用程序进程占据一个专用（dedicated）内存区域；而系统本身则占据一个独立的（dedicated）内存区域

提高：允许多个程序并行运行，在支持多任务操作的同时也适用于分时操作系统。第一种实现多任务操作的存储管理方案。

划分为几个分区，便只允许几道作业并发

具体实现：

1**）如何划分分区大小**

等分粒度：仅适用于多个相同流程同时运行的情况（处理同一类对象的各种情况）。存在一定的局限性。

区域划分不均：较多的小型区域、适中的中间规模以及较少的大区域。根据应用实例的规模，在空闲资源中合理分配相应合适的空间。

2**）需要的数据结构**

建立一记录相关信息的 分区表（或分区链表），表项有:

|起始位置|大小|状态|

分区表中，表项值随着内存的分配和释放而动态改变

3**）分配回收操作**

也可以通过将...空闲分区表/占用分区表来实现对...的划分。从而使得每个表格的长度得到进一步优化。

检索算法：空闲分区表可能根据不同的分配策略以不同的排序方式排列条目（根据大小顺序排列或按照地址高低顺序排列）

过程：从空闲分区表中查找；确定一个既满足需求又尚未被分配出去的区域；将该区域授予请求处理的任务；如果无法找到足够大的可用空间，则决定不再为当前用户提供必要的内存支持。

（3）动态分区分配

在操作系统中采用虚拟存储技术时会采用一种称为虚拟存储管理的方法。这种方法的核心思想是将物理磁盘空间划分为多个逻辑上独立的部分称为虚拟磁盘或者虚拟分区这些虚拟区域能够通过硬件连接到同一个逻辑实体并支持其数据操作功能。这种方法的一个显著特点是允许每个虚拟区域能够具有不同的容量从而能够更好地适应不同类型的程序和数据量的需求。

空闲分区表项：从1项到n项：

虚拟内存空间会持续不断地从一个较大的初始专用区域细分，并通过释放回用来扩展其可用容量，最终形成了整个内存空间中多个独立的专用区域。

动态分区分配

优点：并发进程数没有固定数的限制，不产生内碎片。

缺点：有外碎片（分区间无法利用的空间）

具体实现**:**

1**）分区分配中的数据结构**

①空闲分区表：

•记录每个空闲分区的情况。

每个空闲分区都与一个表目相对应，并且这些表目通常包含分区内所需的序号、起始地址以及区间的大小等数据项。

②空闲分区链：

每个分区的开始位置处进行配置，在此位置上设置用来管理分区分配的参数以及用来作为各分区之间连接标记的前向指针。

末尾区域将建立一个反向指针，在该区域的末端部分依次添加状态标志位以及分区大小索引项以实现后续查询操作。

2**）分区分配算法**

动态内存分配策略，在内存空间划分多样且尺寸分布不均的情况下。当向系统提交一个新的作业时**，“需要选择一种适合的内存管理算法，并从空闲的内存区域列表或链表中挑选出一个合适的可用分区”。

①首次适应算法****FF

1.空闲分区排序：以 地址递增的次序链接。

2.查找：在内存分配过程中依次从链表头部开始逐步搜索以定位满足需求的一个足够大的空闲分区；

3.划分：从该分区中指定一块所需内存容量的空间供使用，并使剩余的空闲部分继续存在于空闲链中。

若从头到尾检索不到满足要求的分区则分配失败

优点：优先利用内存低址部分，保留了高地址部分的大空闲区；

缺点：但随着低址区域不断细分的过程进行下去，则会不可避免地导致大量细小碎片形成；在每次查找过程中均需从该区域出发，并且这会导致逐步提高搜索开销的情况发生。

②循环首次适应算法

1.空闲分区排序：按地址

在执行过程中，在上次找到的空闲分区之后的一个可用空闲分区中进行检索操作直至发现满足需求的一个可用空闲分区。为了确保算法的有效运行，在此过程中需持续执行上述步骤来确保资源的有效利用。

设置一个起始查寻指针

采用循环查找方式

3.分配：分出需要的大小

优点：空闲分区分布均匀，减少查找开销

缺点：缺乏大的空闲分区

③最佳适应算法

总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。

1.**空闲分区排序：**所有空闲分区按 容量从小到大排序成空闲分区表或链。

2.检索：从表或链的头开始，找到的第一个满足的就分配

3.分配：分出需要的大小

缺点：在每次进行合适大小的分区切割后剩下的空闲区域也总是最少的，并会生成许多难以有效利用的小空闲区域（称为外碎片）。

④最差适应算法

基本不留下小空闲分区，但会出现缺乏较大的空闲分区的情况

⑤快速适应算法

基于进程所使用的最大连续空闲内存块进行划分内存空间，并将具有相同最大连续空闲内存块的所有单元组合为一条链；同时负责管理多个不同尺寸的最大连续空闲内存块集合（即分区）。当系统运行需要动态内存分配时，在这些存储区域中找到与当前请求最大内存需求最为接近的最大连续空闲内存块集合（即最接近匹配区），然后系统会从该匹配区域内选择相应的单元进行释放以供新的进程使用；类似于这种基于最近似区的方法被称为伙伴算法

能快速找到合适分区，但链表信息会很多；实际上是空间换时间。

3**）分区分配操作**

分配内存

找到满足需要的合适分区， 划出进程需要的空间

if s <=size**，将整个分区分配给请求者**

当s大于size时****, 按请求的大小释放一部分内存块到空闲链中，并返回该区域的首地址。

回收内存

当进程完成并释放内存时（即free memory），系统会根据回收区首址a，在空闲分区链表中确定合适插入位置，并依据具体情况更新空闲分区数据；同时有可能执行空闲分区merging。

回收分区

收集区域（首址 a）与一个分组 f1 末尾（首址 b+大小）相邻：将收集区域与分组 f1 合并，并重新配置分组 f1 的条目规模。

该回收区域（容量为a+的起始地址）与分区f2相邻：将该区域与分区f2整合，并对其实体进行重新设置其起始地址和分区容量

（3）当出现以下两种情况时，则将回收区与前后的两个区域相连：将这三个区域合并为一个新区域，并采用前一区域(F1)的各项属性及起始地址；同时不再保留区域(F2)的相关信息；新区域的总大小等于三者的总和。

(4)****回收区无相邻分区：需单独创建新的表项，并填入回收区的起始地址及大小信息，在空闲链中按照起始地址插入到合适位置

（4）动态 重定位分区分配**——有紧凑功能的动态分区分配**

用户程序在内存中转移，并将空闲空间进行压缩以提升空间利用率。但必然导致地址变化，并进行‘重定位’工作。

伙伴系统

分区大小有规定，且分区动态变化

不论现有分块还是空闲区域的规模,均等于2^{k}（其中k为整数）。其中整体可用空间的规模为2^{m},则有1 \leq k \leq m.

在系统运行过程中，在内存持续被划分为多个独立的空闲区域的同时（或与此同时），从而生成多个互不相连的自由空间块。为此设计了一种基于双向链表的空间管理策略：为所有等量大小的空间分配一个双向链接结构（或双层索引机制），该结构将包含k条独立的双向指针列表（或分层索引），每个列表内的空间单元尺寸统一为2^m字节（或固定长度）。

系统要求申请n个大小的空间后，在计算所需空间数量n = 2^i之后查找对应的链表结构。如果该i大小的链表不存在，则继续查找下一个较大的链表（即i+1）。找到相应的分区后将其均分后的一半用于实际资源分配操作，并将另一半连接到下一级别（较小一级）的相应位置上以完成空间管理流程

4.一次分配和回收都可能对应多次的划分和合并。

（5）内存空间管理之对换

当内存空间仍无法满足需求时，在无法完成的任务或无须使用的情况下将相关程序与数据暂存于外存以便腾出更多内存量同时将具备运行条件的所有进程及其所需的相关程序与数据加载至内存区域

按对换单位分类：

整体对换**(或进程对换)****：以整个进程为单位（连续分配）**

页面对换或分段对换：以页或段为单位（离散分配）

外存上	存储内容	驻留时间	主要目标	分配方式
文件区	文件	较长久 不频繁	提高文件存储空间的利用率	离散
对换区	从内存换出的进程	短暂 频繁	提高进程换入和换出的速度	连续