伙伴算法和Slab分配器-HNU操作系统课堂讨论

题目:操作系统一般对用户空间采用分页管理而对内核对象采用slab分配器,为什么?Linux的伙伴算法工作原理以及Slab是如何工作的?
这是湖南大学操作系统课程一次讨论课中的一个选题,我整理了我个人所准备的讨论内容,对此题目进行一个比较详尽的解答。

大蓝书镇楼

前置知识

显然,这是一个复合的问题,要说清楚为什么,首先得先知道他们都是什么。

内存分页

内存分页是什么

在内存分页以前,电脑内存管理采用的是段式的,直接计算物理内存,靠首地址和偏移量来获取内存地址,同样获取到的也是连续的地址。
而内存分页机制则是把物理内存切分成等大的小块(一般是4KB),并且产生一个页表,来让虚拟内存和物理内存之间互相转换,而不是直接访问物理内存了。

内存分页的作用

防止外部碎片

什么是外部碎片呢?可以想象,在采取段式内存访问的时候会产生一个问题:假设某个内存段被释放了,但是它非常小,那么在别的进程需要分配内存的时候,就很难利用上这一段小小的内存,这就是外部碎片。采取内存分页机制,由于内存是被以一个最小单位分发的,所以就不会出现这种外部碎片导致内存浪费的现象。

段式内存模式
内存分页模式

保护模式

内存的访问会有什么安全问题呢?假设两个进程访问了同一块内存区域,那么就可以对二者的数据造成不可预计的破坏。在原本的“实模式”下,段寄存器直接存储的是段基址,直接计算出来了段的物理地址,这样的缺点是应用程序可以访问任何物理地址,造成了上述的不安全情况。所以,随着计算机技术的发展,保护模式产生了。
因为CPU的技术发展,寄存器的位数也发生了改变,保护模式下的段寄存器下不再放置段基地址,而是一个段选择子。
段选择子是什么?
详细拆开这里有很多地方可以说,但是目前大可把它当作一个索引,只是它还包含了一些特权级等信息。有了这个段选择子,我们就可以去GDT之中取得段落的描述符了。GDT是一张全局段落描述表,是为了这个新模式而产生的数据结构。获得段描述符之后就可以从中取得段基址,进行原本的运算。如果此时开启了内存分页模式,这里运算之后会得到一个“线性地址”,然后再得出物理地址。

寻址
段页式管理图示


但是后来,产生了“平坦模型”,让分页模式开启的状态下产生了一些变化,但是这个可以下次再讨论了。
而之前我们说过的“特权级”,就是用来对内存的访问权限进行保护的,其中0级是最高保护等级,是内核代码运行的等级,3级是最低的保护等级,应用程序一般都是这个特权级的。

最初的内存分页

现在我们一般都说内存分页是为了解决内部碎片的,但是一个技术在引入的时候的作用与现在并不一定是一样的。其实在早期,这个技术是作为解决物理内存过小而发展出来的虚拟内存机制,方便在内存和外存之间交换数据。而当时有的“段交换”性能则不太好。

现在的内存分页技术

这里还是有很多的,但是由于我们的题目说到了slab,所以这里当然就要说LInux的伙伴算法喽。由此,前置的知识差不多都了解了,可以正式回到问题本身。

名词的介绍

在这个知识点附近聚集了不少专用词汇,网上各处也有些翻译问题,在此我提出本文中我个人采取的中文译法:
在分页内存中,进程被等分为页,内存被等分为页框(也称帧,但是本文中称为页框),二者等大,在进程执行时,页装入页框执行。
在伙伴算法中,则又会将空闲的页框集合起来变成“块”(block),不同级别的块会分别连接在一起,组织成一个链表。

伙伴算法

终于要开始说伙伴算法了。作为一项实现内存分页技术的算法,它要达成什么样的任务呢?

  • 遵从CPU的内存管理机制
  • 速度快效率高
  • 能够实现内存保护
  • 能够实现虚拟内存
  • 共享
  • 重定位
    在本文中,不用对他们全部解释,接下来就着重讨论一下它是如何实现空闲内存的管理的吧。

如何组织空闲内存

上文说到,伙伴算法会将空闲的内存集合起来变成块,再把不同大小的块组织成不同级别的链表。而不同的级别指的就是这个空闲的块是由2的几次幂个空闲叶组成的。也就是说,0级的空闲块就是单个空闲页(2^0),三级的空闲块就是八个空闲页组成的(2^3)……

order构成示例


