传统的自旋锁实际上就是一个整数，值为1时表示没有被占用，值为0或负数时表示锁已经被占用，此时spin_lock循环等待，直到spin_unlock将自旋锁的值置为1，在这个过程中没有保存线程申请自旋锁的顺序信息，后进入等待的线程有可能先获得自旋锁。

    排队自旋锁(FIFO Ticket Spinlock)是 Linux 内核 2.6.25 版本引入的一种新型自旋锁，它通过保存执行线程申请锁的顺序信息解决了这种问题，让先申请自旋锁的线程先得到锁。

    1. Ticket spinlock的实现原理

    排队自旋锁还是使用一个整形slock，并将其分为两个部分：

    Ticket Number

    Next和Owner的长度与CPU的个数相关, 当CPU的个数 < 256时，Next和Owner为8位。当CPU的个数 > 256时，Next和Owner为16位。

    #if (NR_CPUS < 256)

    #define TICKET_SHIFT 8

    ...

    #else

    #define TICKET_SHIFT 16

    slock初始化时被置为0，Next和Owner都被置为0，当内核线程申请自旋锁时，比较原始的Next和Owner并将Next加1，如果原始的Next域和Owner域相等则表示锁处理未使用状态，否则改线程轮询等待直到Next域和Owner域相等。当释放锁时将Owner域加1.

    2. Ticket spinlock的实现代码

    下面查看__ticket_spin_lock和__ticket_spin_unlock两个函数(NR_CPUS < 256)：

    加锁：

    点击(此处)折叠或打开

    static __always_inline void __ticket_spin_lock(arch_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");

    }

    a. xaddw %w0, %1： 将inc和lock->slock的低16位置交换，并将相加后的值存贷lock->slock中.

    例：slock = 0x00 00 11 10，操作之后slock = 0x00 00 12 10, inc = 0x00 00 11 10.

    b. cmpb %h0, %b0： 比较inc的低8位（Owner）和高8位（Next），相等则获得锁返回，不相等则继续执行；

    c. 不断轮询lock->slock, 等待直到Next和Owner相等。

    解锁

    点击(此处)折叠或打开

    static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)

    {

    asm volatile(UNLOCK_LOCK_PREFIX "incb %0" // 将owner加1

    : "+m" (lock->slock)

    :

    : "memory", "cc");

    }

    a. 解锁只执行一个操作就是讲slock的Owner字段加1；

    通过这种方式，线程调用__ticket_spin_lock的顺序存放在Next字段中，Next字段小的线程会先得到锁。

   凌阳嵌入式Linux培训网提供更多linux内核学习资料：http://emb.sunplusedu.com/answer/2013/0801/2064.html