对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_BARRIER和CPU_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可以提高性能、节能减排。

致谢

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