这时候另一个问题就出现了:连续空闲的页面数量不一定是2的幂数,那如何划分和组织这些页面就比较复杂了。如何才能更快更有效的实现这个功能呢?
答案就在这个算法的名字上了,伙伴(buddy)!其实在对空闲块进行组织的时候,它每个级别真正需要找到的是有哪个块的伙伴被占用了但是它自己是空闲的呢?
这样我们很快就能扫描出每个级别对应的大小,而不会面临对大块空闲内存的分割问题了,如下图所示:
假设我们的内存总共分为16个页


目前统计完的各级别的空闲块如下:
order(0): 5, 10
order(1): [8,9]
order(2): [12,13,14,15]
order(3):

如何分配内存

假设我们需要分配一个等级为order(1)的内存块,那么伙伴算法就会先找到对应的链表看看有没有空闲。恰好,order(1)中有一个空闲的块,那么该块就会被分配出去,然后从链表之中删除。现在我们的空闲块列表变成了这样:
order(0): 5, 10
order(1):
order(2): [12,13,14,15]
order(3):
这个时候,如果我们还需要分配一个等级为order(1)的内存块呢?
伙伴算法首先查看了对应的链表,发现并没有剩余了,那么算法就回去访问比它高一级的链表order(2),去查看有没有空闲的块。在发现order(2)有一个空闲的块之后,系统就会把它拆成两半,其中[12,13]分配给所需的进程,[14,15]仍然作为空闲块,但是因为长度少了一半,所以直接降级分配给order(1)的链表了。
那么此时此刻,空闲块列表就变成这样了:
order(0): 5, 10
order(1): [14,15]
order(2):
order(3):

如何回收内存

分配内存的问题似乎得到了圆满的解决,那么回收内存该如何处理呢?
让我们恢复最开始的状态:
order(0): 5, 10
order(1): [8,9]
order(2): [12,13,14,15]
order(3):
假设我们需要归还内存中的11号内存页,需要进行什么样的处理呢?伙伴算法会从该内存块对应的等级开始递归,看看能不能找到它的空闲“伙伴”,也就看它能不能和其他空闲块合在一起变成更大的空闲块?
第一步就是要找到回收的分页在order中对应的位置,这一步很简单:index=page_idx>>(order+1) 直接对页的编号进行右移运算。
在这个例子中,页面11很快就会找到对应的空闲伙伴10,合并而成一个大小为order1的空闲块[10,11],然后它又可以在order(1)中找到对应的伙伴[8,9],他们合并成的[8,9,10,11]又会在order(2)中找到伙伴,最终合成了一个由八个连续空闲页组成的order(3)级别的空闲块,进入对应的链表。
经过以上的操作,11号分页被回收,下图是回收后的状态:

Slab 分配器

经过上面的讨论,已经弄明白了内存分页/伙伴算法的功能和运行机制,终于可以进入到问题的第二部分:Slab分配器了
也许从刚才就有一个疑问产生了:既然有外部碎片,那么有没有内部碎片呢?
当然有了。上文说过,一个内存分页的页框一般是4KB,以现在程序内存占用的眼光来看似乎是个相当小的数字,但是系统内核中存在着大量的小实例生成,同时也会非常频繁的回收。对于这种实例来说,4KB的空间也是非常巨大的,里面会有大量的空间遭到浪费,这就是内部碎片。
而且,上文说到伙伴算法的分配和回收机制,如果是应对内核对象这种频繁生成和回收的、小块连续内存的请求,伙伴算法无疑会造成空间、性能上的双重浪费,不再合适了。
所以:
为了解决小块内存的分配,Linux内核基于Solaris 2.4中的slab分配算法实现了自己的slab分配器。除此之外,slab分配器另一个主要功能是作为一个高速缓存,它用来存储内核中那些经常分配并释放的对象。
简单来说,就是Slab分配器在伙伴算法的内存管理上又添加了一层自己的管理机制。它可以依照设定的需要将伙伴系统的内存块分配成更加细小的小块,并且存储在自己的内部列表之中,而不是立刻返回给伙伴系统。这样设计,内核对象的分配和回收不需经过伙伴算法,处理时间会缩短。
由此,我们可以总结出来Slab分配器的目标:

Slab分配器的基本目标

  • 减少伙伴算法在分配内核对象一类的小块连续内存时产生的内部碎片
  • 将频繁使用的对象缓存起来,减少分配、初始化和释放对象的时间开销
  • 通过Slab着色技术以更好的使用CPU硬件高速缓存
    第三点“Slab着色”在之前没有提到,后面再详细说明。

