我看Buddy(伙伴)算法－为什么要有除2操作

我看Buddy(伙伴)算法－为什么要有除2操作

文章来源:http://gliethttp.cublog.cn

实际过程请参考《浅析armlinux-paging_init()->free_area_init_node()函数5-4》[http://gliethttp.cublog.cn]

    对于Buddy(伙伴)算法,采用模型:index >> (i+1);[i为order值,index一般是"size-1"]
所以Buddy管理的内存总大小为size-1,记得在<唐山一中>念高中的时候有这样一道数学题
s=1/2+1/4+1/8+...1/2^n的值是多少,怎么计算呢?先将等式两端分别乘上2,即:
2s=1+1/2+1/4+...1/2^(n+1)=逼近1+s,所以s=逼近1,但永远都达不到1.
所以从这个角度我们可以看到Buddy的算法中,不论MAX_ORDER有多大10,10000...,甚至无穷,也不会把size-1切割到0
size-1数据穷尽,当然这还要考虑小于1字节时已经不存在意义的问题,
但是MAX_ORDER已经有很强的伸缩性了[gliethttp 2007-08-05]
free_area[0].map位图大小=((size-1)/ 2)/8=(size-1) >> (0+1+3)
free_area[1].map位图大小=((size-1)/ 4)/8=(size-1) >> (1+1+3)
...
free_area[9].map位图大小=((size-1)/1024)/8=(size-1) >> (9+1+3)