0. 并发，是机遇也是挑战

0.1 并发与并行

自从多道程序设计技术诞生以来，资源的利用率和系统的吞吐量就得到了极大的提高，也由此出现了多道批处理系统。

多道程序设计具有以下三个特点：

  • 多道：同一时间段内有多道程序在内存中执行。
  • 宏观上并行：系统内的多个程序都处于运行过程中的状态。
  • 微观上串行：这些程序轮流占有CPU，交替执行。

当多道程序运行在可抢占式的操作系统上时，就产生了并发（Concurrent）问题：CPU在一个进程的指令流上的任何一点都可能产生中断，转而去执行其他进程。当系统有一个以上CPU时，那么进程（线程）的执行效率还可以得到进一步的提升，一个CPU执行一个进程（线程）时，另一个CPU可以执行另一个进程，且它们之间互不抢占CPU资源，可以同时执行，此时的这种方式我们称之为并行（Parallel）。

gantt
    title 三个进程并发执行
    dateFormat  m 
    axisFormat  %M
    section 进程A
  	占用CPU   : crit, active, p1,0, 5
    
    section 进程B
    占用CPU   : crit, active, p3 , after p2, 5m
    
    section 进程C
    占用CPU   : crit, active, p2 , after p1, 10m

并发和并行所带来的优点是显而易见的，它使得资源利用率得到提高，多道程序共享计算机资源，从而保证各种资源能够得到充分利用；同时也提高了系统的吞吐量，CPU和其他资源能够总是保持“忙碌”的状态。但是矛盾的同一性告诉我们，既然并发给我们带来了优点，那么它自然也有缺点。当我们并发访问一个共享数据时，就可能会导致共享数据的不一致。

想象一下这样一个场景：假设我们有一个自增程序（它的功能是将一个变量加1），在某一时刻我们运行了这个程序的两个进程，分别是A和B。

我们假设共享变量的初始值是0，显然在没有并发的情况下，A和B都能正确实现它们的功能，分别将共享变量加1，最终的结果为2。但若A和B并发访问共享变量，则有可能导致错误情况。如下图所示，其中一种可能的错误情况就是A和B都执行完毕后，共享变量的值为1，而正确的值应该是2。

sequenceDiagram
	进程A ->> 共享变量: 查询
	共享变量 ->> 进程A : 值为0
    进程B->>共享变量: 查询
    共享变量 ->> 进程B : 值为0
    进程A ->> 共享变量: 将变量设置为0+1=1
    进程B ->> 共享变量: 将变量设置为0+1=1
	Note right of 共享变量: 正确的值应当是1+1=2！

由于协作进程之间可以共享逻辑地址空间，或甚至直接共享内存，所以直到现代操作系统的设计中，所谓的同步（Synchronize）问题，也就是保持共享数据的并发访问下的一致性问题，仍是一个重要议题。

所以，对同步技术的研究可以使得我们正确处理进程、线程间的并发。

0.2 临界区问题

接下来将问题抽象到一个更高的维度。我们实际上可以将并发进程间的同步问题归结为对共享变量、文件等的读写问题。如果我们将修改共享变量的那一段代码视作一个区域，那么问题实际上就转化为了那一片区域的代码的执行问题。这样一段涉及到修改共享变量的代码段称之为临界区（Critical Section），并发进程间的同步问题也就是临界区的访问问题。

为了解决这一问题，可以设计一个“君子协议”，让进程之间协调修改共享变量的顺序，这样就能够做到正确地并发修改共享变量。相应的，所有的程序在修改共享变量之前，都要申请一个“修改许可”，而在修改之后，可以“通知”其他程序，以便别的程序访问。

于是我们可以抽象出以下概念

  • 进入区（Entry Section）：进入临界区以前，请求“许可”的代码段。
  • 临界区（Critical Section）：可能会对共享变量进行修改的代码段。
  • 退出区（Exit Section）：应用程序可以在此“通知”其他进程或者做一些别的操作。
  • 剩余区（Remainder Section）：之后的代码段。
do {
  //------//
  //进入区//
  //------//
      //------//
      //临界区//
      //------//
  //------//
  //退出区//
  //------//
      //------//
      //剩余区//
      //------//
} while(true)

1. 软件同步方法

临界区问题有多种解决方法，比如我们可以在编写程序时就将进程间的同步问题考虑进来。

通过软件层面的算法，我们可以将同步问题扼杀于摇篮之中。

1.1 单标志法：一种最简单的构思

单标志法的思想是：设置一个公用变量turn，其用于指示当前允许进入临界区的进程编号。如当前turn=0，那么只有进程P0允许进入临界区。

