《现代操作系统》—— 进程间通信问题

任何可能出错的地方终将出错。 —— Murphy定律

前言

阅读前面的文章，我们已经知道了进程是操作系统对正在运行的程序的抽象。现代操作系统中，进程通常需要和其他进程进行通信。我们称之为进程间通信 问题。又叫做IPC（Inter Process Communication） 问题。IPC主要解决以下3个问题：

• 一个进程如何把信息传递给另一个进程
• 多个进程在同一个任务中不会出现交叉，即多个进程竞争同一个资源
• 多个相互关联的进程间执行顺序的问题，典型的生产者——消费者问题

上述3个问题中的后2个问题对于线程是同样适用的。所以本文中针对于后2个IPC问题的解决方案同样适用于线程。所以，本文标题虽然叫做进程间通信问题，但其中介绍的方案和思想，同样也适用于线程间通信问题。如下是本文涉及到的一些进程/线程间通信的关键名词：

• 竞争条件
• 共享内存
• 互斥（排它性）
• 临界区
• 忙等待
• 自旋锁
• 互斥量
• 条件变量
• 优先级反转

竞争条件

操作系统中的共享数据通常包括共享内存、共享文件、共享任何软硬件资源，这些我们都称之为共享数据。而在实际的软件开发中，我们遇到的共享数据通常是共享内存。

两个或多个进程读写某些共享数据，而最终的结果取决于进程运行的精确顺序，称为竞争条件（race condition）。竞争条件的症结在于进程A对共享数据的使用尚未结束，进程B就开始使用同样的共享数据。调试存在竞争条件的程序是一件非常麻烦的事，它们在大多数情况下运行良好，仅在极少数场景下会发生无法解释的现象。遇到类似问题时可以考虑竞争条件（多线程也是如此）。另外，多核增长带来的真并行使得竞争条件越来越普遍。

互斥

我们已经知道了竞争条件出现的原因，那如何避免出现竞争条件？要避免这种错误，关键是要找出某种途径来组织多个进程同时读写共享的数据，换言之，我们需要的是互斥（mutual exclusion）。互斥的本质是排他性，即确保当一个进程在使用一个共享变量或其他共享数据时，其他进程不能同时的操作。为了实现互斥而选择适当的原语是任何操作系统的主要涉及内容之一。

临界区

操作系统中，我们把访问共享内存的程序片段称为临界区（critical section）。临界区是访问共享数据的一段代码，而不是一段内存区域。所以编写临界区代码的时候，需要格外小心。

避免竞争条件

我们已经知道了共享内存、竞争条件、临界区。也知道了通过进程间的互斥可以避免发生竞争条件。所以，可以得出，任何两个进程不同时处于其临界区即可有效的避免竞争条件。但这只是必要条件，避免竞争条件的好的解决方案需要满足一下4个条件原则：

• 任何两个进程不能同时处于其临界区
• 不对CPU的速度和数量做任何的假设
• 临界区外运行的进程不能阻塞其他进程
• 不能使进程无限期的等待进入临界区

从抽象的角度看，理想的进程行为如下图所示，在进程A离开临界区之前，进程B无法进入他自己的临界区，直到进程A离开后释放共享内存。

image.png

临界区

（忙等待）互斥

所谓忙等待（busy waiting），是指连续测试一个变量直到某个值出现为止 本质：当一个进程想要进入临界区时，先检查是否允许进入。若不允许，则该进程原地等待，知道允许为止。 这种方法浪费CPU时间，还可能引起预想不到的后果——优先级反转问题。

屏蔽中断

屏蔽中断是一种进程忙等待互斥方案。其思路是：每个进程在刚刚进入临界区后立即屏蔽所有中断，并在离开临界区之前再打开中断。屏蔽中断后，时钟中断也会被屏蔽，所以就不会发生进程的切换。因为CPU只有发生时钟中断或其他中断时才会进行进程的切换。这样，一旦某个进程进入临界区，屏蔽中断后就可以放心大胆的修改共享内存，也不会担心在离开临界区之前其他进程进入。

这个方案的缺点也显而易见的。缺点：

