(2008)内存管理算法介绍 memory management algorithms

《(2008)内存管理算法介绍 memory management algorithms》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内存管理算法By冲出宇宙2008-10-8MemoryManagementAlgorithms内存管理算法By冲出宇宙2008-10-81前言内存资源有限，内存管理很必要。2问题1．内存分配回收要快速。因为内存分配回收十分频繁；2．内存碎片比例要小。理论上，最坏的时候，任何不重整内存的管理算法都会导致接近100%的内存碎片；3算法内存管理算法有如下几个公理：1．空闲内存块用链表（有时是双向链表）串接，链表可以有多个；2．连续多个空闲内存块会合并为一个大块，有时是马上合并，有时是延迟合并；经典算法：1．First-Fit：选择满足要求的第一个内存块，切分出需要的大小，把剩下的内存块放回链表。

2、2．Best-Fit：选择最接近且大于需要大小的空闲内存块，切分出需要的大小，把剩下的内存块放回链表。3．Buddy-System：伙伴系统有很多变形，如Binary-Buddy、Fibonacci-Buddy、Weighted-Buddy和Double-Buddy等。伙伴系统有log2N个链表（N表示可分配内存大小），每个链表串接的内存块大小一样，都是2的幂。如Binary-Buddy，在分配内存的时候，首先找到一个空闲内存块，接着把内存块不断的进行对半切分（切分得到的2个同样大小的内存块互为伙伴），直到切出来的内存块刚好满足分配需求为止。合并的时候，只有伙伴才能合并为一个新的内存块。4

3、．Half-Fit：本算法维护了log2N5内存管理算法By冲出宇宙2008-10-8个链表（N表示可分配内存大小），每个链表里面串接的内存块大小范围在2i到2i+1。分配内存的时候，首先找到对应的链表，然后在链表里面寻找第一个块（First-Fit），分配一部分内存给用户，剩余的内存加入到对应的链表里。实用算法：1．DougLea'sAllocator：DougLea在95年维护了glib里面malloc函数，他构建了一种内存分配算法。这种算法维护了多个链表（一般是128个链表）。算法采用延迟合并策略，即当无法分配内存的时候，才合并相邻内存块。下图简单的描述了其结构：参考：http://

4、g.oswego.edu/dl/html/malloc.html2．TLSF：TLSF和DougLea算法的主要不同在于它维护了更多的链表，多达1024个以上。另外，它采用回收即合并的策略。参考：M.Masmanoetc.Implementationofaconstant-timedynamicstorageallocator.Softw.Pract.Exper.20075内存管理算法By冲出宇宙2008-10-84对比表1、各个算法在内存碎片上的表现对比表2、各个算法在分配和释放上的表现对比5类似磁盘的内存管理如果把内存当作一个磁盘，假设用户每次都这样操作：1．根据id得到一条数据；2．

5、修改数据；3．写回磁盘。这种使用内存的方式，很适合每条数据不是特别大的情况。在这种情况下，可以使用类似磁盘文件管理的方式来管理内存，即把id当作文件名，数据当作文件内容。以下是一种参考方式：5内存管理算法By冲出宇宙2008-10-8内存按照页的方式管理，每个页面的大小固定。每个页包含了如下数据：Id列表数据块空闲数据块id列表里面的每个元素都指向其数据的第一个数据块，数据块之间使用单链表串接。空闲数据块使用链表串接。这种算法的特点是：1．内存使用率高；2．数据物理上不连续；3．分页式内存管理会产生页内碎片。注：本页内碎片可以通过扩大页的大小来缓解。如设置每页大小为100M。6基于移动的内

6、存管理如果申请的内存可以移动（比如，增加一个map，每次访问的时候，都把原来的指针映射到移动之后的内存指针），那么，可以通过移动数据的方法来构建大空闲内存块。以下是一种参考方式：内存按照页的方式管理，每个页面的大小固定。5内存管理算法By冲出宇宙2008-10-8移动内存块之前的内存页状态，白色表示空闲内存块：移动内存块之后的内存页状态：这种算法的特点是：1．内存使用率高；2．数据占用的内存连续；3．需要指针映射或者迁移；4．分页式内存管理会产生页内碎片。注：本处的页内碎片不易解决，建议本算法只在分配内存块大小相差不大的情况下使用。附录1、MemCached的内存管理策略Memcached

7、是著名的开源内存缓冲系统，它的内存管理策略具有一定的参考性。具体的有：1）分页结构。每次申请内存，都不是直接申请一个内存块，而是申请一个大内存块，切分为N个相同的内存块，挂到链表中去。2）多链表结构。Memcached用200个链表来串接所有内存块，每个链表里面内存块大小完全一致。这点和TLSF不同，TLSF算法每个链表保存的内存块大小满足一定的范围，并不是完全一致。每个链表自动维护成LRU形式，分配内存的时候，首先选择