[操作系统] 防止两个进程同时进入临界区的几种方法(尝试)

作者 Shilei Tian 日期 2017-03-17
[操作系统] 防止两个进程同时进入临界区的几种方法(尝试)

本文来探讨进程间通信(Inter Process Communication, IPC)中防止两个进程同时进入临界区的几种方法。首先我们先讲一下一个好的方法应该具备的四个基本条件:

  1. 不会有两个进程同时进入临界区。
  2. 该方法不会对 CPU 的运行速度和数量做任何假设。
  3. 在临界区外运行的进程不会阻塞其他进程。
  4. 不应该存在任何一个永远等待进入临界区的进程。

在各种方法上,大的方向分为:忙等待机制、信号量机制、monitor 机制、消息传递机制,以及一个多进程同步的 barrier 机制,我们一一展开说明。

忙等待(busy waiting)机制

禁用中断

忙等待机制的第一种方法就是禁用中断,意思就是说,一旦有某个进程进入了临界区,那么它就禁用中断。中断一旦禁用,CPU 将会变成该进程独占,不会有任何其他进程能够“夺走”它。这样做确实可以避免临界区冲突,但是后果就是禁用中断这种大事情交给了用户级进程,万一这个进程再也不释放了呢?

还有一个问题,就是这种情况虽然能够避免单核处理器的临界区冲突,但是它对多 CPUs 就似乎不那么奏效,因为它只能禁用运行它的那个 CPU。如果非要将多个 CPU 的中断一起禁用掉,那么还需要更多的更复杂的机制。

此外,这种方式虽然对临界区冲突奏效,但是它有可能会引起竞争条件(race conditioning,当多个进程都企图对共享数据进行某种处理,而最后的结果又取决于进程运行的顺序时,我们认为发生了竞争条件)。因此,这种方法现在几乎是见不到了。

锁机制

第二种尝试就是利用软件方法来解决该问题,设置一个变量,当没有进程进入临界区的时候,它设置为 0,当有进程在临界区时为 1。看起来这个好像没什么问题,但是实际上这种方法根本就不能防止临界区冲突。考虑下面这种情况:

int lock = 0;
Process_A() {
while (lock == 1) { /* wait… */ }
lock = 1;
enter_critical_region();
lock = 0;
}
Process_B() {
while (lock == 1) { /* wait… */ }
lock = 1;
enter_critical_region();
lock = 0;
}

考虑这样一种情况:进程 A 运行刚开始检测 lock 是否为 1,由于此时没有进程进入临界区,因此第 3 行的循环不会执行,马上就要执行第 4 行。恰好此时,进程调度器使进程 B 开始运行。由于上面进程 A 设置锁的那一条代码并没有开始执行,因此此时在进程 B 看来依然是没有进程位于临界区中的,因此第 9 行的循环也不会执行,进程 B 很顺利地进入临界区。如果进程 B 还没有退出临界区的时候,进程调度器又使 CPU 切换到进程 A 来执行,进程 A 会执行第 4 行并且也进入临界区。这时,冲突就发生了。

还有人尝试,可不可以进行两次检测,即如下所示:

int lock = 0;
Process_A_or_B() {
while (lock == 1) { /* wait… */ }
while (lock == 1) { /* wait… */ }
lock = 1;
enter_critical_region();
lock = 0;
}

道理也是一样的,无论执行多少次检测,这种方法都不能够完成任务。

严格变更(strict alternation)

第三种尝试的方式是严格变更,它使用下面的策略:

Process_A() {
while (1) {
while (turn != 0) { /* wait… */ }
enter_critical_region();
turn = 1;
noncritical_region();
}
}
Process_B() {
while (1) {
while (turn != 1) { /* wait… */ }
enter_critical_region();
turn = 0;
noncritical_region();
}
}

对于进程 A 而言,每次检测的是标记变量 turn 是否等于 0,如果不等于 0,就说明有别的进程已经进入临界区。如果等于 0,那么进程 A 进入临界区。下面是该方法的关键地方:在执行完临界区后,进程 A 将 turn 标记为 1,意思是告诉进程 B,我用完了,你可以用了。进程 B 此时第 11 行的循环就可以跳出,进入临界区,在退出临界区时将 turn 置为 0,意思是进程 A 可以用了。

这个逻辑看起来没问题,但实际上会引发大问题。考虑一种情况,进程 A 退出临界区后,进程调度器再次使 CPU 切换到进程 A 来运行,但是此时,turn 已经被置为 1,是为了给进程 B 用。而此时进程 B 并没有进入临界区,那么这样,进程 A 只能等待。这种通过每次都旋转标记变量的方式叫做旋转锁(spin lock)。这种方式规定了进程 A 进入完临界区后,必须进程 B 进入临界区并退出后进程 A 才能继续使用,这样就硬生生地加上了一个,而正是这个违背了上面我们提到的一个好的方法中的第三条,因为这里没有进入临界区的进程 B 会阻塞进程 A。这种情况在两个进程执行速度不匹配的时候尤为明显。

