Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

MCS Lock

回顾

上回 我们介绍了Ticket Lock算法,和传统的简单的CAS操作来实现spin lock相比,它提供了不少很好的性质:比如FIFO、没有饥饿等等。

但是根据论文,ticket lock的scalability很差。我们不妨简单回顾一下(代码片段也摘自该论文):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct spinlock_t
{
  int current_ticket ;
  int next_ticket ;
}
void spin_lock (spinlock_t *lock)
{
  int t = atomic_fetch_and_inc(&lock -> next_ticket );
  while (t != lock->current_ticket )
  ; /* spin */
}
void spin_unlock (spinlock_t *lock)
{
  lock->current_ticket++;
}

正如论文中指出的那样,当某个core上持有锁的线程释放锁时,它将把其他core上的current_ticket对应的cacheline都invalid掉,之前所有等锁的线程都会通过bus来读取最新的cacheline,这将造成“拥堵”(也就是所谓的bus traffic)。由于在绝大多数体系结构下,这些读取请求都会被串行化,one by one的处理,因此spin_lock所需时间将正比于等待锁的线程数目。

本质上,这里的问题还是在于资源共享:所有等锁线程都spin在同一个全局变量上。如果每个线程仅仅spin在本地变量(该线程私有的变量),那么将有效的提高scalability。本文要介绍的MCS Lock就是这样的思路。

实现

这次,我们先给出实现(环境为:GCC 4.8 + X86体系结构 + Ubuntu 14.04 32bit系统),然后再讲解算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#define COMPILER_BARRIER() __asm__ __volatile__("" : : : "memory")
#define CPU_RELAX() __asm__ __volatile__("pause\n": : :"memory")
#define CAS(address, exp, target) __sync_bool_compare_and_swap(address, exp, target)
#define ATOMIC_EXCHANGE(address, val) __atomic_exchange_n(address, val, __ATOMIC_SEQ_CST)
#define CPU_BARRIER() __sync_synchronize()
//=========================================

struct mcs_lock_node
{
  volatile int waiting;
  mcs_lock_node *volatile next;
};

typedef mcs_lock_node *volatile mcs_lock;

static mcs_lock_node* get_my_mcs_node()
{
  static __thread mcs_lock_node my_mcs_node;
  return &my_mcs_node;
}

static void spin_lock(mcs_lock &lock)
{
  mcs_lock_node *me = get_my_mcs_node();
  mcs_lock_node *tmp = me;
  mcs_lock_node *pre;
  me->next = NULL;
  pre = ATOMIC_EXCHANGE(&lock, tmp);
  if (pre == NULL) {
    return;	
  }
  me->waiting = 1;
  COMPILER_BARRIER();
  pre->next = me;
  while (me->waiting) {
    CPU_RELAX();
  }
  CPU_BARRIER();
}

static void spin_unlock(mcs_lock &lock)
{
  CPU_BARRIER();
  mcs_lock_node *me = get_my_mcs_node();
  mcs_lock_node *tmp = me;
  if (me->next == NULL) {
    if (CAS(&lock, tmp, NULL)) {
      return;
    }
    while (me->next == NULL) {
      CPU_RELAX();
    }
  }
  me->next->waiting = 0;
}

算法

MCS Lock算法维护一个队列(队尾指针tail)。

lock:尝试加锁的线程首先获得自己的节点,接着通过原子操作ATOMIC_EXCHANGE,将自己插入队列中,并获得插入前队尾指针tail。如果tail指针为空,说明当前锁是空闲的,没有被任何线程占用,因此获得锁成功;如果tail指针不空,那么设置自己的前驱,然后自旋,等待它的前驱(线程)将自己的waiting域置为0。waiting域一旦为0,那么线程结束spin,该线程就变成锁的持有者了。

unlock:释放锁的线程需要检查是否存在后继,如果存在后继,那么将它的后继的waiting域设置为0即可,后继将结束spin,成功获得锁。一切搞定,如54行代码所示。

如果不存在后继,那么这里需要特别特别注意。不存在后继有两种可能:

它是最后一个线程。47-49行处理的就是这种情况。那么这时候只需要把队列置为空即可。

它不是最后一个线程。那么此时存在另外一个线程在进行加锁操作,尝试加锁的线程已经通过28-33行设置了新的队尾指针,但是还没设置它的前驱,也就是还没执行到34行。因此释放锁的线程需要等待,等待34行被其他线程执行,等待它被人设置为别人的前驱。这也就是50-52行所做的事。

简单说来,MCS Lock就是将线程们用队列管理起来;加锁的线程spin在自己的变量上;释放锁的线程只更新它后继的变量。

练习

1,MCS Lock的优点是显而易见的,因为每个等待锁的线程都spin在自己的局部的变量上。以至于新版的linux内核已经开始采用它,来代替之前的ticket lock实现。那么,它的缺点呢?

2,列出表格,从公平性、是否出现饥饿、时间空间复杂度等方面,全面对比ticket lock、mcs lock、peterson lock等。

3,编写程序测试这几个算法的性能,考察它们的scalability。

附录

MCS Lock测试程序Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<pthread.h>
mcs_lock global_lock = NULL;
void* f(void *arg)
{
  for(int i = 0; i < 1000000; i++) {
    spin_lock(global_lock);
    spin_unlock(global_lock);
  }
  return NULL;
}
int main()
{
  pthread_t pthread1;
  pthread_t pthread2;
  pthread_create(&pthread1, NULL, f, NULL);
  pthread_create(&pthread2, NULL, f, NULL);
  pthread_join(pthread1, NULL);
  pthread_join(pthread2, NULL);
  return 0;
}