Linux 内核的排队自旋锁(FIFO Ticket Spinlock)-1

look_w

引言自旋锁(Spinlock)是一种 Linux 内核中广泛运用的底层同步机制。自旋锁是一种工作于多处理器环境的特殊的锁，在单处理环境中自旋锁的操作被替换为空操作。当某个处理器上的内核执行线程申请自旋锁时，如果锁可用，则获得锁，然后执行临界区操作，最后释放锁；如果锁已被占用，线程并不会转入睡眠状态，而是忙等待该锁，一旦锁被释放，则第一个感知此信息的线程将获得锁。
长期以来，人们总是关注于自旋锁的安全和高效，而忽视了自旋锁的“公平”性。传统的自旋锁本质上用一个整数来表示，值为1代表锁未被占用。这种无序竞争的本质特点导致执行线程无法保证何时能取到锁，某些线程可能需要等待很长时间。随着计算机处理器个数的不断增长，这种“不公平”问题将会日益严重。
排队自旋锁(FIFO Ticket Spinlock)是 Linux 内核 2.6.25 版本引入的一种新型自旋锁，它通过保存执行线程申请锁的顺序信息解决了传统自旋锁的“不公平”问题。排队自旋锁的代码由 Linux 内核开发者 Nick Piggin 实现，目前只针对 x86 体系结构(包括 IA32 和 x86_64)，相信很快就会被移植到其它平台。
传统自旋锁的实现与不足Linux 内核自旋锁的底层数据结构 raw_spinlock_t 定义如下：
清单 1. raw_spinlock_t 数据结构

1 2 3

typedef struct {     unsigned int slock; } raw_spinlock_t;

slock 虽然被定义为无符号整数，但是实际上被当作有符号整数使用。slock 值为 1 代表锁未被占用，值为 0 或负数代表锁被占用。初始化时 slock 被置为 1。
线程通过宏 spin_lock 申请自旋锁。如果不考虑内核抢占，则 spin_lock 调用 __raw_spin_lock 函数，代码如下所示：
清单 2. __raw_spin_lock 函数

1 2 3 4 5 6 7 8 9 10 11 12 13

static inline void __raw_spin_lock(raw_spinlock_t *lock) {     asm volatile("\n1:\t"              LOCK_PREFIX " ; decb %0\n\t"              "jns 3f\n"              "2:\t"              "rep;nop\n\t"              "cmpb $0,%0\n\t"              "jle 2b\n\t"              "jmp 1b\n"              "3:\n\t"              : "+m" (lock->slock) : : "memory"); }

• LOCK_PREFIX 的定义如下：
  清单 3. LOCK_PREFIX宏

  1 2 3 4 5 6 7 8 9 10 11

  #ifdef CONFIG_SMP #define LOCK_PREFIX \         ".section .smp_locks,\"a\"\n"   \         _ASM_ALIGN "\n"         \         _ASM_PTR "661f\n" /* address */ \         ".previous\n"           \         "661:\n\tlock; " #else /* ! CONFIG_SMP */ #define LOCK_PREFIX "" #endif

  
  
  
  在多处理器环境中 LOCK_PREFIX 实际被定义为 “lock”前缀。
  x86 处理器使用“lock”前缀的方式提供了在指令执行期间对总线加锁的手段。芯片上有一条引线 LOCK，如果在一条汇编指令(ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, XCHG)前加上“lock” 前缀，经过汇编后的机器代码就使得处理器执行该指令时把引线 LOCK 的电位拉低，从而把总线锁住，这样其它处理器或使用DMA的外设暂时无法通过同一总线访问内存。
  从 P6 处理器开始，如果指令访问的内存区域已经存在于处理器的内部缓存中，则“lock” 前缀并不将引线 LOCK 的电位拉低，而是锁住本处理器的内部缓存，然后依靠缓存一致性协议保证操作的原子性。
  
• decb 汇编指令将 slock 的值减 1。由于“减 1”是“读-改-写”操作，不是原子操作，可能会被同时申请锁的其它处理器上的线程干扰，所以必须加上“lock”前缀。
  
• jns 汇编指令检查 EFLAGS 寄存器的 SF(符号)位，如果为 0，说明 slock 原来的值为 1，则线程获得锁，然后跳到标签 3 的位置结束本次函数调用。如果 SF 位为 1，说明 slock 原来的值为 0 或负数，锁已被占用。那么线程转到标签 2 处不断测试 slock 与 0 的大小关系，假如 slock 小于或等于 0，跳转到标签 2 的位置继续忙等待；假如 slock 大于 0，说明锁已被释放，则跳转到标签 1 的位置重新申请锁。
  

线程通过宏 spin_unlock 释放自旋锁，该宏调用 __raw_spin_unlock 函数：
清单 4. __raw_spin_unlock函数

1 2 3 4

static inline void __raw_spin_unlock(raw_spinlock_t *lock) {     asm volatile("movb $1,%0" : "+m" (lock->slock) :: "memory"); }

可见 __raw_spin_unlock 函数仅仅执行一条汇编指令：将 slock 置为 1。
尽管拥有使用简单方便、性能好的优点，自旋锁也存在自身的不足：

• 由于传统自旋锁无序竞争的本质特点，内核执行线程无法保证何时可以取到锁，某些执行线程可能需要等待很长时间，导致“不公平”问题的产生。这有两方面的原因：
  
  • 随着处理器个数的不断增加，自旋锁的竞争也在加剧，自然导致更长的等待时间。
    
  • 释放自旋锁时的重置操作将无效化所有其它正在忙等待的处理器的缓存，那么在处理器拓扑结构中临近自旋锁拥有者的处理器可能会更快地刷新缓存，因而增大获得自旋锁的机率。
    
• 由于每个申请自旋锁的处理器均在全局变量 slock 上忙等待，系统总线将因为处理器间的缓存同步而导致繁重的流量，从而降低了系统整体的性能。