Peterson 算法

波兰数学家 T. Dekker 应该是第一位通过软件方法来解决了互斥问题的人,1981 年 G.L. Peterson 发现了一种更简单的方法,主要思路如下:

#define N 2
int turn;
int interested[N];
void enter_region(int process) {
int other = 1 - process;
interested[process] = 1;
turn = process;
while (turn == process && interested[other] == 1) { /* wait… */ }
}
void leave_region(int process) {
interested[process] = 0;
}

现在进程想要进入临界区,只需要调用函数 enter_region(process),离开的时候调用函数 leave_region(process) 即可。当一个进程想要进入临界区时,先将自己标记为“感兴趣的”,并将 turn 置为自己。此时,无论 CPU 如何调度,处于后面出现的进程总会覆盖 turn 并进入临界区。即使是当 CPU 调度回原来的进程,它会发现此时 turn 已经不是自己了,所以它就无法进入临界区。

TSL(Test and Set Lock) 指令

下面我们来看一种需要硬件上面稍微做一点支持的方法。很多电脑,特别是那些拥有多处理的电脑,都会有一条类似 TSL RX, LOCK 的指令。这条指令从 LOCK 指向内存读取一个字到寄存器 RX 中,并将向 LOCK 指向内存写入一个非 0 的值。那么 TSL 指令指令是如何保证上述操作不会受到进程调度的影响呢?通过对内存总线进行封锁。注意:这种方式与禁用中断有本质的不同。禁用中断只会对本 CPU 有效,对于其他处理器而言无效;但对内存总线上锁,其他的 CPU 也无法进行访存,当然这是在一个前提是所有 CPU 都共享同一个内存总线的基础上。现在几乎所有的处理器架构都是共享同一个内存总线。所以当上述这一系列操作在执行的时候,即使进程调度,其他进程也不会出现访问内存操作,所以 TSL 指令是安全的。

那我们看一下如何用 TSL 指令来实现互斥访问临界区的。

enter_region:
TSL REGISTER, LOCK
CMP REGISTER, #0
JNE enter_region
RET
leave_region:
MOVE LOCK, #0
RET

这一段指令利用汇编语言实现,每次将 LOCK 指向的内存中的数据取到 REGISTER 中,如果此时 LOCK 指向的内存中的数据是 0,那么 REGISTER 中就会是 0,且 TSL 指令执行完成后,LOCK 指向的内存将会被写入一个非 0 的值。所以,哪怕进程 A 执行完这一条指令后切换到进程 B 来执行,这时 LOCK 指向的内存中就不会是 0,所以下面就会重新跳回这一段指令的开头,不会引发临界区冲突。

TSL 指令的一个可替代指令是 XCHG,实现了原子地对两个位置的元素进行交换。所有的 Intel x86 处理器都使用 XCHG 来实现底层的同步。对于互斥访问临界区是如下实现的:

enter_region:
MOV REGISTER, #1
XCHG RESITER, LOCK
CMP REGISTER, #0
JNE enter_region
RET
leave_region:
MOVE LOCK, #0
RET

进入临界区那一段指令是先向 REGISTER 中写入 1,然后再用原子交换操作 XCHG 指令写入 LOCK,并将 LOCK 指向的内存中的内容拿回到 REGISTER 中。由于这一段操作是原子进行,因此 LOCK 中的数据为 1 就代表已经有进程在临界区中;如果 LOCK 中的数据为 0,就说明没有进程在临界区中,且此时 LOCK 中也是 1 了。因此,无论进程调度以什么顺序来执行两(多)个进程,都能保证互斥访问的效果。

休眠唤醒机制

Peterson 算法和使用一些类似 TSL 和 XCHG 指令确实能够达到互斥访问临界区的效果,但是它们都有一个缺点是忙等待。忙等待的意思是,一旦有进程在访问临界区,那么另外一个想要访问临界区的进程在运行过程中就一直不停的测试,查看能否访问,这样就造成 CPU 资源的严重浪费。休眠唤醒机制是指,当进程发现无法立即访问临界区的时候,就挂起(休眠或称阻塞),此时进程调度器会选择另外的进程过来运行,这样就实现了 CPU 资源的高效利用。

生产者-消费者问题

