一、连续分配

1. 单一连续分配

基本思想

• 整个内存空间分成系统区和用户区，系统区给操作系统使用，用户区给用户使用。

• 整个用户区分配给一个进程

适用场合

最简单，适用于单用户、单任务OS

优点

易于管理

缺点

• 对要求内存空间少的程序，造成内存浪费

• 程序全部装入，很少使用的程序部分也占用内存

2. 分区管理

基本原理

• 把内存分为一些大小相等或不等的分区

• 每个应用进程占用一个或几个分区，操作系统占用其中一个分区。

特点

适用于多道程序系统和分时系统

问题

• 内部碎片：占用分区之内未被利用的空间

• 外部碎片：占用分区之间难以利用的空闲分区

• 难以进行内存分区的共享。

(1)固定分区分配

基本思想

• 把内存分为大小相等或不等的分区，在每个分区中只装入一道程序。

• 分区的划分一般由系统操作员或操作系统决定，一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。

特点

• 适用于多道程序系统和分时系统

• 支持多个进程并发执行

问题

• 难以进行内存分区的共享

• 存在内部碎片

固定分区的两种划分方法

• 分区大小相等当程序太小时，会造成内存空间的浪费；当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。

• 分区大小不等可把内存区划分成多个较小的分区、适量的中等分区及少量的大分区。

分区分配

• 分区描述表：通常将分区按大小进行排队，并为之建立一张分区使用表。

• 分配算法：为进程分配某个空闲分区

• 分区大小相等时的分配算：任选一个空闲分区

• 分区大小不等时的分配算法：最佳匹配

  • 根据空闲分区选择最佳任务
  • 根据任务选择最佳空闲分区

存储保护

• 防止一个作业有意或无意地破坏操作系统或其它作业

• 通常采用界限寄存器方法

  每个分区都对应上、下界两个寄存器用于内存越界保护，CPU访问每个存储器地址时应满足：下界寄存器的内容不小于访问地址，而访问地址则不大于上界寄存器内容，否则会产生地址越界错误，终止作业的运行。

优点

• 比单一连续分配方法，提高了内存利用率

• 可以支持多道程序，无外部碎片

• 实现简单

缺点

• 分区的数目在系统生成时确定，限制了系统中活跃进程的数目。

• 小作业的内部碎片可能比较大

• 作业必须预先能够估计自己要占用多大的内存空间

(2)动态分区分配

动态分区

根据进程的实际需要，动态地分配内存空间。将涉及到分区分配中所用的数据结构、分区分配算法、分区管理操作三个问题。

数据结构

• 空闲分区表：在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。

• 空闲分区链：为了实现对空闲分区的分配和链接，设置前向指针和后向指针，通过前、后向链接指针将所有的空闲分区链接成一个双向链。

分区分配算法

• 首次匹配算法(首次适应算法，First Fit)

• 循环匹配算法(循环首次适应算法，Next Fit)

• 最佳匹配算法(最佳适应算法，Best Fit)

• 最坏(差)适应算法，Worst Fit

存储保护

• 防止一个作业有意或无意地破坏操作系统或其它作业

• 通常采用界限寄存器方法

  • 上、下界寄存器方法：采用上、下界寄存器分别存放作业的结束地址和开始地 址。

  • 基址、限长寄存器方法：采用基址和限长寄存器分别存放作业的起始地址及作业 的地址空间长度。

优点

• 支持多道程序

• 管理方案相对简单，不需要更多的软、硬件开销

• 实现存储保护的手段比较简单

缺点

• 主存利用不够充分，存在外部碎片

• 无法实现多进程共享存储器的信息

• 无法实现主存的逻辑扩充，进程的地址空间受实际物理内存的限制

二、动态分区

1. 分区管理操作

分配

回收

• 当进程运行完毕释放内存时，需合并相邻的空闲分区，形成大的分区，称为合并技术。

