当同时有多个进程或线程都在访问一个公共资源的时候，并发(Concurrency)就发生了（为了方便，下面只说进程）。因为资源有限，某个进程在使用公共资源的时候，另一个进程如果对这个资源进行更改就麻烦了。我们称这个正在被多个进程同时访问的资源为临界区(Critical section)。

进程竞争

两个或以上的进程都需要访问临界区。比如说某个进程 A 正在驱动打印机，如果这个时候，有另一个进程 B 也要打印。少了保护措施，打印机会一边打印进程 A 的输出，一边打印进程 B 的输出。这种关系叫进程竞争(Process Competition)。

解决方案

解决这个问题的方案必须要满足下面的四个条件：

  1. 互斥(Mutual Exclusion)：资源每次只允许一个进程访问。
  2. 无锁位移(Progress / No Lockout)：一个没有在用资源的进程，不能阻碍别的进程对这个资源进行访问。
  3. 有限等待(Bounded Waiting / 防止饥饿)：一个进程不能一直快速的访问某个资源，以至于其它进程停滞。
  4. 互斥锁(No Deadlock / 防止死锁)：两个进程同时访问某个资源的时候，不会尴尬地互相上锁，不让对方访问。

举例

这里有一个临界区

1
2
3
resource = 0;
def operation(x):
  resource += x`

进程 1 会调用这个临界区

1
2
3
# process_1
operation(5)
print(resource)

进程 2 也会调用这个临界区

1
2
3
# process_2
operation(3)
print(resource)

进程 1 先到达就绪队列，所以它被先运行了。在调用 operation() 的时候，进程 2 进入到了就绪队列中。恰好由于某些原因导致调度器决定换进程 2 跑一会儿。进程 1 在 operation() 中仅仅计算了 resource + x，而并未对 resource 更新（在 Python 中，resource += x 并非原子操作），因此 resource 依旧是 0。进程 2 将 resource 变成了 3，之后调度器才把进程 1 重新运行。进程 1 在这个基础上再加 5 就变成了 8。对于进程 1 来说，这个结果显然不对 $\left(0+5=8\right)$。

遵循上面的 4 个原则，我们改善一下代码。should_wait 是一个全局变量。

1
2
3
4
5
6
7
8
# process_1
p1_running = True
should_wait = 1
while p2_running and (should_wait == 1):
  pass
operation(5)
p1_running = False
print(resource)
1
2
3
4
5
6
7
8
# process_2
p2_running = True
should_wait = 2
while p1_running and (should_wait == 2):
  pass
operation(3)
p2_running = False
print(resource)

假设我们两个进程同时进行，当进程运行到第二行的时候 should_wait 只会在 1 和 2 里面选（总有一个进程比另一个进程设置得晚一点）。如此，再同时进入 while 循环的时候只有一个进程能调用 resource。这实现了互斥，也不会出现死锁的情况。饥饿也不会产生，因为当进程 1 用完之后，p1_running 是 False，进程 2 就可以跳过 while 循环开始执行了。

进程合作

除了多个进程互相竞争某一资源这种情况之外，还有一种情况是进程需要互相协调。就像搬家公司一样，一边有人往家里面搬家具，一边有人布置和摆放，没有被搬进来的家具就无法摆放。这种情况在操作系统里面被称为生产者消费者问题(Producer-consumer problem)，也称有限缓冲问题(Bounded-buffer problem)^1。

信号量

从代码方面来解决并发问题有若干缺点：

  1. 只能给两个进程用。
  2. 一个进程在访问临界区的时候，另一个进程只能一直不断地循环来等待，分配到的 CPU 时间完全被浪费掉了。
  3. 不能复用。

信号量(Semaphores)有时候也叫信号灯，是能统一解决并发问题的方案。信号量是一个非负数的值。它只能接受两种操作（通常称为 $P$ 和 $V$ 操作）：

操作 S > 0 S = 0
V(S) S + 1 S + 1
P(S) S - 1 等到 S > 0 再减 1

信号量必须要保证：

  1. 当有多个进程都在对信号量操作的时候，它会按照一定的顺序来执行（原子性）。
  2. 如果多个进程在 $S = 0$ 的时候都在等待 P(S)，有一个进程必须进行 V(S) 操作。

如图，我们有两个进程正在共用一个资源，并且使用信号量来防止并发带来的问题。

semaphores

在 $t_0$ 的时候进程 2 使用 V(S) 函数给信号量加 1，在 $t_1$ 的时候进程 1 和 2 同时增加信号量。这个量会被分别增加，避免无效。在 $t_8$ 的时候，两个进程同时减信号量，但是因为不够，系统随机阻塞进程 1。直到 $t_{11}$ 进程 2 加 1 之后，进程 1 才得以进行。

实现信号量

很多现代的电脑在硬件层面就已经实现信号量了。通过检查并设置(test-and-set)^2来锁住资源。这种模型通过一个 L(R, x) 的函数来操作信号量。L(R, x) 依次原子地执行下面的操作：

  1. 复制 x 的值给 R
  2. 把 x 设为 False

所有需要同一公共资源的进程都带一段这样的代码:

1
2
3
4
5
6
7
8
9
..
...
do{
  L(will_access, x)
} while (will_access != True)

operation_on_critical_section()
...
...

一开始 x 的值是 True，多个进程会通过 L(R, x) 竞争获取到 x 并把它设置成 False。这样一来其他进程就会一直在 while 循环中，只有 x 再次为 True 的时候才能够继续执行。

二元信号量

很多同步问题不需要整型信号量（General Semaphore）来解决问题。二元信号量只在 0、1 之间变换，它只接受以下操作：

操作 s = 1 s = 0
ab(s) s = 1 s = 1
sb(s) L(R, s) while(R == 0) L(R, s) while(R == 0)

如果一个进程不停地查询信号量是否可用，我们就叫这个进程在忙碌等待(Busy Waiting, busy-looping, spinning)状态^3。忙碌等待占用了 CPU 时间，而且没有任何产出，我们要尽可能的避免这样的情况发生。跟上面的函数一样，这个 L() 函数会原子地：

  1. 复制 s 的值给 R
  2. 设 s 为 0

注意：我用大写的 S 来表示普通信号量，小写的 s 来表示二元信号量。

ab() 和 sb() 的实现

信号量可以通过 P() 和 V() 来实现。而它们的操作也简单，就是对一个普通的整数值 S 进行操作。为了保证每次只有一个操作可以被执行，我们要用一个二元信号量来辅助 P() 和 V() 操作。

这个 S 值有两个作用：

  1. 当 $S \ge 0$ 时，S 是可用的信号量资源数。
  2. 当 $S < 0$ 时，它表示的是有多少个进程被放进了等待队列。

为了避免忙碌等待，当 S 减到 0 以下的时候，进程会被阻塞，然后转到等待队列中。还记得我们上一篇讲到的短期调度器吗？我们一直围绕着就绪队列探讨，而忽略了等待队列，现在就是这个等待队列派上用场的时候了^4。

先上代码：

1
2
3
4
5
6
7
8
def s(): // P(S) 操作
  sb(s) // 上锁，防止其他进程使用公共资源。
  S -= 1
  if(S < 0): //如果可用的资源已经没有了，甚至已经有进程在等待队列中排队了
   ab(s) //解锁
   block() //阻塞进程/将进程送到等待队列中
  else:
   ab(s)
1
2
3
4
5
6
7
8
def a(): // V(S) 操作
  sb(s) //上锁
  S += 1
  if(S <= 0):
    ab(s) //解锁
    reactive() //在等待队列中，选择任意进程运行。
  else:
    ab(s) //解锁

我们看看这些代码能做什么：

bs

解读一下这幅图。在开始之前我先说明一下这幅图的标示：

  1. 带红框的进程说明这个进程还没有跑满一个 CPU 运行周期就被调度器转移了。
  2. 绿色的进程做 V(S) 操作，浅橙色的进程做 P(S) 操作。
  3. 进程优先级 $p1 > p2 > p3$。

现在按照时间顺序，我把整个过程解释一遍。

  • 一开始，就绪列表中只有进程 p2，所以执行它。p2 做 P(S) 操作。
  • 假设在 p2 执行完 sb(s) 的时候，p1 进入了就绪列表，而且因为它的优先级比较高，调度器决定先执行它。
  • 由于被 p2 上了锁，p1 啥也干不了，所以它执行完 sb(s) 发现锁在后会被放回就绪列表；同时，p3 被放进了就绪队列。
  • p1 跑完以后，因为 p2 的优先权比 p3 大，所以继续运行 p2。
  • 因为 S 是 0，p2 执行完 S -= 1 之后被放进了等待列表（阻塞），同时把 s 锁解开。
  • 在 $t_1$ 的时候，就绪列表中因为 p1 的优先级比 p3 高，所以执行 p1。
  • 同样是因为执行完 S -= 1 之后 $S < 0$，p1 也被放进了等待列表中（阻塞）。
  • $t_2$ 的时候调度器选择运行 p3。
  • p3 执行了 V(S)，由此带动了 reactive() 函数，并把 p1 放回就绪状态。
  • p1 在 p3 执行完后，被从就绪状态中转换到运行状态，同时进程 p3 进入到了就绪列表中。
  • p1 运行完以后，p3 执行，p2 因此被移动到就绪队列。
  • p2 被执行。

整个过程 S 不会因为变成 0 而进入到忙碌等待的状态（然而，在 $t_0$ 的时候，p1 的运行是一个由于二元信号量锁引起的短时间忙碌等待，因为 s 被进程 p2 抢占了。即便如此，它依旧是比直接在 S 层面忙碌等待要高效，毕竟 s 的存在让 S 能够唤醒那些在等待队列的进程。）

管程

P() 和 V() 足以解决大部分的同步问题，但是由于过于着重在底层方面解决问题，要监视和检查起来很麻烦（代码分散，容易由于漏写操作导致死锁）。

管程(Monitor)，在更高的一个层面去实现 P() 和 V()。它和信号量是等价的^5。

条件变量(Conditional Variable)自带一个等待队列，进程可以等待这个队列中某些值变成真。

一个管程必须满足以下条件^5：

  1. 多个彼此可以交互并共用资源的线程/进程。
  2. 多个和资源使用有关的变量。
  3. 一个互斥锁（由管程自动管理）。
  4. 一个用来避免竞态条件(Race Condition)的同步机制。

条件变量有两种操作：

  1. wait: 停止进程，将进程放入等待队列，并且将进程和条件变量联系起来。
  2. signal: 重新激活在条件变量队列中的第一个进程（如果没有则不进行任何操作）。

我展示一下怎么用管程处理生产者消费者的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Monitor(){
  let product = 0;
  condition full, empty;

  consume_product(){
    if(product <= 0){
      full.wait(); // 没有产品，消费者等待
    }
    product -= 1;
    empty.signal(); // 消费了一个，通知生产者（如果有在等的）
  }

  produce_product(){
    if(product >= 缓冲区大小) {
        empty.wait(); // 缓冲区满，生产者等待
    }
    product += 1;
    full.signal(); // 生产了一个，通知消费者（如果有在等的）
  }
}

消费者 p1 执行 Monitor.consume_product() 时，因为没有产品可用，p1 阻塞并被扔到 full 的等待队列中。之后，生产者进程 p2 执行 Monitor.produce_product()，该函数给和 full 捆绑的等待队列发送了一个信号，p1 因此被释放，得以运行。由于管程的实现要求有互斥锁，所以 p1 一旦被释放，p2 会被阻塞（或者按照管程的具体实现，p1 被唤醒后需要重新竞争管程锁），并放入一个高优先权的等待队列。待 p1 执行完后才继续执行。通常来说等待队列是 FIFO 模式，但其实这个等待队列也可以用其他调度算法。

常见的同步问题

留坑，找个时间写一下分别用信号量和管程怎么解决这些问题。
但是其实网上有很多教程，这个坑怕是永远填不上了😄

  1. 读者写者问题(英)
  2. 哲学家就餐问题