Ticket Lock
简单回顾
上回 我们介绍了peterson算法来实现spin lock，算法简单，实现简单，但是值得注意和留心的点很多。
粗略说来，peterson算法的主要缺点在于：
1，很难推广到n个线程(n>=3)。原始的算法针对两个线程，如果想应用在多个线程的场景里，需要做一定的修改。
2，peterson算法的动机是仅仅使用load和store来实现互斥访问。然而，我们知道，现代体系结构下，CPU和编译器会对读写操作进行乱序，仅仅依靠读写操作而不使用memory barrier就编写正确的程序非常困难。
Ticket Lock
在介绍Ticket Lock之前，我们首先分析一个妇孺皆知、地球人都知道的实现spin lock的方法（伪代码）：
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。如下图的伪代码所示：
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，原子操作少些，少些，再少些。
这就涉及到我们要谈到的Ticket Lock。
想想我们去银行排队办业务：先拿个号，然后排队，叫到你的号就是服务你的时候了。没叫到你？老老实实等着吧（这里不考虑关系户走后门插队）。
Yedis 中实现了ticket spin lock，这里摘抄如下：
class YedisTicketSpinLock { public: YedisTicketSpinLock() { next_id_ = 0; service_id_ = 0; } bool lock() { uint64_t my_id = FETCH_AND_ADD(&next_id_, 1); CPU_BARRIER(); 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 是一个原子操作:
int fech_and_add(int *p, int inc) { int origin = *p; *p += inc; return origin; } 顺便说一下，也有所谓的 add_and_fech ：
int add_and_fetch(int *p, int inc) { *p += inc; return *p; } 区别就在于返回原来的值还是返回更新后的值
第13行：判断是否到自己的号了，否则就一直等待。
第18行：叫下一个人，和下一个人说，轮到你了。
关于 CPU_BARRIER 、 FETCH_AND_ADD 、 ACCESS_ONCE 和 INC_ATOMIC 的实现，请参考 Yedis 中的相关代码。
公平性：不难看出，先来排队的人将优先获得服务。
性能：不难看出，和之前的不断CAS的版本相比，ticket lock算法中，一次lock调用只有一次原子操作开销。
哈哈，如果过号呢？现实生活里，去银行排队可能因为时间太长不爽闪人了，银行叫人如果连叫三遍还没看到你就会叫下一个人了。
在这里，假如持有锁的线程crash了，来不及调用unlock，那么所有等待锁的线程都将一直spin，除非，哦，除非海量的线程来排队不断自增 next_id_ 导致 next_id_ 溢出回滚，然后重新等于 service_id_ 。
如果持有锁的线程没有crash，它正常释放锁，而叫到的下一个线程之前crash了，那么也会导致所有排队的线程拿不到锁。
顺便说一下，(部分)Linux Kernel的spin lock就是用ticket lock实现的。更多细节可以参考 这里 。
那么ticket lock是否完美呢？有什么惊人的缺点呢？请看下集。
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