• 把屏蔽中断的权力交给用户进程是不明智的。
  • 一方面，如果一个进程屏蔽中断后不再打开中断，其它进程无法获取CPU，遇到恶意程序，整个系统可能会终止。
• 屏蔽中断无法解决多处理器或多核处理器同时访问共享内存。
  • 在一个多处理器系统中屏蔽中断只是对执行disable指令的哪个CPU有效，其他CPU仍可以继续运行，且可以访问共享内存。
  • 在一个多核系统中（例如多处理器系统），屏蔽一个CPU核心的中断不会阻止其他CPU干预第一个CPU的所作的操作。所以，屏蔽中断在多核CPU上也不实用。

综上，屏蔽中断对于操作系统本身而言是一项很有用的技术，但对于用户进程不是一种合适的、通用的互斥机制。一方面，不应该把屏蔽中断交给用户进程，另一方面，屏蔽中断也无法解决多核CPU访问共享内存的问题。

锁变量

既然屏蔽中断无法解决竞争条件问题。欧威第二种方式，可以寻找一种软件解决方案。该方法是设置一个共享（锁）变量。其初始值为0，代表没有进程进入临界区。当一个进程想要进入临界区时，他首先测试这把锁。如果该锁的值为0，则该进程将其设置为1并进入临界区，若这把锁的值为1，则该进程将等待直到锁变量变为0。

但这个方法也无济于事，因为他引入了一个新的共享内存（锁变量）。还是会存在两个进程同时设置锁变量问题。假设一个进程A读取锁变量并发现值为0，然后在将要把锁变量设置为1之前，发生了一次时钟中断。时钟中断导致另一个进程B被调度，当前进程A被挂起，进程B同样去读取锁变量，发现其值也是0，于是将锁变量设置为1。当进程A再次运行时，它继续上次未完成的操作——将锁变量设置为1，并进入临界区。到此为止，进程A、B都进入了临界区，即两个进程同时访问了共享内存。

严格轮换法

我们上面已经介绍过，连续测试一个变量一直等到某个值出现为止，这种方式成为忙等待。所以，不同的测试一个值（通常是一个while循环）是比较浪费CPU时间的，所以通常应该避免。我们只有在有理由认为等待时间是非常短的情况下，才可以使用忙等待。而自旋锁就是一种忙等待的锁。所以，其性能可想而知。

严格轮换法的思路是：假设两个进程，分别是进程0、进程1，同时又一个整型锁变量turn，其初始值为0。进程0在锁变量为0时可以进入临界区，退出临界区之前将锁变量设置为1。进程1在锁变量为1时可以进入临界区，退出临界区之前将锁变量设置为0。严格轮换法虽然能解决竞争条件问题，但是因为存在进程被临界区外的进程阻塞的情况。导致必须要依赖临界区外的进程执行完成才能执行。这违反了上述的第三条原则“临界区外运行的进程不能阻塞其他进程” 这并不是一个好的方法。具体原因是：

• 首先，turn初始值为0，进程0尝试进入临界区，测试turn为0，符合进入临界区条件，于是进程0进入临界区
• 然后，进程0离开临界区，把turn设置为1，此时只有进程1可以进入临界区
• 最后，进程0结束非临界区的操作并返回到while循环的开始，因为turn的值之前被进程0置为1，所以进程0不能进入临界区，需要等待非临界区的进程1把turn置为0，而此时进程1还在忙着非临界区的操作。这样依赖，进程0就被进程1阻塞了。进程0什么时候能够再次运行，取决于进程1什么时候访问并离开临界区后把turn置为0。

假设进程0和进程1是严格轮换的，上述问题就不存在了。所谓严格轮换就是进程0和进程1依次的交替轮流访问临界区，即0、1、0、1、0、1... 但这显然是不现实的。 严格轮换的顺序是：

• turn为0，进程0访问临界区，进程1忙等待
• 进程0离开临界区，turn被进程0置为1
• turn为1，进程1进入临界区，进程0忙等待

一旦进程0、1没有严格轮换，那么进程0离开临界区后将turn置为1，想要再次进入临界区需要等待进程访问并离开临界区后1把turn置为0。进程1会不会访问临界区以及什么时候访问临界区是不可预知的。这样就产生了“临界区外运行的进程（此处为进程1）不能阻塞其他进程（将要访问临界区的进程0）”

