一些概念
竞态条件（Race Conditions）
在一些操作系统中，一起协同工作的进程可能共享一块存储空间，任何一个进程可以读或者写这个存储空间。这个存储空间可以是内存中的一块区域，也可以是文件系统中的一个文件。
举个例子，在多任务打印缓存处理器（print spooler）的工作场景中，当一个进程希望打印一个文件时，它会将这个文件的名称输入到一个特定的缓存处理器目录（spooler directory）中。打印机守护进程（printer daemon）会周期性地检查缓存处理器目录中是否存在任何文件名，当存在时，则打印他们，并且将这个文件名从目录中移除。
假设这个缓存处理器目录可以容纳无限个文件名，文件名索引从0开始。同时，有两个共享变量，out表示下一个需要打印的文件的索引，而in表示下一个在目录中的空位索引。这两个共享变量存储在一个文件中，这个文件可以被任何的进程所访问。
在某一时刻，空位0到3位空（这意味着这四个文件已经被打印了），空位4到6不为空（这意味着这三个文件等待着被打印）。此时，进程A和进程B都分别想添加一个文件到目录中。
进程 A 读取 in 的值（值为7），并存储到本地变量 next_free_slot 中。此时，正好进程 A 用完了它的CPU时间片，于是进程调度器将 CPU 让给进程 B 。进程 B 也读取 in 的值（值为7），并也存储到本地变量 next_free_slot 中。
进程 B 继续运行，它将要打印文件的名称存储到目录的索引为 7 的空位中，并且更新 in 的值为 8 ，此后它去执行去其他任务。
最终，当又轮到了进程 A 继续执行时，它要打印文件的名称存储到目录的索引为 7 的空位中，这个操作会抹去进程 B 之前存储在那里的文件名。紧接着，进程 A 更新 in 的值为 8 。
对于缓存处理器目录而言，整个过程始终是保持一致的，因此打印机守护进程不会提示任何错误。然而，进程 B 提交的打印任务始终不会被执行。
像这种两个以上的进程同时向共享存储区读取并且写入数据，而执行结果不可预知的情况称为竞态条件（Race Conditions），而这个共享存储区就是竞态资源（Race Resources）。
调试包含竞态条件的代码并不能解决这个问题，因为在绝大部分情况下，包含竞态条件的代码都会正常工作（体现为按预期工作），然而在运行的次数很多时，我们会得到一些奇怪的数据。
临界区（Critical Regions/ Critical Sections）
为了避免竞态条件（Race Conditions），我们必须通过一个机制来阻止多个进程同时读取和写入一个竞态资源（共享数据区）。**互斥（mutual exclusion）**是一种解决办法，即当一个进程读写竞态资源（共享数据区）时，互斥机制会拒绝另外的进程读写这个竞态资源。
上面例子的问题就出在当进程 A 还没有完成对竞态资源（缓存处理器目录）的读写时，进程 B 也同时对这个竞态资源进行读写。
而访问竞态资源（共享数据区）的代码片段，就是临界区（Critical Regions/ Critical Sections）。
如果我们可以阻止多个进程同时进入临界区，就可以避免竞态条件（Race Conditions）。
我们用一个例子来说明多个进程进入临界区的情况。
- 在 T1 时刻，进程 A 进入临界区；
- 稍后，在 T2 时刻，进程 B 尝试进入临界区，但是失败了，因为在任一时刻我们只允许有最多一个进程处于临界区；
- 因此，进程 B 只能被临时挂起；
- 在 T3 时刻，进程 A 离开临界区，进程 B 收到通知最终进入临界区；
- 在 T4 时刻，进程 B 离开临界区。
忙等待下的互斥（Mutual Exclusion with Busy-waiting）
在下文中，我们来讨论基于忙等待（busy-waiting）实现互斥（Mutual Exclusion）的不同方案。
禁止中断（Disabling Interrupts）
在单处理器系统（single-processor）中，最简单的方法就是当进入临界区后，禁止所有进程的中断（interrupt）；当离开临界区后，再允许中断。
当禁止进程中断后，调度器就不会再进行进程切换。因此，进入临界区的进程不再需要担心其他进程写入共享数据区（因为其他进程根本没有被执行的机会）。
通常来说，这不是一个好的解决竞态条件问题的办法，因为允许用户进程（user process）禁止中断并不是一个机智的策略。如果用户进程在禁止中断后，一直都不允许中断（这个用户进程也一直处于临界区），这个用户进程最终可以无限地占用CPU。
而且，当系统是多处理器（multiprocessor）系统时，禁用正在被使用的一个处理器的中断并不能阻止其他进程在其他处理器的执行进入共享数据区。如今，越来越多的系统采用多核（multicore）CPU，因此禁止中断并不是一个有效的办法。
锁定变量（Lock Variables）
每一个可以被共享的变量都对应一个锁变量，锁变量的默认值为 0 。
当一个进程进入这个被共享的变量的临界区（critical regions）时，进程需要获取这个锁变量的值，如果锁变量为 0 ，这个进程就设置这个锁变量的值为 1 ，且成功进入临界区；如果锁变量为 1 ，这个进程就等待，直到锁变量为 0 时，才能进入临界区。
因此，一个被共享的变量的锁变量若为 0 ，则意味着没有进程进入这个共享变量的临界区；若为 1 ，则意味着已经有进程进入了这个共享变量的临界区。
然而，这个机制是有潜在问题的。比如，在前面提到的多任务打印缓存处理器（print spooler）的工作场景中。假设进程 A 读取锁变量，并且得到其值为 0 ，在进程 A 设置这个锁变量为 1 之前，进程 B 恰好被调度为运行状态，进程 B 设置锁变量的值为 1。当 CPU 时间又分配给进程 A 时，进程 A 设置锁变量的值为 1 。这时，两个进程同时都进入了竞态条件。
有人可能会想提出，通过让进程 A 在设置锁变量的值为 1 时，重新读取锁变量的值（如仍为 0 ，才进行后续操作）。事实上，这仍然不能解决多进程同时进入竞态条件的问题。因为，若在进程 A 在恰好完成第二次读取锁变量的值时，进程 B 被调度为运行状态，并设置锁变量的值为 1。
总结来说，锁定变量（Lock Variables）不是线程安全的，因为“检查-占锁”这个动作不具备“原子性”。
严格转换法（Strict Alternation）
Peterson 方案（Peterson’s Solution）
TSL 指令（The TSL Instruction）
我们来看一个在硬件层面提供帮助的方法：
TSL RX,LOCK
TSL 表示 Test and Set Lock。它会读取从内存中读取 lock 变量的值到 RX 寄存器（register）中，并设置一个非 0 值到 lock 变量的内存地址中。
这个从读取 lock 变量到寄存器到（在内存中）更新 lock 变量的操作（operation）是保证原子性（atomicity）的，即在这个 TSL 操作完成之前，其他处理器（processsor）是无法访问 lock 变量所在的内存空间的。这样的原子性是通过锁定内存总线（memory buss）实现的，目的当然是防止其他处理器读取在内存中的 lock 变量，最终多个进程同时进入临界区。
总结来说，TSL 指令从指令集支持层面保证了“检查-占锁”动作的原子性。 TSL 指令的不足在于需要让进程进入忙等待（busy waiting）。
避免忙等待（Busy-waiting - Sleep 和 Wakeup 原语
背景
虽然 Peterson 方案（Peterson’s Solution）和使用 TSL 或 XCHG 指令的方案都可以避免竞态条件问题，但他们都需要让进程进行忙等待（busy waiting）。即，在这些解决方案中，当一个进程进入临界区失败时，会进入一个紧密循环（tight loop），直到其成功进入临界区。
紧密循环（tight loop）不仅会浪费CPU时间，而且有时候还会衍生出新的问题。
Sleep 和 Wakeup 原语
一个解决忙等待最简单的解决方案就是 sleep and wakeup。
sleep 是一个可以使得调用者（caller）阻塞的系统调用，而 wakeup 包含一个参数，传入要唤醒的那个进程。
消息传递（Message Passing）
消息传递（Message Passing）使用两个原语（primitive）send 和 receive，他们分别对应两个系统调用（system call）：
send(destination, &message);
和
receive(source, &message);
前者会发送一条消息到指定的目的地，而后者会从指定某接收一条消息（也可以指定为 ANY，则不限消息源）。当没有可达消息时，接收者会阻塞直到有消息到来。
同步屏障（Barriers）
**同步屏障（Barriers）**也是一个同步机制（synchronization mechanism），通常服务于一组进程（而不是一对生产者-消费者类型的进程组）。
在有的应用中，我们会将程序划分为多个阶段（phase），只有当是所有进程就准备完毕可以进入下一个阶段时，所有进程才一起进入下一个阶段。
为此，我们在每个阶段的末尾引入屏障（Barrier）。当一个进程达到屏障时，则会被阻塞，直到其他进程也都全部达到屏障时才恢复就绪态，如下图所示：
潜在的进程间通信问题
死锁（Deadlock）
当两个进程同时占用多个被共享的资源时，就可能出现死锁。比如，A线程等待着B线程向其发送数据，而同时B线程也等待着A线程向其发送数据，此时就产生了死锁（Deadlock）。
数据不一致性（Data Inconsistency）
当共享数据区同时被不同的进程修改时，数据不一致性就会发生，这也可以称为竞态条件/竞争条件（race condition）。竞斥条件是需要被避免的，否则程序会出现不按预期执行的情况。对应地，这个共享存储区被称为竞态资源（Race Resources）。
而修改竞态资源（共享数据区）的代码块，就称为临界区（critical section）。
比如，一天爸爸发现儿子的账号里只有100美元，于是决定存入50美元给儿子。而正在此时，儿子正在取钱，他打算取20美元（取钱后账号应该剩80美元）。
由于爸爸和儿子的操作同时进行，而且进行操作账号时没锁（Lock），最终可能出现他们操作之后，账号的余额为150美元。
使用汇编语言来描述这个过程：
因此，我们需要引入互斥（mutual exclusion）机制，以避免多个进程同时进入临界区，最终避免数据不一致性（Data Inconsistency）的发生。
互斥机制从本质来说，是一种同步（synchronization）机制。
经典的 IPC 问题
哲学家就餐问题（The Dining Philosophers Problem）
问题：5个哲学家坐在一个圆桌，每个哲学家都有一份意大利面，而意大利面非常滑，因此每个哲学家需要两个叉子来吃它。在每两份意大利面之间都有一个叉子，如下所示：
每位哲学家的生活只包括两个状态，吃或者思考。当一个哲学家足够饿时，他会尝试获得他左边和右边的叉子，一次拿一个（以任何的顺序）。如果他成功获得了两个叉子，他就会吃一会儿，然后放下叉子，继续思考。
问题在于，如何设计一个程序使得每个哲学家在任何时间都可以做他想做的，而不会被相互阻塞。
读者-写者问题（The Readers and Writers Problem）
在一个航班预定系统中，多个进程可以同时从数据库中获取信息，但是当一个进程正在写入数据库时，所有的进程都不能进行信息读取。
总结
进程互斥机制（Mutual Exclusion Facilities）
为了解决上面的死锁或数据不一致问题，我们需要引入同步机制，
基于硬件的解决方案
- 禁止中断（Disabling Interrupts）：仅仅适用于单 CPU 系统，不适用于多 CPU 或多核系统；
- TSL 指令（The TSL Instruction）：TSL 表示 Test and Set Lock，TSL 指令从指令集支持层面保证了“检查-占锁”动作的原子性。TSL 指令的不足在于需要让进程进入忙等待（busy waiting）。
- XCHG 指令
基于软件的解决方案
- LockOne锁
- LockTwo算法
- Peterson 算法
- Bakery 算法
- Dekker 算法
各种同步机制的实现方法
- 信号量（Semaphores）：基于 TSL 或 XCHG 指令实现。
- 互斥锁（mutexes）：为信号量的特例，即二元信号量（Binary semaphores）。
- 基于 TSL 或 XCHG 指令实现；
- 实现了多进程/线程的互斥（mutual exclusion）访问，即在任一时刻，只能有一个进程/线程进入临界区状态（critical section）。
- 自旋锁（Spinlock）：也是一种实现互斥（mutual exclusion）的方式，相比于互斥锁（Mutex）会在因无法进入临界区而进入阻塞状态，因而放弃CPU，自旋锁则是不断循环并测试锁的状态（紧密循环（tight loop）），这样就一直占着CPU，这个过程也称为忙等待（busy waiting）。
- 管程（Monitor）：基于 TSL 或 XCHG 指令实现。
Reference
-
《Modern Operating System 4th》
-
互斥锁，同步锁，临界区，互斥量，信号量，自旋锁之间联系是什么？ - https://www.zhihu.com/question/39850927
-
linux 中进程间6种通信方式 - http://www.syyong.com/linux/6-communication-modes-between-processes-in-Linux.html
-
读写自旋锁详解 - https://www.ibm.com/developerworks/cn/linux/l-cn-rwspinlock1/index.html
-
操作系统原理（Operating Systems） - https://www.coursera.org/learn/os-pku/home/welcome