进程P0的代码：

while(turn != 0);	// 进入区
critical section;	// 临界区
turn = 1;	// 退出区
remainder section;	// 剩余区

进程P1的代码：

while(turn != 1);	// 进入区
critical section;	// 临界区
turn = 0;	// 退出区
remainder section;	// 剩余区

单标志法的实现异常简洁，但它的鲁棒性也显然不足。它虽然能确保每次只有一个进程进入临界区，但两个进程必须交替进入临界区，某一个进程想连续两次进入临界区执行是不被允许的。

sequenceDiagram
	进程P_0 ->> 临界区: 进入临界区执行
	Note left of 临界区: turn=0
	临界区 ->> 进程P_0 : 执行完毕
	Note left of 临界区: 修改turn=1
	alt 等待P_1执行
        进程P_1->>临界区: 进入临界区执行
        Note right of 临界区: turn=1
        临界区 ->> 进程P_1 : 执行完毕
        Note right of 临界区: 修改turn=0
    end
    进程P_0 ->> 临界区: 想再次进入临界区...
	Note left of 临界区: 需等待turn被改为0！

然而同步问题要求，对于请求访问临界区的进程，应当保证在有限时间内能够进入临界区，这又称为==有限等待==原则。显然单标志法无法满足有限等待原则，我们必须对它进行改进。

1.2 先检查双标志法：改进！

单标志法的局限在于，在只有一个标志turn的情况下，进程间只能轮转交替。而且只有这一个标志，很难给我们提供更多的信息。我们想随时知道当前临界区的访问情况，如果临界区是空闲的，那么当前进程就应该可以立即进入临界区执行，这又称为==空闲让进==原则。

遵循这样一种思想，可以得到一种双标志法。双标志法的基本思想是每个进程在访问临界区的资源之前，先检查临界区是否正在被其他进程访问。

为此，我们可以设置一个标志数组flag，初始值全部为false。当第i个元素flag[i]为true时，表示进程Pi当前正在访问临界区；若flag[i]为false，则表示进程Pi并未进入临界区。

进程Pi的代码：

while(flag[j]);		// 发现进程P_j正在访问临界区，自旋等待
flag[i] = true;		// 进入区
critical section;	// 临界区
flag[i] = false;	// 退出区
remainder section;	// 剩余区

进程Pj的代码：

while(flag[i]);		// 发现进程P_i正在访问临界区，自旋等待
flag[j] = true;		// 进入区
critical section;	// 临界区
flag[j] = false;	// 退出区
remainder section;	// 剩余区

双标志法解决了两个进程必须交替进入临界区的问题，任何进程在进入临界区前，只需要检查临界区是否有进程正在访问，若当前已经有进程进入临界区，那么其他试图进入临界区的进程必须等待，这是同步问题中的==忙则等待==原则。在这里我们的实现是一个简单的while死循环等待，这种循环又称为自旋等待，需要占用CPU时间。若没有进程在访问临界区，那么就可以进入临界区执行。

但随之而来的问题是，双标志法可能会让两个进程同时进入临界区。

考虑这样一种情况，在某一时刻，进程Pi发现flag[j]为false，这表明进程Pj当前并未进入临界区，于是Pi随即退出自旋等待，准备将自己的flag[i]修改为true，然后进入临界区。然而就在Pi将要修改flag[i]之前，进程Pj也进行了标志检查，发现此时flag[i]为false，同样满足进入临界区的条件。于是进程Pj也退出了自旋等待，准备进入临界区。

sequenceDiagram

	loop 自旋等待
		进程P_i ->> 进程P_i: 
		
	end
	Note left of 临界区: 发现flag[j]为false，退出自旋等待
	loop 自旋等待
		进程P_j ->> 进程P_j: 
	end
	Note right of 临界区: 发现flag[i]为false，退出自旋等待
	

    进程P_i ->>+ 临界区: 进入临界区
	Note left of 临界区: 置flag[i]=true
	进程P_j ->>+ 临界区: 进入临界区
	Note right of 临界区: 置flag[j]=true
	临界区 ->>- 进程P_j: 退出临界区
	临界区 ->>- 进程P_i: 退出临界区
	Note right of 临界区: 同时访问了临界区！

这样的错误结果显然是由于双标志法的检查标志的时机不对而导致的。我们称这个版本的双标志法为先检查双标志法。这个时序的错误同时也告诉我们应该如何对双标志法进行修改。

1.3 后检查双标志法：再改进！

