hlnBlog
0%

伙伴算法以及 Slab 机制

发表于 分类于 ，

伙伴算法以及 Slab 机制

1 伙伴系统

1.1 页框

  • Linux 内核将物理内存划分成固定大小（在 x86 架构下长度为 4KB）的块，被称为页框

1.2 组织结构

img

  • Linux 内核将所有的空闲页划分成 11 个页块链表，每个页块链表分别包含 1、2、4、8、16、32、64、128、256、512、1024 个连续页框的页块
  • 每个页块的第一个页的物理地址是该块大小的整数倍
  • 最多可以申请 1024 个连续页，对应 4MB 大小的连续内存

1.3 分配

  • 当向内核请求分配包含 (2^(i-1), 2^i] 个页的页块时，如果对应的页块链表有空闲页块，则分配；如果对应的页块链表没有空闲页块，则在更大的页块链表中找，找到后将这个页块一分为二，它们互为 “伙伴” ，一半分配给进程使用，另一半再根据大小放入合适的页块链表中

1.4 释放

  • 进程使用完 1 个页块后，对其进行释放，如果在这个时候，这个页块的 “伙伴” 也为空闲的，则将它们两个合并，然后放到合适的页块链表中
  • 如果合并后的页块的 “伙伴” 依然是空闲的，依旧将它们两个合并，然后放到合适的页块链表中，这样的过程一直持续，直到找不到空闲的 “伙伴” 页块

2 Slab 机制

2.1 背景

img

  • 页式管理适合大块内存的情形，而对于内核对象级别的较小内存情形下，不足以占用1个页。在 linux 内核中存在许多小对象，这些对象构造、销毁十分频繁，比如 i-node、dentry 之类的，假如这些对象每次创建的时候向内存要一个页（大小为 4KB），然而实际大小可能只有几个字节，这样就非常浪费，为了解决这个问题就引入了一种新的机制来处理在同一页框中如何分配小存储区的问题

2.2 定义

  • Slab 是一种内存分配器，通过将内存划分为不同大小的空间分配给对象使用，并管理维护高速缓存

2.3 主要作用

  • 为小对象分配内存空间，减少由 “伙伴” 系统机制导致的内部碎片（页块中未被实际使用的内存空间）问题
  • 内核中一些小对象创建、析构很频繁，Slab对这些小对象做缓存，可以重复利用一些相同的对象，减少内存分配次数

2.4 内存分配和管理

  • Slab 机制将不同的对象划分为所谓的高速缓存（cache）组，其中每个高速缓存都存放不同类型的对象
  • 每种对象类型对应一个高速缓存（cache）
  • Slab 由一个或多个物理上连续的页组成，每个高速缓存由多个 slab 组成

2.5 高速缓存

2.5.1 查看当前的 Slab 缓存

  • Linux 内核为常用对象建立缓存，每种类型对应1个高速缓存。文件 /proc/slabinfo 记载了当前的缓存情况，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
$ cat /proc/slabinfo
slabinfo - version: 2.1
# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <limit> <batchcount> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>
ext4_groupinfo_1k     60     60    136   60    2 : tunables    0    0    0 : slabdata      1      1      0
ext4_groupinfo_4k    168    168    144   56    2 : tunables    0    0    0 : slabdata      3      3      0
UDPLITEv6              0      0   1088   30    8 : tunables    0    0    0 : slabdata      0      0      0
UDPv6                 60     60   1088   30    8 : tunables    0    0    0 : slabdata      2      2      0
tw_sock_TCPv6          0      0    280   58    4 : tunables    0    0    0 : slabdata      0      0      0
request_sock_TCPv6      0      0    328   49    4 : tunables    0    0    0 : slabdata      0      0      0
TCPv6                 30     30   2112   15    8 : tunables    0    0    0 : slabdata      2      2      0
kcopyd_job             0      0   3312    9    8 : tunables    0    0    0 : slabdata      0      0      0
dm_uevent              0      0   2632   12    8 : tunables    0    0    0 : slabdata      0      0      0
cfq_queue              0      0    232   70    4 : tunables    0    0    0 : slabdata      0      0      0
............

各字段的含义（参考：slabinfo(5) - Linux manual page (man7.org)），

字段 含义
name 对象的类名
active_objs 当前活跃（使用中）的对象个数
num_objs 所有的对象个数，包括使用中和未使用的对象
objsize 每个对象的大小
objperslab 每个 slab 存放对象的个数
pagesperslab 每个 slab 被分配页的个数

2.5.2 划分

img

  • 为了加速小对象的分配和释放，处于同一个高速缓存中的 slab 被划分到三个链表中：slabs_full、slabs_partial 、slabs_free
  • slabs_full 链表所有 slab 中的对象都处于使用中的状态；slabs_partial 链表部分 slab 有当前未被使用的对象，可以分配给进程；slabs_free 链表不包含分配的对象，主要用于 slab 的销毁