Yebangyu's Blog

Fond of Concurrency Programming, Distributed System and Performance Optimization.

Peterson算法实现spin lock

对spin lock和mutex不熟悉的朋友,可以看上篇博客。

提出问题

如何仅仅通过load和store实现spin lock呢?

本文只考虑、只针对只有两个线程的情形。假设这两个线程的id分别为0和1。编程环境为X86体系结构 + Intel CPU + gcc

分析问题

尝试一:仅使用一个变量

仅使用一个bool类型变量flag,线程i申请锁时,查看flag是否为1-i,如果不是,说明另外一个线程没有在临界区,申请成功,并把flag的值设置为i。

这种方法的问题在于,检查flag是否为1-i,以及设置flag为i这两步不是原子的,无法仅仅通过load和store来原子实现。(需要CAS等类似的原子操作)

尝试二:使用两个变量

根据前面的分析,我们可以使用两个bool变量flag[0]和flag[1]。线程i申请锁时,先把flag[i]设置为true,表示自己试图进入临界区,然后查看flag[1-i]是否为true,如果是,说明另一个线程在临界区,于是spin。

这个方法的问题在于可能发生这样的问题:

线程0把flag[0]设置为true,这时候还没开始检查flag[1],此时线程1把flag[1]设置为true。

接下去,每个线程都发现对方的flag为true,而实际上两个都没在临界区中,却谁都没法拿到锁,发生starvation现象。

尝试三:使用三个变量

在尝试二的基础上,再增加一个变量turn,表示谁先将自己的flag设置为true(仅仅通过那两个flag是没法区分的,想想看,是不是这样的)。因此这个变量可以用来裁决谁取得进入临界区的权利。

解决问题

以上尝试三所描述的方法,就是大名鼎鼎的peterson算法的雏形了。简单实现如下(注意,本文的平台是x86体系结构 + Intel CPU + gcc):

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
class PetersonSpinLock
{
  public:
    PetersonSpinLock()
    {
      flags_[0] = false;
      flags_[1] = false;
      turn_ = false;//initial value does not matter
    }
    bool lock(int thread_id)
    {
      int other = !thread_id;
      flags_[thread_id] = true;
      COMPILER_BARRIER();
      turn_ = thread_id;
      CPU_BARRIER();// essential
      while(flags_[other] && turn_ == thread_id) {
        CPU_RELAX();//spin
      }
      //get lock successfully
      return true;
    }
    bool unlock(int thread_id)
    {
      flags_[thread_id] = false;
      return true;
    }
  private:
    volatile bool flags_[2];
    volatile bool turn_;
};

以下是对peterson算法的思考和讨论。在看我的分析之前,请自己尝试思考以下问题:(温馨提示:在C/C++中,if条件判断是短路求值的。也就是说对于if(A && B),一旦知道A是false,那么B将不用evaluate了)

  • peterson算法如何防止starvation的发生?
  • peterson算法如何防止两个线程同时进入临界区?
  • 代码13行和15行能否调换执行顺序?
  • 代码15行能否改为turn_ = !thread_id
  • 16行的cpu 级别的memory barrier是否必要?
  • 实现(针对两个线程的)peterson算法所需最少空间为多少?

思考了没?下面我们来分析讨论一下:

peterson算法如何防止starvation的发生?

假设某时刻两个线程都在spin,也就是17行中while的条件对两个线程都成立,也就是说:

flag_[0] == true 并且 trun_ == 0 并且 flag_[1] == true 并且turn_ == 1

但是turn_只能有一个值,矛盾。

peterson算法如何防止两个线程同时进入临界区?

如果两者同时进入临界区,说明17行中的while判断对两个线程都为false,也就是说

flag_[1] == false 或者 turn _ == 1

同时

flag_[0] == false 或者 turn_ == 0

因此只有四种情形:

flag_[1] == false && flag_[0] == false 与13行矛盾

flag_[1] == false && turn_ == 0 与13行矛盾

turn_ == 1 && flag_[0] == false 与13行矛盾

turn _ == 1 && turn _ == 0 不可能发生

而一旦例如说,线程0,进入临界区后,线程1会因为turn_的值而spin,直到线程0通过unlock将flag_[0]设置为false。

因此,13、15两行的顺序很重要。是这样的吗?接着往下看。

代码13行和15行能否调换执行顺序?

不可以,否则可能发生两个线程同时进入临界区。

考虑以下情形:

线程0执行turn_ = 0

线程1执行turn_ = 1

线程1执行flag_[1] = true

线程1执行17行的判断,因为flag_[0]为false,所以线程1进入临界区。

线程0执行flag_[0] = true

线程0执行17行判断,此时turn_等于1,所以线程0也进入临界区。

因此13行和15行执行顺序不可以交换;而这两个都是store操作,在X86 Intel CPU下,cpu不会乱序执行它们,因此只需要在14行增加一个compiler级别的memory barrier,防止编译器乱序即可。

代码15行能否改为turn_ = !thread_id

可以。只是如果15行改为turn_ = !thread_id,那么17行需要将turn_ == thread_id也改为turn_ == !thread_id。也就是说turn_的初始值是什么并不重要,turn_设置成什么值也不太重要,重要的是通过turn_能区分出谁先尝试申请锁。

16行的cpu 级别的Memory Barrier是否必要?

非常必要。否则17行对flags_[other]的读取(判断)操作可能和15行发生乱序(写读乱序。而13、15属于写写,是不会被CPU乱序执行的,不用加cpu 级别的memory barrier),最后可能导致两个线程同时进入临界区。这点,请读者务必自己亲自分析。非常重要!

不加Memory Barrier,乱序后,考虑以下情形:

线程0判断flag_[1],发现为false(此时线程1还没开始调用lock函数,flag_[1]还是它的初始值false),进入临界区。

线程1判断flag_[0],发现为true

线程1执行turn_ = 1

线程0执行turn_ = 0

线程1执行17行判断,此时turn_等于0,所以线程1也进入临界区。

实现(针对两个线程的)peterson算法所需最少空间为多少?

3个bit足矣。两个flag_两个bit,turn_也只需要1个bit。

附录:

在X86下,CPU_BARRIERCPU_RELAX以及COMPILER_BARRIER可以用gcc内置feature,通过宏来实现:

1
2
3
#define CPU_BARRIER() __sync_synchronize()
#define COMPILER_BARRIER() __asm__ __volatile__("" : : : "memory")
#define CPU_RELAX() __asm__ __volatile__("pause": : :"memory")

18行不用CPU_RELAX而是简单的一个分号行吗?可以的。不过加了CPU_RELAX可以提高性能、节能减排。

致谢

本文发出后,微博网友@finalpatch 指出应在代码的29、30行加上volatile。非常感谢。

本文发出后,微博网友@linyvxiang 指出了文中的两处笔误。非常感谢。