文档介绍：第12章动态存储管理
概述
可利用空间表及分配方法
存储压缩
边界标识法
无用单元的收集
存储管理是操作系统的重要组成部分,它负责管理计算机系统的存储器。
动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存?又如何收回那些用户不再使用而释放的内存以备新的“请求”产生时重新进行分配。本章简单介绍数据结构在动态存储管理中的一些常用技术,包括可利用空间表及分配方法、边界标识法、无用单元的收集和压缩存储等内容。
概述
动态存储管理的基本问题是系统如何应用户提出的“请求”分配内存?又如何收回那些用户不再使用而释放的内存以备新的“新求”产生时重新进行分配?
在单用户操作系统中,整个内存空间被划分成两个区域:系统区和用户区,系统区供系统程序使用,用户区供单一的用户程序所使用。当计算机采用了多道程序设计技术后,需要在主存储器中同时存放多个作业的程序,而这些程序在主存储器中的位置此时不能由程序员自已来确定,否则将出现多道程序竞争同一存储空间的情况。
J0
J1
J2
J3
J4
J5
J6
J7
J0
J2
J3
J5
J7
(A)系统运行初期
(B)系统运行若干时间以后
可利用空间块
或空闲块
占用块
现在讨论,(b)所示的内存状态下,此时又有新的用户作业进入系统请求分配内存,系统将如何处理?
通常有两种做法:一种策略是系统继续从高地址的空闲块中进行分配,而不理会已分配给用户的内存是否已空闲,直到分配无法进行
另一种策略是用户程序一旦运行结束,便将它所占内存区释放成为空闲块,同时,每当新的用户请求分配内存时,系统需要巡视整个内存区中所有空闲块,并从中找出一个“合适”的空闲块分配之。
为了实现这种分配策略,系统需建立一张记录所有空闲块的可利用空间表。此表的结构可以是目录表也可以是链表。。
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=
例: