This post was written in Chinese, ReadOriginal Post.
Since this post has not been translate to English, Please use the tool provided to translate.

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

进程竞争

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

解决方案

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

  1. 互斥锁(mutual exclusion)：资源每次只允许一个进程访问。
  2. 不能封锁(Lockout, 找不到对应的翻译)：一个没有在用资源的进程，不能阻碍别的进程对这个资源进行访问。
  3. 防止饥饿(starvation)：一个进程不能一直快速的访问某个资源，以至于其它进程停滞。
  4. 防止死锁(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更新， 因此resource依旧是0。进程2将resource变成了3, 之后调度器才把进程1重新运行。进程1在这个基础上再加5就变成了8。对于进程1来说，这个结果显然不对$\left(0+5=8\right)$

遵循上面的5个原则，我们改善一下代码。 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)有时候也叫信号灯，是能统一解决并发问题的方案。信号量是一个非负数的值。它只能接受两种操作：

操作 S > 0 S = 0
a(S) S+1 S + 1
s(S) S - 1 等到 S > 0 再减1

信号量必须要保证:

  1. 当有多个进程都在对信号量操作的时候，它会按照一定的顺序来执行
  2. 如果多个进程在s = 0的时候都在等待s()，有一个进程必须进行a()操作。

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

semaphores

在t0的时候进程2使用a()函数给信号量加1，在t1的时候进程1和2同时增加信号量。这个量会被分别增加，避免无效。在t8的时候，两个进程同时减信号量，但是因为不够，系统随机阻塞进程1。直到t11进程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()的实现

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

这个S值有两个作用

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

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

先上代码：

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

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

bs

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

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

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

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

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

监视器

a()和s()足以解决大部分的同步问题，但是由于过于着重在底层方面解决问题，要监视和检查起来很麻烦。

监视器(Monitor)，或称管程【噗嗤】，在更高的一个层面去实现a()和s()。它和信号量是等价的^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
Monitor(){
  let product = 0;

  consume_product(){
    if(product <= 0){
      wait();
    }else{
      product -= 1;
    }
  }

  produce_product(){
    product += 1
    signal();
  }
}

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

常见的同步问题

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

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