内存管理：伙伴算法
平时，用得最多的是通过new/delete或者malloc/free来申请和释放内存。那么，操作系统中对内存的管理是如何进行的呢？下面介绍一个最常用的内存管理算法，即伙伴算法。伙伴算法对内存的组织如图所示：
 |
图 伙伴算法内存管理
系统中的伙伴算法将内存所有的空闲页面分为N个块组。第K（0 =< K < N）组中块含2k个页面大小。每一组中块的大小是相同的，且同样大小的块形成一个双向链表。
假设要求分配的块的大小为256个页面。那么算法就在块大小为256个页面的块组中进行查找，看是否有这样一个空闲块。如果有，就直接分配；如果没有，该算法会查找下一个更大的块。如果在512大小的块组中找到一个，就将512分为两部分，一分用于分配，一分插入大小为256大小的块中。
其中把满足下面两个条件的块称为伙伴：
1．两个块大小相同；
2．两个块的物理地址连续。
伙伴算法将满足以上的两个块合并为一个块，如果合并后的块还可以跟相邻的块进行合并，那么该算法就继续合并。
伙伴算法的回收过程就是将系统释放的空闲块按照伙伴算法合并后插入相应的块组中。
