sin的博客

Linux对内存区内的页框的分配和释放，采用的算法是伙伴系统。


如上图，Linux分配页时，只能分配2^n个页。内核维护MAX_ORDER个链表，每个链表记录着连续的空闲页。第一个链表中的每一项为1个空闲页，第二个链表中的每一项为2个空闲页，第三个链表中的每一项为4个空闲页。。。，依次类推。分配页时，从对应的链表上摘除空闲页；释放页时，将对应的页归还到对应的链表。分配释放页的过程中，可能伴随着内存页的拆分和合并。比如要分配16个空闲页，但是对应的链表为空，这时如果32个空闲页对应的链表如果不为空，则从链表中摘除32个空闲页，并将其一分为二，其中16个页用于内存分配，剩余16个页则插入到16个页对应的链表中。

尽管页的分配算法是简单的，但是实际过程却非常复杂。这是因为分配页式必须考虑一下几点：
1 备用内存区。当从一个内存区无法得到内存时，系统会从同一内存节点的其它内存区或者从另一个内存节点中的内存区中获取内存。
2 页的换入和换出，在没有足够多的空闲页时，可能需要将页换出以获取空闲内存。
3 页的回收，对一些缓冲区的不再使用的页进行回收，以获取空闲页。
4 系统中必须保持一定“水位”的空闲页，以应付对内存的紧急分配。如果系统将页分配完，在急需内存时，再进行页的回收或换出，无疑是非常糟糕的设计。系统中必须保持一定量的内存页。
5 不同的分配策略。不同的分配策略可能采用的方法有区别。
总之，页的分配和释放需要考虑许多因素，尽量满足内存分配的同时，要保证系统的稳定性和健壮性。