image.png

Peterson解法

Peterson解法也是一种软件解法。该算法由2个ANSI C编写的过程（函数）组成。ANSI是美国国家标准学会的缩写。ANSI C规定C语言为所定义的函数提供函数原型，也就是声明。下图是两个C函数。其工作原理是：

• turn表示轮到哪个进程访问临界区
• 如果intersted数组中的其他进程是TRUE则忙等待，否则可以进入临界区
• 如果两个进程几乎同时调用enter_region，他们将自己的进程号存入turn，但只有后赋值给turn的进程号才有效。假设进程1后写入turn。运行到while语句时，turn为1，他们各自的process分别是0、1。于是进程1while语句的条件turn === process && interested[other] == TRUE为真，所以进程1忙等待。而进程0的while语句的turn和process不等，那么进程0循环0（不需忙等待）直接进入临界区。

image.png

巧妙之处

这个算法的巧妙之处在于使用2个变量来实现进程的互斥操作。2个变量配合完成互斥操作，缺一不可。turn是一个整型变量，代表当前要访问临界区的进程号。interested是一个数组变量，且数组下标是进程号，这样对这个数组每个下标的操作就不存在多进程同时操作数组同一个元素的问题。这确实是一个巧妙之处。如果多进程同时操作了turn也不要紧，以后写入的为准，并且还会参考interested对应下标的值。

TSL指令

TSL指令是一个需要硬件支持的方案。TSL称为测试并加锁（test and set lock）。他将一个内存字LOCK读到寄存器RX中。然后在该内存地址上存一个非零值。读字和写字操作是不可分割的，即该指令结束前其他处理器均不允许访问该内存字。执行TSL指令的CPU将锁住内存中线，以禁止其他CPU在本指令结束前访问内存。TSL指令解决了忙等待的屏蔽中断方案中无法屏蔽多处理器访问共享内存的问题。 因为锁住内存总线不同于屏蔽中断，锁住内存总线后，所有处理器都无法通过内存总线访问内存字。 那些多处理器的计算机都有TSL指令。如下：

TSL RX, LOCK
复制代码

如下2个图，分别是用TSL指令和XCHG指令实现的进入和离开临界区：

image.png

image.png

（睡眠与唤醒）互斥

忙等待互斥的基本原理是：一个进程进入临界区前，先检查是否允许进入，即是否有其他进程正在临界区内，如果不允许进入临界区，则原地等待并不同的检测，直到进入为止。忙等待的缺点也是显而易见的：因为在忙等待的过程中，进程会不断的检测是否可以进入临界区，所以忙等待会浪费CPU的时间。

另一方面，忙等待也会带来优先级反转问题。所谓优先级反转，即高优先级的进程（线程、任务）被低优先级的进程（线程、任务）阻塞的一种现象。

比如，有两个进程H、L。H进程优先级高、L进程优先级低。调度规则规定只要H进程处于就绪状态就可以运行。但如果某一时刻，L处于临界区中，H突然从阻塞态变为就绪态，所以调度程序准备运行H。因为H就绪时L不会被调度，所以L无法离开临界区中。L没有离开临界区，H只能忙等待。所以最后的结果是H一直忙等待、L一直等待被调度。产生了一种类似于"死锁"的优先级反转的现象。

因为忙等待的CPU性能问题，所以需要考虑一种非忙等待的方式避免竞争条件。即在进程无法进入临界区时使进程进入阻塞态而不是忙等待。睡眠与唤醒就是这种方式的实现。

生产者——消费者问题

生产者——消费者问题（producer-consumer），又称为有界缓冲区问题（bounded buffer）。其通常是解决多个进程/线程协同的工作的问题。以两个进程为例，一个是生产者，一个是消费者。它们共享一个公共的固定大小的缓冲区。生产者负责生产数据并放入缓冲区，消费者负责从缓冲区读取数据并消费。当然，生产者和消费者数量可以不是1个，也可以把这个问题一般化为m个生产者和n个消费者问题。