这是一个非常非常经典的 IPC 问题,基本上所有学校的操作系统课程都会作为重点来讲。该问题主要描述的是,有两个进程 P 和 C,一个固定大小的缓冲区 buffer。进程 P 每次检查缓冲区是否满,如果没有,就生产一个产品放到缓冲区中;如果满了的话,就自行休眠。进程 C 每次检查缓冲区是否空,如果没有,就取走一个产品;如果为空,就自行休眠。伪代码如下:

#define N 100
int count = 0;
void producer() {
while (1) {
int item = produce_item();
if (count == N) { sleep; }
insert_item(item);
++count;
if (count == 0) { wakeup(consumer); }
}
}
void consumer() {
while (1) {
if (count == 0) { sleep(); }
int item = remove_item();
--count;
if (count == N - 1) { wakeup(producer); }
consume_item(item);
}
}

上面的代码很容易引起竞争条件,考虑这样的情况:当 count0 时,进程 C 检查当前 count 发现为 0,此时调度器让进程 P 运行,它检查当前 count0,因此它生产一个产品,并调用 wakeup 函数。而此时进程 C 并没有进入休眠状态,所以 wakeup 函数会不了了之。此时进程 C 重新回到运行状态,它会继续前面的状态执行,亦即会进入休眠状态。进程 P 接管过来 CPU,继续生产一直到缓冲区填满后,进入休眠状态。这样,两个进程都进入休眠状态。

问题就出在唤醒机制上,如果唤醒信号不会丢失的话,那么就不会出现上面说的这种竞争条件问题。所以可以设置一个标记位,如果有进程打算休眠时,它会先检查这个标记位,如果该位为 1,它就不会休眠。

但是,如果我们有多个生产者和消费者,一个标记位就不够用,那样问题就变得很复杂了,但问题的本质还是没有被解决。

信号量(semaphore)

这个概念是 E. W. Dijkstra 在 1965 年的时候提出来的,他提议设置一个整数变量来记录我们可以用多少次 wakeup,被称为信号量。他提出在信号量上可以有两种操作:downupdown 操作每次检查信号量是否为 0,如果不是,就将信号量的值减 1,然后继续运行;否则,进程进入休眠状态,并且 down 操作是没有完成的。什么叫没完成呢?就是一旦被唤醒,down 操作还会继续执行。所有的检查、修改操作都是原子执行的。up 操作就很简单了,增加信号量的值,并检查如果有进程处于休眠状态,系统就会选择一个进程进行唤醒。被唤醒的进程会重新执行 down 操作。

有些教材或者材料里面会用 PV 来描述信号量的操作,这是因为 Dijkstra 在提出来的时候用到的正是这两个标志,源于荷兰语中的 Proberen (try)Verhogen (raise, make higher)

那我们来看看如何用信号量来解决生产者-消费者问题。

#define N 100
typedef int semaphore; // semaphores are a special kind of int
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void producer() {
while (1) {
int item = produce_item();
down(&empty);
down(&mutex);
insert_item(item);
up(&mutex);
up(&full);
}
}
void consumer() {
while (1) {
down(&full);
down(&mutex);
int item = remove_item();
up(&mutex);
up(&empty);
consume_item(item);
}
}

注意:无论是对于生产者还是消费者而言,两个 down 操作都不能颠倒顺序。假如生产者中两个 down 操作交换了位置,即先进行 down(mutex),然后再进行 down(empty),那么如果 empty0,此时生产者会阻塞,并且 mutex 并没有被释放。消费者会一直得不到 mutex 也一样阻塞,这样就形成了死锁。

有一个简化版本的信号量——Mutex,它只能是锁或者不锁两个状态。在一些线程库中,mutex 的实现完全在用户层。

管程(Monitor)

不太明白为什么要把 monitor 翻译成管程,从名字上一点都看不出来它和互斥访问有什么关系。下面我们直接用 monitor 本身,而不会用管程这个名字。

为什么要引入这个概念呢?其实就是我们上面刚刚提到的,生产者消费者问题用信号量来做的时候,要注意两个 down 操作的顺序,这就说明我们要非常小心地使用信号量。

为了让上面的操作变得更加方便,就有人提出了一种高层的同步指令:monitor。它的定义是:monitor 是一系列操作、变量、数据结构的集合,它们组合在一起形成一个特殊的模块或包。进程可随心所欲地调用 monitor 里面的操作,但是它们不能通过定义在 monitor 外的操作直接访问到 monitor 里面的数据结构。

这里必须要说明的是,monitor 是一种编程语言上的概念,因此这个概念是语言相关的。现在已知 Java 支持 monitor,而 C/C++ 并不支持这个概念。

