《数据结构》课程教学资源：第十二章 动态存储管理

第12章动态存储管理 >概述 >可利用空间表及分配方法 >边界标识法 >无用单元的收集 >存储压缩

第12章 动态存储管理 ➢概述 ➢ 可利用空间表及分配方法 ➢存储压缩 ➢边界标识法 ➢无用单元的收集

存储管理是操作系统的重要组成部分,它负责 管理计算机系统的存储器。 动态存储管理的基本问题是系统如何应用户提 出的“请求”分配内存?又如何收回那些用户不再 使用而释放的内存以备新的“请求”产生时重新进 行分配。本章简单介绍数据结构在动态存储管理中 的一些常用技术,包括可利用空间表及分配方法、 边界标识法、无用单元的收集和压缩存储等內容

存储管理是操作系统的重要组成部分，它负责 管理计算机系统的存储器。 动态存储管理的基本问题是系统如何应用户提 出的“请求”分配内存？又如何收回那些用户不再 使用而释放的内存以备新的“请求”产生时重新进 行分配。本章简单介绍数据结构在动态存储管理中 的一些常用技术，包括可利用空间表及分配方法、 边界标识法、无用单元的收集和压缩存储等内容

12.1概述 动态存储管理的基本问题是系统如何应用户提 出的“请求”分配内存?又如何收回那些用户不再 使用而释放的内存以备新的“新求”产生时重新进 分配? 在单用户操作系统中,整个内存空间被划分成两 个区域:系统区和用户区,系统区供系统程序使用 用户区供单一的用户程序所使用。当计算机采用了多 道程序设计技术后,需要在主存储器中同时存放多个 作业的程序,而这些程序在主存储器中的位置此时不 能由程序员自已来确定,否则将出现多道程序竞争同 存储空间的情

12.1 概述 动态存储管理的基本问题是系统如何应用户提 出的“请求”分配内存？又如何收回那些用户不再 使用而释放的内存以备新的“新求”产生时重新进 行分配？ 在单用户操作系统中，整个内存空间被划分成两 个区域：系统区和用户区，系统区供系统程序使用， 用户区供单一的用户程序所使用。当计算机采用了多 道程序设计技术后，需要在主存储器中同时存放多个 作业的程序，而这些程序在主存储器中的位置此时不 能由程序员自已来确定，否则将出现多道程序竞争同 一存储空间的情况

013145N017 (A)系统运行初胆 可利用空间 块 或空闲块 Q 23 35 (B)系统行若干时间以后 占用块

J0 J1 J2 J3 J4 J5 J6 J7 J0 J2 J3 J5 J7 (A)系统运行初期 （B）系统运行若干时间以后 可利用空间 块 或空闲块 占用块

现在讨论,在图121(b)所示的内存状态下,此时 又有新的用户作业进入系统请求分配内存,系统将如 何处理? 通常有两种做法:一种策略是系统继续从高地址的空 闲块中进行分配,而不理会已分配给用户的内存是否 已空闲,直到分配无法进行 另一种策略是用户程序一旦运行结束,便将它所占內 存区释放成为空闲块,同时,每当新的用户请求分配 内存时,系统需要巡视整个内存区中所有空闲块,并 从中找出一个“合适”的空闲块分配之

现在讨论，在图12.1（b）所示的内存状态下，此时 又有新的用户作业进入系统请求分配内存，系统将如 何处理？ 通常有两种做法：一种策略是系统继续从高地址的空 闲块中进行分配，而不理会已分配给用户的内存是否 已空闲，直到分配无法进行 另一种策略是用户程序一旦运行结束，便将它所占内 存区释放成为空闲块，同时，每当新的用户请求分配 内存时，系统需要巡视整个内存区中所有空闲块，并 从中找出一个“合适”的空闲块分配之

为了实现这种分配策略,系统需建立一张记录所有空 闲块的可利用空间表。此表的结构可以是目录表也可 以是链表。如图122所示为某系统运行过程中的内存 状态及其两种结构的可利用空间表。 01000020000280003200055000 99999 起始地址内存块大小使用情况 1000010000 空闲 28000 4000 空闲 5500045000 空闲

为了实现这种分配策略，系统需建立一张记录所有空 闲块的可利用空间表。此表的结构可以是目录表也可 以是链表。如图12.2所示为某系统运行过程中的内存 状态及其两种结构的可利用空间表。 0 10000 20000 28000 32000 55000 99999 10000 10000 空闲 28000 4000 空闲 55000 45000 空闲 起始地址 内存块大小 使用情况

I. av 01000010000 0280004000 05500045000|A (C)链表

0 10000 10000 0 28000 4000 0 55000 45000 ^ av （c）链表

12.2可利用空间表及分配方法 操作系统既可借助目录表结构也可借助链表结构 实现动态存储分配,本节将对采用链表的情况进 讨论。 根据系统运行的不同情况,可利用空间表可以有 三种不同的结构形式: 第种情况是系统运行期间所有用户请求分配的存 储量大小相同。对此类系统,可以在系统开始运行 时将内存的用户区域按所需大小分割成若干大小相 同的块,然后用指针链接成一个可利用空间表

12．2可利用空间表及分配方法 操作系统既可借助目录表结构也可借助链表结构 实现动态存储分配，本节将对采用链表的情况进行 讨论。 根据系统运行的不同情况，可利用空间表可以有 三种不同的结构形式： 第一种情况是系统运行期间所有用户请求分配的存 储量大小相同。对此类系统，可以在系统开始运行 时将内存的用户区域按所需大小分割成若干大小相 同的块，然后用指针链接成一个可利用空间表

由于表中结点大小相同,所以在分配时无需查找,只 要将第一个结点分配给用户即可;同样,当用户程序 释放内存时,系统只需将用户释放的空闲块插入在表 头即可。这种情况下的可利用空间表实质上是一个链 栈,对应的存储管理方式在操作系统中称为“固定分 区管理”。 第二种情況是系统运行期间用户请求分配的存储量有 若干大小的固定规格。 对此系统,可将用户存储空间分割成不同规格的若干 块,并将大小相同的空闲块组织在同一个可利用空间 表中,即同一链表中的结点大小相同

由于表中结点大小相同，所以在分配时无需查找，只 要将第一个结点分配给用户即可；同样，当用户程序 释放内存时，系统只需将用户释放的空闲块插入在表 头即可。这种情况下的可利用空间表实质上是一个链 栈，对应的存储管理方式在操作系统中称为“固定分 区管理”。 第二种情况是系统运行期间用户请求分配的存储量有 若干大小的固定规格。 对此系统，可将用户存储空间分割成不同规格的若干 块，并将大小相同的空闲块组织在同一个可利用空间 表中，即同一链表中的结点大小相同

例 tag type link av 00 00 00 space ava 1 0空闲块 tag= 1占用块 0202 2 0结点大小为2KB type={1结点大小为4KB 2结点大小为8KB

tag type link space 0 0 0 0 … 0 0 ^ av 2 0 1 0 1 … 0 1 ^ av 4 0 2 0 2 … 0 2 ^ av 8 0 空闲块 1 占用块 0 结点大小为2KB 1 结点大小为4KB 2 结点大小为8KB tag= type=例: