Buddy System是一种经典的内存管理算法,在Unix和Linux操作系统中都有应用。引入Buddy System算法的目的是为了减少内存碎片,增加内存的使用率。
内存碎片:内存碎片就是内存被分割成多个小块,虽然有很多小块是空闲的,但是这些小块之间不连续,无法满足申请大块连续内存的需求。
举个栗子:
比如有一块256KB的连续内存,并且要申请的也是连续内存
1. 申请32K,再申请64K,再申请64K,还剩96K
2. 释放第一个32K,此时剩余内存32K+96K=128K
3. 这时候再申请128K却无法申请到,原因是32K和96K是不连续的,想要申请连续的128K,只能使用另外的内存空间,这就是内存碎片的产生过程。
Linux内核在频繁的申请和释放不同大小的连续页以后,必然会导致已经分配的块内存在许多小的空闲页,由此带来的问题是,即使有足够的空闲页满足需要,但是想分配大块的连续页也无法满足要求。
Buddy system被证明是非常有效的一套内存管理方法,因此也被相当多的OS采用。
buddy system算法原理
伙伴分配算法的流程如下:
一、如果内存被分配
1 寻找一个合适大小的内存,要求大于申请内存request mem,同时以2的k次方为量纲最小的块。
2. 如果找到了,直接分配
3. 如果没有找到,进行以下尝试
a. 拆分一个比request mem更大的内存块,分成两半
b. 如果拆分出来的一半满足request mem要求,并且不能再分,已经是最小的可满足request mem的要求,就分配该块
c. 重复1,寻找合适的内存块
d. 重复以上流程直到找到合适的内存块
二. 如果内存被释放
1. 释放2的k次方内存块
2. 查看内存块的伙伴,也就是被分配的另一半是否也已经free
3. 如果是,则合并,并重复执行直到有一个伙伴没有被free,无法合并
?内存申请、释放示意图:
a. 申请A=70K的内存,将原始的1024K分成两半,分别是512K,512K超过最小需要的内存大小,将512K继续拆分为两个256K,还是超过最小需要的2的n次方大小,继续将一个的256K拆分为2个128K,将其中一个128K分配给A
b. 申请B=35K,与a类似,将另一半128K拆分为2个64K,将其中1个64K分配给B
c. 申请C=80K,与上述步骤类似,拆分另一个256K,将其中一个128K分配给C
d. 释放A,检查A的另一半128K,无法被释放,因此单独释放A
e. 申请D=60K,将分配B时剩下的另一个64K给D
f. 释放B,检查B的另一半64K,无法被释放,单独释放B
g. 释放D,另一半64K是free的,因此合并为128K,128K的另一半也是free的,因此合并为256K
h. 释放C,C的另一半128K是free的,合并为256K,256K的另一半也是free的继续合并为512K,512K的另一半还是free的,继续合并为1024K,最终获得完整的一大块内存
buddy system的缺点
尽管buddy system能够有效减少内存碎片,但是也同样存在一些缺点。
1. 一个很小的块经常会阻碍一个大块的合并
2. 算法中存在浪费现象,即按照2的n次方分配内存,每一块的使用都可能存在冗余内存
3. 拆分和合并涉及到比较多的链表和bitmap操作,开销也比较大