虚拟存储器分配块策略

当一个应用请求请求一个k字节的块时,分配器搜索空闲链表,查找一个足够大、可以放置所有请求块的空闲块。分配器执行这种搜索当时是由放置策略来决定的。
常见的放置策略有:首次适配、下一次适配、最佳适配


首次适配
当请求块时,分配器从头开始搜索空闲链表、选择第一个合适的空闲块。


下一次适配
下一次适配就是当请求块时,分配器从上一次分配合适块的地方开始搜索合适的空闲块。


最佳适配
最佳适配就是检查每个空闲块,选择匹配所需请求大小的最小空闲块。


首次适配的一个优点就是它趋向于将大的空间保留在链表后面,可能留下小的空间碎片,增加了大空间块的查找时间。
下一次适配比首次适配对存储器的利用率低。
最佳适配对存储器的利用率最高,但是需要搜索所有的空闲块,导致分配块时间变长,降低了吞吐量。

分割空闲块:
当通过以上策略寻找到相应的空闲块后,需要通过另外的策略来分配这个空闲块中的多少空间。如果选择是用整个空闲块,那么就不不会产生内部碎片,如果碎片匹配不完全,产生小的空闲块,那么可能会产生碎片。

相关阅读:
分配器性能指标
存储器 碎片