第四章 首次适算法介绍.ppt

分区分配算法 为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。 常用的4种分配算法： 首次适应算法FF 循环首次适应算法 最佳适应算法 最差适应算法 首次适应算法FF 空闲分区链以地址递增的次序链接。 分配时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；再按作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则失败返回。 缺点：空闲区分布不均匀，小地址的空闲区优先占满，高地址不容易查到；内存利用率不高。 有作业序列：作业A要求18K，作业B要求25K，作业C要求30K。初始内存分配情况如下图所示，问首次适应算法、最佳适应算法和最差适应算法中哪种能满足该作业序列的分配？ 分区分配操作 分配内存 回收内存 分配内存 设请求的分区大小：u.size 设空闲分区大小：m.size 不可再切割的剩余分区大小：size 如果m.size-u.size=size，将整个分区分配给请求者，否则剩余部分留在空闲分区链（表）中。 将分区的首地址返回给调用者 回收内存 当进程释放内存时，系统根据回收区的首址，从空闲分区链（表）中找到相应的插入点，回收区可能出现四种情况： 前三种情况如下面图所示； 第四种情况：既不与F1相邻接，又不与F2相邻接。 * 操作系统 第四章 存储器管理 * OS 30 50 20 40 5 45 46 0 20 50 100 120 160 165 210 256 对于首次适应算法， 作业A分配30K的空闲分区； 作业B分配46K的空闲分区； 此后无法为作业C分配合适的空闲分区了。 对于最佳适应算法， 作业A分配20K的空闲分区； 作业B分配30K的空闲分区； 作业C分配46K的空闲分区. 对于最差适应算法， 作业A分配46K的空闲分区； 作业B分配30K的空闲分区； 此后无法为作业C分配合适的空闲分区了。 F1 回收区 回收区与插入点的前一个空闲区F1相邻接 F1 回收区与插入点的后一个空闲区F2相邻接 回收区 F2 回收区 回收区同时与插入点的前、后两个分区邻接 F1 回收区 F2 F1