这是非常正规的流程,我们基本上也都是这么做的。
那有没有想过,这些同步原语对代码的执行效率会产生多大的影响?是否可以不使用操作系统提供的这些机制,而是用其它纯软件的方法也能达到保护临界区的目的呢?
这篇文章我们介绍一下 Peterson(皮特森)算法,也许实用性不强,但是可以给我们带来一些思考,提高我们的编程元技能。
二、Peterson 算法简介
这个算法主要用来解决临界区的保护问题。我们知道,一个临界区必须保证 3 个条件:
- 互斥访问: 在任意一个时刻,最多只能有一个线程可以进入临界区;
- 空闲让进:当没有线程正在执行临界区的代码时,必须在所有申请进入临界区的线程中,选择其中的一个,让它进入临界区;
- 有限等待:当一个线程申请进去临界区时,不能无限的等待,必须在有限的时间内获得许可进入临界区。也就是说,不论其优先级多低,不应该饿死在该临界区入口处。
Peterson算法是一个实现互斥锁的并发程序设计算法,可以控制两个线程访问一个共享的用户资源而不发生访问冲突。
Peterson 算法是基于双线程互斥访问的 LockOne 与 LockTwo 算法而来。
- LockOne 算法使用一个 flag 布尔数组来实现互斥;
- LockTwo 使用一个 turn 的整型量来实现互斥;
这 2 个算法都实现了互斥,但是都存在死锁的可能。Peterson 算法把这两种算法结合起来,完美地用软件实现了双线程互斥问题。
算法说明如下
两个重要的全局变量:
flag 数组:有 2 个布尔元素,分别代表一个线程是否申请进入临界区;
turn:如果 2 个线程都申请进入临界区,这个变量将会决定让哪一个线程进入临界区;
三、测试代码
- // 被 2 个线程同时访问的全局资源
- static int num = 0;
-
- BOOL flag[2] = { 0 };
- int turn = 0;
-
- void *thread0_routine(void *arg)
- {
- for (int i = 0; i < 1000000; ++i)
- {
- flag[0] = TRUE;
- turn = 1;
- while (TRUE == flag[1] && 1 == turn);
-
- // 临阶区代码
- num++;
-
- flag[0] = FALSE;
- }
-
- return NULL;
- }
-
- void *thread1_routine(void *arg)
- {
- for (int i = 0; i < 1000000; ++i)
- {
- flag[1] = TRUE;
- turn = 0;
- while (TRUE == flag[0] && 0 == turn);
-
- // 临阶区代码
- num++;
-
- flag[1] = FALSE;
- }
-
- return NULL;
- }
全局资源 num 的初始值为 0 ,两个编程分别递增 100 万次,因此最终结果应该是 200 万,实际测试结果也确实如此。
四、Mutex 互斥锁对代码执行效率的影响
单线程中:Mutex 互斥锁对代码执行效率的影响
- for (int i = 0; i < 1000000; ++i)
- {
- num++;
- }
以上代码,耗时约:1.8ms -- 3.5ms。
- for (int i = 0; i < 1000000; ++i)
- {
- pthread_mutex_lock(&mutex);
- num++;
- pthread_mutex_unlock(&mutex);
- }
以上代码,耗时约:23.9ms -- 38.9ms。可以看出,上锁和解锁对代码执行效率的影响还是很明显的。
多线程中:Mutex 互斥锁对代码执行效率的影响
- void *thread0_routine(void *arg)
- {
- for (int i = 0; i < 1000000; ++i)
- {
- pthread_mutex_lock(&mutex);
- num++;
- pthread_mutex_unlock(&mutex);
- }
-
- return NULL;
- }
-
- void *thread1_routine(void *arg)
- {
- for (int i = 0; i < 1000000; ++i)
- {
- pthread_mutex_lock(&mutex);
- num++;
- pthread_mutex_unlock(&mutex);
- }
-
- return NULL;
- }
耗时:
- thread0: diff = 125.8ms
- thread1: diff = 129.1ms
在两个线程中,使用 Peterson 算法来保护临界区
耗时:
- thread1: diff = 1.89ms
- thread0: diff = 1.94ms
五、总结
Peterson 算法使用纯软件来保护临界区,比使用操作系统提供的互斥锁表现出了更好的性能。
但是它也有一个缺点:只能使用在 2 个线程中,但是由于它与平台无关,在某些特殊的场合,也许能够拿来为我们所用!