Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1058236
  • 博文数量: 573
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 66
  • 用 户 组: 普通用户
  • 注册时间: 2016-06-28 16:21
文章分类

全部博文(573)

文章存档

2018年(3)

2016年(48)

2015年(522)

分类: LINUX

2015-12-09 10:17:41

伙伴算法

Linux内核通过伙伴算法来管理物理内存。伙伴系统(Buddy System)在理论上是非常简单的内存分配算法。它的用途主要是尽可能减少外部碎片,同时允许快速分配与回收物理页面。为了减少外部碎片,连续的空闲页面,根据空闲块(由连续的空闲页面组成)大小,组织成不同的链表(或者orders)。这样所有的2个页面大小的空闲块在一个链表中,4个页面大小的空闲块在另外一个链表中,以此类推。


注意,不同大小的块在空间上,不会有重叠。当一个需求为4个连续页面时,检查是否有4个页面的空闲块而快速满足请求。若该链表上(每个结点都是大小为4页面的块)有空闲的块,则分配给用户,否则向下一个级别(order)的链表中查找。若存在(8页面的)空闲块(现处于另外一个级别的链表上),则将该页面块分裂为两个4页面的块,一块分配给请求者,另外一块加入到4页面的块链表中。这样可以避免分裂大的空闲块,而此时有可以满足需求的小页面块,从而减少外面碎片。


伙伴算法举例
假设我们的系统内存只有16个页面RAM。因为RAM只有16个页面,我们只需用四个级别(orders)的伙伴位图(因为最大连续内存大小为16个页面),如下图所示。



在order(0),第一个bit表示开始的2个页面,第二个bit表示接下来的2个页面,以此类推。因为页面4已分配,而页面5空闲,故第三个bit为1。

同样在order(1)中,bit3是1的原因是一个伙伴完全空闲(页面8和9),和它对应的伙伴(页面10和11)却并非如此,故以后回收页面时,可以合并。

分配过程

当我们需要order(1)的空闲页面块时,则执行以下步骤:

1、初始空闲链表为:

order(0): 5, 10

order(1): 8 [8,9]

order(2): 12 [12,13,14,15]

order(3):

2、从上面空闲链表中,我们可以看出,order(1)链表上,有一个空闲的页面块,把它分配给用户,并从该链表中删除。

3、当我们再需要一个order(1)的块时,同样我们从order(1)空闲链表上开始扫描。

4、若在order(1)上没有空闲页面块,那么我们就到更高的级别(order)上找,order(2)。

5、此时有一个空闲页面块,该块是从页面12开始。该页面块被分割成两个稍微小一些order(1)的页面块,[12,13]和[14,15]。[14,15]页面块加到order(1)空闲链表中,同时[12,13]页面块返回给用户。

6、最终空闲链表为:

order(0): 5, 10

order(1): 14 [14,15]

order(2):

order(3):

回收过程

当我们回收页面11(order 0)时,则执行以下步骤:

1、找到在order(0)伙伴位图中代表页面11的位,计算使用下面公示:

index = page_idx >> (order + 1)

= 11 >> (0 + 1)

= 5

2、检查上面一步计算位图中相应bit的值。若该bit值为1,则和我们临近的,有一个空闲伙伴。Bit5的值为1(注意是从bit0开始的,Bit5即为第6bit),因为它的伙伴页面10是空闲的。

3、现在我们重新设置该bit的值为0,因为此时两个伙伴(页面10和页面11)完全空闲。

4、我们将页面10,从order(0)空闲链表中摘除。

5、此时,我们对2个空闲页面(页面10和11,order(1))进行进一步操作。

6、新的空闲页面是从页面10开始的,于是我们在order(1)的伙伴位图中找到它的索引,看是否有空闲的伙伴,以进一步进行合并操作。使用第一步中的计算公司,我们得到bit 2(第3位)。

7、Bit 2(order(1)位图)同样也是1,因为它的伙伴页面块(页面8和9)是空闲的。

8、重新设置bit2(order(1)位图)的值,然后在order(1)链表中删除该空闲页面块。

9、现在我们合并成了4页面大小(从页面8开始)的空闲块,从而进入另外的级别。在order(2)中找到伙伴位图对应的bit值,是bit1,且值为1,需进一步合并(原因同上)。

10、从oder(2)链表中摘除空闲页面块(从页面12开始),进而将该页面块和前面合并得到的页面块进一步合并。现在我们得到从页面8开始,大小为8个页面的空闲页面块。

11、我们进入另外一个级别,order(3)。它的位索引为0,它的值同样为0。这意味着对应的伙伴不是全部空闲的,所以没有再进一步合并的可能。我们仅设置该bit为1,然后将合并得到的空闲页面块放入order(3)空闲链表中。

12、最终我们得到大小为8个页面的空闲块:

阅读(1582) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~