【精品课件】动态存储管理.pptVIP

12．2可利用空间表及分配方法 12．3．1 可利用空间表的结构 12．3．2分配算法 12．3．3回收算法 12．4无用单元的收集 12．5存储压缩 * * 第12章　动态存储管理 概述 可利用空间表及分配方法 存储压缩 边界标识法 无用单元的收集 存储管理是操作系统的重要组成部分，它负责管理计算机系统的存储器。 动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何收回那些用户不再使用而释放的内存以备新的“请求”产生时重新进行分配。本章简单介绍数据结构在动态存储管理中的一些常用技术，包括可利用空间表及分配方法、边界标识法、无用单元的收集和压缩存储等内容。 12.1 概述 动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存？又如何收回那些用户不再使用而释放的内存以备新的“新求”产生时重新进行分配？ 在单用户操作系统中，整个内存空间被划分成两个区域：系统区和用户区，系统区供系统程序使用，用户区供单一的用户程序所使用。当计算机采用了多道程序设计技术后，需要在主存储器中同时存放多个作业的程序，而这些程序在主存储器中的位置此时不能由程序员自已来确定，否则将出现多道程序竞争同一存储空间的情况。 J0 J1 J2 J3 J4 J5 J6 J7 J0 J2 J3 J5 J7 (A)系统运行初期 （B）系统运行若干时间以后 可利用空间块 或空闲块 占用块 现在讨论，在图12.1（b）所示的内存状态下，此时又有新的用户作业进入系统请求分配内存，系统将如何处理？ 通常有两种做法：一种策略是系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存是否已空闲，直到分配无法进行 另一种策略是用户程序一旦运行结束，便将它所占内存区释放成为空闲块，同时，每当新的用户请求分配内存时，系统需要巡视整个内存区中所有空闲块，并从中找出一个“合适”的空闲块分配之。 为了实现这种分配策略，系统需建立一张记录所有空闲块的可利用空间表。此表的结构可以是目录表也可以是链表。如图12.2所示为某系统运行过程中的内存状态及其两种结构的可利用空间表。 0 10000 20000 28000 32000 99999 55000 10000 10000 空闲 28000 4000 空闲 55000 45000 空闲 起始地址 内存块大小 使用情况 0 10000 10000 0 28000 4000 0 55000 45000 ^ av （c）链表 操作系统既可借助目录表结构也可借助链表结构实现动态存储分配，本节将对采用链表的情况进行讨论。 根据系统运行的不同情况，可利用空间表可以有三种不同的结构形式： 第一种情况是系统运行期间所有用户请求分配的存储量大小相同。对此类系统，可以在系统开始运行时将内存的用户区域按所需大小分割成若干大小相同的块，然后用指针链接成一个可利用空间表。 由于表中结点大小相同，所以在分配时无需查找，只要将第一个结点分配给用户即可；同样，当用户程序释放内存时，系统只需将用户释放的空闲块插入在表头即可。这种情况下的可利用空间表实质上是一个链栈，对应的存储管理方式在操作系统中称为“固定分区管理”。 第二种情况是系统运行期间用户请求分配的存储量有若干大小的固定规格。 对此系统，可将用户存储空间分割成不同规格的若干块，并将大小相同的空闲块组织在同一个可利用空间表中，即同一链表中的结点大小相同。 tag type link space 0 0 0 0 0 0 ^ … av2 0 1 0 1 0 1 ^ … av4 0 2 0 2 0 2 ^ … av8 0 空闲块 1 占用块 0 结点大小为2KB 1 结点大小为4KB 2 结点大小为8KB tag= type= 例: 第三种情况是系统在运行期间分配给用户的内存块大小不固定，可以随请求而变。此时，可利用空间表中的结点即空闲块的大小也是随意的。通常，操作系统中的可利用空间表属于这种类型，这种存储管理实际上就是操作系统中的可变分区管理方法。系统初始状态下，整个内存空间是一个空闲块，即可利用空间表中只有一个大小为整个内存区的结点，随着分配和回收的进行，可利用空间表中的结点大小和个数也随之而变。 由于链表中结点大小不同，结点的结构可包含四个域，即：标志域（tag），用于区分此块是否为空闲块、大小域（size），用于指示空闲块的存储量、链域（link），用于指示可利用空间链表中的下一个结点、存储