面试题答案
一键面试1. 内存分配策略
首次适配（First Fit）
- 策略描述：从内存空闲链表的起始位置开始遍历，找到第一个大小大于或等于所需内存大小的空闲块，将其分割一部分分配给请求者，剩余部分仍留在空闲链表中。
- 优点：简单高效，时间复杂度相对较低，因为通常情况下能较快找到满足条件的空闲块，不需要对整个空闲链表进行遍历。
- 缺点：可能会导致大的空闲块被早早分割，后续如果有大内存请求可能无法满足，而且容易在内存低地址区域留下许多小的碎片。
最佳适配（Best Fit）
- 策略描述：遍历整个内存空闲链表，找到大小最接近（大于或等于）所需内存大小的空闲块，将其分割一部分分配给请求者，剩余部分仍留在空闲链表中。
- 优点：能选出最适合请求的空闲块，最大程度减少内存碎片的产生，使内存分配更合理。
- 缺点：需要遍历整个空闲链表来找到最佳块，时间复杂度较高，而且每次分配后剩余的小块碎片可能难以再次利用，长期运行可能产生较多碎片。
伙伴系统（Buddy System）
- 策略描述：将内存空间划分为大小为$2^k$（$k = 0, 1, 2, ...$）的块，当请求分配内存时，找到能满足请求的最小的$2^k$大小的块进行分配。如果没有合适大小的块，则将大的块分裂为两个相等的“伙伴”块，直到找到合适大小的块。当释放内存时，检查释放块的伙伴是否也空闲，如果是，则合并成一个更大的块。
- 优点：内存管理简单，分配和释放速度较快，能有效减少外部碎片。
- 缺点：内部碎片相对较多，因为分配的块大小只能是$2$的幂次方，可能会比实际需求大很多。
2. 内存碎片管理与提高内存利用率
- 合并空闲块：当程序释放内存时，malloc函数会检查相邻的空闲块，如果相邻块都空闲，则将它们合并成一个更大的空闲块。这样可以减少内存碎片，提高内存利用率。例如，在首次适配和最佳适配策略下，空闲链表中的空闲块可能分散在不同位置，通过合并操作可以将这些分散的空闲块整合起来。
- 使用内存池：可以预先分配一块较大的内存作为内存池，当程序请求内存时，优先从内存池中分配。对于一些频繁分配和释放小内存块的场景，内存池可以避免频繁的系统调用分配内存，减少碎片产生。当内存池中的内存不足时，再从系统分配新的内存块加入内存池。
- 整理内存：定期或在特定情况下，对内存中的数据进行移动和整理，将所有已使用的内存块紧凑排列，把所有空闲块合并成一个大的连续空闲区域，从而消除内存碎片。不过这种方式实现较为复杂，可能会影响程序的运行效率，因为移动数据需要消耗额外的时间和资源。