《数据结构》 第八章动态存储管理
《数据结构》 第八章 动态存储管理
内容和要求 第八章动态存储管理 内容和要求 可利用空间表、边界标识法、伙伴系统和无用 单元收集。 要求掌握可利用空间表及分配办法 可利用空间表及分配方法 边界标识法 伙伴系统 无用单元收集 存储紧缩 一重点 可利用空间表及分配 第2页
第八章 动态存储管理 第2页 可利用空间表及分配方法 边界标识法 伙伴系统 无用单元收集 存储紧缩 内容和要求 可利用空间表、边界标识法、伙伴系统和无用 单元收集。 要求掌握可利用空间表及分配办法。 重点 可利用空间表及分配。 内容和要求
动态存储管理的基本问题及方法 第八章动态存储管理 存储管理是一个既复杂而又重要的问题。在后续课 程——操作系统和编译技术(或方法、原理)中,将对 其作较深入的研究。在数据库技术中,也涉及大量有关 存储管理的问题。本章仅就动态存储管理方面一些基本 技术进行讨论 在以往的算法描述中,有关存储分配请求、存储回 收等项工作往往一带而过,好比是存储“自动满足”又 “自动回收”。偶尔亦考虑某一数据结构下判断是否溢 出或者是否释放内存空间等问题。这是必要的,主要是 为了把当时的重点和核心放在研究数据的逻辑特性、物 理表示、算法描述与分析上,而对有关存储管理的问题 作了一定的简化 第3页
第八章 动态存储管理 第3页 动态存储管理的基本问题及方法 存储管理是一个既复杂而又重要的问题。在后续课 程——操作系统和编译技术（或方法、原理）中，将对 其作较深入的研究。在数据库技术中，也涉及大量有关 存储管理的问题。本章仅就动态存储管理方面一些基本 技术进行讨论。 在以往的算法描述中，有关存储分配请求、存储回 收等项工作往往一带而过，好比是存储“自动满足”又 “自动回收”。偶尔亦考虑某一数据结构下判断是否溢 出或者是否释放内存空间等问题。这是必要的，主要是 为了把当时的重点和核心放在研究数据的逻辑特性、物 理表示、算法描述与分析上，而对有关存储管理的问题 作了一定的简化
动态存储管理的基本问题及方法 第八章动态存储管理 动态存储管理的基本问题 (1)如何按用户提出的“请示”分配内存? (2)如何回收那些用户不再使用而“释放”的内 存,以备新的“请示”产生时重新进行分配? 存储管理问题的解决途径 (1)由用户来解决 2)由系统来解决; (3)由系统和用户共同解决 第4页
第八章 动态存储管理 第4页 动态存储管理的基本问题 (1) 如何按用户提出的“请示”分配内存？ (2) 如何回收那些用户不再使用而“释放”的内 存，以备新的“请示”产生时重新进行分配？ (1) 由用户来解决； (2) 由系统来解决； (3) 由系统和用户共同解决。 存储管理问题的解决途径 动态存储管理的基本问题及方法
动态存储管理的基本问题及方法 第八章动态存储管理 在计算机系统中,存储管理的分级 )操作系统为进程分配所需要的存储空间,以便能在机器 上运行。一旦运行结束从系统撤离时,操作系统就回收进程所使 用的空间。此类存储管理问题将在《操作系统》课程中过论 (②)进程对数据结构分配及回收存储空间,例如编译进程为 变量、数组以及各种表格分配、回收空间。出类在值管理问题将 在编译方法》课程中过论。 (3)数据结构中,某结构中的元素或子结构分配、回收在 猪空。此类存值管理问题将是《数据结构》课程研宄的范 下面仅限于在数据结构一级上研究存储管理的方法。但其基 本思想和方法亦完全适用于其他两个级别。 第5页
第八章 动态存储管理 第5页 在计算机系统中，存储管理的分级 (1) 操作系统为进程分配所需要的存储空间，以便能在机器 上运行。一旦运行结束从系统撤离时，操作系统就回收进程所使 用的空间。此类存储管理问题将在《操作系统》课程中讨论。 动态存储管理的基本问题及方法 (2) 进程对数据结构分配及回收存储空间，例如编译进程为 变量、数组以及各种表格分配、回收空间。此类存储管理问题将 在《编译方法》课程中讨论。 (3) 数据结构中，对某结构中的元素或子结构分配、回收存 储空间。此类存储管理问题将是《数据结构》课程研究的范畴 。 下面仅限于在数据结构一级上研究存储管理的方法。但其基 本思想和方法亦完全适用于其他两个级别
动态存储管理的基本问题及方法 第八章动态存储管理 一些有关存储管理的重要问题一 (1)由谁来负责存储空间的分配与回收?是户自身,还是由 系统的一个专门子系统为用户分配并发现不再使用的空间而加以回 收? (2)分配和释放存储空间的单位是相同还是有大有小? 3)系统包时收全闲的空间?是及防国收还是数团收或当 空闻用完放才去回收? (4)是否考虑存储碎片的紧凌问题? 5)当请示存储空间时,满足该请示的最好分配略是什么? 是寻找容量大致相当的存储块给予,还是不加选择地依次给一块至 少能满足的空间? 6)怎样安摊空存储块的次序?随机排列或按地址排列或按 容量大小排列? 第6页
第八章 动态存储管理 第6页 一些有关存储管理的重要问题 (1) 由谁来负责存储空间的分配与回收？是用户自身，还是由 系统的一个专门子系统为用户分配并发现不再使用的空间而加以回 收？ (2) 分配和释放存储空间的单位是相同还是有大有小？ (3) 系统何时回收空闲的空间？是及时回收还是定期回收或当 存储空间用完时才去回收？ (4) 是否考虑存储碎片的紧凑问题？ (5) 当请示存储空间时，满足该请示的最好分配策略是什么？ 是寻找容量大致相当的存储块给予，还是不加选择地依次给一块至 少能满足的空间？ (6) 怎样安排空闲存储块的次序？随机排列或按地址排列或按 容量大小排列？ 动态存储管理的基本问题及方法
动态存储管理的基本问题及方法 第八章动态存储管理 两个术语旧产 占用块称已分配给用户使用的地址连续的内存区为占用块。在 不同的动态存储管理系统中,请求分配的内存量大小不同,可能 小到几个字节,多至若干k字节。但系统每次分配给用户的都是 个地址连续的内存区 空闲块称未曾分配的、地址连续的内存区为空闲块或可和用空 间块。不管怎么旋时产情求分配的工作时,整个 内存区是 内存,系统将怎样分配 区域)。 示例1尔 准的初期及系统 运行一段时间后的状态示意如下 (a)系统运行初期 线Q (b)系统运行若干时间之后 图81动态存储分配过程中的内存状态第了
第八章 动态存储管理 第7页 u1 u2 u3 u4 u5 u6 u7 u8 u1 u3 u4 u6 u8 (b)系统运行若干时间之后 (a) 系统运行初期； 图8.1 动态存储分配过程中的内存状态 示例1 系统运行期间，动态存储分配过程的初期及系统 运行一段时间后的状态示意如下 两个术语 占用块 称已分配给用户使用的地址连续的内存区为占用块。在 不同的动态存储管理系统中，请求分配的内存量大小不同，可能 小到几个字节，多至若干k字节。但系统每次分配给用户的都是 一个地址连续的内存区。 空闲块 称未曾分配的、地址连续的内存区为空闲块或可利用空 间块。不管怎么样的动态存储管理系统，在刚开始工作时，整个 内存区是一个空闲块（在编译系统中称之为堆，即堆区域）。 动态存储管理的基本问题及方法 空闲块 占用块 此时用户再次请求分配 内存，系统将怎样分配 ？
动态存储管理的基本间题及方法 第八章动态存储管理 两种分配策略: 1)系统继续从高地址的空闲块中进行分配,而不理会己分配给用户的内存 区是否已空闲,直到分配无法进行,才回收所有空闲块,并重新组织内存,将所 有空闲的内存区联接成一个大的空闲块 (2)用户一旦运行结東,便将它所占内存区释放成为空闲块,每当新用户请 求分配内存时,系统巡视整个内存区中所有空闲块,从中找出一个合适者分配之。 此时,系统需建立一张记录所有空闲块的可利用空间表(录表或链表) 示例1可利用空间表的图示形式 25,00039,000 10.000 31.000 59,000 99,999 内存状态(a) 起始地址一内存块大小使用情况 10,00015,000 目录表(b)31,0008,000 59,00041,000 空空空 闲闲闲 av10,000 链表(0 3 59 015,000 8.000 41,000∧ 图82动态存储管理过程中的内存状态和可利用空间表 第8页
第八章 动态存储管理 第8页 两种分配策略： (1) 系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存 区是否已空闲，直到分配无法进行，才回收所有空闲块，并重新组织内存，将所 有空闲的内存区联接成一个大的空闲块； 10,000 15,000 空 闲 31,000 8,000 空 闲 59,000 41,000 空 闲 起始地址 内存块大小 使用情况 目录表 (b) 动态存储管理的基本问题及方法 (2) 用户一旦运行结束，便将它所占内存区释放成为空闲块，每当新用户请 求分配内存时，系统巡视整个内存区中所有空闲块，从中找出一个合适者分配之。 此时，系统需建立一张记录所有空闲块的可利用空间表（目录表或链表）。 10,000 25,000 31,000 39,000 59,000 99,999 内存状态 (a) 示例1 可利用空间表的图示形式 链 表 (c) 0 15,000 0 8,000 0 41,000 ∧ 31,000 59,000 av 10,000 图8.2 动态存储管理过程中的内存状态和可利用空间表
可利用空间表及分配方法 第八章动态存储管理 可利用空间表的结构形式 可利用空间表中包含所有可分配的空闲块,每一块是链表中的 个结点。当用户请示分配时,系统从可利用空间表中删除一个结 点分配之;当用户释放其所占内存时,系统即回收该内存区并将它 插入到可利用空间表中 可利用空间表可以有下列三和不同的结构形式: 结构形式一:结点均含大相厦的空闲块 若系统运行期间所有用户请求分配的存储量大小 相同,则系统开始运行时,将归它使用的内存区按所 需大小分割成若干大小相同的块,并用指针链接成 个可利用空间表。分配时取表头结点,回收时按插表 头形式。这种情况下的可利用空间表实际是一个链栈 是一种最简单的动态存储管理的方式 第9页
第八章 动态存储管理 第9页 可利用空间表及分配方法 可利用空间表中包含所有可分配的空闲块，每一块是链表中的 一个结点。当用户请示分配时，系统从可利用空间表中删除一个结 点分配之；当用户释放其所占内存时，系统即回收该内存区并将它 插入到可利用空间表中。 可利用空间表的结构形式 结构形式一：结点均含大小相同的空闲块。 可利用空间表可以有下列三和不同的结构形式： 若系统运行期间所有用户请求分配的存储量大小 相同，则系统开始运行时，将归它使用的内存区按所 需大小分割成若干大小相同的块，并用指针链接成一 个可利用空间表。分配时取表头结点，回收时按插表 头形式。这种情况下的可利用空间表实际是一个链栈 。是一种最简单的动态存储管理的方式
可利用空间表及分配方法 第八章动态存储管理 结构形式二:建立若干个可利用空间表,同一链表中的结点大小 相同。不同链表中的结点大小,一般成倍数关系 示例2有三种大小结点(设结点天小分别为248字)的可利 用空间表的结点结构及其可利用空间表 分配过程? tag type link av2囗 ⑦00 space av4囗 0囚 (a)结点结构; av81 空闲 团2 02A tag=古用块 0结点大小的2个字 type=1结点大小的4个字 2结点大小的8个字 (b)可利用空间表 图83有三种大小结点的可利用空间表 第10页
第八章 动态存储管理 第10页 示例2 有三种大小结点（设结点大小分别为2,4,8个字）的可利 用空间表的结点结构及其可利用空间表。 结构形式二：建立若干个可利用空间表，同一链表中的结点大小 相同。不同链表中的结点大小，一般成倍数关系。 可利用空间表及分配方法 tag type link space 0 空闲块 1 占用块 0 结点大小的2个字 1 结点大小的4个字 2 结点大小的8个字 tag= type= (a)结点结构； 图8.3 有三种大小结点的可利用空间表 0 0 0 0 0 0 ∧ 0 1 0 1 0 1 ∧ 0 2 0 2 0 2 ∧ av2 av4 av8 (b)可利用空间表 分配过程？