第 12章 动态存储管理
概述
可利用空间表及分配方法
存储压缩
边界标识法
无用单元的收集存储管理是操作系统的重要组成部分，它负责管理计算机系统的存储器。
动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何收回那些用户不再使用而释放的内存以备新的“请求”产生时重新进行分配。本章简单介绍数据结构在动态存储管理中的一些常用技术，包括可利用空间表及分配方法、
边界标识法、无用单元的收集和压缩存储等内容。
12.1 概述动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何收回那些用户不再使用而释放的内存以备新的“新求”产生时重新进行分配？
在单用户操作系统中，整个内存空间被划分成两个区域：系统区和用户区，系统区供系统程序使用，
用户区供单一的用户程序所使用。当计算机采用了多道程序设计技术后，需要在主存储器中同时存放多个作业的程序，而这些程序在主存储器中的位臵此时不能由程序员自已来确定，否则将出现多道程序竞争同一存储空间的情况。
J0 J1 J2 J3 J4 J5 J6 J7
J0 J2 J3 J5 J7
(A)系统运行初期
（ B）系统运行若干时间以后可利用空间块或空闲块占用块现在讨论，在图 12.1（ b）所示的内存状态下，此时又有新的用户作业进入系统请求分配内存，系统将如何处理？
通常有两种做法：一种策略是系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存是否已空闲，直到分配无法进行另一种策略是用户程序一旦运行结束，便将它所占内存区释放成为空闲块，同时，每当新的用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个“合适”的空闲块分配之。
为了实现这种分配策略，系统需建立一张记录所有空闲块的可利用空间表。此表的结构可以是目录表也可以是链表。如图 12.2所示为某系统运行过程中的内存状态及其两种结构的可利用空间表。
0 10000 20000 28000 32000 9999955000
10000 10000 空闲
28000 4000 空闲
55000 45000 空闲起始地址 内存块大小 使用情况
0 10000 10000 0 28000 4000 0 55000 45000 ^
av
（ c）链表
12,2可利用空间表及分配方法操作系统既可借助目录表结构也可借助链表结构实现动态存储分配,本节将对采用链表的情况进行讨论 。
根据系统运行的不同情况,可利用空间表可以有三种不同的结构形式：
第一种情况是系统运行期间所有用户请求分配的存储量大小相同。对此类系统，可以在系统开始运行时将内存的用户区域按所需大小分割成若干大小相同的块，然后用指针链接成一个可利用空间表。
由于表中结点大小相同，所以在分配时无需查找，只要将第一个结点分配给用户即可；同样，当用户程序释放内存时，系统只需将用户释放的空闲块插入在表头即可。这种情况下的可利用空间表实质上是一个链栈，对应的存储管理方式在操作系统中称为,固定分区管理” 。
第二种情况是系统运行期间用户请求分配的存储量有若干大小的固定规格。
对此系统，可将用户存储空间分割成不同规格的若干块，并将大小相同的空闲块组织在同一个可利用空间表中，即同一链表中的结点大小相同。
tag type link
space
0 0 0 0 0 0 ^…
av2
0 1 0 1 0 1 ^…
av4
0 2 0 2 0 2 ^…
av8
0 空闲块
1 占用块
0 结点大小为 2KB
1 结点大小为 4KB
2 结点大小为 8KB
tag=
type=
例,
第三种情况是系统在运行期间分配给用户的内存块大小不固定,可以随请求而变 。 此时,可利用空间表中的结点即空闲块的大小也是随意的 。 通常,操作系统中的可利用空间表属于这种类型,这种存储管理实际上就是操作系统中的可变分区管理方法 。 系统初始状态下,整个内存空间是一个空闲块,即可利用空间表中只有一个大小为整个内存区的结点,随着分配和回收的进行,可利用空间表中的结点大小和个数也随之而变 。
由于链表中结点大小不同，结点的结构可包含四个域，即：标志域（ tag），用于区分此块是否为空闲块、大小域（ size），用于指示空闲块的存储量、链域（ link），用于指示可利用空间链表中的下一个结点、存储空间域（ space），它是一个大小为 size的连续存储空间。
tag size link
space
0 空闲块
tag=
1 占用块由于可利用空间表中的结点大小不同，因此相应的分配与回收过程较为复杂。假设某用户需大小为 n
的内存，而可利用空间表中仅有一块大小为 m≥n的空闲块，则只需将其中大小为 n的一部分分配给申请的用户，同时将剩余大小为 m-n的部分作为一个结点留在链表中即可。当可利用空间表中存在多个空间大小不小于 n的空闲块时，一般可采用以下三种不同的分配策略。
（ 1）最先适应分配算法，这种方法又称为首次适配法。每次分配时，总是顺序查找可利用空间链表，找到第一个能满足长度要求的空闲区为止。分割这个找到的未分配区，一部分分配给作业，另一部分仍为空闲区。
（ 2）最优适应分配算法。这种分配算法每次从空闲区中挑选一个能满足作业要求的最小分区，这样可保证不去分割一个更大的区域，使装入大作业比较容易得到满足。
（ 3）最坏适应分配算法。最坏适应分配算法总是挑选一个能满足作业要求的最大的空闲区分割给作业使用，这样可使剩下的空闲区不至于太小，这种算法对中、小作业是有利的。
上述三种分配方法的选取一般需要考虑以下因素：
用户的逻辑要求；请求分配量的大小分布；分配和释放的频率以及效率对系统的重要性等 。
无论采用何种分配方法在进行回收系统空闲块时需要考虑“结点合并”的问题，即当系统在不断进行分配和回收的过程中，大的空闲块逐渐被分割成小的占用块，当用户程序将某一占用块释放重新成为空闲块时，如果将它作为一个独立的空闲块插入到链表中，
将出现两个或多个地址相邻的空闲块作为几个结点独立放在可利用空间表中，显然这不利于以后出现的大容量作业的请求。为了更有效地利用内存，就要求系统在回收时应考虑将地址相邻的空闲块合并成尽可能大的结点。
12,3边界标识法边界标识法是操作系统中用以进行动态分区分配的一种存储管理方法，它属于 12.2节中介绍的第三种情况，即用户请求的内存块大小不固定，随不同的请求而变化。系统将所有的空闲块链接在一个双重循环链表结构的可利用空间表中；分配可按最先适应分配算法进行，也可按最优适应分配算法进行。系统的特点在于：在每个内存区的头部和底部两个边界上分别设有标识，以识别该区域为占有块或空闲块，使得在回收用户释放的空闲块时容易判别在物理位臵上与其相邻的内存区域是否为空闲块，以便将所有地址连续的空闲存储区组合成一个尽可能大的空闲块。
12,3,1 可利用空间表的结构
llink tag size
space
rlink
uplink tag
head
foot
它表示一个空闲块。整个结点由三部分组成。其中 space为一段地址连续的存储单元，是可以分配给用户的内存区域，它的大小保存在 head中的 size域中。
它以头部 head和底部 foot作为它的两个边界；在 head
和 foot中分别设有标志域 tag，且设定空闲块中 tag的值为,0”，占用块中 tag的值为,1”； foot位于结点底部，
因此它的地址是随结点中 space空间的大小而变的。
为方便操作，可利用空间表可组织成双重循环链表。
head中的 llink和 rlink分别指向链表中的前趋结点和后继结点，表中不设表头结点，表头指针 pav可以指向表中任一结点，即任何一个结点都可看成是链表中的第一个结点；表头指针为空则表明可利用空间表为空。
1000
0
0 600
0
0 2000
0
0
pav
12,3,2分配算法本节以最先适应分配算法来说明边界标识法的应用 。 实现时,可以从表头指针 pav所指的第一个结点开始进行查询,找到第一个容量不小于请求分配的存储量的空闲块即可进行分配 。 为了使整个系统更有效地运行,在边界标识法中可做如下两条约定：
（ 1） 假设找到的某个待分配的空闲块的容量为 m个字,若每次只从中分配 n（ n<m） 个字给用户作业,
则剩余 m-n个字大小的空闲块结点仍留在链表中 。 如此进行多次分配之后,链表中会出现一些容量极小称之为,碎片,的空闲块,这样将大大减慢分配 （ 查找 ）
的速度 。 为克服这一弊端,可以选定一个适当的容量
e,当 m-n<e时,就将容量为 m的空闲块整块分配给用户作业；反之,只分配其中 n个字的内存块 。 同时,
为了避免修改指针,在分配部分空间时约定将结点中的高地址部分分配给用户 。
（ 2） 按照最先适应分配策略,每次在分配存储块时总是从表头指针 pav所指的结点开始进行查找,找到第一不小于 n的空闲块即进行分配 。 但是,由于每次总是从同一个结点开始查找,必然造成存储容量小的结点集中在链表的前端,这同样会增加查找较大空闲块的时间 。 因此,在每次分配完成之后,令指针 pav指向刚进行分配的结点的后继结点,这就是为何将可利用空间表组织成循环链表的原因 。
例如,对图 12.6所示的可利用空间表进行分配一个大小为 500个字的存储单元后可利用空间表的状态如图 12.7所示,此时,表头指针 pav指向了下一个结点 。
1000
0
0 600
0
0 2000
0
0
pav 分配 500个字
500
0
pav
12,3,3回收算法当用户释放占用块，系统需立即回收以备新的请求产生时进行再分配。为了使物理地址毗邻的空闲块结合成一个尽可能大的结点，首先需要检查刚释放的占用块的左、右紧邻是否为空闲块。采用边界标识法实现动态存储管理时每个内存区（无论是占用块或空闲块）的边界上都设有标志值，因此很容易区分刚释放的占用块的左、右紧邻是否为空闲块或占用块。
若释放块的左,右邻区均为占用块,则处理最为简单,只要将此新的空闲块作为一个结点插入到可利用空间表中即可；若只有左邻区是空闲块,则应将回收块与其左邻区合并成一个结点；若只有右邻区是空闲块,则应将回收块与其右邻区合并成一个结点；若左,
右邻区都是空闲块,则应将三块合起来成为一个结点留在可利用空间表中 。
12,4无用单元的收集可利用空间表虽然方便地实现了存储空间的动态管理,但它的主要特点是应用户的请求而分配内存,在用户释放存储空间时进行回收 。 因此,在这类存储管理系统中,用户必须明确给出,请求,和,释放,的信息 。 但用户难免在某些时候会因为疏漏或其它原因致使系统没有进行回收而产生,无用单元,的问题 。
此处,,无用单元,指的是那些用户不再使用而系统又没有回收的结构或变量 。 例如,下列 C程序段
s=malloc（ 20） ；
t=malloc（ 12） ；
…
s=t;
执行的结果是使执行 s=malloc（ 20）为用户分配的结点成为无用单元，无法得到使用。
另外，由于数据结构本身的原因也有可能造成无用单元的产生，如广义表中存在着共享和递归成份，对共享结点来说，当该结点从某一条链上删除时它可能还链接在别的关系中，并不能立即释放该结点的空间，
所以只有在全部链接关系中都被删除时，该结点才是无用结点，该结点所占用的空间才成为无用单元可以回收。
因此，要及时释放共享结点所占的空间，必须给每个结点增设一个共享计数器，记录本结点被几个链共享，当结点从某一链中被删除时，就将此计数器减
1，反之在插入时计数器加 1，一旦该计数器被减到 0
时，说明该结点在结构中不再有用，便可以回收。
这种处理方法的缺点是增加了额外的存储开销,
同时也使程序的处理变得更加复杂 。 有时少量无用单元的存在并不会影响系统的正常运行,但是当无用单元积累到一定阶段,就要求系统去找出这些无用单元,
并把它们送回到可利用空间表中去 。 在这里关键的问题是如何从整个存储空间中找出那些无用单元 。
“标志,算法通过周游广义表给每个有用结点记上标志,
相应地所有无用结点由于不带标志,因此只要扫描一遍内存就可通过标志判断哪些是有用结点,哪些是无用结点,这样便可将所有的无用单元收回至可利用空间表 。
实际运行的系统中结点的大小可能不等，但这并不影响“标志”算法，标志算法只要求找到结点的开始地址和其中描述结点之间关系的几个字段，并不关心结点中其它信息的长短。因此，可以假设所有结点的结构如图 12.8所示。
mark tag link1 link2 size
info
其中,link1和 link2是两个指向同类型结点的指针，其意义可以解释为广义表的双链表示法。 mark是一标志位，初值为 0，执行标志算法后，将全部有用结点的
mark字段值臵为 1，其值继续保持为 0的则为无用单元。
tag也是一个标志位，初值为 0，在标志算法执行过程中，周游到本结点所对应的子表时被臵成,1”，返回以后再恢复成,0”。 size字段表示本结点的长度，它主要在回收和压缩算法中起作用，在标志算法中它并不起作用。
算法 12.3给出了标志算法 。 算法初始时,所有结点的 mark和 tag字段都臵为 0,指针变量 t指向广义表的根结点 。 算法执行中,p指向当前处理的结点,r指向 p所指结点的前趋结点 。 算法结束时,所有广义表中的有用结点中的 mark字段被臵成,1”。
12,5存储压缩在动态存储管理中,由于每个用户作业所需的存储空间大小不尽相同,所以当系统运行一段时间后必然导致可利用空间表中存在一些容量很小的内存块,这些内存块分布在内存中的不同区域,它们很难再次被作业利用 （ 在操作系统中这种小块内存被称为,碎片,）,这大大降低了存储空间的利用率 。
,存储压缩,是将所有的空闲块移到一个连续的存储区,从而使可利用空间形成一个连续的存储块,
这样可以满足大作业的需求,提高系统的利用率 。
实施“存储压缩“通常有两种做法，一种是一旦有用户释放存储块即进行回收压缩；另一种是在程序执行过程中不回收用户随时释放的存储块，而是在可利用空间不够分配或在进行无用单元的收集时进行“存储压缩”。
例,压缩前 压缩后存储压缩的过程比较复杂,不仅要改变结点的物理地址,同时还要修改结点中的全部指针 。 实际上,存储压缩是有条件的,当某个有用块中的程序正在执行与外设相关的输入输出操作时不能进行程序的移动 （ 具体的原因在操作系统相关课程中学习 ） 。 此处,可以通过以下三个步骤来实现存储压缩：
（ 1） 给有用结点分配新地址；
（ 2） 修改有用结点的指针值；
（ 3） 将有用结点移动到新分配的位臵 。
概述
可利用空间表及分配方法
存储压缩
边界标识法
无用单元的收集存储管理是操作系统的重要组成部分，它负责管理计算机系统的存储器。
动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何收回那些用户不再使用而释放的内存以备新的“请求”产生时重新进行分配。本章简单介绍数据结构在动态存储管理中的一些常用技术，包括可利用空间表及分配方法、
边界标识法、无用单元的收集和压缩存储等内容。
12.1 概述动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何收回那些用户不再使用而释放的内存以备新的“新求”产生时重新进行分配？
在单用户操作系统中，整个内存空间被划分成两个区域：系统区和用户区，系统区供系统程序使用，
用户区供单一的用户程序所使用。当计算机采用了多道程序设计技术后，需要在主存储器中同时存放多个作业的程序，而这些程序在主存储器中的位臵此时不能由程序员自已来确定，否则将出现多道程序竞争同一存储空间的情况。
J0 J1 J2 J3 J4 J5 J6 J7
J0 J2 J3 J5 J7
(A)系统运行初期
（ B）系统运行若干时间以后可利用空间块或空闲块占用块现在讨论，在图 12.1（ b）所示的内存状态下，此时又有新的用户作业进入系统请求分配内存，系统将如何处理？
通常有两种做法：一种策略是系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存是否已空闲，直到分配无法进行另一种策略是用户程序一旦运行结束，便将它所占内存区释放成为空闲块，同时，每当新的用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个“合适”的空闲块分配之。
为了实现这种分配策略，系统需建立一张记录所有空闲块的可利用空间表。此表的结构可以是目录表也可以是链表。如图 12.2所示为某系统运行过程中的内存状态及其两种结构的可利用空间表。
0 10000 20000 28000 32000 9999955000
10000 10000 空闲
28000 4000 空闲
55000 45000 空闲起始地址 内存块大小 使用情况
0 10000 10000 0 28000 4000 0 55000 45000 ^
av
（ c）链表
12,2可利用空间表及分配方法操作系统既可借助目录表结构也可借助链表结构实现动态存储分配,本节将对采用链表的情况进行讨论 。
根据系统运行的不同情况,可利用空间表可以有三种不同的结构形式：
第一种情况是系统运行期间所有用户请求分配的存储量大小相同。对此类系统，可以在系统开始运行时将内存的用户区域按所需大小分割成若干大小相同的块，然后用指针链接成一个可利用空间表。
由于表中结点大小相同，所以在分配时无需查找，只要将第一个结点分配给用户即可；同样，当用户程序释放内存时，系统只需将用户释放的空闲块插入在表头即可。这种情况下的可利用空间表实质上是一个链栈，对应的存储管理方式在操作系统中称为,固定分区管理” 。
第二种情况是系统运行期间用户请求分配的存储量有若干大小的固定规格。
对此系统，可将用户存储空间分割成不同规格的若干块，并将大小相同的空闲块组织在同一个可利用空间表中，即同一链表中的结点大小相同。
tag type link
space
0 0 0 0 0 0 ^…
av2
0 1 0 1 0 1 ^…
av4
0 2 0 2 0 2 ^…
av8
0 空闲块
1 占用块
0 结点大小为 2KB
1 结点大小为 4KB
2 结点大小为 8KB
tag=
type=
例,
第三种情况是系统在运行期间分配给用户的内存块大小不固定,可以随请求而变 。 此时,可利用空间表中的结点即空闲块的大小也是随意的 。 通常,操作系统中的可利用空间表属于这种类型,这种存储管理实际上就是操作系统中的可变分区管理方法 。 系统初始状态下,整个内存空间是一个空闲块,即可利用空间表中只有一个大小为整个内存区的结点,随着分配和回收的进行,可利用空间表中的结点大小和个数也随之而变 。
由于链表中结点大小不同，结点的结构可包含四个域，即：标志域（ tag），用于区分此块是否为空闲块、大小域（ size），用于指示空闲块的存储量、链域（ link），用于指示可利用空间链表中的下一个结点、存储空间域（ space），它是一个大小为 size的连续存储空间。
tag size link
space
0 空闲块
tag=
1 占用块由于可利用空间表中的结点大小不同，因此相应的分配与回收过程较为复杂。假设某用户需大小为 n
的内存，而可利用空间表中仅有一块大小为 m≥n的空闲块，则只需将其中大小为 n的一部分分配给申请的用户，同时将剩余大小为 m-n的部分作为一个结点留在链表中即可。当可利用空间表中存在多个空间大小不小于 n的空闲块时，一般可采用以下三种不同的分配策略。
（ 1）最先适应分配算法，这种方法又称为首次适配法。每次分配时，总是顺序查找可利用空间链表，找到第一个能满足长度要求的空闲区为止。分割这个找到的未分配区，一部分分配给作业，另一部分仍为空闲区。
（ 2）最优适应分配算法。这种分配算法每次从空闲区中挑选一个能满足作业要求的最小分区，这样可保证不去分割一个更大的区域，使装入大作业比较容易得到满足。
（ 3）最坏适应分配算法。最坏适应分配算法总是挑选一个能满足作业要求的最大的空闲区分割给作业使用，这样可使剩下的空闲区不至于太小，这种算法对中、小作业是有利的。
上述三种分配方法的选取一般需要考虑以下因素：
用户的逻辑要求；请求分配量的大小分布；分配和释放的频率以及效率对系统的重要性等 。
无论采用何种分配方法在进行回收系统空闲块时需要考虑“结点合并”的问题，即当系统在不断进行分配和回收的过程中，大的空闲块逐渐被分割成小的占用块，当用户程序将某一占用块释放重新成为空闲块时，如果将它作为一个独立的空闲块插入到链表中，
将出现两个或多个地址相邻的空闲块作为几个结点独立放在可利用空间表中，显然这不利于以后出现的大容量作业的请求。为了更有效地利用内存，就要求系统在回收时应考虑将地址相邻的空闲块合并成尽可能大的结点。
12,3边界标识法边界标识法是操作系统中用以进行动态分区分配的一种存储管理方法，它属于 12.2节中介绍的第三种情况，即用户请求的内存块大小不固定，随不同的请求而变化。系统将所有的空闲块链接在一个双重循环链表结构的可利用空间表中；分配可按最先适应分配算法进行，也可按最优适应分配算法进行。系统的特点在于：在每个内存区的头部和底部两个边界上分别设有标识，以识别该区域为占有块或空闲块，使得在回收用户释放的空闲块时容易判别在物理位臵上与其相邻的内存区域是否为空闲块，以便将所有地址连续的空闲存储区组合成一个尽可能大的空闲块。
12,3,1 可利用空间表的结构
llink tag size
space
rlink
uplink tag
head
foot
它表示一个空闲块。整个结点由三部分组成。其中 space为一段地址连续的存储单元，是可以分配给用户的内存区域，它的大小保存在 head中的 size域中。
它以头部 head和底部 foot作为它的两个边界；在 head
和 foot中分别设有标志域 tag，且设定空闲块中 tag的值为,0”，占用块中 tag的值为,1”； foot位于结点底部，
因此它的地址是随结点中 space空间的大小而变的。
为方便操作，可利用空间表可组织成双重循环链表。
head中的 llink和 rlink分别指向链表中的前趋结点和后继结点，表中不设表头结点，表头指针 pav可以指向表中任一结点，即任何一个结点都可看成是链表中的第一个结点；表头指针为空则表明可利用空间表为空。
1000
0
0 600
0
0 2000
0
0
pav
12,3,2分配算法本节以最先适应分配算法来说明边界标识法的应用 。 实现时,可以从表头指针 pav所指的第一个结点开始进行查询,找到第一个容量不小于请求分配的存储量的空闲块即可进行分配 。 为了使整个系统更有效地运行,在边界标识法中可做如下两条约定：
（ 1） 假设找到的某个待分配的空闲块的容量为 m个字,若每次只从中分配 n（ n<m） 个字给用户作业,
则剩余 m-n个字大小的空闲块结点仍留在链表中 。 如此进行多次分配之后,链表中会出现一些容量极小称之为,碎片,的空闲块,这样将大大减慢分配 （ 查找 ）
的速度 。 为克服这一弊端,可以选定一个适当的容量
e,当 m-n<e时,就将容量为 m的空闲块整块分配给用户作业；反之,只分配其中 n个字的内存块 。 同时,
为了避免修改指针,在分配部分空间时约定将结点中的高地址部分分配给用户 。
（ 2） 按照最先适应分配策略,每次在分配存储块时总是从表头指针 pav所指的结点开始进行查找,找到第一不小于 n的空闲块即进行分配 。 但是,由于每次总是从同一个结点开始查找,必然造成存储容量小的结点集中在链表的前端,这同样会增加查找较大空闲块的时间 。 因此,在每次分配完成之后,令指针 pav指向刚进行分配的结点的后继结点,这就是为何将可利用空间表组织成循环链表的原因 。
例如,对图 12.6所示的可利用空间表进行分配一个大小为 500个字的存储单元后可利用空间表的状态如图 12.7所示,此时,表头指针 pav指向了下一个结点 。
1000
0
0 600
0
0 2000
0
0
pav 分配 500个字
500
0
pav
12,3,3回收算法当用户释放占用块，系统需立即回收以备新的请求产生时进行再分配。为了使物理地址毗邻的空闲块结合成一个尽可能大的结点，首先需要检查刚释放的占用块的左、右紧邻是否为空闲块。采用边界标识法实现动态存储管理时每个内存区（无论是占用块或空闲块）的边界上都设有标志值，因此很容易区分刚释放的占用块的左、右紧邻是否为空闲块或占用块。
若释放块的左,右邻区均为占用块,则处理最为简单,只要将此新的空闲块作为一个结点插入到可利用空间表中即可；若只有左邻区是空闲块,则应将回收块与其左邻区合并成一个结点；若只有右邻区是空闲块,则应将回收块与其右邻区合并成一个结点；若左,
右邻区都是空闲块,则应将三块合起来成为一个结点留在可利用空间表中 。
12,4无用单元的收集可利用空间表虽然方便地实现了存储空间的动态管理,但它的主要特点是应用户的请求而分配内存,在用户释放存储空间时进行回收 。 因此,在这类存储管理系统中,用户必须明确给出,请求,和,释放,的信息 。 但用户难免在某些时候会因为疏漏或其它原因致使系统没有进行回收而产生,无用单元,的问题 。
此处,,无用单元,指的是那些用户不再使用而系统又没有回收的结构或变量 。 例如,下列 C程序段
s=malloc（ 20） ；
t=malloc（ 12） ；
…
s=t;
执行的结果是使执行 s=malloc（ 20）为用户分配的结点成为无用单元，无法得到使用。
另外，由于数据结构本身的原因也有可能造成无用单元的产生，如广义表中存在着共享和递归成份，对共享结点来说，当该结点从某一条链上删除时它可能还链接在别的关系中，并不能立即释放该结点的空间，
所以只有在全部链接关系中都被删除时，该结点才是无用结点，该结点所占用的空间才成为无用单元可以回收。
因此，要及时释放共享结点所占的空间，必须给每个结点增设一个共享计数器，记录本结点被几个链共享，当结点从某一链中被删除时，就将此计数器减
1，反之在插入时计数器加 1，一旦该计数器被减到 0
时，说明该结点在结构中不再有用，便可以回收。
这种处理方法的缺点是增加了额外的存储开销,
同时也使程序的处理变得更加复杂 。 有时少量无用单元的存在并不会影响系统的正常运行,但是当无用单元积累到一定阶段,就要求系统去找出这些无用单元,
并把它们送回到可利用空间表中去 。 在这里关键的问题是如何从整个存储空间中找出那些无用单元 。
“标志,算法通过周游广义表给每个有用结点记上标志,
相应地所有无用结点由于不带标志,因此只要扫描一遍内存就可通过标志判断哪些是有用结点,哪些是无用结点,这样便可将所有的无用单元收回至可利用空间表 。
实际运行的系统中结点的大小可能不等，但这并不影响“标志”算法，标志算法只要求找到结点的开始地址和其中描述结点之间关系的几个字段，并不关心结点中其它信息的长短。因此，可以假设所有结点的结构如图 12.8所示。
mark tag link1 link2 size
info
其中,link1和 link2是两个指向同类型结点的指针，其意义可以解释为广义表的双链表示法。 mark是一标志位，初值为 0，执行标志算法后，将全部有用结点的
mark字段值臵为 1，其值继续保持为 0的则为无用单元。
tag也是一个标志位，初值为 0，在标志算法执行过程中，周游到本结点所对应的子表时被臵成,1”，返回以后再恢复成,0”。 size字段表示本结点的长度，它主要在回收和压缩算法中起作用，在标志算法中它并不起作用。
算法 12.3给出了标志算法 。 算法初始时,所有结点的 mark和 tag字段都臵为 0,指针变量 t指向广义表的根结点 。 算法执行中,p指向当前处理的结点,r指向 p所指结点的前趋结点 。 算法结束时,所有广义表中的有用结点中的 mark字段被臵成,1”。
12,5存储压缩在动态存储管理中,由于每个用户作业所需的存储空间大小不尽相同,所以当系统运行一段时间后必然导致可利用空间表中存在一些容量很小的内存块,这些内存块分布在内存中的不同区域,它们很难再次被作业利用 （ 在操作系统中这种小块内存被称为,碎片,）,这大大降低了存储空间的利用率 。
,存储压缩,是将所有的空闲块移到一个连续的存储区,从而使可利用空间形成一个连续的存储块,
这样可以满足大作业的需求,提高系统的利用率 。
实施“存储压缩“通常有两种做法，一种是一旦有用户释放存储块即进行回收压缩；另一种是在程序执行过程中不回收用户随时释放的存储块，而是在可利用空间不够分配或在进行无用单元的收集时进行“存储压缩”。
例,压缩前 压缩后存储压缩的过程比较复杂,不仅要改变结点的物理地址,同时还要修改结点中的全部指针 。 实际上,存储压缩是有条件的,当某个有用块中的程序正在执行与外设相关的输入输出操作时不能进行程序的移动 （ 具体的原因在操作系统相关课程中学习 ） 。 此处,可以通过以下三个步骤来实现存储压缩：
（ 1） 给有用结点分配新地址；
（ 2） 修改有用结点的指针值；
（ 3） 将有用结点移动到新分配的位臵 。
