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）：
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; 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: bool flags_[2]; bool turn_; };
以下是对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 与14行矛盾
flag_[1] == false && turn_ == 0 与14行矛盾
turn_ == 1 && flag_[0] == false 与14行矛盾
turn _ == 1 && turn _ == 0 不可能发生
假设线程0进入临界区，进入临界区后由于 flag_[0] == true ，线程1将在while处spin。
代码14行和15行能否调换执行顺序？
调换顺序后无法保证先设置flag为true的线程先进入临界区。
代码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行发生乱序（写读乱序。而14、15属于写写，是不会乱序的，不用加barrier），最后可能导致两个线程同时进入临界区。这点，请读者自行分析。非常重要！
实现（针对两个线程的）peterson算法所需最少空间为多少？
3个bit足矣。两个flag_两个bit，turn_也只需要1个bit。
下次，我们将讨论peterson算法的拓展，用于n个线程的情形。
附录：
在X86下， CPU_BARRIER 和 CPU_RELAX 可以用gcc内置的宏实现：
#define CPU_BARRIER() __sync_synchronize() #define CPU_RELAX() __asm__ __volatile__("pause/n": : :"memory")
18行不用CPU_RELAX而是简单的一个分号行吗？可以的。不过加了CPU_RELAX可以节能减排，降低cpu的空耗。
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