为了修复先检查双标志法带来的时序上的错误，我们可以将对flag数组的检查移动到修改flag数组的操作之后，也就是每个进程想进入临界区之前，先修改自己的标志，再去检查对方的标志。这就是所谓的后检查双标志法。

进程Pi的代码：

flag[i] = true;		// 进入区
while(flag[j]);		// 进入区 发现进程P_j正在访问临界区，自旋等待
critical section;	// 临界区
flag[i] = false;	// 退出区
remainder section;	// 剩余区

进程Pj的代码：

flag[j] = true;		// 进入区
while(flag[i]);		// 进入区 发现进程P_i正在访问临界区，自旋等待
critical section;	// 临界区
flag[j] = false;	// 退出区
remainder section;	// 剩余区

然而很遗憾，后检查双标志法也不能很好的work。究其原因，是当两个进程都同时想进入临界区时，大家都会先将自己的标志置为true，然后再去检查对方的标志。于是双方都会发现对方的标志为true，这样就会造成相互谦让等待。结果就是双方都无法进入临界区，从而导致饥饿现象。从另一方面来说，这种无限期的等待也违反了有限等待原则。

1.4 神形兼备终极版本：Peterson's Algorithm

Peterson算法将单标志法和后检查双标志法结合起来，为了防止进程间的谦让导致的无限期等待问题，再次引入变量turn，表示当前允许哪个进程进入临界区。每个进程在设置自己的标志后再设置turn的值，而此时flag标志一个进程是否想要进入临界区。

进程Pi的代码：

flag[i] = true; turn = j;		// 进入区
while(flag[j] && turn == j);	// 进入区 
critical section;	// 临界区
flag[i] = false;	// 退出区
remainder section;	// 剩余区

进程Pj的代码：

flag[j] = true; turn = i;		// 进入区
while(flag[i] && turn == i);	// 进入区
critical section;	// 临界区
flag[j] = false;	// 退出区
remainder section;	// 剩余区

Peterson算法的正确性不难证明。考虑进程Pi想要进入临界区的情况。当进程Pi想要进入临界区时，首先会将flag[i]置为true，表明自己想进入临界区，同时会将turn置为j，进行一次“谦让”。此时的进程Pj无外乎一下两种情况：

  • 如果Pj此时想要进入临界区，或者正在临界区中执行，那么flag[j]一定为true。满足Pi的等待条件，Pi必须等待。
  • 如果此时Pj不想进入临界区，或者已经退出临界区，那么flag[j]一定为false。Pi的等待条件不满足，于是Pi可以立即进入临界区执行。
flowchart TD
	node_1[P_i准备进入临界区] --> node2[flag置为true同时turn置为j]
	node2 --> node5[检查flag和turn]
	
	subgraph 忙则等待

        node5 --P_j在临界区或想进入临界区--> node5
	end
	subgraph 空闲则入
        node5 --P_j不在临界区中--> node3[P_i进入临界区]
	end

Peterson算法的巧妙之处在于，利用了flag解决临界资源的互斥访问问题，同时利用turn解决饥饿问题。

至此，从软件层面已经可以很好的解决临界区的访问问题了。

2. 硬件同步方法

我们看到，在软件层面实现同步的方法实现起来较为复杂，而这种复杂性产生的原因，是软件方法随时可能被另一进程中断。而处理器从硬件层面，给我们提供了能保证不被中断地互斥访问临界区的方法。

2.1 关中断

对于单处理器环境，临界区问题实际上可以简单粗暴的加以解决。我们只需要在修改共享变量时禁止中断出现，这样就能确保当前的指令流可以有序执行，不会被抢占。由于不会执行其他的指令，自然也就不用担心共享变量被其他进程修改。这种方法也往往为非抢占式内核所采用。

...
   //------//
  	//关中断//
   //------//
       //------//
       //临界区//
       //------//
   //------//
  	//开中断//
   //------//
   ...

然而在多处理器的环境下，这种解决方案是不可行的。多处理器的中断禁用会很耗时，因为消息需要传递到所有处理器，而且会严重降低系统效率。

关中断所带来的一些缺点还包括

  • 禁用中断的代码段执行的时间如果很长，会导致系统其他优先级高的进程得不到执行。
  • 如果进程关中断后不开中断，则会导致系统直接终止。

让应用程序关中断带来的风险很高，所以CPU提供了一些特殊的硬件指令供应用程序使用，可以实现关中断访问临界区的功能。

2.2 使用原子指令

