动态存储管理的基本问题及方法 第八章动态存储管理 一些有关存储管理的重要问题一 (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)可利用空间表 分配过程？