连续分区存储管理方式

连续/分区分配方式:指为一个用户程序分配一块连续的内存空间。

单一连续分配方式
分区分配方式
- 固定分区分配方式
- 动态分区分配方式
动态重定位分区分配方式

单一连续分配方式

将内存分为系统区（内存低端，分配给OS用）和用户区（内存高端，分配给用户用）。采用静态分配方式，即作业一旦进入内存，就要等待它运行结束后才能释放内存。

主要特点：管理简单，只需少量的软件和硬件支持，便于用户了解和使用。但因内存中只装入一道作业运行，内存空间浪费大，各类资源的利用率也不高。

分区分配方式

分区分配方式是满足多道程序设计需要的一种最简单的存储管理方法。

将内存分成若干个分区（大小相等/不相等），除OS占用一个分区外，其余的每一个分区容纳一个用户程序。按分区的变化情况，可将分区存储管理进一步分为：

固定分区存储管理
动态分区存储管理

固定分区分配方式

内存空间的划分：将内存空间划分为若干个固定大小的分区，除OS占一分区外，其余的每一个分区装入一道程序。分区的大小可以相等，也可以不等，但事先必须确定，在运行时不能改变。即分区大小及边界在运行时不能改变。

系统需建立一张分区说明表或使用表，以记录分区号、分区大小、分区的起始地址及状态（已分配或未分配）。

内存分配

当某个用户程序要装入内存时，由内存分配程序检索分区说明表，从表中找出一个满足要求的尚未分配的分区分配给该程序，同时修改说明表中相应分区的状态；若找不到大小足够的分区，则拒绝为该程序分配内存。

当程序执行完毕，释放占用的分区，管理程序将修改说明表中相应分区的状态为未分配，实现内存资源的回收。

主要特点：管理简单，但因作业的大小并不一定与某个分区大小相等，从而使一部分存储空间被浪费。所以主存的利用率不高。

动态分区分配方式

动态分区分配又称为可变式分区分配，是一种动态划分存储器的分区方法。

存储管理方法

不事先将内存划分成一块块的分区，而是在作业进入内存时，根据作业的大小动态地建立分区，并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数目也是可变的。

主要特点

管理简单，只需少量的软件和硬件支持，便于用户了解和使用。进程的大小与某个分区大小相等，从而主存的利用率有所提高。

空闲分区链

用链头指针将系统中的空闲分区链接起来，构成空闲分区链。每个空闲分区的起始部分存放相应的控制信息（如大小，指向下一空闲分区的指针等）。

分区分配算法

为了将一个作业装入内存，应按照一定的分配算法从空闲分区表（链）中选出一个满足作业需求的分区分配给作业，如果这个空闲分区的容量比作业申请的空间要大，则将该分区一分为二，一部分分配给作业，剩下的部分仍然留在空闲分区表（链）中，同时修改空闲分区表（链）中相应的信息。目前常用分配算法有：

首次适应算法 (First Fit)
循环首次适应算法 (Next Fit)
最佳适应算法 (Best Fit)
最坏适应算法 (Worst Fit)
快速适应算法 (Quick Fit)

首次适应算法

n空分区（链）按地址递增的次序排列。

n在进行内存分配时，从空闲分区表/链首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。

n然后按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍按地址递增的次序保留在空闲分区表（链）中。

首次适应算法的特点

优先利用内存低地址部分的空闲分区,从而保留了高地址部分的大空闲区。

但由于低地址部分不断被划分，致使低地址端留下许多难以利用的很小的空闲分区(碎片或零头)，而每次查找又都是从低地址部分开始，这增加了查找可用空闲分区的开销。

循环首次适应算法

又称为下次适应算法，由首次适应算法演变而来。在为作业分配内存空间时，不再每次从空闲分区表/链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足其大小要求的空闲分区为止。

然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍按地址递增的次序保留在空闲分区表/链中。

最佳适应算法

算法要求：

空闲分区表/链按容量大小递增的次序排列。在进行内存分配时，从空闲分区表/链首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。

按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。如果该空闲分区大于作业的大小，则与首次适应算法相同，将剩余空闲分区仍按容量大小递增的次序保留在空闲分区表/链中。

算法特点

若存在与作业大小一致的空闲分区，则它必然被选中，若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，从而保留了大的空闲分区，但空闲区一般不可能正好和它申请的内存空间大小一样，因而将其分割成两部分时，往往使剩下的空闲区非常小，从而在存储器中留下许多难以利用的小空闲区（外碎片或外零头）

最坏适应算法(WF)

空闲分区表/链按容量大小递减的次序排列。在进行内存分配时，从空闲分区表/链首开始顺序查找，找到的第一个能满足作业要求的空闲分区，一定是个最大的空闲区。这样可保证每次分割后的剩下的空闲分区不至于太小（还可被分配使用，以减少“外碎片”），仍把它按从大到小的次序保留在空闲分区表/链中。