由CPU来控制临界区的访问带来的好处就是不必担心进程关中断所带来的各种潜在的风险。许多线代操作系统都提供这样的硬件指令，比如可以原子地（Atomically）检测（Test）和修改（Set）变量的内容，或原子地交换两个字。所谓原子性，就是在这些指令的执行过程中，不会发生CPU的中断。其对应的指令序列要么全部完成，要么全部不完成。

我们可以利用这些特殊指令，相对简单的解决临界区问题。以下所讨论的并非特定机器上的特定指令，而是这些指令背后的主要思想和概念。

2.2.1 Test And Set

Test And Set即测试（测试参数的值）并置位（修改参数的值），简称为TAS指令。这条指令实现的功能如下：

bool test_and_set(bool *target) {
	bool rv = *target;
    target = true;		// 修改参数的值
    return rv;			// 总是返回参数的旧值
}

我们可以使用它实现临界区的互斥访问。

  • 声明一个bool型变量lock，初始化为false。
  • 进程在进入区使用TAS指令将lock改为true，在退出区将lock改为false。

使用TAS指令互斥访问临界区的代码如下：

bool lock = false;					// 声明锁

do {
	while(test_and_set(&lock));		// 进入区 加锁
    critical section;				// 临界区
    lock = false;					// 释放锁
    remainder section;				// 剩余区
} while(true);

2.2.2 Exchange

Exchange（交换）指令的功能是交换内存中的两个值。

void exchange(bool* a, bool* b) {
    bool tmp = *a;
    *a = *b;
    *b = tmp;
}

通过使用Exchange指令，我们同样也可以实现一个互斥协议。

  • 我们将一个共享变量bolt初始化为false。
  • 然后每个进程都尝试用一个值为true的局部变量key去尝试交换bolt的值，只有交换成功的那个进程可以进入临界区。
  • 同时，由于bolt的值被换成了true，其他进程将会被阻止进入临界区，这样一来就实现了临界区的互斥访问。
bool bolt = false;

do {
  bool key = true;
  while(key)
    exchange(&bolt, &key);
  /* critical section */
  bolt = false;
  /* remainder section */
} while(true)

基于Exchange指令实现的互斥访问流程如下：

flowchart TD
	node1[bolt = false key = true] --> node2[尝试交换bolt和key]
	node2 --交换成功--> node3[进入临界区]
	node2 --交换失败--> node2
	node3 --> node4[bolt = false]

2.2.3 Compare And Swap

Compare And Swap即比较并交换，简称CAS指令。这条指令的功能是在修改旧的值之前先检查旧的值是否被修改（是否与期望的值相符），如果与期望值相符，那么将它改为新的值，否则什么也不做。与TAS指令一样，CAS同样返回的是共享变量的值。

int compare_and_swap(int *value, int expected, int new_value) {
	int old_value = *value;
	if (old_value == expected)	// 如果与期望的值相符
		*value = new_value;	// 改为新的值
	return old_value;	// 总是返回旧的值
}

CAS指令的思想其实很容易理解，这里我们仍然以前面提到的经典的高并发计数器问题为例。

假如我们有一个计数器count，初始值为0。当两个进程A和B分别访问计数器时，可能会出现：

  • 进程A将计数器的值取出，加1，设置为1。
  • 进程B同时将计数器的值取出，加1，设置为1。然而此时count的值实际上已经被进程A修改为1了。

要避免这种错误的结果，实际上就可以通过CAS机制实现。我们只需要让进程在修改count的值之前，比较一下count的值是否仍是之前取出的值（预期）。

sequenceDiagram
	进程A ->> count: 查询
	count ->> 进程A : 值为0
    进程B->>count: 查询
    count ->> 进程B : 值为0
    进程A ->> count: compare_and_swap(count, 0, 1)
    count ->> 进程A : 返回值为0
    Note left of count: 返回值是0，说明比较成功，count被改为1
    进程B ->> count: compare_and_swap(count, 0, 1)
    count ->> 进程B : 返回值为1
	Note right of count: 返回值是1，说明比较失败，没有修改count的值

使用机器指令实现临界区的互斥访问具有以下特点：

  • 适用于单处理器或共享内存的多处理器。
  • 适用于任意数量的进程
  • 简单且易于证明
  • 可用于支持多个临界区。

但也有一些比较严重的缺点：

  • 使用了忙等待：当一个进程等待进入临界区时，它不应该消耗CPU资源，我们称之为==让权等待==原则。显然，使用上面基于原子指令的互斥访问不符合让权等待原则。
  • 可能产生饥饿：当一个进程离开临界区且有多个进程正在等待时，哪个进程能够进入临界区完全是随机的，可能会导致饥饿现象。
  • 可能死锁：考虑单处理器的情况，假如进程P0执行上述原子指令并进入临界区后被中断，并将CPU让给更高优先级的进程P1。但P1也尝试使用同一个资源，由于互斥机制，它将被拒绝访问，陷入忙等待循环。而由于P0的优先级低于P1，故P0永远不会被调度执行，于是P0和P1陷入死锁。

