Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

Ticket Lock

简单回顾

上回 我们介绍了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_ADDACCESS_ONCEINC_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是否完美呢?有什么惊人的缺点呢?请看下集