layout: post
title: "Big Kernel Lock vs FIFO Ticket Spinlock in Linux"
date: 2013-10-30 18:58
comments: true
categories: Linux
tag: [linux, kernel, spinlock, big kernel lock, baidu]
keywords: linux kernel, spinlock kernel lock
description: a item from 2014 baidu interview
这里先写一篇基础文章引入一下自旋锁、排队自旋锁和大内核锁。
自旋锁(Spinlock)是一种 Linux 内核中广泛运用的底层同步机制。自旋锁是一种工作于多处理器环境的特殊的锁，在单处理环境中自旋锁的操作被替换为空操作。当某个处理器上的内核执行线程申请自旋锁时，如果锁可用，则获得锁，然后执行临界区操作，最后释放锁；{% img right http://image.zcool.com.cn/cover/20/23/1305391757594.jpg 328 268 %}如果锁已被占用，线程并不会转入睡眠状态，而是忙等待该锁，一旦锁被释放，则第一个感知此信息的线程将获得锁。
linux传统的自旋锁
本质上用一个整数来表示，值为1代表锁未被占用。这种无序竞争的本质特点导致执行线程无法保证何时能取到锁，某些线程可能需要等待很长时间。随着计算机处理器个数的不断增长，这种“不公平”问题将会日益严重。
排队自旋锁(FIFO Ticket Spinlock)是 Linux 内核 2.6.25 版本引入的一种新型自旋锁，它通过保存执行线程申请锁的顺序信息解决了传统自旋锁的“不公平”问题。排队自旋锁的代码由 Linux 内核开发者 Nick Piggin 实现。
传统的Linux 内核自旋锁的底层数据结构 raw_spinlock_t 定义如下：
typedef struct {
unsigned int slock;
} raw_spinlock_t;
slock 虽然被定义为无符号整数，但是实际上被当作有符号整数使用。slock 值为 1 代表锁未被占用，值为 0 或负数代表锁被占用。初始化时 slock 被置为 1。
线程通过宏 spin_lock 申请自旋锁。
尽管拥有使用简单方便、性能好的优点，自旋锁也存在自身的不足：
- 由于传统自旋锁无序竞争的本质特点，内核执行线程无法保证何时可以取到锁，某些执行线程可能需要等待很长时间，导致“不公平”问题的产生。这有两方面的原因：
- 随着处理器个数的不断增加，自旋锁的竞争也在加剧，自然导致更长的等待时间。
- 释放自旋锁时的重置操作将无效化所有其它正在忙等待的处理器的缓存，那么在处理器拓扑结构中临近自旋锁拥有者的处理器可能会更快地刷新缓存，因而增大获得自旋锁的机率。
- 由于每个申请自旋锁的处理器均在全局变量 slock 上忙等待，系统总线将因为处理器间的缓存同步而导致繁重的流量，从而降低了系统整体的性能。
linux排队自旋锁
传统自旋锁的“不公平”问题在锁竞争激烈的服务器系统中尤为严重，因此 Linux 内核开发者 Nick Piggin 在 Linux 内核 2.6.25 版本中引入了排队自旋锁：通过保存执行线程申请锁的顺序信息来解决“不公平”问题。
排队自旋锁仍然使用原有的 raw_spinlock_t 数据结构，但是赋予 slock 域新的含义。为了保存顺序信息，slock 域被分成两部分，分别保存锁持有者和未来锁申请者的票据序号(Ticket Number)，如下图所示:
图示：next和owner域
如果处理器个数不超过 256，则 Owner 域为 slock 的 0-7 位，Next 域为 slock 的 8-15 位，slock 的高 16 位不使用；如果处理器个数超过 256，则 Owner 和 Next 域均为 16 位，其中 Owner 域为 slock 的低 16 位。可见排队自旋锁最多支持 216=65536 个处理器.。
只有 Next 域与 Owner 域相等时，才表明锁处于未使用状态（此时也无人申请该锁）。排队自旋锁初始化时 slock 被置为 0，即 Owner 和 Next 置为 0。内核执行线程申请自旋锁时，原子地将 Next 域加 1，并将原值返回作为自己的票据序号。如果返回的票据序号等于申请时的 Owner 值，说明自旋锁处于未使用状态，则直接获得锁；否则，该线程忙等待检查 Owner 域是否等于自己持有的票据序号，一旦相等，则表明锁轮到自己获取。线程释放锁时，原子地将 Owner 域加 1 即可，下一个线程将会发现这一变化，从忙等待状态中退出。线程将严格地按照申请顺序依次获取排队自旋锁，从而完全解决了“不公平”问题。
linux大内核锁
大内核锁本质上也是自旋锁，但是它又不同于自旋锁，自旋锁是不可以递归获得锁的，因为那样会导致死锁。但大内核锁可以递归获得锁。大内核锁用于保护整个内核，而自旋锁用于保护非常特定的某一共享资源。进程保持大内核锁时可以发生调度，具体实现是：在执行schedule时，schedule将检查进程是否拥有大内核锁，如果有，它将被释放，以致于其它的进程能够获得该锁，而当轮到该进程运行时，再让它重新获得大内核锁。注意在保持自旋锁期间是不运行发生调度的。
需要特别指出，整个内核只有一个大内核锁，其实不难理解，内核只有一个，而大内核锁是保护整个内核的，当然有且只有一个就足够了。
还需要特别指出的是，大内核锁是历史遗留，内核中用的非常少，一般保持该锁的时间较长，因此不提倡使用它。从2.6.11内核起，大内核锁可以通过配置内核使其变得可抢占（自旋锁是不可抢占的），这时它实质上是一个互斥锁，使用信号量实现。
大内核锁的API包括：
void lock_kernel(void);
该函数用于得到大内核锁。它可以递归调用而不会导致死锁。
void unlock_kernel(void);
该函数用于释放大内核锁。当然必须与lock_kernel配对使用，调用了多少次lock_kernel，就需要调用多少次unlock_kernel。
大内核锁的API使用非常简单，按照以下方式使用就可以了：
lock_kernel();
//对被保护的共享资源的访问
…
unlock_kernel()；