2.3 锁

使用处理器提供的原子指令的解决方案还可以进一步抽象。软件工程中的依赖倒置原则告诉我们，我们应当依赖于抽象，而不是依赖于具体实现。

使用原子指令的解决方案实际上可以统一抽象成如下过程：

do {
	//-----//
	//获得锁//
	//-----//
      //-----//
      //临界区//
      //-----//
	//-----//
	//释放锁//
	//-----//
      //-----//
      //剩余区//
      //-----//
} while(true)

要实现对临界区的互斥访问，无非是在访问临界区之前“加锁”，离开临界区之后“释放锁”。由此，我们可以设计一种简单的工具：互斥锁（Mutex Lock）。我们可以采用互斥锁保护临界区，从而防止竞争条件。

锁应当有两个方法，Acquire()获得锁，Release()释放锁。当Acquire()方法使用TAS指令时，我们可以给出其中一种设计方案：

class Lock {
	int value = 0;
}

Lock::Acquire() {
	while(test_and_set(value));	// spin
}

Locak::Release() {
	value = 0;
}

这种实现的主要缺点是，它需要忙等待（busy waiting），违背了让权等待原则。另外，这种类型的互斥锁也被称为自旋锁（spin lock），因为进程不停地旋转等待，直到锁变得可用。

而另一种类型的锁则是无忙等待锁，可以实现如下：

class Lock {
	int value = 0;
  WaitQueue q;	// 等待队列
}

Lock::Acquire() {
	while(test_and_set(value)) {
    add this TCB to wait queue;
    schedule();	// 执行调度程序
  }
}

Locak::Release() {
	value = 0;
  remove a thread t from wait queue q
  wakeup(t);	// 唤醒一个进程
}

通过对软件方法和硬件方法的同步问题解决方案的构思，我们已经能够总结出解决同步问题的四个原则了：

  • 空闲让进：如果临界区是空闲的，那么当前进程就应该可以立即进入临界区执行。
  • 忙则等待：若当前已经有进程进入临界区，那么其他试图进入临界区的进程必须等待。
  • 有限等待：对于请求访问临界区的进程，应当保证在有限时间内能够进入临界区。
  • 让权等待：当一个进程等待进入临界区时，它不应该消耗CPU资源。

3. 高级同步方法

前面所提到的软件和硬件的同步方法都或多或少存在缺陷。软件同步方法实现起来较为复杂，让程序员在每个程序中都使用那样的软件同步方法显然不现实。硬件同步方法实现起来虽然更简单，但它同样存在饥饿，死锁的问题。因此，有必要寻找更高级的同步方法。

3.1 信号量

信号量机制不仅仅用于提供并发性的操作系统的设计中，还广泛应用于高级程序设计语言之中。它的功能类似于互斥锁，但它的鲁棒性更好，也提供了更为高级的方法，以便进程之间同步。

信号量定义了两个标准原子操作：wait()和signal()。信号量机制最早是由荷兰计算机科学家Dijkstra提出的，wait()来源于荷兰语Proberen（测试），所以又称为P操作；同样的，signal()来源于荷兰语Verhogen（增加），所以又称为V操作。

一个最简单的忙等待的信号量（整型信号量，因为只需一个整数类型即可实现）实现如下：

void wait(int S) {
	while(S <= 0);	// busy wait
	S--;
}

void signal(int S) {
	S++;
}

它的使用也非常简单。例如，现在有两个并发运行的进程P0和P1，P0有语句S0而P1有语句S1。我们希望在S0执行之后再执行S1，可以用信号量轻松实现这个需求。只需设置一个信号量syn并初始化为0，然后在S_0之后执行signal()操作，在S1之前执行wait()操作即可。

P0的代码：

S0;
signal(syn);

P1的代码：

wait(syn);
S1;

整个执行过程也很简单：

sequenceDiagram
	
	loop
	进程P_1 ->> syn: wait
	Note right of syn: 初始值为0
	syn ->> 进程P_1: 失败
	end
	进程P_0 ->> syn: signal
	Note right of syn: 值改为1
	进程P_1 ->> syn: wait
	syn ->> 进程P_1: 成功

3.1.1 二元信号量（二进制信号量）

