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

look_w

排队自旋锁的设计原理传统自旋锁的“不公平”问题在锁竞争激烈的服务器系统中尤为严重，因此 Linux 内核开发者 Nick Piggin 在 Linux 内核 2.6.25 版本中引入了排队自旋锁：通过保存执行线程申请锁的顺序信息来解决“不公平”问题。
排队自旋锁仍然使用原有的 raw_spinlock_t 数据结构，但是赋予 slock 域新的含义。为了保存顺序信息，slock 域被分成两部分，分别保存锁持有者和未来锁申请者的票据序号(Ticket Number)，如下图所示：
图 1. 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 即可，下一个线程将会发现这一变化，从忙等待状态中退出。线程将严格地按照申请顺序依次获取排队自旋锁，从而完全解决了“不公平”问题。
排队自旋锁的实现排队自旋锁没有改变原有自旋锁的调用接口，该 API 是以 C 语言宏的形式提供给开发人员。下表列出 6 个主要的 API 和相对应的底层实现函数：
表 1. 排队自旋锁 API宏底层实现函数描述spin_lock_init无将锁置为初始未使用状态(值为 0)spin_lock__raw_spin_lock忙等待直到 Owner 域等于本地票据序号spin_unlock__raw_spin_unlockOwner 域加 1，将锁传给后续等待线程spin_unlock_wait__raw_spin_unlock_wait不申请锁，忙等待直到锁处于未使用状态spin_is_locked__raw_spin_is_locked测试锁是否处于使用状态spin_trylock__raw_spin_trylock如果锁处于未使用状态，获得锁；否则直接返回
下面介绍其中 3 个底层函数的实现细节，假定处理器个数不超过 256。

• __raw_spin_is_locked
  清单 5. __raw_spin_is_locked 函数

  1 2 3 4 5

  static inline int __raw_spin_is_locked(raw_spinlock_t *lock) {     int tmp = *(volatile signed int *)(&(lock)->slock);     return (((tmp >> 8) & 0xff) != (tmp & 0xff)); }

  
  
  
  
  • 此函数判断 Next 和 Owner 域是否相等，如果相等，说明自旋锁处于未使用状态，返回 0；否则返回1。
    
  • tmp 这种复杂的赋值操作是为了直接从内存中取值，避免处理器缓存的影响。
    
• __raw_spin_lock
  清单 6. __raw_spin_lock 函数

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  static inline void __raw_spin_lock(raw_spinlock_t *lock) {     short inc = 0x0100;     __asm__ __volatile__ (         LOCK_PREFIX "xaddw %w0, %1\n"         "1:\t"         "cmpb %h0, %b0\n\t"         "je 2f\n\t"         "rep ; nop\n\t"         "movb %1, %b0\n\t"         /* don't need lfence here, because loads are in-order */         "jmp 1b\n"         "2:"         :"+Q" (inc), "+m" (lock->slock)         :         :"memory", "cc"); }

  
  
  
  
  • LOCK_PREFIX 宏在前文中已经介绍过，就是“lock”前缀。
    
  • xaddw 汇编指令将 slock 和 inc 的值交换，然后把这两个值相加后的和存到 slock 中。也就是说，该指令执行完毕后，inc 存有原来的 slock 值作为票据序号，而 slock 的 Next 域被加 1。
    
  • comb 比较 inc 变量的高位和低位字节是否相等，如果相等，表明锁处于未使用状态，直接跳转到标签 2 的位置退出函数。
    
  • 如果锁处于使用状态，则不停地将当前的 slock 的 Owner 域复制到 inc 的低字节处(movb 指令)，然后重复 c 步骤。不过此时 inc 变量的高位和低位字节相等表明轮到自己获取了自旋锁。
    
• __raw_spin_unlock
  清单 7. __raw_spin_unlock 函数

  1 2 3 4 5 6 7 8

  static inline void __raw_spin_unlock(raw_spinlock_t *lock) {     __asm__ __volatile__(         UNLOCK_LOCK_PREFIX "incb %0"         :"+m" (lock->slock)         :         :"memory", "cc"); }

  
  
  
  
  • 在 IA32 体系结构下，如果使用 PPro SMP 系统或者启用了 X86_OOSTORE，则 UNLOCK_LOCK_PREFIX 被定义为“lock”前缀；否则被定义为空。
    
  • incb 指令将 slock 最低位字节也就是 Owner 域加 1。
    

Windows 操作系统的排队自旋锁(Queued Spinlock)介绍排队自旋锁并不是一个新想法，某些操作系统早已采用了类似概念，只是实现方式有所差别。例如在 Windows 操作系统中排队自旋锁被称为 Queued Spinlock。
Queued Spinlock 的工作方式如下：每个处理器上的执行线程都有一个本地的标志，通过该标志，所有使用该锁的处理器（锁拥有者和等待者）被组织成一个单向队列。当一个处理器想要获得一个已被其它处理器持有的 Queued Spinlock 时，它把自己的标志放在该 Queued Spinlock 的单向队列的末尾。如果当前锁持有者释放了自旋锁，则它将该锁移交到队列中位于自己之后的第一个处理器。同时，如果一个处理器正在忙等待 Queued Spinlock，它并不是检查该锁自身的状态，而是检查针对自己的标志；在队列中位于该处理器之前的处理器释放自旋锁时会设置这一标志，以表明轮到这个正在等待的处理器了。
与 Linux 的排队自旋锁相比，Queued Spinlock 的设计更为复杂，但是 Queued Spinlock 拥有自己的优势：

• 忙等待 Queued Spinlock 的每个处理器在针对该处理器的标志上旋转，而不是在全局的自旋锁上测试旋转，因此处理器之间的同步比 Linux 的排队自旋锁少得多。
  
• Queued Spinlock 拥有真实的队列结构，因此便于扩充更高级的功能。
  

扩展排队自旋锁的一点想法排队自旋锁设计简单、实现容易且性能优秀，因此肯定会受到开发人员的欢迎。本节讨论一下排队自旋锁未来可能有用的一些扩展功能：

• 超时(Timeout)
  尽管排队自旋锁保证了内核执行线程严格按照申请顺序获取锁，但是由于锁的竞争剧烈（例如处理器个数达到64或更多），线程仍然可能会等待过长的时间。当该线程获得锁时，环境也许已发生变化而导致无法完成任务。因此申请线程可以预先指定一个等待阈值，一旦超过该阈值且尚未获得锁，则自动从等待队伍中退出，并返回代表超时的错误值。
  
• 优先级(Priority)
  当前的实现中，所有的线程一律平等，严格按照申请顺序等待。某些执行关键操作的线程也许需要特殊对待，即赋予更高的优先级。一旦它们申请自旋锁，就把他们插入到等待队列的前部优先执行。