神刀安全网

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_BARRIERFETCH_AND_ADDACCESS_ONCEINC_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是否完美呢?有什么惊人的缺点呢?请看下集。

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Ticket Lock

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址