操作系统实验报告
实验三：主存空间的分配与回收
一、实验题目
采用可变式分区管理，使用首次或最佳适应算法实现主存的分配与回收
二、实验内容
主存是中央处理机能直接存取指令和数据的存储器。能否合理而有效地使用主存，在很大程度上将影响到整个计算机系统的性能。本实验采用可变式分区管理，使用首次或最佳适应算法实现主存空间的分配与回收。要求采用分区说明表进行。
三、实验目的
通过本次实验，帮助学生理解在可变式分区管理方式下，如何实现主存空间的分配与回收。
提示：
（1）可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无，则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被作业占用，有的分区空闲。例如，某时刻主存空间占用情况如图1所示。
010K20K45K65K
110K
256K
操作系统（10KB）作业1（10KB）作业4（25KB）空闲区1（20KB）作业2（45KB）
空闲区2（146KB）
表1空闲区说明表
f起始地址
长度
状态
45K
20KB
未分配
110K
146KB
未分配
空表目
图1主存空间占用情况
空表目
空表目
为了说明哪些分区是空闲的，可以用来装入
…
…
…
新的作业，必须要有一张空闲区说明表，如表1
所示。
其中，起始地址指出各空闲区的主存起始地址，长度指出空闲区大小。
状态栏未分配指该栏目是记录的有效空闲区，空表目指没有登记信息。
由于分区个数不定，所以空闲区说明表中应有足够的空表目项，否则造成溢出，无法登记。
同样，再设一个已分配区表，记录作业或进城的主存占用情况。
（2）当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需求量，这时应该将空闲区一分为二。一个分给作业，另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽可能分配低地址部分的空闲区，将较大空闲区留在高地址端，以利于大作业的装入。为此在空闲区表中，按空闲区首地址从低到高进行登记。为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。其分配框图如图2所示。开始
申请XK主存
J0
JJ1
查看第J个表目的登记项
N
等于置状态为“空表目将空表目向后移
状态为“未分配”吗？
Y
长度XK
N小于
大于
长度＝长度－XK始址＝始址＋XK
Jr