buddy算法是用来做内存管理的经典算法

《buddy算法是用来做内存管理的经典算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、buddy算法是用来做内存管理的经典算法，目的是为了解决内存的外碎片。避免外碎片的方法有两种：1，利用分页单元把一组非连续的空闲页框映射到非连续的线性地址区间。2，开发适当的技术来记录现存的空闲连续页框块的情况，以尽量避免为满足对小块的请求而把大块的空闲块进行分割。内核选择第二种方法。这个算法的时间效率更高，但是由于使用best-fit方法的缘故，会产生内存浪费。buddy算法将所有空闲页框分组为11个块链表，每个块链表的每个块元素分别包含1,2,4,8,16,32,64,128,256,512,1024个连续的页框，每个块的第一个页框的物理地址是该块大小的整数倍

2、。如，大小为16个页框的块，其起始地址是16*2^12(一个页框的大小为4k,16个页框的大小为16*4K,1k=1024=2的10次方，4k=2的12次方)的倍数。例，假设要请求一个128个页框的块，算法先检查128个页框的链表是否有空闲块，如果没有则查256个页框的链表，有则将256个页框的块分裂两份，一份使用，一份插入128个页框的链表。如果还没有，就查512个页框的链表，有的话就分裂为128，128，256，一个128使用，剩余两个插入对应链表。如果在512还没查到，则返回出错信号。回收过程相反，内核试图把大小为b的空闲伙伴合并为一个大小为2b的单独快，满

3、足以下条件的两个块称为伙伴：1，两个块具有相同的大小，记做b；2，它们的物理地址是连续的，3，第一个块的第一个页框的物理地址是2*b*2^12的倍数，该算法迭代，如果成功合并所释放的块，会试图合并2b的块来形成更大的块。1.1.1查找buddy页在buddy算法中，每一页都有一个buddy页与之相对应，使用__page_find_buddy函数可以找到指定页面对应的buddy页面：/**Locatethestructpageforboththematchingbuddyinour*pair(buddy1)andthecombinedO(n+1)pagetheyfo

4、rm(page).**1)AnybuddyB1willhaveanorderOtwinB2whichsatisfies*thefollowingequation:*B2=B1^(1<

5、scontiguousatleastuptoMAX_ORDER*/staticinlinestructpage*__page_find_buddy(structpage*page,unsignedlongpage_idx,unsignedintorder){unsignedlongbuddy_idx=page_idx^(1<

6、号。页号0123456789101100000000000001-124816326412825651210242048101-24-81632641282565121024204810012-4816-32-64128256512102420481000124-816-32-64-128-256-51210242048从上表中可以看出，负号表示这个页对应的BUDDY页在此页的前面，正号则表示其BUDDY页在此页的后面。从上表还可以看出，不论输入的页号是否为2的整数倍，其BUDDY页都与其相差2的整数倍。由于此函数只是计算BUDDY页的页面差距，它并不判断这两个页

7、面是否符合BUDDY的条件，因此还需要一个独立的函数来判断这两个页面是否真的互为BUDDY。1.1.2确认两个页面是否互为buddy要确认两个指定的页面是否互为buddy，可以使用page_is_buddy函数：/**Thisfunctioncheckswhetherapageisfree&&isthebuddy*wecandocoalesceapageanditsbuddyif*(a)thebuddyisnotinahole&&*(b)thebuddyisinthebuddysystem&&*(c)apageanditsbuddyhavethesameorder

8、&&*(d