二元信号量的值只能为0或1，因此二元信号量类似于互斥锁。也就是说，在没有提供互斥锁的系统上，完全可以使用二元信号量来提供互斥。

3.1.2 计数信号量

计数信号量可以用于控制访问具有多个实例的资源，初值可以设置为可用的资源数量。当进程需要使用资源时，执行wait()操作，释放资源时，执行signal()操作。当资源数为0时，表示所有的资源都在使用中。之后，所有需要使用该资源的进程都将阻塞，直到计数信号量大于0。对信号量的操作总结如下：

  • 一个信号量可以初始化为一个非负整数。
  • wait()操作使信号量减1。若值变为负数，则阻塞执行wait()操作的进程。
  • signal()操作使信号量的值加1。若操作后值扔小于等于0，则从被wait()操作阻塞的进程中唤醒一个进程。

不同于忙等待的信号量，计数信号量是无忙等待的信号量（又称记录型信号量，因为使用了一个队列记录等待的进程），可以实现如下：

typedef struct {
	int value;
	truct process *wait_list;
} semaphore;

void wait(semaphore S) {
	if (--S.value < 0) {
		add this process to S->wait_list;	// 将当前进程添加到等待队列，然后阻塞
		block();
	}
}

void signal(semaphore S) {
	if (++S.value <= 0) {
		remove a process P from S->wait_list;	// 从等待队列中取出一个进程，然后将其唤醒
		wakeup(P);
	}
}

3.2 信号量带来的挑战

3.2.1 死锁

具有等待队列的信号量可能会产生相互等待的情况：两个或多个进程无限等待一个事件，而该事件又只能这些由等待进程中的一个来产生。这种相互等待的状况就是死锁。

假如有两个进程P0和P1，和两个二元信号量S和Q。它们各自执行都需要使用信号量S和Q。

进程P0

wait(S);
wait(Q);
/*
继续执行
*/
signal(S);
signal(Q);

进程P1

wait(Q);
wait(S);
/*
继续执行
*/
signal(Q);
signal(S);

而在某个时刻，P0执行了wait(S)，紧接着P1执行了wait(Q)，接下来，P0若需要继续执行，还需要等待P1执行signal(Q)，所以P0进入阻塞状态。同样的，P1想要继续执行则需要等待P0执行signal(S)。于是，P0和P1进入了无限期等待的死锁。

flowchart TD
	P_0 --wait--> S
	P_1 --wait--> Q
	P_1 --wait--> S
	P_0 --wait--> Q

3.2.2 饥饿

不论是计数信号量还是二元信号量，都需要使用队列来保存正在等待该信号量的进程。这样也产生了一个问题：应该按照什么顺序将进程从等待队列中唤醒？当然，最公平的策略是先进先出（FIFO），被阻塞最久的进程最先从队列中移出。采用这一策略定义的信号量称为强信号量（Strong Semaphore），而未规定进程唤醒顺序的信号量称为弱信号量（Weak Semaphore）。强信号量保证了不会产生饥饿问题，而弱信号量就无法保证。

3.2.3 优先级反转

假设有三个进程、、，它们之间的优先级关系为。假如某个时刻进程需要资源，而目前正在被访问，通常情况下，将等待用完资源。但是此时恢复了可运行状态，不讲武德抢占进程的执行，就会发生优先级翻转（Priority Inversion）：的优先级比低，但是竟然影响了的等待时间。

gantt
    title 优先级反转
    dateFormat  m 
    axisFormat  %M
    section L
  	使用资源R   : crit, active, p1,0, 2
    
    section M
    抢占L使用资源R   : crit, active, p2 , after p1, 5m
    
    section H
    等待中...   : done, p3 , 0, 7

这种情况只会出现在具有三个优先级以上的系统中，最简单的避免办法就是只有两个优先级，但是这也不现实。通常，解决这个问题的办法是采用优先级继承协议（Priority-Inheritance Protocol）。所有正在访问资源的进程获得需要访问它的更高优先级的进程的优先级，直到它释放该资源。

在上面的例子中，就是让在执行时临时继承的优先级，这样就无法抢占它执行。这样，当执行完毕后，就能得到执行，而不是。

3.3 高级程序设计语言中的利器：管程

虽然信号量提供了一种比较简单（相较于软件同步方法）的方式实现进程间同步，但对于它的使用必须谨慎。比如P操作和V操作通常分散在程序当中，但它们又必须成对出现；程序员还需注意时序问题，操作的时序错误可能会导致死锁。除此之外，还有前面所提到的饥饿问题等等。

