buddy和slab那些事 |
您所在的位置：网站首页 › 内部碎片外部碎片 › buddy和slab那些事 |
buddy和slab那些事
下面的过程引用：http://www.cnblogs.com/zhaoyl/p/3695517.html
order（0）bimap有8个bit位（
页面最多16个页面，所以16/2）
order（1）bimap有4个bit位（
order（0）bimap有8个bit位，所以8/2）；
也就是order（1）第一块由
两个页框page1 与page2组成与order（1）第2块由
两个页框page3 与page4组成，这两个块之间有一个bit位
order（2）bimap有2个bit位（
order（1）bimap有4个bit位，所以4/2）
order（3）bimap有1个bit位（
order（2）bimap有4个bit位，所以2/2）
在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、此时（
order（1）上没有空闲页面块）有一个空闲页面块，该块是从页面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个页面的空闲块
slab分配器
每当我们要分配内存的时候，我们会使用malloc，malloc是C语言中分配内存的函数，我们可以使用malloc及其在C标准库中的相关函数，大多数程序分配若干字节内存时，经常会调用这些函数。内核也必须经常分配内存，但无法借助于标准库的函数，之前描述的伙伴系统支持按页分配内存，但这个单位对于内核而言实在太大了。如果需要为一个10个字符的字符串分配空间，分配一个4KB或更多空间的完整页面，不仅仅浪费而且完全不可接收，所以内核需要将页拆分为更小的单位，以便可以容纳大量的小对象。 slab分配器为每种对象分配一个高速缓存，这个缓存可以看做是同类型对象的一种储备。每个高速缓存所占的内存区又被划分多个slab，每个slab是由一个或多个连续的页框组成。每个页框中包含若干个对象，既有已经分配的对象，也包含空闲的对象。slab分配器的大致组成图如下： 这样做的目的有两个： 1.slab可以对小对象空间进行分配，而不需要分配整个页面给对象，这样可以节省空间 2.内核中对于频繁使用的小对象，slab会对此作缓存，避免了频繁的内存分配和回收，提高了速度
关于slab的机理需要进一步学习，等看完以后在完善剩余的部分！！谢谢 slub经典分析： https://blog.csdn.net/lukuen/article/details/6935068 |
【本文地址】