monitor 有一个很重要的性质,这个性质实现了互斥访问:在任何时候,最多只有一个进程访问 monitor。由于 monitor 是一种语言结构,因此互斥访问的工作就交给了编译器来做。一般来说,monitor 操作的前几条指令就是来确保没有进程正在操作 monitor,如果有,那么进程就挂起。编译器通常也是使用 mutex 或 binary semaphore 来实现的,这些操作对于编程人员来说是透明的,他们只需要知道,扔在 monitor 里面的操作是不会发生临界区冲突的。

下一个问题就是,如何实现进程的阻塞?因为有了 monitor 的概念后,我们可以保证进程访问临界区是没有冲突的,但是对于进程之间的同步又怎么样实现?就拿生产者消费者问题来说,当生产者发现缓冲区满了以后,生产者该如何阻塞?

这里需要引入另一个概念——条件变量(condition variables),在它上面有两个操作:waitsignal。当一个 monitor 的操作发现它没法进行下去了,它就对某个条件变量执行 wait,这样就会使调用的进程阻塞,也会允许之前无法进入 monitor 的进程进入。对于其他进程而言,可以对相应的条件变量执行 signal 操作,来唤醒因为该条件变量而阻塞的进程。为了防止 signal 操作后两个进程同时进入 monitor,我们需要规定一下 signal 操作的操作。一种可能的实现方案是,新唤醒的进程执行,以前的进程挂起;另外一种是调用 signal 操作的进程必须立即退出 monitor,也就是说,signal 只能作为 monitor 操作的最后一条指令;还有一种是,调用 signal 的进程继续执行,唤醒的进程就等待该进程结束。

注意:条件变量并不是计数器,因此它不会像是信号量一样,汇集 signal 操作以备后续,对于信号量的操作,如果没有人 wait,那它就丢失了。这就要求,wait 操作必须在 signal 之前执行,否则 signal 操作就白费了。

消息传递(message passing)

我猜这个应该就是国内教材中所谓的消息队列所指的那种方法吧?进程间的通信是通过两个指令 sendreceive 来实现的,这两个指令就是系统调用了,而不是语言特性。使用 send 操作能够将消息发往指定接收者,调用 receive 操作能够接收来自指定发送者的消息,当然,也可以不指定发送者。当没有消息发送过来时,调用 receive 的进程将会阻塞。

在设计消息传递的时候,需要面临的几个问题,比如位于网络上的两台主机,如何保证消息的到达(你会说这个怎么能算是进程间通信?其实不然,一个 IP 地址加上一个端口号就能够在 Internet 上确定唯一的进程,两台主机之间的通信,说到底就是两台主机上的两个进(线)程之间的通信)?这个时候通常会有 ACK 机制,那么紧接着的问题就是如何确定重传的消息到底是不是真的重传的等一系列问题,想必如果你了解 TCP 为提供可靠服务实现的一些技术,这个问题你也就明白了。再比如,消息是怎么传递的?网络上那种通过 TCP 的我们不考虑,我们就考虑一台电脑上的两个进程之间怎么通信?因为每个进程之间的内存空间是相互隔离的,从一个进程想要发送一条消息到另外一个进程,必然要涉及到内存的复制,这种操作显然要比使用信号量或者 monitor 要低效很多。有一种做法,是将消息设计成寄存器大小的数据,这样内存的复制就避免了,进行寄存器操作将要快得多。

那我们接下来看一下如何利用消息传递并且不使用共享内存的方式来解决生产者消费者问题,代码如下:

#define N 100
void producer() {
while (1) {
int item = produce_item();
message m;
receive(consumer, &m);
build_message(&m, item);
send(consumer, &m);
}
}
void consumer() {
message m;
for (int i = 0; i < N; ++i) send(producer, &m);
while (1) {
receive(producer, &m);
int item = extract_item(&m);
send(producer, &m);
consume_item(item);
}
}

这里我们从消费者开始讲起。注意到消费者上去先向生产者发送了 N 个消息,你可以这样理解:货物是通过篮子传送的,消费者如果想要拿到货物,先要将自己手头所有的空篮子(N 个)发给生产者。生产者只有在手头有空篮子的情况下才会进行生产并发货,否则就等待。这个所谓的有篮子的情况,指的就是生产者中的 receive 函数所进行的操作。通过这种方式,系统中的消息个数一直都是固定的 N 个。至于那些没有被消费但已经发出的消息,这些都是由操作系统负责保管,应该就是用队列机制进行的,所以才有了消息队列这种说法吧。

Barrier 机制

前面我们所讲的这些机制,都是保证两个进程不会同时进入临界区域,以及为了防止发生竞争条件而设计的。在本文的最后,我们讲述一种被称为 barrier 的机制,来保证多个进程之间的同步。