伙伴系统(buddy system)
当一个请求需要分配m个物理页,buddy system会寻找一个有\(2^n\)页的块(\(2^n-1 < m < 2^n\))分配给他。
我们使用一个空闲链表数组实现buddy system,其中a[i]代表块大小为\(2^i个页\)(每页为4kb)
假设我们要分配15kb内存,根据buddy system,我们需要寻找一个16kb(4页)大小的块
因为有4页,所以我们需要查看链表数组的第2项(代表\(2^2\))。
由下图发现,数组的第二项为空,代表此时还没有16kb大小的空闲块。
buddy system会继续查找更大的块(图中为32kb),将32kb进行分类操作,获得两个16kb大小的块。
将其中一个用于服务请求,另一个则插入到第2条链表(数组的第二项)
SLAB分配器
buddy system最小的分配单位为1页(4k)。但很多时候,内核需要分配的内存大小远小于4k,这时候如果还用buddy system会出现严重的内部碎片问题。于是有了用于分配小内存的SLAB分配器。
SLAB分配器只分配大小固定的内存块,对于每一种块的大小,SLAB都会用独立的内存资源池进行分配
SLAB分配器向buddy system申请一定大小的物理内存,并将获得的物理内存块作为一个slab(一个数据结构)。slab被划分为等长的小块内存,被组织成空闲链表的形式
所有的分配请求从current指针指向的slab中获得空闲内存块。当SLAB分配器接受一个分配请求时,它首先定位最适合大小的内存资源池,从current指针指向的slab中拿出一个空闲块。
若拿出一个空闲块后,该slab不再拥有空闲块,则这个slab中的内存块已经全部分配完了。发生两个移动 : 将该slab移动到full里面来,并从partial指向的链表中取出一个slab交给current。
当释放一个块到相应的slab空闲链表中,若该slab已全部分配完,则移动到partial,若原本仅分配出一块,那么将其释放还给buddy system