Slab分配器的运行原理

之前说过,Slab分配器的前两个主要作用是减少内部碎片以及管理内核对象,那么它是如何实现的呢?
首先,Slab分配器产生了称作“高速缓存”的实例,这些高速缓存通过双向链表相连。每一个高速缓存都存储了大量的Slab,每个Slab包含了数个内存页框(一般不会超过24个),Slab再将它拥有的内存页框管理为一个个小的内核对象。

slab分配器大致结构


接下来对上面的数据结构进行一一解释:

1.高速缓存

可以理解为,他们是Slab分配器的第一级管理器。

struct kmem_cache_s { 
    struct list_head    slabs_full;
    struct list_head    slabs_partial;
    struct list_head    slabs_free;
    unsigned int        objsize;
    unsigned int        flags;
    unsigned int        num;
    spinlock_t          spinlock; 

 
    unsigned int        gfporder; 
    unsigned int        gfpflags; 
    
    size_t              colour;
    unsigned int        colour_off;
    unsigned int        colour_next;
    
    kmem_cache_t        *slabp_cache; 
    //... 
    struct list_head    next;
    // ...
 };

其中,前三个字段都是用来存储Slab的,由名字可以看出它们代表了未被分配过的、部分分配的、被分配空的Slab;
objsize: 需存储的内核对象的大小;
num: 一个slab能存储的对象个数;
gfporder:规定了每个slab能占有多少个页框。这个字条代表了一个伙伴算法空闲内存块的级别,每个slab可以占又两个该级别的内存块;
colour…: 着色区大小(后文介绍)

1.Slab
这就是Slab分配器产生的第二级管理器,它们被存储在高速缓存之中。

typedef struct slab_s { 
    struct list_head    list;
    unsigned long       colouroff;
    void                *s_mem;
    unsigned int        inuse;
    kmem_bufctl_t       free;
} slab_t;


其中,list:该Slab被连接在对应的高速缓存的哪条链上
colouroff:着色补偿
s_mem:存储对象的起始地址
inuse:已经被分配的对象数量
free:保存了空闲对象链表的首节点索引
在Slab管理器运作的时候,slab的数量是动态变化的。当新产生出一个高速缓存的时候,它上面三个存储slab的链表应当都是空的,当系统申请内核对象发现没有可用的slab的时候,就会创建一个新的slab并加入到那三个链表的其中之一。当slab过少的时候,slab管理器会自动分配;当slab过多的时候,slab管理器也会将一些slab释放回伙伴系统。

总结

以上,就是slab分配器的基本原理,再次总结一下它的各部分概念吧:
首先,这个整体的结构叫做slab管理器,它的主要组成是高速缓存连接而成的双向链表;
每个高速缓存是不同的,区别在于他们管理的slab能占有多少个页框、需要存储的内核对象的大小……每个高速缓存可以生成并存储对应的slab,在不需要的时候也会把slab释放;
slab则是这个结构里面最底层的管理者,它会分配出一个个内核对象所需的具体空间,并且进行管理。

引用自知乎@linux

Slab分配器的初始化过程

这一部分也是比较有意思的,当我们说起结构复杂且庞大的slab分配器的时候,它是如何完成初始化的呢?
这里又出现了一个非常有意思的问题。我们的高速缓存也是一种小内存对象,需要让slab分配器来分配出来;但是高速缓存又是slab分配器的主要结构——所以似乎变成了一个先有鸡还是先有蛋的问题(这个问题我可以用辩证法解释,也许以后会出一个单独的博客),要产生一个高速缓存,需要slab分配器;当我们没有高速缓存的时候,我们也就没有slab分配器。
所以,就有了一个特殊的开头。首先会初始化一个特殊的高速缓存,叫做cache_cache。它是一个结构体变量,以下给出它的定义:

static kmem_cache_t cache_cache = { 
    slabs_full:       LIST_HEAD_INIT(cache_cache.slabs_full), 
    slabs_partial:    LIST_HEAD_INIT(cache_cache.slabs_partial), 
    slabs_free:       LIST_HEAD_INIT(cache_cache.slabs_free), 
    objsize:          sizeof(kmem_cache_t), 
    flags:            SLAB_NO_REAP, 
    spinlock:         SPIN_LOCK_UNLOCKED, 
    colour_off:       L1_CACHE_BYTES, 
    name:             "kmem_cache", 
};


