动态异长分区的存储分配与回收算法

实验5 动态异长分区的存储分配与回收算法

5.1 实验目的

理解存储管理的功能，掌握动态异长分区的存储分配与回收算法。 存储器是计算机系统中的关键资源，存储管理一直是操作系统的最主要功能之一。存储管理既包括内存资源管理，也包括用于实现分级存储体系的外存资源的管理。通常， 内存与外存可采用相同或相似的管理技术，如内存采用段式存储管理，则外存也采用段式存储管理。存储管理需要完成如下功能： 存储分配、存储共享、存储保护、存储扩充、地址映射。 当一个作业进入内存时，由操作系统将其变为进程,并为进程分配存储空间。进程运行结束时, 由操作系统将其所占用的存储空间收回。

不同的操作系统对内存空间的划分与分配方法是不同的，通常分为两类：静态等长分区的分配和动态异长分区的分配。静态等长分区常用于页式存储管理方式与段页式存储管理方式，存储空间被静态地划分为若干个长度相等的区域，每个区域被称作一个页面。 动态异长分区常用于界地址存储管理方式与段式存储管理方式，存储空间被动态地划分为若干个长度不等的区域。

5.2 实验要求

本实验要求模拟动态异长分区的分配算法、回收算法和碎片整理算法。 5.3 实验步骤

5.3.1 数据结构分析

为了实现存储资源的分配和回收，操作系统需

要记录内存资源使用情况，即哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程等。为此一般需要两个表，一个为分配表, 另外一个为空闲区域表。前者记录已经分配的区域, 后者记录着所有当前未被进程占用的空闲区域, 如图5-1所示。

图5-1 空闲区域表

显然, 没有记录于表中的区域即为已被进程所

占用的非空闲区域，在实际的操作系统中，这些区域登记在进程的PCB中。而PCB中除了关于内存资源的信息外，还有其它大量信息。

由于本实验是对存储管理算法的模拟，所以用一个线程来代表一个进程，用线程驻留区域表来描述线程占用的内存空间，如图5-2所示。

图5-2 线程驻留区表

同时，需要一张表来记录各个线程对内存的请求信息，如图5-3所示。

5.3.2 算法分析

常用的动态异长分区的分配算法有：最先适应算法、最佳适应算法和最坏适应算法。

1. 最先适应算法(First Fit，FF)

对于存储申请命令, 选取满足申请长度要求且起始地址最小的空闲区域。在实现时, 可将系统中所有的空闲区域按照起始地址由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分的长度为原长度与分配长度之差, 将其仍记录于空闲区域表中。

回收时，按回收区的首地址查询空闲区表，若有与回收区相临的空闲区，则将其合并到相临区中，否则，把回收区按照地址从低到高的顺序插入到空闲区域表的适当位置。 2. 最佳适应算法(Best Fit，BF)

分配时取满足申请要求且长度最小的空闲区域。在实现时, 可将系统中所有的空闲区域按照长度由小到大的次序依次记录于空闲区域表中。与最先适应算法相类似, 当进程申请存储空间时, 系统由表的头部开始查找, 取第一个满足要求的表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分即剩余部分的长度为原长度与分配长度之差, 由于剩余部分的长度已经改变，所以应重新将其按长度从小到大的顺序插入到空闲区域表中。

回收时，不仅要按回收区的首地址查询空闲区表，找到与回收区相临的空闲区，将其合并到相临区中，而且要把合并后的回收区按照长度递增的顺序插入到空闲区域表的适当位置。

3. 最坏适应算法(Worst Fit，WF)

分配时取满足申请要求且长度最大的空闲区域。在实现时, 可将系统中所有的空闲区域按照长度由大到小的次序依次记录于空闲区域表中。当进程申请存储空间时, 取第一个表目。如果该表目所对应的区域长度恰好与所申请的区域长度相同, 则将该区域全部分配给申请者。否则将该区域分割为两部分, 一部分的长度与所申请的长度相同, 将其分配给申请者；另一部分即剩余部分的长度为原长度与分配长度之差, 由于剩余部分的长度已经改变，所以应重新将其按长度递减的顺序插入到空闲区域表中。

回收时，不仅要按回收区的首地址查询空闲区表，找到与回收区相临的空闲区，将其合并到相临区中，而且要把合并后的回收区按照长度递减的顺序插入到空闲区域表的适当位置。

5.3.3 设计并分析测试数据

假设初始内存布局如图5-4，图中的起始地址以及大小都以KB来衡量。

起始地址 0 占用者

大 小

10

20

40

70

80 85

145

160

180

图5-4初始内存布局

由图5-4可见，初始时共有五个线程驻留在内存，它们是a,b,c,d,e，线程驻留区表如图5-5；还有五个 …… 此处隐藏：20248字，全部文档内容请下载后查看。喜欢就下载吧 ……