|
我看Buddy(伙伴)算法－到底是怎么"找朋友"的
文章来源:http://gliethttp.cublog.cn
在《浅析armlinux-paging_init()->free_area_init_core()函数5-4》中我们为size大小的内存页,创建了
(size-1)>>(i+4)大小的位图管理空间,比如拿i=0、i=1和i=2,即order=0、order=1和order=2,来具体分析分析.
order=0 --- 需要((size-1)/2)/8字节的位图空间来管理size-1大小内存页
order=1 --- 需要((size-1)/4)/8字节的位图空间来管理size-1大小内存页
order=2 --- 需要((size-1)/8)/8字节的位图空间来管理size-1大小内存页
但是我们都知道,对于size-1个字节的数据,必须使用(size-1+7)/8个字节的位图才可以,
这里为什么还要除以2呢,在《我看Buddy(伙伴)算法－为什么要有除2操作》[http://gliethttp.cublog.cn]
中以分配的角度做了除以2分析.
现在从使用角度来看看,为什么只需要一半的位图量,就可以管理2倍于它的(size-1)字节空间呢,
Buddy(伙伴)算法,我把它理解成"找朋友"算法,首先明确一点"位图中的一个位代表相邻的两个伙伴页当前被使用情况",
这样1个位顶2个位来用,就可以管理其2倍大小的size-1个内存页了.
在《我看Buddy(伙伴)算法－到底是怎么计算"伙伴"地址的》[http://gliethttp.cublog.cn]中,
我们知道偶数号位图-A和+1后的紧邻奇数号位图-B,它们是伙伴,它们两个共用位图A>>1,如:
对于order=0,索引0-[0],索引1-[1]是伙伴 ---------------- 共用位图0
索引2-[2],索引3-[3]是伙伴 ---------------- 共用位图1
... ...
索引2*n-[2*n],索引2*n+1-[2*n+1]是伙伴 ---------------- 共用位图n
对于order=1,[索引0-页地址0,索引1-页地址2]是伙伴 ---------------- 共用位图0
[索引2-页地址4,索引3-页地址6]是伙伴 ---------------- 共用位图1
... ...
[索引n-页地址2n,索引n+1-页地址2(n+1)]是伙伴---------------- 共用位图n
对于order=2,[索引0-页地址0,索引1-页地址4 ]是伙伴 ---------------- 共用位图0
[索引2-页地址8,索引3-页地址12]是伙伴 ---------------- 共用位图1
... ...
[索引n-页地址4n,索引n+1-页地址4(n+1)]是伙伴---------------- 共用位图n
所以用n个位图就可以描述2n个单元了.
拿第80位map_bit80来说,一开始map_bit80管理的两个伙伴都没有被分配出去,这时map_bit80=0,
由于需要现在A页块要被分配出去了,A分配出去的同时和1进行异或操作map_bit80=map_bit80^1=1,
现在有两种情况:
1.B不被分配出去,A此时需要释放了,A开始"找朋友",
首先计算A和朋友B对应的位图,因为map_bit80此时为1,所以与1异或之后map_bit80=map_bit80^1=0,
之后判断异或之后的结果map_bit80,如果异或结果为0,表明A的"朋友",存在,"找朋友"顺利完成,
将A和它的朋友B合并成大空间A+B,放入orde=order+1,上,通过循环,此时order已经加1,继续检测加1后
order的朋友是否可以继续合并,这样一直合并到MAX_ORDER-1为止.
2.B被分配出去,此时A仍在使用,B对共用位图map_bit80同样进行异或操作map_bit80=map_bit80^1=0,
3.B和A都被分配出去了,此时其中有一个要释放,比如A,它开始"找朋友",我们知道它肯定找不到朋友,因为B也被分配出去了,
那A是怎么知道B不存在呢,还是异或操作,两个都被分配出去了,所以当前map_bit80=0,经过异或之后
map_bit80=map_bit80^1=1,结果为1,表示"伙伴"不存在,那么不用合并,直接回收即可.
总结:不论是"申请分配"动作还是"释放回收"动作,都会对共用位图进行异或操作,之所以这样来做,目的不在于"申请分配"上,
而是在"释放回收"上,当回收时,通过异或结果来判断,当前回收页的伙伴是否已经空闲的存在,结果为0,表示可以"合并成大页",
结果为1,表示"伙伴"忙,所以位图存在的主要意义是"能够将小块内存合并成大块内存".
|
