彼德森（Peterson）算法在多线程环境的实际应用与并发问题的解决（i++）

这是一篇关于简单情况下进行并发控制的文章，核心是彼德森算法，还有一些编程实现方面的小技巧，希望对浏览到的人提供帮助。

并发是os中最常见的问题之一，在早期，人们尝试使用纯算法的方法在软件层面进行实现，但这种方案由于不具备普适性，而且不够高效，后续的研究者采用软硬件结合的方式进行设计。但早期的方法仍然对我们有启发的意义。

这里简单的说明一下彼德森算法：（这位博主讲的不错，我这里copy一下）

链接：彼德森算法详解

当你看完上面这篇博文以后，你应该了解了彼德森算法的原理，但我发现在这方面，大家都没有给出很好的算法实现或模拟过程，所以这里我给出该算法在两个线程下的真实模拟过程：

用最为简单的 i++; 操作为例 （至于我为什么要举这个例子，可以看我的另一篇博文：i++原子性详解）

我们给定一个大数NN，执行这样的操作：

如果是单线程条件下，这是完全没有问题的。但是我们开两个线程时，会导致一些严重的后果，比如，发生上下文切换，(如果看完了我的另一篇文章，你应该理解这里，链接：i++原子性详解)，导致i的运行结果和我们的预期不一样。此时就需要加锁控制，锁的实现为彼德森算法。

小技巧：彼德森算法使用0，1变量，我们可以通过对线程进行命名0和1的方式，再在线程内部将其从char转为int类型，来实现彼德森的应用。（具体见代码部分）

//编译：gcc pthread.c -o test -lpthread

这里我们让NN=1000000000；

在不加锁的时候运行一下，得到如下截图：

我们发现结果不正确，我们开了两个线程，预期得到1000000000*2的结果，但答案却出乎意料，为了解决这个问题，要进行并发控制，怎么控制呢，加锁就行了，如图：

我们设计的锁为内部执行彼德森算法，对外封装为这俩兄弟：

加锁：enter_region(f); 

解锁： leave_region(f);

通过在临界区加锁，我们就通过彼德森算法实现的自旋锁，得到了正确的答案。

观众疑问环节：

为什么不在for循环内加锁/p>

答：这样会导致效率变得非常低，在我使用的NN=1000000000这个数量级，会带来恐怖的时间开销。有兴趣的同学可以使用我提供的源码自己运行一下，感受一下自旋锁带来的一些问题（更详细的内容要深入学习并发的内容，我这里不多介绍了）。

注：关于多线程部分做一个小解释：

1.

这是创建两个线程变量

2.

这里是创建线程函数的地方，由于我们要创建两个线程，所以要创建两次。

3.

这里是主线程对子线程的等待，我开了两个线程，所以等待两次。

4.

有的同学可能不太明白这里是什么意思，这里大概说明一下：

       彼德森算法需要的参数为0或1（int类型），但我们的函数名在主线程中设置为”0″和”1″,是char类型，所以，为了将参数顺利传入彼德森函数。我们要将函数名转换为int类型，这里使用c库中的atoi实现char转为int。

5.

这里是记录时间的部分，可以展示运行的时间，知道这个即可。

源代码如下：

运行环境：windows10 + VMware workStation16 + Ubuntu 20 64位 + Clion

tips：

1.要记得加上pthread库的编译指令，在clion中，在cmake里面添加即可：

2.#include <sys/time.h> 有些同学会在这里有问题，建议搜一下解决方法，我已经忘掉了23333

如果这篇文章对你有帮助，求各位大侠点个赞，评论一下啦。

文章知识点与官方知识档案匹配，可进一步学习相关知识

来源：_hdk