简单回顾

上回 我们介绍了peterson算法来实现spin lock，算法简单，实现简单，但是值得注意和留心的点很多。

粗略说来，peterson算法的主要缺点在于：

1，很难推广到n个线程(n>=3)。原始的算法针对两个线程，如果想应用在多个线程的场景里，需要做一定的修改。

2，peterson算法的动机是仅仅使用load和store来实现互斥访问。然而，我们知道，现代体系结构下，CPU和编译器会对读写操作进行乱序，仅仅依靠读写操作而不使用memory barrier就编写正确的程序非常困难。

Ticket Lock

在介绍Ticket Lock之前，我们首先分析一个妇孺皆知、地球人都知道的实现spin lock的方法（伪代码）：

1
2
3
4
5
6
7
8
9
10

int flag = 0;
void lock()
{
  while (!cas(flag, 0, 1));
  //get lock ! now , flag == 1
}
void unlock()
{
  flag = 0;
}

上面代码的第四行使用一个CAS原子操作：判断如果flag是否为0，如果为0，将它的值设置为1。判断和设置，所谓的test和set是一个原子操作，返回ture；如果不为0，则不设置，返回false。

这就是大名鼎鼎的test-and-set来实现spin lock。想想看，这种实现方式有什么缺点？

缺点一：不保证公平性，不满足FIFO先来先服务。假如有两个线程在第4行上spin，那么当持有锁的线程释放锁之后，这两个线程谁会成功拿到锁和谁先来spin没有任何直接关系。

缺点二：我们知道，不管CAS操作是否成功，都会产生大量的因为需要保证cache coherency而产生的message，降低性能。因此有一种改进方式：在CAS之前，先读取flag的值，当flag的值为0的时候，再尝试CAS。如下图的伪代码所示：

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

int flag = 0;
void lock()
{
  while(true) {
    if (flag == 0) {
      if (cas(flag, 0, 1)) {
        break;
      }
    }
  }
  //get lock ! now , flag == 1
}
void unlock()
{
  flag = 0;
}

改进后的算法叫做test-and-test-and-set，然而即使经过改进，上面的两个问题依旧存在。在很多场景下，我们希望：

1，保证公平性。

2，原子操作少些，少些，再少些。

3，没有饥饿。

这就涉及到我们要谈到的Ticket Lock。

想想我们去银行排队办业务：先拿个号，然后排队，叫到你的号就是服务你的时候了。没叫到你？老老实实等着吧（这里不考虑关系户走后门插队）。

Soupen中实现了ticket spin lock，这里摘抄如下：

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

class SoupenTicketSpinLock
{
  public:
    SoupenTicketSpinLock()
    {
      next_id_ = 0;
      service_id_ = 0;
    }
    bool lock()
    {
      uint64_t my_id = FETCH_AND_ADD(&next_id_, 1);
      while(my_id != ACCESS_ONCE(service_id_)) {}
      return true;
    }
    void unlock()
    {
      INC_ATOMIC(&service_id_, 1);
    }
  private:
    uint64_t next_id_;
    uint64_t service_id_;
};

第11行：获得自己的号，同时把号码递增。其中fetch_and_add是一个原子操作:

1
2
3
4
5
6

int fech_and_add(int *p, int inc)
{
  int origin = *p;
  *p += inc;
  return origin;
}

顺便说一下，也有所谓的add_and_fech：

1
2
3
4
5

int add_and_fetch(int *p, int inc)
{
  *p += inc;
  return *p;
}

区别就在于返回原来的值还是返回更新后的值

第12行：判断是否到自己的号了，否则就一直等待。

第17行：叫下一个人，和下一个人说，轮到你了。

关于FETCH_AND_ADD、ACCESS_ONCE和INC_ATOMIC的实现，请参考Soupen中的相关代码。

公平性：不难看出，先来排队的人将优先获得服务。

性能：不难看出，和之前的不断CAS的版本相比，ticket lock算法中，一次lock调用只有一次原子操作开销。

饥饿：不难看出，每个线程都可以按照自己的排队顺序拿到锁，不会发生饥饿现象。

哈哈，如果过号呢？现实生活里，去银行排队可能因为时间太长不爽闪人了，银行叫人如果连叫三遍还没看到你就会叫下一个人了。

在这里，假如持有锁的线程crash了，来不及调用unlock，那么所有等待锁的线程都将一直spin，除非，哦，除非海量的线程来排队不断自增next_id_导致next_id_溢出回滚，然后重新等于service_id_。

如果持有锁的线程没有crash，它正常释放锁，而叫到的下一个线程之前crash了，那么也会导致所有排队的线程拿不到锁。

顺便说一下，(部分)Linux Kernel的spin lock就是用ticket lock实现的。更多细节可以参考这里。

那么ticket lock是否完美呢？有什么惊人的缺点呢？请看下集