该问题在于当缓冲区被生产者生产的数据塞满，而此时生产者还想向缓冲区放入新的数据时。其解决办法是让生产者睡眠，当消费者从缓冲区取出一个数据时（此时缓冲区有空闲的空间），再唤醒生产者，生产者得以继续生产数据。同样，消费者从缓冲区中取数据发现缓冲区中数据个数为0，那么消费者就会睡眠，当生产者发现缓冲区的数据增加到1时，生产者会再唤醒消费者。

但这里存在竞争条件。为了跟踪缓冲区的数量，需要一个整型变量count来记录缓冲区中数据量以及设置一个缓冲区的组大容量N。当count达到N时，让生产者睡眠；当count达到0时，让消费者睡眠。当count从N降为N-1时，消费者唤醒生产者；当count从0变为1时，生产者唤醒消费者。

为什么会出现竞争条件呢？本质的原因是会存在发送给一个尚未睡眠的进程/线程的信号丢失了。因为我们没有对count的访问加以限制。可能会出现这种情况：缓冲区为空，即count = 0，消费者读取的count == 0，此时消费者准备睡眠，但在消费者睡眠之前调度程序决定暂停消费者，消费者被挂起但未在逻辑上睡眠。生产者生产一项数据并放入共享缓冲区，此时count从0 变为 1，所以生产者认为刚才消费者读取了count为0，此时消费者肯定在睡眠，于是生产者就调用weakUp唤醒消费者。但因为消费者在逻辑上并没有睡眠而是被调度程序挂起，这样导致信号被丢失了。当消费者下次被调度并运行时，它判断先前读取到的count为0，认为共享缓冲区为空（而实际上缓冲区已经有数据了），所以消费者进入睡眠。这样种情况下，消费者没有被唤醒，生产者不断的生产数据直到填满缓冲区，最终生产者也进入了睡眠。这两个进程都将一直睡眠下去。

# define N 100
int count = 0;

void producer(void) {
    int item;
    while(TRUE) {
        item = produce_item();
        if (count == N) { sleep(); }
        insert_item(item);
        count += 1;
        if (count == 1) { weakUp(cousumer); }
    }
}

void cousumer(void) {
    int item;
    while(TRUE) {
        if (count == 0) { sleep(); }
        item = remove_item();
        count -= 1;
        if (count = N -1) ( weakUp(producer); )
        cousume_item(item);
    }
}

信号量

上面我们了解到，生产者——消费者问题的竞争条件本质原因是生产者发送给消费者的weakUp丢失了。可以用信号量解决丢失的weakUp问题。信号量是一个整型变量，用来累计进程/线程被唤醒的次数，供将来使用。信号量大于0时，代表将要有一个或多个唤醒操作；信号量为0时，代表没有唤醒操作。笔者之前写过一篇iOS的信号量相关文章，其底层就是操作系统的信号量机制。

信号量是一个整型变量，所以他有2种操作：down、up。

• down：该操作会对信号量执行减一操作。对一个信号执行down操作，会检查其值是否大于0，若大于0，则会将值减一，然后进程/线程继续向下执行自己的任务。若该值为0，则不会对其进行减一操作，而是会让进程/线程睡眠。等待信号量的值大于0。
• up：该操作会对信号量执行加一操作。对一个信号执行up操作，首先信号量的值会加一。加一之后，信号量的值肯定大于0，如果此时有进程（一个或多个）在该信号上睡眠（即有进程/线程等待该信号量）。则系统会选择一个等待该信号量的进程/线程。等待该信号量进程/线程随后会执行down操作，信号量随即会被减一。所以，对有进程在其上睡眠的信号量而言（或者说有进程等待的信号量而言），对该信号量执行up操作后会立即执行down操作，信号量值没有发生变化，但在该信号量上睡眠的进程少了一个。因为信号量从0变为1时，系统会选择一个等待该信号量的进程获得该信号量，获得该信号量的进程会对该信号量减一，然后该进程不再睡眠，继续执行。

用信号量解决生产者-消费者问题

用信号量解决生产者-消费者问题。操作系统在执行以下操作是暂时屏蔽全部中断：测试信号量、更新信号量，以及在需要时(信号量为0时)需要让进程睡眠。

该解决方案使用3个信号量：