当程序员没有正确使用信号量时，可能会导致各种错误。为了进一步提高开发效率，Brinch Hansen（1973）和Hoare（1974）又在信号量的基础之提出了一种更高级的同步原语：管程（Monitor）。管程的特性保证了进程间的互斥，无需程序员自己实现，从而降低了死锁发生的可能性。管程中还提供了条件变量，可以让程序员灵活地实现进程同步。

3.3.1 什么是管程

管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。通常，管程主要由四个部分组成。分别是条件变量、共享数据、对数据进行操作的一组过程和对共享数据赋初值的语句。管程能保障共享资源的互斥执行，即一次只能有一个进程可以在管程内活动。这一特性是由管程本身实现的。因此，程序员可以不必显式地编写程序代码去实现这种同步制约。

管程的四个特点如下：

  • 进程只能通过调用管程中的过程来进入管程内部。
  • 管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所提供的过程 (函数）来间接地访问管程中的共享变量。
  • 为了保证管程共享变量的数据完整性，规定管程互斥进入。任何时刻只能有一个进程在管程中执行，调用管程的其他进程都将被阻塞，直到管程可用。
  • 管程通常是用来管理资源的，因而在管程内部设有进程等待队以及相应的阻塞和唤醒操作。
monitor
monitor

管程其中一个很重要的特性任一时刻管程中只能有一个活跃进程，这一特性使管程能有效地完成互斥。那么这是如何实现的呢？Java给出的答案是借助编译器（C语言等并不支持管程）。

管程是编程语言的组成部分，编译器知道它们的特殊性，因此可以采用与其他过程调用不同的方法来处理对管程的调用。典型的处理方法是，当一个进程调用管程过程时，编译器将在该过程前插入几条指令，用于检查在管程中是否有其他的活跃进程。如果有，调用进程将被挂起至等待进入管程的队列，直到另一个进程离开管程将其唤醒。如果没有活跃进程在使用管程，则该调用进程可以进人。

进人管程时的互斥由编译器负责，通常的做法是用一个互斥量或二元信号量。 因为是由编译器而非程序员来安排互斥，所以出错的可能性要小得多。在任一时刻，编写管程的人无须关心编译器是如何实现互斥的，只需知道将所有的临界区转换成管程过程即可，绝不会有两个进程同时执行临界区中的代码。

由于管程是互斥进人的，所以当一个进程试图进入一个已被占用的管程时，它应当在管程的入口处等待， 因而在管程的入口处有一个进程等待队列，称作入口等待队列。

如果进程P唤醒进程 Q，则P等待Q继续，如果进程Q在执行又唤醒进程R，则Q等待R继续……。如此， 在管程内部，由于执行唤醒操作，可能会出现多个等待进程，因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列（注意，它与条件变量的等待队列不同），并且它的优先级高于人口等待队列的优先级。但是后面我们将看到，由于调度方式的不同，所以并不是所有的管程都需要有紧急等待队列。

3.3.2 条件变量

尽管管程提供了一种实现互斥的简便途径，但这还不够。我们还需要一种办法使得进程因缺少某个资源而无法继续运行时，能够被阻塞进入该资源的等待队列中。解决的方法是引入条件变量（Condition Variables)，每个条件变量都定义了两个操作：wait()和signal()，同时每个条件变量都拥有一个等待队列（见上图）。这两个操作的描述如下：

  • wait()操作可以使调用它的进程在该条件变量上阻塞。
  • signal()操作即发出一个信号，可以唤醒一个之前因wait()该条件变量而阻塞的进程。但如果没有这样的进程，则什么也不做。

当一个管程过程发现它无法继续运行时（例如，在后文将提到的生产者-消费者问题中，生产者发现缓冲区满），它会在某个条件变量上（如full)执行 wait()操作。该操作导致调用进程自身阻塞，并进入该条件变量的等待队列。同时，还将从管程外的等待队列中唤醒一个进程，并调入管程执行。而所有阻塞在条件变量的等待队列中的进程，将在其他进程执行了signal()操作之后被唤醒。

flowchart TD
	node1[进入管程执行] --继续执行还需某个条件变量--> node2[对该条件变量执行wait操作]
	node2 --执行wait操作的进程阻塞--> node3[从等待进入管程的队列中唤醒一个进程]
	node3 --被唤醒的进程--> node1
	node1 --> node4[对某个条件变量执行signal操作]
	node4 --> node5[从该变量的等待队列中唤醒一个进程,如果有的话]
	node5 --被唤醒的进程--> node1
	node1 --> node6[执行完毕]
	node6 --> node3

