操作系统内存分配问答 #2
问题:解释以下分配算法。
首次拟合
最佳拟合
最差拟合
伙伴系统
下次拟合
答案:
首次拟合
在第一次适合的方法是分配第一个空闲分区或足够大的孔以容纳进程。 它在找到第一个合适的空闲分区后结束。
优势
最快的算法，因为它搜索的越少。
缺点
分配后剩余的未使用的内存区域如果太小就会变成浪费。 因此无法完成对更大内存需求的请求。
最佳拟合
最佳匹配处理分配满足请求进程要求的最小空闲分区。 该算法首先搜索整个空闲分区列表并考虑足够的最小孔。 然后它会尝试找到一个接近所需实际工艺尺寸的孔。
优势
内存利用率比先适应好得多，因为它首先搜索可用的最小空闲分区。
缺点
它速度较慢，甚至可能会用微小的无用漏洞填满内存。
最差拟合
最差拟合方法是找到最大的可用空闲部分，以便剩余的部分足够大以供使用。 这是最佳拟合的反面。
优势
降低产生小间隙的速度。
缺点
如果需要更大内存的进程在稍后阶段到达，则无法容纳它，因为最大的空洞已经被分割和占用。
伙伴系统
在伙伴系统中，空闲块的大小以 2 的整数幂的形式表示。例如 2, 4, 8, 16 等。最多为内存大小。 当请求大小为 2k 的空闲块时，会从大小为 2k 的空闲块列表中分配一个空闲块。 如果没有大小为 2k 的空闲块可用，则将下一个更大大小的块 2k+1 分成称为伙伴的两半来满足请求。
示例
让总内存大小为 512KB，让一个进程 P1，需要 70KB 被换入。由于孔列表仅适用于 2 的幂，因此 128KB 就足够大了。 最初没有 128KB，块也没有 256KB。 因此，512KB 块被分成两个 256KB 的伙伴，一个被进一步分成两个 128KB 的块，其中一个分配给进程。 Next P2 需要 35KB。 将 35KB 向上取整为 2 的幂，需要一个 64KB 的块。
所以当 128KB 块被分成两个 64KB 的伙伴时。 又一个进程 P3(130KB) 将在整个 256KB 中进行调整。 在这样的块空闲时满足请求后，两个块/好友可以重新组合形成两倍大的原始块，当它的下半个好友也空闲时。
优势
好友系统更快。 当一个大小为 2k 的块被释放时，会搜索一个 2k 内存大小的空洞以检查是否可以合并，而在其他算法中，必须搜索所有空洞列表。
缺点
它在内存利用率方面经常变得低效。 由于所有请求都必须四舍五入到 2 的幂，一个 35KB 的进程被分配到 64KB，因此浪费了额外的 29KB 导致内部碎片。 好友之间可能存在漏洞，导致外部碎片化。
下次拟合
下次拟合是第一次拟合的修改版本。 它首先适合找到一个空闲分区。 下次调用时，它会从中断处开始搜索，而不是从头开始。