可以看出来,它的objsize(上文说到这是它需存储的内核对象的大小)被设定为高速缓存的大小,所以它的作用就是用来分配出来高速缓存的。
那么到现在,整个Slab分配器的运行原理差不多就解释完了。当然具体很多细节还是要落实到具体的代码中,由于长度有限,就不在本文中全部展示了。

Slab分配器的完整运行过程

梳理一下:

  1. 初始化cache_cache
  2. 由cache_cache产生高速缓存
    1. 产生一个高速缓存对象
    2. 计算该高速缓存存储的每个slab需要多少个页框
    3. 计算每个slab能分配多少个对象
    4. 计算着色信息
    5. 初始化该高速缓存上的三个链表
    6. 把该高速缓存对象放到cache_cache的存储链表之中
  3. 生成的高速缓存在链表之中查看是否有可用的Slab
  4. 如果没有,申请出一个新的Slab来进行对象分配,放到slab_partial列表之中
  5. Slab查看自己的free字段有无空闲对象可用
  6. 根据Slab内部的使用情况,调整该Slab在高速缓存中存储的位置

Slab着色

之前多次提到了着色,但是一直没有说这到底是什么东西?一开始知道这个名字的时候,我想起了夸克色禁闭,不过它俩的共同点大概就只有都是用“颜色”来做比喻的吧。
为了解释Slab着色,首先要解释什么叫硬件缓存/CPU缓存:

CPU缓存

在以前的计算机系统中学习中,我们可能知道计算机硬件的组成部分有CPU,存储器和输入输出设备。存储器呢,分为了内存和外存/主存和辅存。但是现在的计算机为了满足日益高涨的性能需求,在主存这个部分产生了更多的细分和升级,由原本的“内存条”添设了硬件高速缓存。经常了解电脑游戏硬件的人肯定听说过三级缓存这个词,这就是发展到现在的硬件缓存。
而硬件缓存,就相当于是更高速的存储设备,这样在cpu需要数据的时候可以做到更快速的数据供给。
以当前的计算机而言,一共有三级缓存,都处在CPU元件之上。
一级缓存L1在每个CPU核心的内部,与CPU同速运行,性能能强大,但是碍于内部结构很狭小,所以一级缓存的容量都很小。
二级缓存L2是为了协调一级缓存和内存的速度的。CPU调用数据的时候会优先调用一级缓存,但是如果一级缓存内部没有需要的数据,这种状况就叫做缓存未命中,这时就需要访问内存了。但是一级缓存非常小,内存的读取速度相比之下又非常慢,当处理器的速度提升的时候,未命中的概率就会提高。但是,提升内存的速度技术非常困难,加大一级缓存的容量同样很难实现,所以就产生了二级缓存这种中间产物。因为它不在处理器核心内部,所以速度稍微慢一些,但是既比内存快很多,容量又远大于一级缓存。
三级缓存L3是为了进一步提高CPU的缓存命中率,进一步降低从CPU到内存的延迟。在拥有三级缓存的CPU中,只有大约5%的数据需要从内存中调用(该数据来自网络)。
不过现在二级缓存的作用被弱化了,基本来说三级缓存的大小变成了更重要的参数。

缓存行(Cacheline)

硬件缓存的内部结构和内存是有所区别的,它的主要单位是“缓存行(cacheline)”,每一个缓存行的大小一般是64字节。

着色的原理

在CPU进行缓存的时候,会更倾向于把Slab分配器中大小相同的对象放入同一行缓存行,这就可能造成某些缓存行堆积了大量的相同大小的对象的状况。在CPU频繁调用同一行中的不同对象的时候,就会造成这一行的数据进行频繁反复的刷新和覆盖,造成性能损失。
而前文提到的slab中的着色补偿就是来解决这个状况的。它不会再让对象连续存储,而是加入一些不能使用的区域,作为“着色区”,它的作用就是尝试把不同的内存对象尽量分配到不同的缓存行去,来减少冲突现象。

结语

这算是我发出的第一篇技术型的博客,虽然我已经在小班讨论的时候准备过一次了,但是整理成博客付出的精力还是超乎我的想象。
不过我相信这这一篇博客对于这个问题的阐述是比较详尽的,顺便补齐了一些前置的知识点,希望我做的努力是有意义的。

更多技术文章请关注我的博客:技术文章

如有错误或侵权请指出

评论

  1. 倪哥
    8月前
    2022-4-23 19:03:44

    i了 一位财务专业的人看了知乎外行!

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