数据结构 C语言版 教学课件 作者 李云清 第12章_动态存储管理.ppt

《数据结构 C语言版 教学课件 作者 李云清 第12章_动态存储管理.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、统中，整个内存空间被划分成两个区域：系统区和用户区，系统区供系统程序使用，用户区供单一的用户程序所使用。当计算机采用了多道程序设计技术后，需要在主存储器中同时存放多个作业的程序，而这些程序在主存储器中的位置此时不能由程序员自已来确定，否则将出现多道程序竞争同一存储空间的情况。J0J1J2J3J4J5J6J7J0J2J3J5J7(A)系统运行初期（B）系统运行若干时间以后可利用空间块或空闲块占用块现在讨论，在图12.1（b）所示的内存状态下，此时又有新的用户作业进入系统请求分配内存，系统将如何处理？通常有两种做法：一种策略是系统继续从高地址的空闲块中进行分配，而

3、不理会已分配给用户的内存是否已空闲，直到分配无法进行另一种策略是用户程序一旦运行结束，便将它所占内存区释放成为空闲块，同时，每当新的用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个“合适”的空闲块分配之。为了实现这种分配策略，系统需建立一张记录所有空闲块的可利用空间表。此表的结构可以是目录表也可以是链表。如图12.2所示为某系统运行过程中的内存状态及其两种结构的可利用空间表。01000020000280003200099999550001000010000空闲280004000空闲5500045000空闲起始地址内存块大小使用情况0100

4、0010000028000400005500045000^av（c）链表12．2可利用空间表及分配方法操作系统既可借助目录表结构也可借助链表结构实现动态存储分配，本节将对采用链表的情况进行讨论。根据系统运行的不同情况，可利用空间表可以有三种不同的结构形式：第一种情况是系统运行期间所有用户请求分配的存储量大小相同。对此类系统，可以在系统开始运行时将内存的用户区域按所需大小分割成若干大小相同的块，然后用指针链接成一个可利用空间表。由于表中结点大小相同，所以在分配时无需查找，只要将第一个结点分配给用户即可；同样，当用户程序释放内存时，系统只需将用户释放的空闲块插入在

5、表头即可。这种情况下的可利用空间表实质上是一个链栈，对应的存储管理方式在操作系统中称为“固定分区管理”。第二种情况是系统运行期间用户请求分配的存储量有若干大小的固定规格。对此系统，可将用户存储空间分割成不同规格的若干块，并将大小相同的空闲块组织在同一个可利用空间表中，即同一链表中的结点大小相同。tagtypelinkspace000000^…av2010101^…av4020202^…av80空闲块1占用块0结点大小为2KB1结点大小为4KB2结点大小为8KBtag=type=例:第三种情况是系统在运行期间分配给用户的内存块大小不固定，可以随请求而变。此时，可

6、利用空间表中的结点即空闲块的大小也是随意的。通常，操作系统中的可利用空间表属于这种类型，这种存储管理实际上就是操作系统中的可变分区管理方法。系统初始状态下，整个内存空间是一个空闲块，即可利用空间表中只有一个大小为整个内存区的结点，随着分配和回收的进行，可利用空间表中的结点大小和个数也随之而变。由于链表中结点大小不同，结点的结构可包含四个域，即：标志域（tag），用于区分此块是否为空闲块、大小域（size），用于指示空闲块的存储量、链域（link），用于指示可利用空间链表中的下一个结点、存储空间域（space），它是一个大小为size的连续存储空间。tagsiz

7、elinkspace0空闲块tag=1占用块由于可利用空间表中的结点大小不同，因此相应的分配与回收过程较为复杂。假设某用户需大小为n的内存，而可利用空间表中仅有一块大小为m≥n的空闲块，则只需将其中大小为n的一部分分配给申请的用户，同时将剩余大小为m-n的部分作为一个结点留在链表中即可。当可利用空间表中存在多个空间大小不小于n的空闲块时，一般可采用以下三种不同的分配策略。（1）最先适应分配算法，这种方法又称为首次适配法。每次分配时，总是顺序查找可利用空间链表，找到第一个能满足长度要求的空闲区为止。分割这个找到的未分配区，一部分分配给作业，另一部分仍为空闲区。（

8、2）最优适应分配算法。这种分配算法每次