• 系统根据回收区的首址，从空闲区链中找到相应的插入点，此时可能出现以下四种情况之一。

2. 紧凑与动态重定位

动态重定位的引入

• 在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。

• 在动态分区中，由于分区的不断划分与合并，会产生许多零散分区。

• 若零散分区均很小，则即使总空间空间很大，也可能无法装入大进程。

• 采用动态重定位技术的分区分配称为可重定位分区分配。

• 紧凑技术——将内存中的所有作业进行移动，使它们全都相邻接，这样，可把原来分散的多个小分区合成一个大分区的方法，称为紧凑。

动态重定位的实现

地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行，通常需要硬件的支持。

可重定位分区分配

采用动态重定位技术的分区分配方式。

3. 内存扩充

问题提出

• 一个作业的逻辑地址空间大于内存可使用空间时，该作业就不能装入运行

• 当并发运行作业的程序地址空间总和大于内存可用空间时，多道程序设计实现就会碰到非常大的困难。

内存扩充含义

借助大容量辅存在逻辑上实现内存扩充，来解决内存容量不足的问题。

4. 覆盖与交换

• 目标

  • 在较小的可用内存中运行较大的程序。

• 原理

  • 在任何时候只在内存中保留所需的指令和数据；当需要其它指令时，它们会装入到刚刚不再需要的指令所占用的内存空间。

覆盖

• 基本思想

  • 一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。

• 实现

  • 将程序的必要部分代码和数据常驻内存
  • 可选部分在其他程序模块中实现，平时存放在外存中(覆盖文件)，需要用到时才装入到内存
  • 不存在调用关系的模块不必同时装入到内存，可相互覆盖

• 优点

  • 覆盖不需要OS提供特殊的支持

• 缺点

  • 程序员必须适当地设计和编写覆盖结构，即编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。

交换(对换)

• 基本思想

  • 把内存中暂不能运行的进程或者暂不使用的程序和数据换出到外存上，以腾出足够的内存空间,把已具备运行条件的进程或进程所需要的程序和数据换入内存。

• 示意图

• 交换粒度

  • 整体交换——进程交换交换是以整个进程为单位，目的是解决内存紧张问题，进一步提高内存利用率。

  • 部分交换——页面交换、分段交换分页、分段交换的基础,目的是为了支持虚拟存储系统。

• 对换空间的管理

  • 外存：对换区比文件区侧重于对换速度。
  • 对换区一般采用连续分配。

• 对换的优点

  • 换入及换出操作由内存管理模块完成，与程序结构无关。

覆盖 vs. 交换

覆盖技术与对换技术的比较

• 覆盖技术主要用在早期的操作系统中

• 交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现

• 覆盖只能覆盖那些与覆盖段无关的程序段

• 交换技术不要求用户给出程序段之间的逻辑覆盖结构

• 交换发生在进程或作业之间，覆盖发生在同一进程或作业内

三、分区分配算法

1. 首次匹配算法

基本思想

要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。

优点

为大作业分配大的内存空间创造了条件。

缺点

低址部分不断被划分，会留下许多难以利用的、很小的空闲分区；且查找开销较大。

要求

空闲分区表或空闲分区链按地址从低到高排列。

2. 循环匹配算法

基本思想

将所有的空闲分区构成一个循环链表。采用循环查找方式，设置一个起始查寻指针，用于指示下一次起始查寻的空闲分区。

优点

能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销。

缺点

缺乏大的空闲分区。

要求

空闲分区表或空闲分区链按地址从低到高排列。

3. 最佳匹配算法

基本思想

每次分配内存时，总是把能满足要求又是最小的空闲分区分配给作业，避免大材小用。

优点

产生的外部碎片都很小。

缺点

每次分配后余下的部分往往因为太小而无法利用，从而造成新的浪费。

要求

空闲分区表或空闲分区链按容量从小到大排列。

4. 最坏（差）适应算法

基本思想

