2．3 主存空间的分配与回收
一、设计目的
本设计题目主要让大家熟悉主存的各种分配与回收。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时，将作业或进程所占用的主存空间归还给系统。主存的分配与回收的实现是与主存储器的管理方式有关的。通过本次设计，帮助学生理解在不同的存储管理方式下，如何实现主存空间的分配与回收。使学生初步具有研究、设计、编制和调试操作系统模块的能力。
二、设计要求
1．问题描述
采用可变式分区管理，使用首次或最佳适应算法实现主存的分配与回收。可以采用分区说明表或空闲区链来进行。
可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无；则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被作业占用，有的分区空闲。
2．基本要求
设计多个作业或进程动态请求内存资源的模拟系统，使用首次或最佳适应算法实现内存的分配与回收，实现可变式分区管理；设计相应的内存分配算法，定义相关数据结构，以及输出显示每次请求分配内存的结果和内存的已分配和未分配的状况。
三、设计思想、环境说明和使用工具
1．设计思想
初始化系统的内存分区说明表；输入当前作业或进程的使用内存情况，检索系统内的内存分区说明表，判断是否可分配，也就是查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无；则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被作业占用，有的分区空闲。使用内存的分配和回收算法进行，完成所有作业或进程的内存使用请求，作业完成后回收其所占用的内存给系统；并可输出查看内存的当前使用状况。
例如，某时刻主存空间占用情况如图3-1所示。
(1) 为了说明哪些分区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，如表3-1所示。
0 操作系统(10KB) 10K 作业1(10KB) 作业4(25KB) 45K 空闲区1(20KB) 65K 作业2(45KB) 空闲区2(146KB) 20K 110K 256K 图3-1 主存空间占用情况
表3-1 空闲区说明表
起始地址 45K 110K 长度 20KB 146KB 状态 未分配 未分配 空表目 空表目 空表目 … … … 其中，起始地址指出各空闲区的主存起始地址，长度指出空闲区大小。 状态有：
未分配：该栏目是记录的有效空闲区。 空表目：没有登记信息。
由于分区个数不定，所以空闲区说明表中应有足够的空表目项。否则造成溢出，无法登记。
同样，再设一个已分配区表，记录作业或进程的主存占用情况。 (2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个
足够大的空闲区。有时找到的空闲区可能大于作业需求量，这时应将空闲区一分为二。一个分给作业；另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽可能分配低地址部分的空闲区，将较大空闲区留在高地址端，以利于大作业的装入。为此在空闲区表中，按空闲区首地址从低到高进行登记。为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。其分配框图如图3-2所示。
置状态为“空表目” 将空表目向后移
图3-2 首次适应算法分配框图 登记已分配区表和空闲区表，输出系统中各数据结构的值。返回分配给作业的主存始址。 长度=长度－XK 始址=始址＋XK 作业等待 大于 Y 等于 长度>=XK? Y 小于 状态为“未分配”吗? N J为空闲区说明表的最后一个表目？ J=0 申请XK主存 开始 J=J+1 查看第J个表目的登记项 N 返回 (3) 当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时要考虑相邻空闲区合并的问题。作业的释放区与空闲区的邻接分以下4种情况考虑：
A．释放区下邻(低地址邻接)空闲区； B．释放区上邻(高地址邻接)空闲区； C．释放区上下都与空闲区邻接； D．释放区与空闲区不邻接。
首次适应算法回收框图如图3—3所示。 2．环境说明 工具：C语言。
在WINDOWS环境下使用VC++6.0进行开发。
四、主要的数据结构
数据结构说明： #define N 5
structfreearea /*定义一个空闲区说明表结构，并初始化变量*/ { int startaddress; /*空闲区始址*/ int size； /*空闲区大小*/
int state； /*空闲区状态：0为空表目，1为可用空闲块*/
}freeblock[N]＝{{20，20，1}，{80，50，1}，{150，100，1}，{300，
30，0},{600,100,1}};
五、课程设计应提交的主要内容
1．写出实现主存的分配和回收程序的数据结构、算法和算法流程图。 2．打印出程序清单。
3．写出程序调试及运行情况。
4．写出系统设计中出现的问题及解决的方法。 5．课程设计的体会。 6．自我评价与总结。
有等待装入的作业吗？ N 返回 Y 按地址顺序调整和紧缩空闲区说明表 有与释放区下邻的空闲区吗？ N 在空闲区说明表中找一空表目登记： 始址=S 长度=L 状态=未分配 Y N 开始 S=释放区始址 L=释放区长度 查空闲区说明表 有与释放区的高地址邻接(上邻)的空闲区吗？ Y L=L＋上邻空闲区长度 Y 有与释放区下邻的空闲区吗？ N 把上邻空闲区登记栏中的始址改为S，长度改为L 把上邻空闲区登记栏中的状态置为“空表目”，且将空表目向后调整。 把下邻空闲区登记栏中的长度改为： 长度=长度＋L 唤醒等待的作业并返回 图3-3 首次适应算法回收框图