值得注意的是，条件变量不是计数信号量，条件变量也不能像信号量那样积累信号以便以后使用。所以，如果向一个条件变量发送信号，但是在该条件变量上并没有等待进程，则该信号将被丢弃。 换句话说，wait操作必须在signal之前。这条规则使得实现简单了许多。

3.3.3 Hoare管程

当管程内正在执行的进程唤醒了位于等待队列中（可能是条件变量的等待队列、紧急等待队列或入口等待队列）的进程后，当前的进程又何去何从呢？针对这个问题，有三种主流的解决方案。

第一种方法是Hoare提出的，因此称为Hoare管程。具体的设计思想是，Hoare管程会立即让新唤醒的进程运行，而挂起当前进程到紧急等待队列的尾部。

Hoare
Hoare

3.3.4 Hansen管程

Hansen管程则要求执行signal()操作的进程必须立即退出管程，也就是signal语句只能作为管程过程的最后一条语句。也正因如此，Hansen管程并不需要紧急等待队列。Hansen管程实际上是Hoare管程与后面所提到的Mesa管程的折中。

3.3.5 Mesa管程

Mesa管程来源于Lampson和Redell为Mesa语言所开发的一种管程。

在Mesa管程中，signal()原语被notify()原语所取代。notify即通知，所以Mesa管程又称使用通知和广播的管程。

Mesa管程的思想是，被唤醒的进程需要等待，直到当前进程执行完毕离开管程。具体的操作是，当一个正在管程中的进程执行notify()操作时，会使得x的条件变量等待队列得到通知；与此同时，发信号的进程会继续执行。notify()操作的结果是，当处理器可用时，会恢复执行位于条件变量x的等待队列头部的进程。所以和Hansen管程一样，Mesa管程也不需要紧急等待队列。

Mesa
Mesa

Java与管程

Java是支持管程的编程语言之一，不过它并非采用Hoare模型和Hansen模型，而是采用了Mesa模型。正因如此，每一个Java对象都拥有一个wait()方法和一个notify()方法。

Java中对于管程的实现就是synchronized关键字。只要在方法声明的前面加入synchronized关键字，或者使用synchronized关键字声明一个代码块，JVM即可保证该代码块的互斥访问。

与上面标准的管程模型不同的是，Java的Monitor属于一种简单的管程模型，因为它并没有使用多个条件变量的队列，不管是竞争锁产生的阻塞，还是拿到锁因为某个条件不合格导致的阻塞，统一都放入一个队列了。

关于具体的实现细节，之后应该还会再写一篇文章介绍。

4. 经典同步问题

经过对各种同步方法的一一总结，我们终于来到了最后一节，掌握了工具的下一步是学习如何使用工具。由于软件同步方法比较复杂，硬件同步方法又偏底层，所以这里我们以有界缓冲问题为例，仅简单了解一下信号量和管程的使用。

4.1 有界缓冲问题

有界缓冲问题又称为生产者-消费者问题。该问题描述了共享固定大小缓冲区的两个进程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。

使用信号量的解决方案

semaphore mutex = 1;
semaphore fillCount = 0;
semaphore emptyCount = BUFFER_SIZE;

procedure producer() {
    while (true) {
        item = produceItem();
        P(emptyCount);
            P(mutex);
                putItemIntoBuffer(item);
            V(mutex);
        V(fillCount);
    }
}
procedure consumer() {
    while (true) {
        P(fillCount);
            P(mutex);
                item = removeItemFromBuffer();
            V(mutex);
        V(emptyCount);
        consumeItem(item);
    }
}

使用管程的解决方案，由于管程一定能保证互斥，不必特地考虑保护临界区。

monitor ProducerConsumer {
    int itemCount;
    condition full;
    condition empty;

    procedure add(item) {
        while (itemCount == BUFFER_SIZE)
            wait(full);
        putItemIntoBuffer(item);
        itemCount = itemCount + 1;
        if (itemCount == 1)
            notify(empty);
    }

    procedure remove() {
        while (itemCount == 0)
            wait(empty);
        item = removeItemFromBuffer();
        itemCount = itemCount - 1;
        if (itemCount == BUFFER_SIZE - 1)
            notify(full);
        return item;
    }
}

procedure producer() {
    while (true) {
        item = produceItem()
        ProducerConsumer.add(item)
    }
}

procedure consumer() {
    while (true) {
        item = ProducerConsumer.remove()
        consumeItem(item)
    }
}

当然，除了有界缓冲问题，其他典型的还有例如读者-写者问题、哲学家就餐问题等，篇幅所限，此处不再一一赘述。