操作系统第一次研讨.ppt

操作系统 研讨课 施 亮 5、设某个时刻，系统中有3个空闲区，其大小和首地址分别为：（35KB,100KB）、（12KB,156KB）、（28KB,200KB）。分别使用首次适应、最佳适应和最坏适应算法对下列内存分配请求进行分配（设分配时从空闲区的高地址分配，以保持剩余空闲区首地址不变），根据分配结果对3种算法进行比较。 （1）12KB、30KB、28KB （2）15KB、20KB、28KB 三种适应算法的原理 首次适应： 最佳适应: 最坏适应: 在分配内存时，在链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止 每次分配内存时，总是把能满足要求，又是最小的空闲分区分配给作业，避免“大材小用” 与最佳适应算法相反，它在扫描整个空闲分区表或链表时，总是挑一个最大的空闲去，从中分割一部分存储空间给作业使用 30k 35k 12k 28k 100k 156k 200k 首次适应 12k 28k 分配失败！！！ (12k,30k,28k) 35k 12k 28k 100k 156k 200k 最佳适应 12k 28k 30k (12k,30k,28k) 30k 35k 12k 28k 100k 156k 200k 最坏适应 12k 28k 分配失败！！！ (12k,30k,28k) 35k 12k 28k 100k 156k 200k 首次适应 15k 28k 20k (15k,20k,28k) 35k 12k 28k 100k 156k 200k 最佳适应 15k 28k 20k (15k,20k,28k) 分配失败！！！ 35k 12k 28k 100k 156k 200k 最佳适应 15k 28k 20k (15k,20k,28k) 分配失败！！！ 三种适应的优缺点 首次适应 优点：该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高低址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件 缺点：低址部分不断被划分，会留下许多难以利用的、很小的空闲区，称为碎片。而每次查找又都是从低址部分开始的，这无疑有会增加查找可用空闲分区时的开销 最佳适应 优点：第一次找到的能满足要求的空闲去必然是最佳的 缺点：因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的碎片 最坏适应 优点：可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中小作业有利 缺点：总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲区