1. 互斥与同步⚓
1.1 竞争与协作⚓
1.1.1 互斥的概念⚓
由于多线程执行操作共享变量的这段代码可能会导致竞争状态，因此我们将此段代码称为临界区（critical section），它是访问共享资源的代码片段，一定不能给多线程同时执行。
互斥（mutualexclusion），保证一个线程在临界区执行时，其他线程应该被阻止进入临界区。
1.1.2 同步的概念⚓
同步，就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。
1.2 互斥与同步的实现和使用⚓
为了实现进程/线程间正确的协作，操作系统必须提供实现进程协作的措施和方法，主要的方法有两种：
- 锁：加锁、解锁操作；
- 信号量：P、V 操作；
这两个都可以方便地实现进程/线程互斥，而信号量比锁的功能更强一些，它还可以方便地实现进程/线程同步。
下文的实现都是简单的演示。
1.2.1 锁⚓
使用加锁操作和解锁操作可以解决并发线程/进程的互斥问题。
任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可进入临界区；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。
根据锁的实现不同，可以分为「忙等待锁」和「无忙等待锁」。
1.2.1.1 测试和置位指令⚓
在说明「忙等待锁」的实现之前，先介绍现代 CPU 体系结构提供的特殊原子操作指令 —— 测试和置位（Test-and-Set）指令。
用 C 代码表示 Test-and-Set 指令的形式如下：
- 把 old_ptr 更新为 new 的新值
- 返回 old_ptr 的旧值；
关键是这些代码是原子执行。因为既可以测试旧值，又可以设置新值，所以我们把这条指令叫作「测试并设置」。
原子操作就是要么全部执行，要么都不执行，不能出现执行到一半的中间状态。
1.2.1.2 忙等待锁（自旋锁）⚓
用 Test-and-Set 指令实现的忙等待锁：
当某一个线程已经持有锁（即 flag 为 1）。本线程调用 lock()，然后调用 TestAndSet(flag, 1)，只要另一个线程一直持有锁，TestAndSet() 会重复返回 1，本线程会一直忙等。当 flag 终于被改为 0，本线程会调用 TestAndSet()，返回 0 并且原子地设置为 1，从而获得锁，进入临界区。
当获取不到锁时，线程就会一直 while 循环，不做任何事情，所以就被称为「忙等待锁」，也被称为自旋锁（spin lock）。
在单处理器上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。
1.2.1.3 无等待锁⚓
不自旋，当没获取到锁的时候，就把当前线程放入到锁的等待队列，然后执行调度程序，把 CPU 让给其他线程执行。
推荐：《操作系统导论》第 28 章锁。
1.2.2 信号量⚓
原理就是 P、V 操作，可以参考前文 《进程间的通信方式》。
信号量数据结构与 PV 操作的算法描述如下图：
PV 操作的函数是由操作系统管理和实现的，所以操作系统已经使得执行 PV 函数时是具有原子性的。
1.2.3 生产者 - 消费者问题⚓
生产者 - 消费者问题描述：
- 生产者在生成数据后，放在一个缓冲区中；
- 消费者从缓冲区取出数据处理；
- 任何时刻，只能有一个生产者或消费者可以访问缓冲区；
需要三个信号量，分别是：
- 互斥信号量 mutex：用于互斥访问缓冲区，初始化值为 1；
- 资源信号量 fullBuffers：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）；
- 资源信号量 emptyBuffers：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n（缓冲区大小）；
1.3 经典同步问题⚓
1.3.1 哲学家就餐⚓
问题描述：
- 5 个老大哥哲学家，闲着没事做，围绕着一张圆桌吃面；
- 巧就巧在，这个桌子只有 5 支叉子，每两个哲学家之间放一支叉子；
- 哲学家围在一起先思考，思考中途饿了就会想进餐；
- 奇葩的是，这些哲学家要两支叉子才愿意吃面，也就是需要拿到左右两边的叉子才进餐；
- 吃完后，会把两支叉子放回原处，继续思考；
如何保证哲 学家们的动作有序进行，而不会出现有人永远拿不到叉子呢？
1.3.1.1 方案一⚓
这种解法存在一个极端的问题：假设五位哲学家同时拿起左边的叉子，桌面上就没有叉子了， 这样就没有人能够拿到他们右边的叉子，也就说每一位哲学家都会在 P(fork[(i + 1) % N ]) 这条语句阻塞了，很明显这发生了死锁的现象。
1.3.1.2 方案二⚓
既然「方案一」会发生同时竞争左边叉子导致死锁的现象，那么我们就在拿叉子前，加个互斥信号量，代码如下：
方案二虽然能让哲学家们按顺序吃饭，但是每次进餐只能有一位哲学家，而桌面上是有 5 把叉子，按道理是能可以有两个哲学家同时进餐的，所以从效率角度上，这不是最好的解决方案。
1.3.1.3 方案三⚓
避免哲学家可以同时拿左边的刀叉，采用分支结构，根据哲学家的编号的不同，而采取不同的动作。
即让偶数编号的哲学家「先拿左边的叉子后拿右边的叉子」，奇数编号的哲学家「先拿右边的叉子后拿左边的叉子」。
V 操作是不需要分支的，因为 V 操作是不会阻塞的。
方案三既不会出现死锁，也可以两人同时进餐。
1.3.1.4 方案四⚓
另外一种可行的解决方案，我们用一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态（正在试图拿叉子）。
那么，一个哲学家只有在两个邻居都没有进餐时，才可以进入进餐状态。
方案四同样不会出现死锁，也可以两人同时进餐。
1.3.2 读者 - 写者问题⚓
问题描述：
- 「读 - 读」允许：同一时刻，允许多个读者同时读
- 「读 - 写」互斥：没有写者时读者才能读，没有读者时写者才能写
- 「写 - 写」互斥：没有其他写者时，写者才能写
1.3.2.1 方案一⚓
读者优先策略：
- 只要有读者正在读的状态，后来的读者都可以直接进入，
- 如果读者持续不断进入，则写者会处于饥饿状态。
1.3.2.2 方案二⚓
写者优先策略：
- 只要有写者准备要写入，写者应尽快执行写操作，后来的读者就必须阻塞；
- 如果有写者持续不断写入，则读者就处于饥饿状态；
注意，这里 rMutex 的作用，开始有多个读者读数据，它们全部进入读者队列，此时来了一个写者，执行了 P(rMutex) 之后，后续的读者由于阻塞在 rMutex 上，都不能再进入读者队列，而写者到来，则可以全部进入写者队列，因此保证了写者优先。
同时，第一个写者执行了 P(rMutex) 之后，也不能马上开始写，必须等到所有进入读者队列的读者都执行完读操作，通过 V(wDataMutex) 唤醒写者的写操作。
1.3.2.3 方案三⚓
公平策略：
- 优先级相同；
- 写者、读者互斥访问；
- 只能一个写者访问临界区；
- 可以有多个读者同时访问临界资源；
开始来了一些读者读数据，它们全部进入读者队列，此时来了一个写者，执行 P(flag) 操作，使得后续到来的读者都阻塞在 flag 上，不能进入读者队列，这会使得读者队列逐渐为空，即 rCount 减为 0。
这个写者也不能立马开始写（因为此时读者队列不为空），会阻塞在信号量 wDataMutex 上，读者队列中的读者全部读取结束后，最后一个读者进程执行 V(wDataMutex)，唤醒刚才的写者，写者则继续开始进行写操作。