最佳适配分配：所有内存块大小相同时如何分配？

（注：图中展示了多个大小为2KB的空闲内存块，编号为Block 1、Block 2等）

每个内存块大小为2KB，现在需要分配1KB内存，使用Best-Fit（最佳适配）算法应该选择哪个块？既然所有块大小相同，理论上都符合最佳适配的要求，实际该选哪一个？我原本以为会选Block 2，但这个答案是错误的。

解答 #

最佳适配算法的核心是挑选能容纳需求的最小空闲块，当所有空闲块尺寸完全一致时，算法的实际选择规则就取决于空闲块的遍历顺序：

• 绝大多数操作系统的最佳适配实现，都是按空闲块的地址从低到高的顺序遍历，找到第一个符合条件的块就直接分配，也就是地址最靠前的那个空闲块。
• 你误以为会选Block 2，应该是没搞清楚这种“块大小一致”场景下的遍历规则——此时没有“更优”的块，算法只会按预设的遍历顺序选第一个符合要求的块。

内容的提问来源于stack exchange，提问作者Muntasir Aonik