数据结构 动态存储管理 第八章动态存储管理 主讲：张昱 重点：内存空间的分配与回收算法，以 yuzhang@ustc.edu 及可利用空间表的结构。 0551-3603804 难点：无用单元收集算法的理解与掌 握。 /35 2/35 第八章动态存储管理 8.1概述(1) 8.1概述 。程序中的变量如何存储管理？ 。早期，由程序员自己先成： 8.2可利用空间表及分配方法 在执行痕序之前，光高将厕机悬语言成江铺语言感写的在序情远到 内存的个国定区城上，并预先给变量和分配好对应的内存地 8.3边界标识法 址绝对成湘时地址) 8.4伙伴系统 ,有了高级语言后，程序员不需直接和内存地址打交道： 变量对应的内年地址复是电城座在城是盛热：时进折分靴 8.5无用单元收集 ·操作系统 存情管理是操作系械和铺泽瘦序的一 木热且广垂的问L 8.6存储紧缩 ·单用户操作系统：内存空可藏切分为素绿区（供系线超序使用）和用 户区（供单一的用户程序所使用） 多道程序设计：多个用户程序共率一个内存区城，每个用户程序 用的内存就由操作系统来进行分配。 3/35 4/35 图 8.1概述(2) 8.1概述(3) ■动态存储管理的基本问题 ·系统如何用用户提出的“请求”分配内存？ 。如何回收那些用户不再使用而“释放”的内存，以备新的 动态存储管理系统刷开工时 空闲块 “请求”产生时重新进行分配？ 用户提出的“请求”： 不☑不N 。可能是进入系统的一个作业 。也可能是程序执行过程中的一个动态变量 占用块 系能运行初期 系统每次分配给用户都是一个地址连续的内存区。称已分 配给用户使用的地址连续的内存区为“占用块”，称未曾分 不N ■ 配的地址违续的内存区为“可利用空间块”或“空闲块”。 系能运行若干时间之后 5/35 图 6/35 图
1 1/35 数据结构——动态存储管理 主讲：张昱 yuzhang@ustc.edu 0551-3603804 2/35 重点：内存空间的分配与回收算法，以 及可利用空间表的结构。 难点：无用单元收集算法的理解与掌 握 。 第八章 动态存储管理 3/35 第八章 动态存储管理 8.1 概述 8.2 可利用空间表及分配方法 8.3 边界标识法 8.4 伙伴系统 8.5 无用单元收集 8.6 存储紧缩 4/35 8.1 概述(1) 程序中的变量如何存储管理？ 早期，由程序员自己完成： 在执行程序之前，先需将用机器语言或汇编语言编写的程序输送到 内存的某个固定区域上，并预先给变量和数据分配好对应的内存地 址(绝对或相对地址) 有了高级语言后，程序员不需直接和内存地址打交道： 变量对应的内存地址都是由编译程序在编译或执行时进行分配 操作系统 单用户操作系统：内存空间被划分为系统区(供系统程序使用)和用 户区(供单一的用户程序所使用) 多道程序设计：多个用户程序共享一个内存区域，每个用户程序使 用的内存就由操作系统来进行分配。 存储管理是操作系统和编译程序的一 个复杂且重要的问题！ 5/35 8.1 概述(2) 动态存储管理的基本问题 系统如何用用户提出的“请求”分配内存？ 如何回收那些用户不再使用而“释放”的内存，以备新的 “请求”产生时重新进行分配？ 用户提出的“请求”： 可能是进入系统的一个作业 也可能是程序执行过程中的一个动态变量 系统每次分配给用户都是一个地址连续的内存区。称已分 配给用户使用的地址连续的内存区为“占用块”，称未曾分 配的地址连续的内存区为“可利用空间块”或“空闲块”。 6/35 8.1 概述(3) U1 U2 U3 U4 U5 U6 U7 U8 系统运行初期 U1 U3 U4 U6 U8 系统运行若干时间之后 占用块 动态存储管理系统刚开工时 空闲块
8.1概述(4) 8.1概述(5) M不N 下☐ 10000 2000 39000 59000 99999 当有新的用户进入系统请求分配内存，系统将如何做呢？ 3100 。策略一：从高地址的空闲块中进行分配，当分配无法进 (a)内存状态 行时，系统回收所有用户不再使用的空闲块，并量新组 忽始地址内存块大小使用情况 织内存，将所有空闲的内存区连接在一起成为一个大的 10,00015,000 空用 空闲块。 31,000 8,000 。策略二：从所有空闲块中找出一个“合适”的空闲块分配 空用 0150007 080002 041.0002 之 59,000 41,000 空用 系统需要建立一张记录所有空闲块的“可利用空间麦”， (b)目录表 (c)能表 它可以是目录表，也可以是“能表。 回 8/35 图 8.2可利用空间表及分配方法 8.2可利用空间表及分配方法(1) 。可利用空间表的表示一链表 。一个空闲块)一个结点 讨论利用可利用空间表进行动态 ·用户请求分配时，系统从表中剩除一个结点分配之 存储分配的方法， ·用户释放所占内存时，系统即回收并将它插入到表中 ■目录表简单，将在操作系统课程中介 。可利用空间表的结构 绍 。系统运行期间所有用户请求分配的存储量大小相同 。这里仅就链表的情况进行讨论 ·由于表中结点大小相同，则分配时无需查找 。可以用链找实现 —操作系统中的固定分区管理 9/35 图 10/35 图 8.2可利用空间表及分配方法(2) 8.2可利用空间表及分配方法(3) 系统运行期间用户请求分配的 tag type link ·系统运行期间用户请求分配的存储量有若干种 存储量有若干种大小的规格 value 大小的规格 。建立若干个可利用空间 a2口 ·分配 表，同一链表中的结点大 o000 ·从结点大小和请求分配的量相同的链表中查找 小相同 a4 结点并分配之 。每个结点的第一个字设有 01 01G 01a ·若没有，则从结点较大的链表中查找结点，将 链城(ink):指向同一蛙 其中一部分分配给用户，剩余的播入到相应大 表中下一结点的指针 av8口 小的链表中 标志城(tag上0-空厢 0202 02N 若各链表都没有合适的结点，则要执行“存情紧 块、1-占用换 缩”将小块合并 结点类型城(ype):区 回收 分大小不同的德点 ·将释放的空闲块插入到相应大小的链表的表头 11/35 图 12/35 2
2 7/35 8.1 概述(4) 当有新的用户进入系统请求分配内存，系统将如何做呢？ 策略一：从高地址的空闲块中进行分配，当分配无法进 行时，系统回收所有用户不再使用的空闲块，并重新组 织内存，将所有空闲的内存区连接在一起成为一个大的 空闲块。 策略二：从所有空闲块中找出一个“合适”的空闲块分配 之。 系统需要建立一张记录所有空闲块的“可利用空间表”， 它可以是“目录表”，也可以是“链表”。 U1 U3 U4 U6 U8 8/35 8.1 概述(5) U6 0 10000 25000 31000 39000 59000 99999 (a) 内存状态 59,000 41,000 空闲 31,000 8,000 空闲 10,000 15,000 空闲 起始地址 内存块大小 使用情况 (b) 目录表 0 15,000 av (c) 链表 0 8,000 0 41,000 ^ 9/35 8.2 可利用空间表及分配方法 讨论利用可利用空间表进行动态 存储分配的方法. 目录表简单，将在操作系统课程中介 绍 这里仅就链表的情况进行讨论 10/35 8.2 可利用空间表及分配方法(1) 可利用空间表的表示——链表 一个空闲块Æ一个结点 用户请求分配时，系统从表中删除一个结点分配之 用户释放所占内存时，系统即回收并将它插入到表中 可利用空间表的结构 系统运行期间所有用户请求分配的存储量大小相同 由于表中结点大小相同，则分配时无需查找 可以用链栈实现 ——操作系统中的固定分区管理 11/35 8.2 可利用空间表及分配方法(2) 系统运行期间用户请求分配的 存储量有若干种大小的规格 建立若干个可利用空间 表，同一链表中的结点大 小相同 每个结点的第一个字设有 链域(link)：指向同一链 表中下一结点的指针 标志域(tag)：0-空闲 块、1-占用块 结点类型域(type)：区 分大小不同的结点 tag type link value 0 0 av2 0 0 0 0 ^ 0 1 av4 0 1 0 1 ^ 0 2 av8 0 2 0 2 ^ 12/35 8.2 可利用空间表及分配方法(3) 系统运行期间用户请求分配的存储量有若干种 大小的规格 分配 从结点大小和请求分配的量相同的链表中查找 结点并分配之 若没有，则从结点较大的链表中查找结点，将 其中一部分分配给用户，剩余的插入到相应大 小的链表中 若各链表都没有合适的结点，则要执行“存储紧 缩”将小块合并 回收 将释放的空闲块插入到相应大小的链表的表头
8.2可利用空间表及分配方法(4) 8.2可利用空间表及分配方法(5) ·系统运行期间分配给用户的内存块的大小不 ■可利用空间表中的结点大小不同时的分配方法 固定 候设用户需大小为m的内存 ·开始时，整个内存空间是一个空闲块 ,若链表中仅有一块大小为m>的空闲块：将其中大小 。随着分配和回收的进行，可利用空间表中的结点 为n的一部分分配给用户，剩余大小为mn的作为一个 大小和个数也随之而变 结点窗在能表中 。结点的结构 。若链表中有若干个不小于的空闲块：有三种分配策$ ,链域(ink):指向同一链表中下一结点的指针 ·首次拟合法：取第一个不小于的空用块 。标志城(tag):0-空闲块、1-占用块 tag size link 。量佳拟合法：取表中一个不小于m且最接近的空闲块 。大小城《sz):指示该空闲块的存情量 表技空用块大小自小到大有序，适于太小范较广的系线 s印ace:地址违埃的内存空间 space 最拟合法：取表中不小于且是表中最大的空闲块 操作系统中的可变分区管理 表按空用快大小自大至小有序，通于太小范■较空的系绕 13/35 回 14/35 图 8.3边界标识法(1) 8.3边界标识法(2) ■边界标识法(Boundary tag method) 可利用空间表的结构 ,可利用空间表：双重循环链表 typedef struet WORD{∥内存字类型 union【 ,分配：首次拟合或最住拟合 head llink tag size rlink VORD *llink:指向前驱结表 WORD*aplink:∥指向本站底头部 ,特点 space int tag:∥0空用：1-占用 。每个内存区的头部和底部两个边界上分别设有标 int size;∥换大小 识，以标识该区域为占用块或空闲块，使得在回收 WORD*rink:指向后城结表 时易于判别在物理位置上与其相邻的内存区域是否 ,在共玄本分 为空闲块，以便将所有地址违续的空闲存储区组合 foot uplink tag 成一个尽可能大的空闲块。 #define FootLoc(p)p+p->size-1 15/35 图 16/35 图 8.3边界标识法(3) 8.3边界标识法(4) 分配算法（算法8.1P200) ■回收算法(P201w203) 氯设用首次椒合法进行分配，请求分配的存情量为， 般设用户产释放的内存区的头年地址为印 为使整个系就更有批地适行，在边界标识法中作知下的定 。要检查刚释放的占用块州的左、右繁邻是否为空闲快 ,服设找到的特分配空细块的容量为个字（包括头部），选定一个适 。与M年地址景邻的内存区的库都地址为-1 当的常量e,当m-n≤e时，就将春量为m的空闲块整块分配给用 ,与M高地址景都的内存区的头都地址为p+p->sze 户，否则只分配其中个李的内存换。 。M的左、右邻区均为占用快：简单酒入 为遭免修政指针，约定将该结点中的高地址部分分配给用户。 ·M的左部区为空佣快，有邻区为占用换：合并左郁区和M,增加左 都空闲块结点的sze域的值，置新设置结点的底部 ·每次分配从不同的结点（如刚进行分配的结点的后缝）开始进行查 。M的右邻区为空调块，左邻区为占用快合并M和右部区，结点的 找，使分配后剩余的小块均匀地分布在链表中。一遵免小块集中 底部位置不变，头部要变，链表的指针也要变 在头指针所指结点附近，从而增加查询较大空闲块的时间 ·M的左、右邻区均为空闲块：合并左邻区、M和右邻区，增加左邻 17/35 图 空闲块的$立山，在能表中制除右邻空闲块鲔点，修放康都回 18/35 3
3 13/35 8.2 可利用空间表及分配方法(4) 系统运行期间分配给用户的内存块的大小不 固定 开始时，整个内存空间是一个空闲块 随着分配和回收的进行，可利用空间表中的结点 大小和个数也随之而变 结点的结构 链域(link)：指向同一链表中下一结点的指针 标志域(tag)：0-空闲块、1-占用块 大小域(size)：指示该空闲块的存储量 space：地址连续的内存空间 ——操作系统中的可变分区管理 tag size link space 14/35 8.2 可利用空间表及分配方法(5) 可利用空间表中的结点大小不同时的分配方法 假设用户需大小为n 的内存 若链表中仅有一块大小为m≥n的空闲块：将其中大小 为n的一部分分配给用户，剩余大小为m-n的作为一个 结点留在链表中 若链表中有若干个不小于n的空闲块：有三种分配策略 首次拟合法：取第一个不小于n的空闲块 最佳拟合法：取表中一个不小于n且最接近n的空闲块 表按空闲块大小自小到大有序，适于大小范围较广的系统 最差拟合法：取表中不小于n且是表中最大的空闲块 表按空闲块大小自大至小有序，适于大小范围较窄的系统 15/35 8.3 边界标识法(1) 边界标识法(Boundary tag method) 可利用空间表：双重循环链表 分配：首次拟合或最佳拟合 特点 每个内存区的头部和底部两个边界上分别设有标 识，以标识该区域为占用块或空闲块，使得在回收 时易于判别在物理位置上与其相邻的内存区域是否 为空闲块，以便将所有地址连续的空闲存储区组合 成一个尽可能大的空闲块。 16/35 8.3 边界标识法(2) 可利用空间表的结构 llink tag size rlink space uplink tag head foot typedef struct WORD{ // 内存字类型 union { WORD *llink; // 指向前驱结点 WORD *uplink; // 指向本结点头部 }; int tag; // 0-空闲; 1-占用 int size; // 块大小 WORD *rlink; //指向后继结点 OtherType other; //字的其它部分 }WORD, head, foot, *Space; // 指向p所指结点的底部 #define FootLoc(p) p+p->size-1 17/35 8.3 边界标识法(3) 分配算法 (算法8.1 P200) 假设用首次拟合法进行分配，请求分配的存储量为n。 为使整个系统更有效地运行，在边界标识法中作如下约定 假设找到的待分配空闲块的容量为m个字(包括头部)，选定一个适 当的常量e，当m-n≤e时，就将容量为m的空闲块整块分配给用 户；否则只分配其中n个字的内存块。 为避免修改指针，约定将该结点中的高地址部分分配给用户。 每次分配从不同的结点(如刚进行分配的结点的后继)开始进行查 找，使分配后剩余的小块均匀地分布在链表中。——避免小块集中 在头指针所指结点附近，从而增加查询较大空闲块的时间 18/35 8.3 边界标识法(4) 回收算法(P201~203) 假设用户释放的内存区的头部地址为p 要检查刚释放的占用块M的左、右紧邻是否为空闲块 与M低地址紧邻的内存区的底部地址为p-1 与M高地址紧邻的内存区的头部地址为p+p->size M的左、右邻区均为占用块：简单插入 M的左邻区为空闲块，右邻区为占用块：合并左邻区和M，增加左 邻空闲块结点的size域的值，重新设置结点的底部 M的右邻区为空闲块，左邻区为占用块：合并M和右邻区，结点的 底部位置不变，头部要变，链表的指针也要变 M的左、右邻区均为空闲块：合并左邻区、M和右邻区，增加左邻 空闲块的size值，在链表中删除右邻空闲块结点，修改底部
8.4伙伴系统(1) 8.4伙伴系统(2) 伙伴系统(buddy system) ·可利用空间表的结构 ·与边界标识法类似 年define m16 typedef struet WORD!内存字类型 。不同点是：在伙伴系统中，无论是占用块或空闲块，其大小均为 2的k次幂(k为某个正蓝数) head llink tag kval rlink VORD *link:∥指向前狐结森 int tag:刀0空闲：占用】 。可利用空问表 细tka止∥块大小，值为2的罩次k space WORD*rink:指向后整蜂戒 ·若可利用内存喜量为2个字，则空闲换的大小只能是2、 OtherType other:∥字的其它年分 21、…、2m WORD.head: ·所有大小相同的空闲块建于一张子表中，每个子表是一个双重精 typedef struct HeadNode 环城表，可能有m+1个子表 2k-1 t nodesize;∥被链表的空闲块的大小 ·将m+1个表头指针用向量结构组织成一个表 2 WORD*s出城能表的表头糯针 3 FreeList[m+H:录头向量类型 2m 19/35 回 20/35 回 8.4伙伴系统(3) 8.4伙伴系统(4) ■分配算法（算法8.2P205) ·回收算法(P205,206) 银设用请求分配的存铺量为n, 假设用户释放的内存区的起始地址为，块的大小为2 ,若21<n<2北1，且第k+1个子表不空，则只要除此蛙表中第 一个结点并分配给用户即可 ·伙伴系统仅考虑互为“伙伴”的两个空闲块的归并 若22<n≤21-1，结点大小为21的子表为空，则从结点大小 为2必的子表中取出一块，将其中一半分配给用户，剩余的一半作为 伙伴：两个由同一大块分裂出来的小块就称为“互为 一个新结点插入在结点大小为21的子表中 伙伴”。假设即为大小为2k的空闲块的初始地址，且 ,若2+1<n<2L1(为小于k的整款)，并且所有结点小于2的子 pMOD2k+1=0,则初始地址为P和p+2的两个空 表均为空，则周样福从结点大小为2*的子表中取出一块，将其中 2~分配给用户，剩余部分分剂成若干个轴点分别插入在结点大小 闲块互为伙伴。 为2、21、、21的子表中。 21/35 图 22/35 图 8.4伙伴系统(5) 8.5无用单元收集(1) ,判别其伙伴是否为空闲块 ■8.2~8.4节讨论的存储管理系统中，用户必须明确给出 ·若是，则在相应子表中找到其伙伴并除之，然后再兴别合并 “请求”和“释放”的信息 后的空闲块的伙伴是否是空用块 →因为用户的硫漏或结构本身的原因致使系统在不恰当的 。若否，则只要将释放的空用块葡单插入在相应子表中即可 时候或没有进行回收而产生“无用单元”或“悬挂访问”的问 ,伙伴块的起始地址 题。 「p+2(若pMOD2=0) 。无用单元：那些用户不再使用而系统没有回收的结构和变量。 buddy(p,k)= p-2(若pMOD2=2) :p=malloc(size);..P=NULL; 。悬挂访问：访问已经被得放的结点 ▣对伙伴系统的评价 例：p=malloc(size);…q=p;free(pjia=*q 。优点：算法简单、速度快 因结构本身的特性，也会产生上述问夏 例如广义表的结构：共事子表（图8.9P207) ·峡点：由于只归并伙伴而容易产生醉片 图 24/35 图 4
4 19/35 8.4 伙伴系统(1) 伙伴系统(buddy system) 与边界标识法类似 不同点是：在伙伴系统中，无论是占用块或空闲块，其大小均为 2的k次幂(k为某个正整数) 可利用空间表 若可利用内存容量为2m个字，则空闲块的大小只能是20、 21、…、 2m 所有大小相同的空闲块建于一张子表中，每个子表是一个双重循 环链表，可能有m+1个子表 将m+1个表头指针用向量结构组织成一个表 20/35 8.4 伙伴系统(2) 可利用空间表的结构 llink tag kval rlink space head #define m 16 typedef struct WORD{ // 内存字类型 WORD *llink; // 指向前驱结点 int tag; // 0-空闲; 1-占用 int kval; // 块大小,值为2的幂次k WORD *rlink; //指向后继结点 OtherType other; //字的其它部分 }WORD, head; typedef struct HeadNode{ int nodesize; // 该链表的空闲块的大小 WORD *first; //该链表的表头指针 } FreeList[m+1]; //表头向量类型 20 … 2k-1 2k … 2m … 21/35 8.4 伙伴系统(3) 分配算法 (算法8.2 P205) 假设用请求分配的存储量为n 。 若2k-1<n ≤ 2k-1，且第k+1个子表不空，则只要删除此链表中第 一个结点并分配给用户即可 若2k-2<n ≤ 2k-1-1，结点大小为2k-1的子表为空，则从结点大小 为2k的子表中取出一块，将其中一半分配给用户，剩余的一半作为 一个新结点插入在结点大小为2k-1的子表中 若2k-i-1<n ≤ 2k-i-1(i为小于k的整数)，并且所有结点小于2k的子 表均为空，则同样需从结点大小为2k的子表中取出一块，将其中 2k-i分配给用户，剩余部分分割成若干个结点分别插入在结点大小 为2k-i、 2k-i+1、…、 2k-1的子表中。 22/35 8.4 伙伴系统(4) 回收算法(P205，206) 假设用户释放的内存区的起始地址为p，块的大小为2k 伙伴系统仅考虑互为“伙伴”的两个空闲块的归并 伙伴：两个由同一大块分裂出来的小块就称为“互为 伙伴”。假设p为大小为2k的空闲块的初始地址，且 p MOD 2k+1=0，则初始地址为p和p+2k的两个空 闲块互为伙伴。 23/35 8.4 伙伴系统(5) 判别其伙伴是否为空闲块 若是，则在相应子表中找到其伙伴并删除之，然后再判别合并 后的空闲块的伙伴是否是空闲块 若否，则只要将释放的空闲块简单插入在相应子表中即可 伙伴块的起始地址 对伙伴系统的评价 优点：算法简单、速度快 缺点：由于只归并伙伴而容易产生碎片 1 1 2 ( MOD 2 0 ) buddy( , ) 2 ( MOD 2 2 ) k k k kk p p p k p p + + ⎧ + = = ⎨ ⎩ − = 若 若 24/35 8.5 无用单元收集(1) 8.2~8.4节讨论的存储管理系统中，用户必须明确给出 “请求”和“释放”的信息 Î因为用户的疏漏或结构本身的原因致使系统在不恰当的 时候或没有进行回收而产生“无用单元”或“悬挂访问”的问 题。 无用单元：那些用户不再使用而系统没有回收的结构和变量。 例： p = malloc(size); …. p=NULL; 悬挂访问：访问已经被释放的结点 例： p = malloc(size); …. q=p; free(p); a = *q; 因结构本身的特性，也会产生上述问题 例如广义表的结构: 共享子表(图8.9 P207)
8.5无用单元收集(2) 8.5无用单元收集(3) 。如何解决广义表结构中的“无用单元”或“悬挂访问”问题？ ·如何解决广义表结构中的“无用单元”或悬挂访问”问愿？ 。使用访问计数悬 。收集无用单元 在所有子表成广义表上增加一个表头结点，并设立 在程序运行中，所有的能表站点不管是否还有用， 国难 都不被回收，直到整个可利用空间表为空。此时中断 一个“计数城”，它的值为指向过子表减广义表的指针 执行准序，收集无用单元，分两步进行： 数目。当读计数城的值为0时，此于表或广义表中的站 1)对所有占用站点加上标志(0-未用，1-占用) 点才被释放。 2》对整个可利用存储空间顺序扫描一造，将标志为0 的站点能成一个新的可利用空间袁， 25/35 回 26/35 图 8.5无用单元收集(4) 8.5无用单元收集(5) 。标志(mark)算法：加标志的操作实质上是通历广义表，将 。非递归标志算法 广义表中所有结点的标志战(mark)赋值为“1”. 。程序中附设栈成队列实现广义表的遍历。 。假设广义表采用头尾链表示： 。类似于图的深度优先薄历或广度优先遭历 原子结，点(mark,tag,atom:表结点(mark,tag,hp,tp) 。评价：栈或队列的空间同样是不确定的 。递归算法： ,利用表结点本身的指针城标记墙历路径的标志算法 盖本项：1)表为空，则无须迪历： ·前述的递归和非递归标志算法，设栈的目的是： 2)若是一个敢据元囊，则标志元套结点 )记录谴历时所走的略径，以使在速历表头之后沿原路 归销项：首先标志表结点，再分别速历表头和表尾 逃圈，娘而对表见进行通历。 评价：需要一个较大的卖现遂归用的栈的铺动内存，黄内存不能 用于动本分家。由于表的层次不定，使得找的容量不易确定中可 ,利用已经标志过的表结点中的tag,hp和t中p域代普栈记 能会找逆出 27/35 录遗历过程中的路径，震8.10，P208209)图 8.5无用单元收集(6) 8.5无用单元收集(7) 。利用表结点本身的指针域标记速历路径的标志算法 。利用表结点本身的指针罐标记塘历路径的标志算法 。算法思想 银设印指向刚加上兼态的某个表布底时，指向p的举兼站点，q 氧流即指向侧加上标志的莱个表塘点时，指向p的章表结燕， 指向p的兼头或表见.（如因8.1(ab).P2I0 q指向p的表头成表见.（加图8.11(ab,P210 当q指向的表头结点时，可能有三种情况出现： 当q粉向的表头结点时，可能有三种情况出现： 3)设即的表头为来加桥志的于表， 1)设p的表头只是一个元素体点(mark,tag。.atom), 则橘先遭历表头子表，即1=p;P=q: 则墙历表头仅需对该是头结点打上标志后即◆推向的是品： 为丁记下指针移动的路径，以便在印递回原结点时同时找到 2)设p的表头为空表或是巴加上桥志的于章(mark,tag.tp.hp), 的母表结点，则庄能壶t之前，应先记下整动的路径，即全所推 则无需速历表头只要令指向的麦是： 德点的b卫望的值为t2且ta蝶的值为0”， 29/35 图 3035 图 5
5 25/35 8.5 无用单元收集(2) 如何解决广义表结构中的“无用单元”或“悬挂访问”问题？ 使用访问计数器 在所有子表或广义表上增加一个表头结点，并设立 一个“计数域”，它的值为指向该子表或广义表的指针 数目。当该计数域的值为0时,此子表或广义表中的结 点才被释放。 26/35 8.5 无用单元收集(3) 如何解决广义表结构中的“无用单元”或“悬挂访问”问题？ 收集无用单元 在程序运行中，所有的链表结点不管是否还有用， 都不被回收，直到整个可利用空间表为空。此时中断 执行程序，收集无用单元，分两步进行: 1)对所有占用结点加上标志(0-未用，1-占用) 2)对整个可利用存储空间顺序扫描一遍，将标志为0 的结点链成一个新的可利用空间表。 困难 27/35 8.5 无用单元收集(4) 标志(mark)算法: 加标志的操作实质上是遍历广义表，将 广义表中所有结点的标志域(mark)赋值为“1”。 假设广义表采用头尾链表示： 原子结点(mark, tag,atom); 表结点(mark, tag,hp,tp) 递归算法： 基本项：1）表为空，则无须遍历； 2）若是一个数据元素，则标志元素结点 归纳项：首先标志表结点，再分别遍历表头和表尾 评价：需要一个较大的实现递归用的栈的辅助内存，该内存不能 用于动态分配。由于表的层次不定，使得栈的容量不易确定Î可 能会栈溢出 28/35 8.5 无用单元收集(5) 非递归标志算法 程序中附设栈或队列实现广义表的遍历。 类似于图的深度优先遍历或广度优先遍历 评价：栈或队列的空间同样是不确定的 利用表结点本身的指针域标记遍历路径的标志算法 前述的递归和非递归标志算法，设栈的目的是： Æ记录遍历时所走的路径，以便在遍历表头之后沿原路 退回，继而对表尾进行遍历。 利用已经标志过的表结点中的tag, hp和tp域代替栈记 录遍历过程中的路径。(图8.10, P208~209) 29/35 8.5 无用单元收集(6) 利用表结点本身的指针域标记遍历路径的标志算法 算法思想 假设p指向刚加上标志的某个表结点时，t指向p的母表结点， q指向p的表头或表尾。(如图8.11(a)(b),P210) 当q指向p的表头结点时，可能有三种情况出现： 1）设p的表头只是一个元素结点(mark, tag, atom)， 则遍历表头仅需对该表头结点打上标志后即令q指向p的表尾； 2）设p的表头为空表或是已加上标志的子表(mark, tag, tp, hp) ， 则无需遍历表头只要令q指向p的表尾； 30/35 8.5 无用单元收集(7) 利用表结点本身的指针域标记遍历路径的标志算法 假设p指向刚加上标志的某个表结点时，t指向p的母表结点，q 指向p的表头或表尾。(如图8.11(a)(b),P210) 当q指向p的表头结点时，可能有三种情况出现： 3）设p的表头为未加标志的子表， 则需先遍历表头子表，即t = p; p = q； 为了记下t指针移动的路径，以便在p退回原结点时同时找到p 的母表结点，则在修改t 之前，应先记下t移动的路径，即令p所指 结点的hp域的值为t，且tag域的值为“0
8.5无用单元收集(8) 8.5无用单元收集(9) 利用表结点本身的指针域标记遍历路径的标志算法 利用表结点本身的指针城标记遍历路径的标志算法 服设指向刚加上标志的某个表点时，指向p的章表华底，q 银设印指向刚加上标志的莱个表站点时，指向印的垂表施点，q 指向p的表头戴表见.（如丽8.1I(ab.P210 指向p的表头或来见.（如图8.11(abP210) 当q指向的表具结点时，可能有三种情况出现： 当q指向P的表尾结点时，可能有三种情况出现： 1)p的表尾为来加林老的子表， 2)p的表尾为空藏是巴咖林志的于表， 则需速历表尾子表，同样=pP=阳 则p应港回到其母表结点即t所滑结点，相应地也应后退一步， 为丁记下指针移动的略径，以便在退回原结点时同时找到加 即退到t结点的母表结点。 的母表结点，则在政之道，应先记下整动的路径，即全所推 t的移动路径已经记录在t>tp或在>p中，究竟是哪一个？ 能点的t越的值为， →根据tag来确定：t==0,取t->hp:tag==l,取->p 着指肉的结点是其母表表头，则应能续遭历其母表的表儿。 回 若指肉的结点是其母表表见，则应雕城找更高一层的母表结点。 31/35 3235 8.5无用单元收集(10) 8.6存储紧缩(1) :利用表结点本身的指针域标记遍历路径的标志算法 ·另一种动态存储管理方法 评价：不需要附加存储，但是几乎每个表结点的指针 ·无论何时，可利用空间都是一个地址连续的存储区， 城的值都要作两次改变，时间开销大。 在编译程序中称之为“堆” 分配 。无用单元收集算法的定量估计（略） 设立一个指针，赫为堆指针，地峰指向堆的最低（高） 。《垃圾收集》，人民邮电出版社，2004 地址。当用户中请N个单位的存储块，堆指针向高（低） Richard Jones,Rafael D Lins,Garbage Collection: 地址移动N个存储草位，而移动之前的堆指针的值就是 分配给用户的占用块的初始地址， Algorithms for Automatic Dynamic Memory Management, John Wiley Sons,Inc.1996 。回收：必须将所释放的空闲块合并到整个堆上去一 存储紧绵。 33/35 图 3435 图 8.6存储紧缩(2) 。存情紧缩的时机 ·方法1：一且有用户释敢存篇块即进行回收繁端 ·方法2：在程序执行过程中不回收用户随时廉放的存待快，直到 可利用空间不够分配或堆指针指向最高地址时才进行存储紧缩。 。存储繁缩的实现步骤 1)首先对占用块进行标志 2)计算占用块的新地址 3)修改用户的初始变量表 4)检查每个占用块中存储的数操 5)将所有占用块迁移到新地址去 35/35 图 6
6 31/35 8.5 无用单元收集(8) 利用表结点本身的指针域标记遍历路径的标志算法 假设p指向刚加上标志的某个表结点时，t指向p的母表结点，q 指向p的表头或表尾。(如图8.11(a)(b),P210) 当q指向p的表尾结点时，可能有三种情况出现： 1） p的表尾为未加标志的子表， 则需遍历表尾子表，同样t=p; p = q; 为了记下t指针移动的路径，以便在p退回原结点时同时找到p 的母表结点，则在修改t 之前，应先记下t 移动的路径，即令p所指 结点的tp域的值为t。 32/35 8.5 无用单元收集(9) 利用表结点本身的指针域标记遍历路径的标志算法 假设p指向刚加上标志的某个表结点时，t指向p的母表结点，q 指向p的表头或表尾。(如图8.11(a)(b),P210) 当q指向p的表尾结点时，可能有三种情况出现： 2） p 的表尾为“空”或是已加标志的子表， 则 p 应退回到其母表结点即 t 所指结点，相应地t也应后退一步， 即退到 t 结点的母表结点。 t 的移动路径已经记录在t->tp或t->hp中，究竟是哪一个？ Æ根据tag来确定：tag==0, 取t->hp; tag==1, 取t->tp 若t指向的结点是其母表表头，则应继续遍历其母表的表尾。 若t指向的结点是其母表表尾，则应继续找更高一层的母表结点。 33/35 8.5 无用单元收集(10) 利用表结点本身的指针域标记遍历路径的标志算法 评价：不需要附加存储，但是几乎每个表结点的指针 域的值都要作两次改变，时间开销大。 无用单元收集算法的定量估计(略) 《垃圾收集》，人民邮电出版社，2004 Richard Jones , Rafael D Lins，Garbage Collection : Algorithms for Automatic Dynamic Memory Management， John Wiley & Sons,Inc. 1996 34/35 8.6 存储紧缩(1) 另一种动态存储管理方法 无论何时，可利用空间都是一个地址连续的存储区， 在编译程序中称之为“堆” 分配 设立一个指针，称为堆指针，始终指向堆的最低(高) 地址。当用户申请N个单位的存储块，堆指针向高(低) 地址移动N个存储单位，而移动之前的堆指针的值就是 分配给用户的占用块的初始地址。 回收：必须将所释放的空闲块合并到整个堆上去—— 存储紧缩。 35/35 8.6 存储紧缩(2) 存储紧缩的时机 方法1：一旦有用户释放存储块即进行回收紧缩 方法2：在程序执行过程中不回收用户随时释放的存储块，直到 可利用空间不够分配或堆指针指向最高地址时才进行存储紧缩。 存储紧缩的实现步骤 1）首先对占用块进行标志 2）计算占用块的新地址 3）修改用户的初始变量表 4）检查每个占用块中存储的数据 5）将所有占用块迁移到新地址去