每次分配内存时，总是把能满足要求又是最大的空闲分区分配给作业。

优点

留下来的空闲分区较大，便于下次利用。

缺点

大的空间分区不易保留，对大作业不利。

要求

空闲分区表或空闲分区链按容量从大到小排列。

分区分配算法示例

某操作系统采用动态分区存储管理技术。操作系统在低地址占用了100KB的空间，用户区主存从100KB处开始占用512KB。初始时，用户区全部为空闲，分配时截取空闲分区的低地址部分作为分配区。在执行以下申请、释放操作序列后：请求300KB、请求100KB、释放300KB、请求150KB、请求50KB、请求90KB，请回答

1. 采用首次适应算法时，主存中有哪些空闲分区？画出主存分布图，并指出空闲分区的首地址和大小。

2. 采用最佳适应算法时，主存中有哪些空闲分区？画出主存分布图，并指出空闲分区的首地址和大小。

3. 若随后又申请80KB，针对上述两种情况产生什么后果？说明了什么问题？

答案

1. 采用首次适应算法

2. 采用最佳适应算法

3. 首次适应算法的优点在于优先分配低地址部分的空闲分区，保留高地址部分的空闲分区，使得当需要大分区时可以找到。

四、伙伴系统

• 静态划分方案限制了系统中活跃进程的数目。并且，只能运行不超过分区大小的进程，如果进程远远小于分区大小，则内存空间的利用率非常低。

• 动态划分方案使存储管理复杂化，并且需要系统付出紧凑外零头的额外开销。

• 伙伴系统(Buddy System)：综合静态划分技术和动态划分技术的优点

基本思想

无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，l≤k≤m，其中：$2^l$表示分配的最小分区的大小，$2^m$表示分配的最大分区的大小，通常是整个可分配内存的大小。

假设系统的可利用空间容量为$2^m$个字节，则系统开始运行时，整个内存区是一个大小为$2^m$的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k个空闲分区链表。

存储空间的分配

进程申请大小为k的空间，系统为之分配一个$2^i$的空闲分区，其中，$2^i-1\le k\leq 2^i$

1. 查找大小为$2^i$的空闲分区，若找到则分配

2. 若未找到大小为$2^i$的空闲分区，则查找大小为$2^i+1$的空闲分区；若找到，则将该空闲分区划分为相等的两个分区(一对伙伴)，其中的一个用于分配，另一个分区加入大小为$2^i$的空闲分区链中；

3. 若未找到$2^i+1$的空闲分区，则需要查找大小为$2^i+2$的空闲分区，若找到则需要进行两次划分。第一次将其分割为大小为$2^i+1$的两个分区，一个用于分配，另一个加入到大小为$2^i+1$的空闲分区链中；第二次将第一次用于分配的空闲分区分割为$2^i$的两个分区，一个用于分配，另一个加入到大小为$2^i$的空闲分区链中。

4. 若仍未找到$2^i+2$的空闲分区，则继续查找$2^i+3$的空闲分区，以此类推。

存储空间的回收

当进程执行完毕，释放一个大小为$2^i$的分区时，系统用下面的算法回收该分区：

1. 若事先不存在$2^i$的空闲分区，则保留该分区为一个独立的空闲分区

2. 若事先已存在$2^i$的空闲分区时，则将其与伙伴分区合并为大小为为$2^i+1$的空闲分区

3. 若事先已存在$2^i+1$的空闲分区时，继续合并为$2^i+2$的空闲分区，以此类推。

示例

系统的初始内存为1MB，若进程P1、P2、P3、P4、P5相继申请100KB、200KB、120KB、300KB、160KB的内存空间，其申请、释放顺序为P1申请、P2申请、P3申请、P4申请、P2释放、P3释放、P5申请、P1释放、P5释放、P4释放。

则系统分配、回收(合并)伙伴分区的过程如图所示：

特点

速度快，但内存利用率不高。