# 同步，第 4 部分：临界区问题 > 原文：<https://github.com/angrave/SystemProgramming/wiki/Synchronization%2C-Part-4%3A-The-Critical-Section-Problem> ## 候选解决方案 ## 什么是临界区问题？ 正如[同步，第 3 部分：使用互斥锁和信号量](/angrave/SystemProgramming/wiki/Synchronization%2C-Part-3%3A-Working-with-Mutexes-And-Semaphores)中已经讨论的那样，我们的代码的关键部分一次只能由一个线程执行。我们将此要求描述为“互斥”;只有一个线程（或进程）可以访问共享资源。 在多线程程序中，我们可以使用互斥锁和解锁调用来包装关键部分： ```c pthread_mutex_lock() - one thread allowed at a time! (others will have to wait here) ... Do Critical Section stuff here! pthread_mutex_unlock() - let other waiting threads continue ``` 我们如何实施这些锁定和解锁通话？我们可以创建一个确保相互排斥的算法吗？下面显示了不正确的实现， ```c pthread_mutex_lock(p_mutex_t *m) { while(m->lock) {}; m->lock = 1;} pthread_mutex_unlock(p_mutex_t *m) { m->lock = 0; } ``` 乍一看，代码似乎有效;如果一个线程试图锁定互斥锁，则后一个线程必须等到锁被清除。然而，该实现 _ 不满足互斥 _。让我们从两个同时运行的线程的角度仔细研究这个“实现”。在下表中，时间从上到下 - | 时间 | 线程 1 | 线程 2 | | --- | --- | --- | | 1 | `while(lock) {}` | | | 2 | | `while(lock) {}` | | 3 | 锁= 1 | lock = 1 | 哎呀！有竞争条件。在不幸的情况下，两个线程都检查了锁并读取了一个假值，因此能够继续。 ## 临界区问题的候选解决方案。 为了简化讨论，我们只考虑两个线程。请注意，这些参数适用于线程和进程，而经典的 CS 文献则根据需要对关键部分或共享资源进行独占访问（即互斥）的两个进程来讨论这些问题。 提升标志表示线程/进程进入临界区的意图。 请记住，下面列出的伪代码是更大程序的一部分;线程或进程通常需要在进程的生命周期内多次进入临界区。因此，想象每个示例都包含在一个循环中，在这个循环中，线程或进程正在处理其他内容。 下面描述的候选解决方案有什么问题吗？ ``` // Candidate #1 wait until your flag is lowered raise my flag // Do Critical Section stuff lower my flag ``` 答案：候选解决方案＃1 也会遇到竞争条件，即它不满足互斥，因为两个线程/进程都可以读取彼此的标志值（=降低）并继续。 这表明我们应该在检查另一个线程的标志之前提高标志 _- 这是下面的候选解决方案＃2。_ ``` // Candidate #2 raise my flag wait until your flag is lowered // Do Critical Section stuff lower my flag ``` 候选人＃2 满足互斥 - 两个线程不可能同时进入临界区。但是这段代码遇到了死锁！假设两个线程希望同时进入临界区： | Time | Thread 1 | Thread 2 | | --- | --- | --- | | 1 | 升旗 | | | 2 | | raise flag | | 3 | 等...... | wait ... | Ooops 两个线程/进程现在正在等待另一个线程/进程降低其标志。两个人都不会进入临界区，因为它们现在都永远被卡住了！ 这表明我们应该使用回合制变量来尝试解决谁应该继续进行。 ## 回合制解决方案 以下候选解决方案＃3 使用基于回合的变量来礼貌地允许一个线程然后另一个继续 ``` // Candidate #3 wait until my turn is myid // Do Critical Section stuff turn = yourid ``` 候选者＃3 满足互斥（每个线程或进程获得对临界区的独占访问权限），但是两个线程/进程必须采用严格的回合制方法来使用临界区;即，它们被迫进入交替的临界区段访问模式。例如，如果线程 1 希望每毫秒读取一个哈希表，但另一个线程每秒写入一个哈希表，则读取线程必须再等待 999ms 才能再次从哈希表中读取。这个“解决方案”无效，因为如果临界区中没有其他线程，我们的线程应该能够进行并进入临界区。 ## 解决临界区问题所需的属性？ 在解决临界区问题时，我们希望有三个主要的理想属性 * 相互排斥 - 线程/进程获得独占访问权限;其他人必须等到它退出临界区。 * 有界等待 - 如果线程/进程必须等待，那么它只需要等待一段有限的时间（不允许无限等待时间！）。有界等待的确切定义是，在给定进程进入之前，任何其他进程可以进入其临界区的次数存在上限（非无限）。 * 进度 - 如果临界区内没有线程/进程，则线程/进程应该能够继续（进行中）而不必等待。 考虑到这些想法，让我们检查另一个使用转向标志的候选解决方案，前提是两个线程同时需要访问。 ## Turn 和 Flag 解决方案 以下是 CSP 的正确解决方案吗？ ``` \\ Candidate #4 raise my flag if your flag is raised, wait until my turn // Do Critical Section stuff turn = yourid lower my flag ``` 一位教练和另一位 CS 教员最初这么认为！但是，分析这些解决方案很棘手。即使是关于这一特定主题的同行评审论文也包含不正确的解乍一看它似乎满足相互排斥，有界等待和进步：回合制标志仅用于平局事件（因此允许进度和有界等待）并且似乎满足互斥。但是......也许你能找到一个反例？ 候选者＃4 失败，因为线程不会等到另一个线程降低其标志。经过一些思考（或灵感）后，可以创建以下场景来演示如何不满足互斥。 想象一下，第一个线程运行此代码两次（因此转向标志现在指向第二个线程）。当第一个线程仍在 Critical Section 中时，第二个线程到达。第二个线程可以立即继续进入临界区！ | Time | 转 | 线程＃1 | 线程＃2 | | --- | --- | --- | --- | | 1 | 2 | 举起我的旗帜 | | | 2 | 2 | 如果你的旗帜升起，请等到轮到我 | raise my flag | | 3 | 2 | //做关键部分的事情 | 如果你的旗帜升起，请等到轮到我了（TRUE！） | | 4 | 2 | // Do Critical Section stuff | //做关键部分 - OOPS | ## 工作方案 ## 彼得森的解决方案是什么？ 彼得森在 1981 年的一篇 2 页的论文中发表了他的小说和令人惊讶的简单解决方案。他的算法的一个版本如下所示，使用共享变量`turn`： ``` \\ Candidate #5 raise my flag turn = your_id wait until your flag is lowered and turn is yourid // Do Critical Section stuff lower my flag ``` 该解决方案满足互斥，有界等待和进步。如果线程＃2 已设置为 2 并且当前位于关键部分内。线程＃1 到达，_ 将转回设置为 1_ ，现在等待直到线程 2 降低标志。 链接彼得森的原始文章 pdf： [G. L. Peterson：“关于互斥问题的神话”，信息处理快报 12（3）1981,115-116](http://dl.acm.org/citation.cfm?id=945527) ## 彼得森的解决方案是第一个解决方案吗？ 不，Dekkers 算法（1962）是第一个可证明正确的解决方案。该算法的一个版本如下。 ``` raise my flag while(your flag is raised) : if it's your turn to win : lower my flag wait while your turn raise my flag // Do Critical Section stuff set your turn to win lower my flag ``` 注意如果循环迭代为零，一次或多次，如何在临界区期间始终引发进程的标志。此外，该标志可以被解释为进入临界区的直接意图。只有当其他进程也引发了标志时，一个进程才会推迟，降低其意图标志并等待。 ## 我可以在 C 或汇编程序中实现 Peterson（或 Dekkers）算法吗？ 是的 - 通过一些搜索，即使在今天也可以在生产中找到特定的简单移动处理器：Peterson 的算法用于为 Tegra 移动处理器实现低级 Linux 内核锁（片上系统 ARM 处理和 Nvidia 的 GPU 核心） [https://android.googlesource.com/kernel/tegra.git/+/android-tegra-3.10/arch/arm/mach-tegra/sleep.S#58](https://android.googlesource.com/kernel/tegra.git/+/android-tegra-3.10/arch/arm/mach-tegra/sleep.S#58) 但是，通常，如果另一个核心更新共享变量，CPU 和 C 编译器可以重新排序 CPU 指令或使用过时的 CPU 核心本地缓存值。因此，对于大多数平台来说，简单的 C 代码伪代码实在太天真了。你现在可以停止阅读了。 哦......你决定继续读书。好吧，这里是龙！不要说我们没有警告你。考虑这个高级和粗糙的话题，但（剧透警报）一个快乐的结局。 考虑以下代码， ```c while(flag2 ) { /* busy loop - go around again */ ``` 一个有效的编译器会推断出`flag2`变量永远不会在循环内部发生变化，因此测试可以优化到`while(true)`使用`volatile`来防止这种编译器优化。 独立指令可以由优化编译器重新排序，或者在运行时由 CPU 进行无序执行优化。如果代码需要修改和检查变量以及精确的顺序，则进行这些复杂的优化。 相关的挑战是 CPU 核心包括用于存储最近读取或修改的主存储器值的数据高速缓存。修改后的值可能无法写回主存储器或立即从存储器重新读取。因此，在两个 CPU 代码之间可能不共享数据改变，例如上述示例中的标志和转弯变量的状态。 但结局很快乐。幸运的是，现代硬件使用“内存屏障”（也称为内存屏障）CPU 指令来解决这些问题，以确保主内存和 CPU 的缓存处于合理且连贯的状态。更高级别的同步原语（例如`pthread_mutex_lock`）将调用这些 CPU 指令作为其实现的一部分。因此，在实践中，使用互斥锁定和解锁调用的周围临界区域足以忽略这些较低级别的问题。 进一步阅读：我们建议以下网络帖子讨论在 x86 进程上实现 Peterson 的算法以及关于内存障碍的 linux 文档。 [http://bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/](http://bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/) [http://lxr.free-electrons.com/source /Documentation/memory-barriers.txt](http://lxr.free-electrons.com/source/Documentation/memory-barriers.txt) ## 硬件方案 ## 我们如何在硬件上实现关键部分问题？ 我们可以使用 C11 Atomics 完美地完成这项工作！这里详细介绍了一个完整的解决方案（这是一个自旋锁互斥， [futex](https://locklessinc.com/articles/mutex_cv_futex/) 实现可以在网上找到）。 ```c typedef struct mutex_{ atomic_int_least8_t lock; pthread_t owner; } mutex; #define UNLOCKED 0 #define LOCKED 1 #define UNASSIGNED_OWNER 0 int mutex_init(mutex* mtx){ if(!mtx){ return 0; } atomic_init(&mtx->lock, UNLOCKED); // Not thread safe the user has to take care of this mtx->owner = UNASSIGNED_OWNER; return 1; } ``` 这是初始化代码，这里没什么特别的。我们将互斥锁的状态设置为已解锁并将所有者设置为已锁定。 ```c int mutex_lock(mutex* mtx){ int_least8_t zero = UNLOCKED; while(!atomic_compare_exchange_weak_explicit (&mtx->lock, &zero, LOCKED, memory_order_relaxed, memory_order_relaxed)){ zero = UNLOCKED; sched_yield(); //Use system calls for scheduling speed } //We have the lock now!!!! mtx->owner = pthread_self(); return 1; } ``` 哎呀！这段代码有什么作用？好吧，启动它初始化一个我们将保持为解锁状态的变量。 [原子比较和交换](https://en.wikipedia.org/wiki/Compare-and-swap)是大多数现代架构支持的指令（在 x86 上它是`lock cmpxchg`）。此操作的伪代码如下所示 ```c int atomic_compare_exchange_pseudo(int* addr1, int* addr2, int val){ if(*addr1 == *addr2){ *addr1 = val; return 1; }else{ *addr2 = *addr1; return 0; } } ``` 除了全部完成 _ 原子 _ 意味着在一个不间断的操作中。 _ 弱 _ 部分意味着什么？原子指令也容易出现**虚假失败**意味着这些原子函数有两个版本 _ 强 _ 和 _ 弱 _ 部分，强有力保证成功或失败而弱者可能会失败。我们使用弱，因为弱更快，我们处于循环中！这意味着如果它经常失败，我们就可以了，因为无论如何我们都会继续旋转。 这个记忆订单业务是什么？我们之前讨论的是记忆围栏，现在就是这样！我们不会详细说明，因为它超出了本课程的范围，而不是本文 [的范围。](https://gcc.gnu.org/wiki/Atomic/GCCMM/AtomicSync) 在 while 循环中，我们未能抓住锁！我们将零重置为解锁并暂停一会儿。当我们醒来时，我们试图再次抓住锁。一旦我们成功交换，我们就处于关键部分！我们将互斥锁的所有者设置为解锁方法的当前线程并返回成功。 这如何保证互斥，在使用原子时我们并不完全确定！但是在这个简单的例子中我们可以因为能够成功地期望锁定为 UNLOCKED（0）并将其交换为 LOCKED（1）状态的线程被认为是赢家。我们如何实施解锁？ ```c int mutex_unlock(mutex* mtx){ if(unlikely(pthread_self() != mtx->owner)){ return 0; //You can't unlock a mutex if you aren't the owner } int_least8_t one = 1; //Critical section ends after this atomic mtx->owner = UNASSIGNED_OWNER; if(!atomic_compare_exchange_strong_explicit( &mtx->lock, &one, UNLOCKED, memory_order_relaxed, memory_order_relaxed)){ //The mutex was never locked in the first place return 0; } return 1; } ``` 为了满足 api，你不能解锁互斥锁，除非你是拥有它的人。然后我们取消分配互斥锁所有者，因为关键部分在原子之后结束了。我们想要一个强大的交换，因为我们不想阻止（pthread_mutex_unlock 不会阻塞）。我们希望锁定互斥锁，然后将其交换为解锁。如果交换成功，我们解锁互斥锁。如果交换不是，这意味着互斥锁已解锁，我们尝试将其从 UNLOCKED 切换到 UNLOCKED，从而保持解锁的非阻塞。