算法特点

总是挑选满足作业要求的最大的分区分配给作业。这样使分给作业后剩下的空闲分区也较大，可装下其它作业。

但由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足。

快速适应算法

算法要求

又叫分类搜索法，将空闲分区根据容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区（链）表。系统中存在多个空闲分区（链）表，同时在内存中设立一张管理索引表，每个表项对应了一种空闲分区类型，并指向该类型的空闲分区表的表头。空闲分区的分类是根据进程常用的空间大小进行划分的。

优点：查找效率高，找到该类后，取下第一块分配即可；不会产生碎片；

缺点：分区归还给系统时算法复杂，系统开销大；内存空间存在一定的浪费。

分区分配操作

系统利用某种分配算法，从空闲分区表/链中找到所需大小的分区。

分配内存

分区的切割：

设请求的分区大小为u.size，空闲分区的大小为m.size,若m.size-u.size£csize（csize是事先规定的不再切割的剩余分区的大小），说明多余部分太小，可不再切割，将整个分区分配给请求者；否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区表/链中，然后，将分配区的首址返回给调用者。

分配流程图如下

3928

回收内存

当作业执行结束时，释放所占有的内存空间，OS应回收已使用完毕的内存分区。

系统根据回收分区的大小及首地址，在空闲分区表中检查是否有邻接的空闲分区，如有，则合成为一个大的空闲分区，然后修改有关的分区状态信息。

回收分区与已有空闲分区的相邻情况有以下四种：

case 0

回收分区R上面邻接一个空闲分区F1，合并后首地址为空闲分区F1的首地址，大小为F1和R二者大小之和。

这种情况下，回收后空闲分区表中表项数不变。

case 1

回收分区R下面邻接一个空闲分区F2，合并后首地址为回收分区R的首地址，大小为R和F2二者大小之和。

这种情况下，回收后空闲分区表中表项数不变。

case 2

回收分区R上下邻接空闲分区F1和F2，合并后首地址为上空闲分区F1的首地址，大小为F1、R和F2三者大小之和。

这种情况下，回收后空闲分区表中表项数不但没有增加，反而减少一项。

case 3

回收分区R不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区首地址、大小等信息。

这种情况下，回收后空闲分区表中表项数增加一项。

动态重定位分区分配方式

碎片问题

在分区存储管理方式中，必须把作业装入到一片连续的内存空间。如果系统中有若干个小的分区，其总容量大于要装入的作业，但由于它们不相邻接，也将导致作业不能装入内存。

这种内存中无法被利用的存储空间称为“零头”或“碎片”。根据碎片出现的情况分为以下两种：

内部碎片

指分配给作业的存储空间中未被利用的部分。如固定分区中存在的碎片。

外部碎片

指系统中无法利用的小的空闲分区。如动态分区中存在的碎片。

对系统中存在碎片，目前主要有两种技术(之一)：

拼接或紧凑或紧缩技术

将内存中所有作业移到内存一端（作业在内存中的位置发生了变化，这就必须对其地址加以修改或变换即称为重定位），使本来分散的多个小空闲分区连成一个大的空闲区。如图所示。

这种通过移动作业从把多个分散的小分区拼接成一个大分区的方法称为拼接或紧凑或紧缩。

拼接时机：分区回收时；当找不到足够大的空闲分区且总空闲分区容量可以满足作业要求时。

可以充分利用存储区中的“零头/碎片”，提高主存的利用率。但若 “零头/碎片”太多，则拼接频率过高会使系统开销加大。

覆盖技术

覆盖技术主要用在早期的OS中（内存<64KB），可用的存储空间受限，某些大作业不能一次全部装入内存，产生了大作业与小内存的矛盾。

覆盖：把一个程序划分为一系列功能相对独立的程序段（称为覆盖），让执行时并不要求同时装入内存的覆盖组成一组（称为覆盖段），共享主存的同一个区域，从而解决在小的存储空间中运行大作业的问题。这种内存扩充技术就是覆盖。

内存交换

交换技术也是“扩充”内存容量和提高内存利用率的有效措施。现代OS中广泛采用。

最早用在MIT的兼容分时系统CTSS中，任何时刻系统中只有一个完整的用户作业，当运行一段时间后，因时间片用完或等待某事件发生，系统就把它交换到外存上，同时把另一作业调入内存让其运行，这样，可以在内存容量不大的小型机上分时运行，早期的一些分时系统多数采用这种交换技术。

交换技术：将暂时不用的某个进程及数据（首先是处于阻塞状态优先级最低的）部分（或全部）从内存移到外存（备份区或对换区，采用连续分配的动态存储管理方式）中去，让出内存空间，同时将某个需要的进程调入到内存，让其运行。交换到外存的进程需要时可以被再次交换回（选择换出时间最久的）内存中继续执行。

Operating System-存储管理之分区

相关概念

存储器的结构层次

逻辑地址和物理地址