• full：用来记录填充的缓冲槽，即缓冲的数据项的数量。初始值为0，因为没有生产数据项。
• empty：用来记录空的缓冲槽，即缓冲区的空闲的曹数。初始值为缓冲区中的缓冲槽数，因为没有生产数据项。
• mutex：一个互斥量，确保生产者和消费者不会同时访问缓冲区。初始值为1。互斥量是一个处于两态之一的变量，所以又称为二元信号量。

# define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer(void) {
    int item;
    while (TRUE) {
        item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void cousumer(void) {
    int item;
    while (TRUE) {
        down(&full);
        down(&mutex);
        item = remove_item();
        up(&mutex);
        up(&empty);
        consume_item(item);
    }
}

信号量empty/full用来保证某种事件的顺序发生或不发生。在上例中，信号量保证缓冲区满的时候生产者停止运行，缓冲区空的时候消费者停止运行。

信号量的另一种用途是用来解决进程/线程同步执行的问题。比如异步网络请求的顺序执行就可以使用信号量。可参考笔者之前的iOS中用信号量实现异步任务同步执行。

互斥量

互斥量可以看做是信号量的简化版。如果不需要信号量的计数能力，可以使用互斥量。 互斥量是一个处于两态之一的整型变量，所以又称为二元信号量。互斥量仅适用于管理共享资源或一小段代码，在允许或阻塞对临界区的访问上是很有用的。即通常用来解决多线程的竞争条件问题，同一时刻只允许一个线程访问临界区，使得多个线程同步的、顺序的访问临界区。由于互斥量在实现时简单且有效，所以互斥量在实现用户空间线程包时非常有用。

和信号量一样，互斥量也是一个整型变量，它有2个状态：解锁、加锁。所以互斥量只需要一个二进制位即可表示。0表示解锁、非零值表示加锁。互斥量有2个过程（函数）：mutex_lock、mutex_unlock。mutex_lock用于加锁、mutex_unlock用于解锁。

互斥量的工作机制：当一个线程访问临界区时，会先调用mutex_lock，如果互斥量当前是解锁的（为0），则代表当前没有其它线程处于临界区中，临界区可用。调用线程会加锁并进入临界区。相反，如果互斥量当前是加锁的（非0），则代表当前有线程正处于临界区中，临界区不可用。调用线程会被阻塞，直到临界区中的线程完成并调用mutex_unlock解锁。如果多个线程被阻塞在该互斥量上（即有多个线程要访问同一个临界区），则随机选择一个线程并允许他获得锁。

因为互斥量非常简单，所以操作系统有可用的TSL或XCHG指令即可很容易的在用户空间实现它。如下：

mutex_lock:
    TSL REGISTER, MUTEX
    CMP REGISTER, #0
    JZE ok
    CALL thread_yield
    JMP mutex_lock
ok: RET

mutex_unlock:
    MOVE MUTEX, #0
    RET

pthread中的互斥量

pthread中提供了许多可以用来同步线程的函数。如下：

互斥量在允许或阻塞对临界区的访问上是很有用的。条件变量则允许线程由于一些未到达的条件而阻塞。基于互斥量的实现是互斥锁。基于条件变量的实现是条件锁。 条件变量和互斥量经常一起使用：一个线程锁住一个互斥量，用于对一个临界区(共享缓冲区)执行排他性操作而不是其他线程干扰。然后线程不能获得其他的结果时等待一个条件变量，直到另一个线程向它发送了信号，使得它可以继续执行。

管程

虽然引入了信号量和互斥量之后，解决了进程间通信的竞争条件问题。但这并没有让进程间通信变得容易，开发者需要谨慎的加锁、解锁。还要考虑各种锁的先后顺序，编程的复杂度被大大提升，反而可能写出错误的代码，导致严重的后果，比如死锁。

为了更易于编写正确的程序，Brinch Hansen(1973)提出了一种高级同步原语，称为管程。管程是一个由过程、变量及数据结构等组成的一个集合，听起来像是面向对象编程里面的一个类对象。

进程可以在任何需要的时候调用管程中的过程，但不可以在管程之外声明的过程中直接访问管程内的数据结构。换言之，进程只可以调用管程中的过程，而不能访问管程的变量。

管程不是系统调用，它是编程语言范畴内的概念，属于编程语言的一部分。它只存在于某些编程语言中，C语言不支持管程。

消息传递

信号量和管程用来解决多进程/多线程访问共享内存（临界区）或多个CPU上的互斥问题是有效的。但在分布式系统中，存在多个CPU，并且每个CPU拥有自己的私有内存，他们通过局域网通信，没有所谓的共享内存，以上介绍的诸如信号量、管程的原语将无济于事。原因是：信号量、管程等这些原语无法提供机器间的信息交换。所以还需要一种其他进程间通信的原语。这里介绍的就是消息传递（message passing）。

消息传递这种进程间通信方式使用2个通信原语：send、receive。他们和信号量的up、down一样都属于系统调用，而不像管程属于语言成分。所以，我们可以很容易的将他们加到系统库中。例如：

1. send(destination, &message)
2. receive(source, &message)

以上这两个过程分别代表想目标进程发送一个消息和从源进程接收一个消息。

屏障

前面介绍了信号量、互斥量、管程的用于进程、线程间的同步互斥机制。也介绍了消息传递这种同步互斥机制。下面介绍的内存屏障（barrier）也是一种进程/线程的同步机制。但他通常适用于一组进程/线程。简单的说：假设有一组4个进程构成了一个相关的进程组，当其中一个进程到达屏障时，它会被挂起，知道组内的其他进程都到达屏障，它们才能够一起被放行。如下图所示：

image.png

在多线程中，屏障也多有应用，比如有3个异步的子线程网络请求，我们需要3个网络请求都返回后才允许执行下一步的任务，此时可以使用屏障。

QA

操作系统为什么用C语言编写？ 操作系统的底层都是使用C语言或类C语言（C++）编写的。而基本上不用像Java、Modula3、Pascal这样的语言。因为C语言是强大、高效、可预知和有特性的语言。而对于Java，他就是不可预知的，他在关键时刻可能会用完存储器。它的垃圾回收机制也可能在不合适的时机调用垃圾回收程序回收内存。笔者总结了C语言作为操作系统御用语言的原因，主要从跨平台、运行效率、内存管理等方面介绍：

• 成熟度高的语言。
  • 开发操作系统的语言必须是一门成熟的语言。成熟的语言背后的逻辑是：1.语言本身比较完善，符合一定的国际标准。2.现有工具库比较丰富。3.有足够多的活跃者。
• 最好是开源语言。
  • 最好是开源语言，这样对于厂商来说不存在版权问题。另一方面，开源的语言拥有更多的社区活跃者和贡献者，语言和社区本身的成熟度高。
• 必须是跨平台语言。
  • 某些操作系统内核需要具备可移植性，可以在Linux、Unix、macOS、Windows等系统上移植，一门跨平台语言是首选。
• 必须是编译型语言。代码编译完成再运行。
  • 一方面可以前置检查语法错误，在编译期间进行各种检查，而不是到了解释期再报错，使用解释型语言对于操作系统是灾难性的。
  • 另一方面可以保证运行时效率。编译型语言使用编译器编译成更低级的汇编代码或机器码，这样可以直接运行而无需运行时解释，其运行效率比解释型语言高。
• 内存管理要明确清晰。
  • 操作系统的内存管理要非常严格。通常需要编写操作系统的开发者手动开辟/释放内存。而对于有垃圾回收机制的语言来说，比如Java，显然是做不到的。因为把内存回收交给Java语言，内存可能在回收之前就已经满了，也可能在使用之前就已经被回收了。所以，把内存管理交给开发者是比较明智的。
• 开发时间和软件效率之间取一个平衡。
  • 有人说，使用C语言开发系统比其他语言麻烦，但我们不能忽略C语言运行和内存管理等方面的高效性。一方面，操作系统属于底层代码，其运行效率和稳定性非常重要。另一方面，操作系统效果对于上层软件代码的迭代频率低，操作系统的内核几年甚至十几年都变化甚微，所以所谓的使用C语言开发麻烦，在操作系统上也只是“麻烦一次”。

文／VV木公子（原创作者）

PS：如非特别说明，所有文章均为原创作品，著作权归作者所有，转载请联系作者获得授权，并注明出处！