共计 8781 个字符，预计需要花费 22 分钟才能阅读完成。
前言
先来看看虚构的小故事
曾经早晨 11 点了，程序员小明的双手还在键盘上飞舞着，眼神仍然凝视着的电脑屏幕。
没方法这段时间公司业绩增长中，需要天然也多了起来，加班天然也少不了。
天气变化莫测，这时窗外下起了蓬勃大雨，同时闪电轰鸣。
但这一丝都没有影响到小明，始料未及，忽然一道微小的雷一闪而过，办公楼就这么停电了，随后整栋楼都在回荡着的小明那一声撕心裂肺的「卧槽」。
此时，求小明的心里面积有多大？
等小明心里平复后，忽然肚子十分的痛，想上厕所，小明心想必定是早晨吃的某堡王有问题。
整栋楼都停了电，小明两眼一抹黑，啥都看不见，只能靠摸墙的办法，一步一步的来到了厕所门口。
到了厕所（共享资源），因为切实太急，小明间接冲入了厕所里，用手摸索着刚好第一个门没锁门，便夺门而入。
这就荒谬了，这个门外面正好小红在上着厕所，正好这个厕所门是坏了的，没方法锁门。
光明中，小红尽管看不见，但靠着声音，发现自己背后的这扇门有动静，感觉不对劲，于是铆足了力量，用她衣着高跟鞋脚，使劲地一脚踢了过来。
小明很侥幸，被踢中了「命根子」，撕心裂肺地喊出了一个字「痛」！
故事说完了，扯了那么多，实际上是为了阐明，对于共享资源，如果没有上锁，在多线程的环境里，那么就可能会产生翻车现场。
接下来，用 30+ 张图，带大家走进操作系统中防止多线程资源竞争的 互斥、同步 的办法。
注释
竞争与合作
在单核 CPU 零碎里，为了实现多个程序同时运行的假象，操作系统通常以工夫片调度的形式，让每个过程执行每次执行一个工夫片，工夫片用完了，就切换下一个过程运行，因为这个工夫片的工夫很短，于是就造成了「并发」的景象。
另外，操作系统也为每个过程创立微小、公有的虚拟内存的假象，这种地址空间的形象让每个程序如同领有本人的内存，而实际上操作系统在背地机密地让多个地址空间「复用」物理内存或者磁盘。
如果一个程序只有一个执行流程，也代表它是单线程的。当然一个程序能够有多个执行流程，也就是所谓的多线程程序，线程是调度的根本单位，过程则是资源分配的根本单位。
所以，线程之间是能够共享过程的资源，比方代码段、堆空间、数据段、关上的文件等资源，但每个线程都有本人独立的栈空间。
那么问题就来了，多个线程如果竞争共享资源，如果不采取有效的措施，则会造成共享数据的凌乱。
咱们做个小试验，创立两个线程，它们别离对共享变量 i 自增 1 执行 10000 次，如下代码（尽管说是 C++ 代码，然而没学过 C++ 的同学也是看到懂的）：
按理来说，i 变量最初的值应该是 20000，但很可怜，并不是如此。咱们对下面的程序执行一下：
运行了两次，发现呈现了 i 值的后果是 15173，也会呈现 20000 的 i 值后果。
每次运行岂但会产生谬误，而且失去不同的后果。在计算机里是不能容忍的，尽管是小概率呈现的谬误，然而小概率事件它肯定是会产生的，「墨菲定律」大家都懂吧。
为什么会产生这种状况？
为了了解为什么会产生这种状况，咱们必须理解编译器为更新计数器 i 变量生成的代码序列，也就是要理解汇编指令的执行程序。
在这个例子中，咱们只是想给 i 加上数字 1，那么它对应的汇编指令执行过程是这样的：
能够发现，只是单纯给 i 加上数字 1，在 CPU 运行的时候，实际上要执行 3 条指令。
构想咱们的线程 1 进入这个代码区域，它将 i 的值（假如此时是 50）从内存加载到它的寄存器中，而后它向寄存器加 1，此时在寄存器中的 i 值是 51。
当初，一件可怜的事件产生了：时钟中断产生。因而，操作系统将以后正在运行的线程的状态保留到线程的线程管制块 TCP。
当初更糟的事件产生了，线程 2 被调度运行，并进入同一段代码。它也执行了第一条指令，从内存获取 i 值并将其放入到寄存器中，此时内存中 i 的值仍为 50，因而线程 2 寄存器中的 i 值也是 50。假如线程 2 执行接下来的两条指令，将寄存器中的 i 值 + 1，而后将寄存器中的 i 值保留到内存中，于是此时全局变量 i 值是 51。
最初，又产生一次上下文切换，线程 1 复原执行。还记得它曾经执行了两条汇编指令，当初筹备执行最初一条指令。回顾一下，线程 1 寄存器中的 i 值是 51，因而，执行最初一条指令后，将值保留到内存，全局变量 i 的值再次被设置为 51。
简略来说，减少 i（值为 50）的代码被运行两次，按理来说，最初的 i 值应该是 52，然而因为 不可控的调度，导致最初 i 值却是 51。
针对下面线程 1 和线程 2 的执行过程，我画了一张流程图，会更明确一些：
互斥的概念
下面展现的状况称为 竞争条件（_race condition_），当多线程相互竞争操作共享变量时，因为运气不好，即在执行过程中产生了上下文切换，咱们失去了谬误的后果，事实上，每次运行都可能失去不同的后果，因而输入的后果存在 不确定性（_indeterminate_）。
因为多线程执行操作共享变量的这段代码可能会导致竞争状态，因而咱们将此段代码称为 临界区（_critical section_），它是访问共享资源的代码片段，肯定不能给多线程同时执行。
咱们心愿这段代码是 互斥（_mutualexclusion_）的，也就说保障一个线程在临界区执行时，其余线程应该被阻止进入临界区，说白了，就是这段代码执行过程中，最多只能呈现一个线程。
另外，说一下互斥也并不是只针对多线程。在多过程竞争共享资源的时候，也同样是能够应用互斥的形式来防止资源竞争造成的资源凌乱。
同步的概念
互斥解决了并发过程 / 线程对临界区的应用问题。这种基于临界区管制的交互作用是比较简单的，只有一个过程 / 线程进入了临界区，其余试图想进入临界区的过程 / 线程都会被阻塞着，直到第一个过程 / 线程来到了临界区。
咱们都晓得在多线程里，每个线程并肯定是程序执行的，它们根本是以各自独立的、不可预知的速度向前推动，但有时候咱们又心愿多个线程能密切合作，以实现一个独特的工作。
例子，线程 1 是负责读入数据的，而线程 2 是负责解决数据的，这两个线程是相互合作、相互依赖的。线程 2 在没有收到线程 1 的唤醒告诉时，就会始终阻塞期待，当线程 1 读完数据须要把数据传给线程 2 时，线程 1 会唤醒线程 2，并把数据交给线程 2 解决。
所谓同步，就是并发过程 / 线程在一些关键点上可能须要相互期待与互通音讯，这种互相制约的期待与互通信息称为过程 / 线程同步。
举个生存的同步例子，你肚子饿了想要吃饭，你叫妈妈早点做菜，妈妈听到后就开始做菜，然而在妈妈没有做完饭之前，你必须阻塞期待，等妈妈做完饭后，天然会告诉你，接着你吃饭的事件就能够进行了。
留神，同步与互斥是两种不同的概念：
- 同步就好比：「操作 A 应在操作 B 之前执行」，「操作 C 必须在操作 A 和操作 B 都实现之后能力执行」等；
- 互斥就好比：「操作 A 和操作 B 不能在同一时刻执行」；
- *
互斥与同步的实现和应用
在过程 / 线程并发执行的过程中，过程 / 线程之间存在合作的关系，例如有互斥、同步的关系。
为了实现过程 / 线程间正确的合作，操作系统必须提供实现过程合作的措施和办法，次要的办法有两种：
- _锁_：加锁、解锁操作；
- _信号量_：P、V 操作；
这两个都能够不便地实现过程 / 线程互斥，而信号量比锁的性能更强一些，它还能够不便地实现过程 / 线程同步。
锁
应用加锁操作和解锁操作能够解决并发线程 / 过程的互斥问题。
任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可进入临界区；在实现对临界资源的拜访后再执行解锁操作，以开释该临界资源。
依据锁的实现不同，能够分为「忙期待锁」和「无忙期待锁」。
咱们先来看看「忙期待锁」的实现
在阐明「忙期待锁」的实现之前，先介绍古代 CPU 体系结构提供的非凡 原子操作指令 —— 测试和置位（_Test-and-Set_）指令。
如果用 C 代码示意 Test-and-Set 指令，模式如下：
测试并设置指令做了下述事件:
- 把
old_ptr更新为new的新值 - 返回
old_ptr的旧值；
当然，要害是这些代码是原子执行。因为既能够测试旧值，又能够设置新值，所以咱们把这条指令叫作「测试并设置」。
那什么是原子操作呢？原子操作就是要么全副执行，要么都不执行，不能呈现执行到一半的中间状态
咱们能够使用 Test-and-Set 指令来实现「忙期待锁」，代码如下：
咱们来确保了解为什么这个锁能工作：
- 第一个场景是，首先假如一个线程在运行，调用
lock()，没有其余线程持有锁，所以flag是 0。当调用TestAndSet(flag, 1)办法，返回 0，线程会跳出 while 循环，获取锁。同时也会原子的设置 flag 为 1，标记锁曾经被持有。当线程来到临界区，调用unlock()将flag清理为 0。 - 第二种场景是，当某一个线程曾经持有锁（即
flag为 1）。本线程调用lock()，而后调用TestAndSet(flag, 1)，这一次返回 1。只有另一个线程始终持有锁，TestAndSet()会反复返回 1，本线程会始终 忙等。当flag终于被改为 0，本线程会调用TestAndSet()，返回 0 并且原子地设置为 1，从而取得锁，进入临界区。
很显著，当获取不到锁时，线程就会始终 wile 循环，不做任何事件，所以就被称为「忙期待锁」，也被称为 自旋锁（_spin lock_）。
这是最简略的一种锁，始终自旋，利用 CPU 周期，直到锁可用。在单处理器上，须要抢占式的调度器（即一直通过时钟中断一个线程，运行其余线程）。否则，自旋锁在单 CPU 上无奈应用，因为一个自旋的线程永远不会放弃 CPU。
再来看看「无期待锁」的实现
无期待锁顾明思议就是获取不到锁的时候，不必自旋。
既然不想自旋，那当没获取到锁的时候，就把以后线程放入到锁的期待队列，而后执行调度程序，把 CPU 让给其余线程执行。
本次只是提出了两种简略锁的实现形式。当然，在具体操作系统实现中，会更简单，但也离不开本例子两个根本元素。
如果你想要对锁的更进一步了解，举荐大家能够看《操作系统导论》第 28 章锁的内容，这本书在「微信读书」就能够收费看。
信号量
信号量是操作系统提供的一种协调共享资源拜访的办法。
通常 信号量示意资源的数量，对应的变量是一个整型（sem）变量。
另外，还有 两个原子操作的零碎调用函数来管制信号量的，别离是：
- _P 操作_：将
sem减1，相减后，如果sem < 0，则过程 / 线程进入阻塞期待，否则持续，表明 P 操作可能会阻塞； - _V 操作_：将
sem加1，相加后，如果sem <= 0，唤醒一个期待中的过程 / 线程，表明 V 操作不会阻塞；
P 操作是用在进入临界区之前，V 操作是用在来到临界区之后，这两个操作是必须成对呈现的。
举个类比，2 个资源的信号量，相当于 2 条火车轨道，PV 操作如下图过程：
操作系统是如何实现 PV 操作的呢？
信号量数据结构与 PV 操作的算法形容如下图：
PV 操作的函数是由操作系统治理和实现的，所以操作系统曾经使得执行 PV 函数时是具备原子性的。
PV 操作如何应用的呢？
信号量不仅能够实现临界区的互斥访问控制，还能够线程间的事件同步。
咱们先来说说如何应用 信号量实现临界区的互斥拜访。
为每类共享资源设置一个信号量 s，其初值为 1，示意该临界资源未被占用。
只有把进入临界区的操作置于 P(s) 和 V(s) 之间，即可实现过程 / 线程互斥：
此时，任何想进入临界区的线程，必先在互斥信号量上执行 P 操作，在实现对临界资源的拜访后再执行 V 操作。因为互斥信号量的初始值为 1，故在第一个线程执行 P 操作后 s 值变为 0，示意临界资源为闲暇，可调配给该线程，使之进入临界区。
若此时又有第二个线程想进入临界区，也应先执行 P 操作，后果使 s 变为负值，这就意味着临界资源已被占用，因而，第二个线程被阻塞。
并且，直到第一个线程执行 V 操作，开释临界资源而复原 s 值为 0 后，才唤醒第二个线程，使之进入临界区，待它实现临界资源的拜访后，又执行 V 操作，使 s 复原到初始值 1。
对于两个并发线程，互斥信号量的值仅取 1、0 和 -1 三个值，别离示意：
- 如果互斥信号量为 1，示意没有线程进入临界区；
- 如果互斥信号量为 0，示意有一个线程进入临界区；
- 如果互斥信号量为 -1，示意一个线程进入临界区，另一个线程期待进入。
通过互斥信号量的形式，就能保障临界区任何时刻只有一个线程在执行，就达到了互斥的成果。
再来，咱们说说如何应用 信号量实现事件同步。
同步的形式是设置一个信号量，其初值为 0。
咱们把后面的「吃饭 - 做饭」同步的例子，用代码的形式实现一下：
妈妈一开始询问儿子要不要做饭时，执行的是 P(s1)，相当于询问儿子需不需要吃饭，因为 s1 初始值为 0，此时 s1 变成 -1，表明儿子不须要吃饭，所以妈妈线程就进入期待状态。
当儿子肚子饿时，执行了 V(s1)，使得 s1 信号量从 -1 变成 0，表明此时儿子须要吃饭了，于是就唤醒了阻塞中的妈妈线程，妈妈线程就开始做饭。
接着，儿子线程执行了 P(s2)，相当于询问妈妈饭做完了吗，因为 s2 初始值是 0，则此时 s2 变成 -1，阐明妈妈还没做完饭，儿子线程就期待状态。
最初，妈妈终于做完饭了，于是执行 V(s2)，s2 信号量从 -1 变回了 0，于是就唤醒期待中的儿子线程，唤醒后，儿子线程就能够进行吃饭了。
生产者 - 消费者问题
生产者 - 消费者问题形容：
- 生产者 在生成数据后，放在一个缓冲区中；
- 消费者 从缓冲区取出数据处理；
- 任何时刻，只能有一个 生产者或消费者能够拜访缓冲区；
咱们对问题剖析能够得出：
- 任何时刻只能有一个线程操作缓冲区，阐明操作缓冲区是临界代码，须要互斥；
- 缓冲区空时，消费者必须期待生产者生成数据；缓冲区满时，生产者必须期待消费者取出数据。阐明生产者和消费者 须要同步。
那么咱们须要三个信号量，别离是：
- 互斥信号量
mutex：用于互斥拜访缓冲区，初始化值为 1； - 资源信号量
fullBuffers：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）； - 资源信号量
emptyBuffers：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n（缓冲区大小）；
具体的实现代码：
如果消费者线程一开始执行 P(fullBuffers)，因为信号量 fullBuffers 初始值为 0，则此时 fullBuffers 的值从 0 变为 -1，阐明缓冲区里没有数据，消费者只能期待。
接着，轮到生产者执行 P(emptyBuffers)，示意缩小 1 个空槽，如果以后没有其余生产者线程在临界区执行代码，那么该生产者线程就能够把数据放到缓冲区，放完后，执行 V(fullBuffers)，信号量 fullBuffers 从 -1 变成 0，表明有「消费者」线程正在阻塞期待数据，于是阻塞期待的消费者线程会被唤醒。
消费者线程被唤醒后，如果此时没有其余消费者线程在读数据，那么就能够间接进入临界区，从缓冲区读取数据。最初，来到临界区后，把空槽的个数 + 1。
经典同步问题
哲学家就餐问题
当初我在校招的时候，面试官也问过「哲学家就餐」这道题目，我过后听的一脸懵逼，无论面试官怎么讲述这个问题，我也始终没听懂，就莫名其妙的说这个问题会「死锁」。
当然，我这答复槽透了，所以当场 game over，残暴又悲惨故事，就不多说了，反正过后菜就是菜。
时至今日，看我来图解这道题。
先来看看哲学家就餐的问题形容：
5个老大哥哲学家，闲着没事做，围绕着一张圆桌吃面；- 巧就巧在，这个桌子只有
5支叉子，每两个哲学家之间放一支叉子； - 哲学家围在一起先思考，思考中途饿了就会想进餐；
- 奇葩的是，这些哲学家要两支叉子才违心吃面，也就是须要拿到左右两边的叉子才进餐；
- 吃完后，会把两支叉子放回原处，持续思考；
那么问题来了，如何保障哲 学家们的动作有序进行，而不会呈现有人永远拿不到叉子呢？
计划一
咱们用信号量的形式，也就是 PV 操作来尝试解决它，代码如下：
下面的程序，好似很天然。拿起叉子用 P 操作，代表有叉子就间接用，没有叉子时就期待其余哲学家放回叉子。
不过，这种解法存在一个极其的问题：假如五位哲学家同时拿起右边的叉子，桌面上就没有叉子了，这样就没有人可能拿到他们左边的叉子，也就说每一位哲学家都会在 P(fork[(i + 1) % N ]) 这条语句阻塞了，很显著这产生了死锁的景象。
计划二
既然「计划一」会产生同时竞争右边叉子导致死锁的景象，那么咱们就在拿叉子前，加个互斥信号量，代码如下：
下面程序中的互斥信号量的作用就在于，只有有一个哲学家进入了「临界区」，也就是筹备要拿叉子时，其余哲学家都不能动，只有这位哲学家用完叉子了，能力轮到下一个哲学家进餐。
计划二尽管能让哲学家们按程序吃饭，然而每次进餐只能有一位哲学家，而桌面上是有 5 把叉子，按情理是能能够有两个哲学家同时进餐的，所以从效率角度上，这不是最好的解决方案。
计划三
那既然计划二应用互斥信号量，会导致只能容许一个哲学家就餐，那么咱们就不必它。
另外，计划一的问题在于，会呈现所有哲学家同时拿右边刀叉的可能性，那咱们就防止哲学家能够同时拿右边的刀叉，采纳分支构造，依据哲学家的编号的不同，而采取不同的动作。
即让偶数编号的哲学家「先拿右边的叉子后拿左边的叉子」，奇数编号的哲学家「先拿左边的叉子后拿右边的叉子」。
下面的程序，在 P 操作时，依据哲学家的编号不同，拿起左右两边叉子的程序不同。另外，V 操作是不须要分支的，因为 V 操作是不会阻塞的。
计划三即不会呈现死锁，也能够两人同时进餐。
计划四
在这里再提出另外一种可行的解决方案，咱们 用一个数组 state 来记录每一位哲学家在过程、思考还是饥饿状态（正在试图拿叉子）。
那么，一个哲学家只有在两个街坊都没有进餐时，才能够进入进餐状态。
第 i 个哲学家的左邻右舍，则由宏 LEFT 和 RIGHT 定义：
- LEFT : (i + 5 – 1) % 5
- RIGHT : (i + 1) % 5
比方 i 为 2，则 LEFT 为 1，RIGHT 为 3。
具体代码实现如下：
下面的程序应用了一个信号量数组，每个信号量对应一位哲学家，这样在所需的叉子被占用时，想进餐的哲学家就被阻塞。
留神，每个过程 / 线程将 smart_person 函数作为主代码运行，而其余 take_forks、put_forks 和 test 只是一般的函数，而非独自的过程 / 线程。
计划四同样不会呈现死锁，也能够两人同时进餐。
读者 - 写者问题
后面的「哲学家进餐问题」对于互斥拜访无限的竞争问题（如 I/O 设施）一类的建模过程非常有用。
另外，还有个驰名的问题是「读者 - 写者」，它为数据库拜访建设了一个模型。
读者只会读取数据，不会批改数据，而写者即能够读也能够批改数据。
读者 - 写者的问题形容：
- 「读 - 读」容许：同一时刻，容许多个读者同时读
- 「读 - 写」互斥：没有写者时读者能力读，没有读者时写者能力写
- 「写 - 写」互斥：没有其余写者时，写者能力写
接下来，提出几个解决方案来剖析剖析。
计划一
应用信号量的形式来尝试解决：
- 信号量
wMutex：管制写操作的互斥信号量，初始值为 1； - 读者计数
rCount：正在进行读操作的读者个数，初始化为 0； - 信号量
rCountMutex：管制对 rCount 读者计数器的互斥批改，初始值为 1；
接下来看看代码的实现：
下面的这种实现，是读者优先的策略，因为只有有读者正在读的状态，起初的读者都能够间接进入，如果读者继续一直进入，则写者会处于饥饿状态。
计划二
那既然有读者优先策略，天然也有写者优先策略：
- 只有有写者筹备要写入，写者应尽快执行写操作，起初的读者就必须阻塞；
- 如果有写者继续一直写入，则读者就处于饥饿；
在计划一的根底上新增如下变量：
- 信号量
rMutex：管制读者进入的互斥信号量，初始值为 1； - 信号量
wDataMutex：管制写者写操作的互斥信号量，初始值为 1； - 写者计数
wCount：记录写者数量，初始值为 0； - 信号量
wCountMutex：管制 wCount 互斥批改，初始值为 1；
具体实现如下代码：
留神，这里 rMutex 的作用，开始有多个读者读数据，它们全副进入读者队列，此时来了一个写者，执行了 P(rMutex) 之后，后续的读者因为阻塞在 rMutex 上，都不能再进入读者队列，而写者到来，则能够全副进入写者队列，因而保障了写者优先。
同时，第一个写者执行了 P(rMutex) 之后，也不能马上开始写，必须等到所有进入读者队列的读者都执行完读操作，通过 V(wDataMutex) 唤醒写者的写操作。
计划三
既然读者优先策略和写者优先策略都会造成饥饿的景象，那么咱们就来实现一下偏心策略。
偏心策略：
- 优先级雷同；
- 写者、读者互斥拜访；
- 只能一个写者拜访临界区；
- 能够有多个读者同时拜访临街资源；
具体代码实现：
看完代码不知你是否有这样的疑难，为什么加了一个信号量 flag，就实现了公平竞争？
比照计划一的读者优先策略，能够发现，读者优先中只有后续有读者达到，读者就能够进入读者队列，而写者必须期待，直到没有读者达到。
没有读者达到会导致读者队列为空，即 rCount==0，此时写者才能够进入临界区执行写操作。
而这里 flag 的作用就是阻止读者的这种非凡权限（非凡权限是只有读者达到，就能够进入读者队列）。
比方：开始来了一些读者读数据，它们全副进入读者队列，此时来了一个写者，执行 P(falg) 操作，使得后续到来的读者都阻塞在 flag 上，不能进入读者队列，这会使得读者队列逐步为空，即 rCount 减为 0。
这个写者也不能立马开始写（因为此时读者队列不为空），会阻塞在信号量 wDataMutex 上，读者队列中的读者全副读取完结后，最初一个读者过程执行 V(wDataMutex)，唤醒方才的写者，写者则持续开始进行写操作。
唠叨唠叨
不负众望，小林又迁延了，又没有达到「周更」，羞愧羞愧，预计很多读者都快遗记小林是谁了，小林求求大家不要取关呀！
是的，就在上上周，大好的周末，小林偷懒了，重温了两天的「七龙珠 Z」动漫，看的的确很爽啊，尽管曾经看过很多遍了，谁叫我是龙珠迷。
没方法这就是生存，时而松时而紧。
小林是专为大家图解的工具人，Goodbye，咱们下次见！
好文举荐：
过程和线程基础知识全家桶，30 张图一套带走
20 张图揭开内存治理的迷雾，霎时恍然大悟
