我读过Modern Operating Systems 4th Edition,Andrew Tanenbaum,其中介绍了一些处理内存管理的方法(使用位图,使用链表)和一些可用于分配内存的算法(第一次适合,下一次适合,最适合,最差,快速适合),它们是不同的,但没有一个是最好的。
我正在尝试制作自己的内存分配器,它将优先考虑尽可能低的外部碎片(内存块太小而无法使用)和分配/释放的速度(首先是碎片比速度)。我实现了最差的匹配(认为这将产生尽可能少的外部碎片,因为它总是在分配时选择最大的连续内存空间,并且该内存的剩余部分足以在以后用于另一个分配。我使用排序实现它可用空间的降序列表和按地址排序的已分配空间的集合。分配的复杂性是 O(1) + 维护列表排序和释放的成本 O(log n1) - 用于查找地址 + O(n2) - 用于解析空闲空间列表并插入找到的地址。n1 = 集合的元素,n2 = 列表的元素。
我有多个问题。首先是如何改进算法?其次,还有哪些其他用于内存分配的算法会优先考虑内存碎片?第三,我列出的算法是否有任何改进版本可以优先考虑内存碎片?我想知道尽可能多的算法/改进我所知道的算法的方法,这将减少外部碎片。