进程间通信
进程经常需要与其他进程通信。进程间通信 ( $Inter\ \ Process\ \ Communication$, $IPC$ ) 最好使用一种结构良好的方式并且不要使用中断。进程间通信存在三个问题：一个进程如何把信息传递给另一个，如何确保两个或更多的进程在关键活动中不会出现交叉，以及进程之间执行顺序的正确性。
在一些操作系统中，协作的进程可能共享一些彼此都能读写的公用存储区，可能是一块内存，也可能是一个共享文件。当两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，就称为竞争条件 ( $race\ \ condition$ )。包含有竞争条件的程序在大多数情况下都不会出错，但在极少数情况下会产生一些奇怪的现象，尤其是在多核环境中更为明显。而要避免竞争条件带来的错误，关键是要找出某种途径来阻止多个进程同时读写共享数据。换言之，我们需要的是互斥 ( $mutual\ \ exclusion$ )，即以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。
避免竞争条件的问题也可以用一种抽象的方式进行描述。一个进程的一部分时间做内部计算或另外一些不会引发竞争条件的操作。在某些时候进程可能需要访问共享内存或共享文件，或执行另外一些会导致竞争的操作。我们把对共享内存进行访问的程序片段称作临界区域 ( $critical\ \ region$ ) 或临界区 ( $critical\ \ section$ )。如果我们能适当地安排，使得两个进程不可能同时处于临界区中，就能避免竞争条件。
尽管这样的要求避免了竞争条件，但它还不能保证使用共享数据的并发进程能够正确和高效地进行协作。对于一个好的解决方案，需要满足以下 $4$ 个条件：
- 任何两个进程不能同时处于临界区；
- 不应对
CPU的速度和数量做任何假设； - 临界区外运行的进程不得阻塞其他进程；
- 不得使进程无限期等待进入临界区。
1. 互斥
1.1 屏蔽中断
在单处理器系统中，最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。屏蔽中断后，时钟中断也被屏蔽。CPU只有发生时钟中断或其他中断时才会进行进程切换，这样，在屏蔽中断后CPU将不会被切换到其他进程。于是，一旦某个进程屏蔽中断后，它就可以检查和修改共享内存，而不必担心其他进程介入。
但是这个方案并不好，因为屏蔽中断的权力交给了用户进程。而且对于多处理器系统，屏蔽中断指令仅仅对执行 $disable$ 指令的那个CPU有效，其他CPU仍然可以运行。另一方面，对于内核来说，屏蔽中断指令是非常方便的。所以屏蔽中断对于操作系统本身而言是一项很有用的技术，但对于用户进程则不是一种合适的通用互斥机制。
1.2 锁变量
设想有一个共享锁变量，其初始值为 $0$ 。当一个进程想进入临界区时，会首先测试锁。如果锁的值为 $0$ ，则进程将其设置为 $1$ 并进入临界区。否则，进程等待直到值变为 $0$ 。虽然实现简单，但是却存在着多个进程同时读到 $0$ 的可能。
1.3 严格轮换法
// 进程a
while (1) {
while (turn != 0);
critical_region();
turn = 1;
noncritical_region();
}
// 进程b
while (1) {
while (turn != 1);
critical_region();
turn = 0;
noncritical_region();
}
通过连续检查一个变量来决定哪个进程进入临界区。连续测试一个变量直到某个值出现为止，称为忙等待 ( $busy\ \ waiting$ )。由于这种方式浪费CPU时间，所以通常应该避免。只有在有理由认为等待时间是非常短的情况下，才使用忙等待。用于忙等待的锁，称为自旋锁 ( $spin\ \ lock$ )。
1.4 Peterson解法
#define FALSE 0
#define TRUE 1
#define N 2 // 进程数
int turn;
int interested[N]; // 初始值为0 (FALSE)
void enter_region(int process) {
int other;
other = 1 - process; // 另一个进程号
interested[process] = TRUE; // 设置感兴趣
turn = process; // 设置标志
while (turn == process && interested[other] == TRUE); // 其他进程感兴趣则挂起
}
void leave_region(int process) {
interested[process] = FALSE; // 表示离开临界区
}
在进入临界区之前，各个进程使用其进程号作为参数来调用 $enter_-region$ 。该调用在需要时将使进程等待，直到能安全地进入临界区。在完成对共享变量的操作之后，进程将调用 $leave_-region$ ，表示操作已完成。
1.5 TSL指令
在某些计算机中，特别是那些设计为多处理器的计算机，都有下面一条指令：
TSL RX, LOCK
称为测试并加锁 ( $test\ \ and\ \ set\ \ lock$ )，它将一个内存字读到寄存器 $RX$ 中，然后在该内存地址上存一个非零值。读字和写字操作保证是不可分割的，即该指令结束之前其他处理器均不允许访问该内存字。执行TSL指令的CPU将锁住内存总线，以禁止其他CPU在本指令结束之前访问内存。为了使用TSL指令，需要使用一个共享变量 $lock$ 来协调对共享内存的访问。当 $lock$ 为 $0$ 时，任何进程都可以使用TSL指令将其设置为 $1$ 并读写共享内存。当操作结束时，进程用一条普通的MOV指令将 $lock$ 的值重新设置为 $0$ 。
2. 睡眠与唤醒
Peterson解法和TSL解法都是我们想要的正确的解法，但是都存在忙等待的缺点。这些解法的本质是：当一个进程想进入临界区时，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止。如果进程之间存在优先级，甚至还可能带来优先级反转问题 ( $priority\ \ inversion\ \ problem$ )，即高优先级进程就绪时，低优先级进程仍处于临界区并且永远不会被调度的问题。
$sleep$ 原语将引起调用进程阻塞的系统调用，即被挂起，直到另外一个进程将其唤醒。$wakeup$ 调用有一个参数，即将要被唤醒的进程。另一种方法是让 $sleep$ 和 $wakeup$ 各有一个参数，即有一个用于匹配 $sleep$ 和 $wakeup$ 的内存地址。
生产者-消费者 ( $producer-consumer$ ) 问题，也称为有界缓冲区 ( $bounded-buffer$ ) 问题。两个进程共享一个公共的固定大小的缓冲区，其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出信息。问题在于当缓冲区已满，而此时生产者还想向其中放入一个新的数据项的情况，解决办法是让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒。同样地，当消费者试图从缓冲区中取出数据而发现缓冲区为空时，消费者就睡眠，直到生产者向其中放入一些数据时再将其唤醒。
#define N 100 // 缓冲区中的槽数目
int count = 0; // 缓冲区中的数据项数目
void producer(void) {
int item;
while (TRUE) {
item = produce_item();
if (count == N) sleep();
insert_item(item);
count = count + 1;
if (count == 1) wakeup(consumer);
}
}
void consumer(void) {
int item;
while (TRUE) {
if (count == 0) sleep();
item = remove_item();
count = count - 1;
if (count == N - 1) wakeup(producer);
consume_item(item);
}
}
上述的实现有可能会出现竞争条件，因为对 $count$ 的访问未加限制。有可能出现以下情况：缓冲区为空，消费者读取 $count$ 发现为 $0$ ，于是准备暂停消费者并启动生产者。生产者在添加数据项之后，$count$ 加 $1$ ，并认为消费者一定在睡眠，于是调用 $wakeup$ 唤醒消费者。但是消费者此时在逻辑上并未睡眠，所以 $wakeup$ 信号丢失。而当生产者填满缓冲区时，也会进入睡眠，从而使得两个进程都进入睡眠。解决这个问题的关键在于丢失的 $wakeup$ 信号，一种弥补方法是修改规则，添加一个唤醒等待位。当一个 $wakeup$ 信号发送给一个清醒的进程信号时，该位置 $1$ 。在进程睡眠时，如果标志位为 $1$ ，则会清除标志位并唤醒。
3. 信号量
信号量 ( $semaphore$ ) 方法使用一个整形变量来累计唤醒次数，供以后使用。一个信号量的取值可以为 $0$ ( 表示没有保存下来的唤醒操作 ) 或者为正值 ( 表示有一个或多个唤醒操作 )。对一个信号量执行 $down$ 操作，会检查其值是否大于 $0$ ，如果是则减 $1$ ，否则进程进入睡眠状态。检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成，从而保证一旦一个信号量操作开始，则在操作完成或阻塞之前其他进程均无法访问信号量。对一个信号量执行 $up$ 操作会将其值加 $1$ 。对一个有进程在其上睡眠的信号量执行一次 $up$ 操作之后，该信号量的值仍旧是 $0$ ，但在其上睡眠的进程却少了一个。同样的，信号量的值加 $1$ 和唤醒一个进程的操作也是不可分割的。
为了确保信号量能正确工作，最重要的是采用一种不可分割的方式实现它，通常是将 $up$ 和 $down$ 作为系统调用实现。我们可以使用信号解决 $wakeup$ 丢失的问题：
#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); // 将空槽数目减1
down(&mutex); // 进入临界区
insert_item(item);
up(&mutex); // 离开临界区
up(&full); // 将满槽数目加1
}
}
void consumer(void) {
int item;
while (TRUE) {
down(&full); // 将满槽数目减1
down(&mutex); // 进入临界区
item = remove_item();
up(&mutex); // 离开临界区
up(&empty); // 将空槽数目加1
consume_item(item);
}
}
信号量的另一种用途是用于实现同步 ( $synchronization$ )。信号量 $full$ 和 $empty$ 用来保证某种事件的顺序发生或不发生。
3.1 互斥量
如果不需要信号量的计数能力，有时可以使用信号量的一个简化版本，称为互斥量 ( $mutex$ )。互斥量仅仅适用于管理共享资源或一小段代码，是一个可以处于两态之一的变量：解锁和加锁。这样，只需要一个二进制位即可表示，不过实际上常常使用一个整型。
4. 管程
信号量和互斥量虽然方便了进程间通信的进行，但也会带来死锁 ( $dead\ \ lock$ ) 问题。为了更易于编写正确的程序，管程 ( $monitor$ ) 就被提出了。一个管程是一个由过程、变量及数据结构等组成的一个集合，它们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但它们不能在管程之外声明的过程中直接访问管程内的数据结构。管程是一种语言概念，C语言并不支持管程。
管程有一个很重要的特性，即任一时刻管程中只能有一个活跃进程，这一特性使管程能有效地完成互斥。管程是编程语言的组成部分，编译器直到它们的特殊性，因此可以采用与其他过程调用不同的方法来处理对管程的调用。进入管程的互斥由编译器负责，但通常的做法是用一个互斥量或二元信号量。为了使进程在无法继续运行时被阻塞，管程引入了两个条件变量 ( $condition\ \ variables$ ) 以及相关的两个操作：$wait$ 和 $signal$ 。当一个管程过程发现它无法继续运行时，会在某个条件变量上执行 $wait$ 操作。该操作将导致调用进程自身阻塞，并且还将另一个以前等在管程之外的进程调入管程。如果在一个条件变量上有若干个进程正在等待，则在对该条件变量执行 $signal$ 操作后，系统调度程序只能在其中选择一个使其恢复运行。
4.1 匿名管道
通过 $pipe(\ )$ 函数创建。
- 管道是半双工的，数据只能向一个方向流动；
- 只能用于父子进程或者兄弟进程之间；
- 每个进程都维护一个用于读的 $fd[0]$ 和一个用于写的 $fd[1]$ ；
- 一个进程向管道中写的内容被另一端进程读出，写入每次都追加在缓冲区末尾，读取每次都从缓冲区头部读取。
实质是内核缓冲区，通过FIFO方式读写数据，如果缓冲区满，会阻塞写入进程直到数据被读出；如果缓冲区空，会阻塞读取进程直到有数据写入。
4.2 有名管道/FIFO
匿名管道没有名字，只能用于具有亲缘关系的进程之间。有名管道提供了一个路径名与之关联，以文件形式存在于文件系统中，允许任意进程通信。有名管道是单向的，常用于C-S架构中，作为聚合点，多个客户端向管道中写入数据，服务端从管道中读取。
5. 消息队列
消息队列是存放在内核中的消息链表，每个消息队列由消息队列标识符表示。在某个进程向消息队列发消息之前，并不需要保证另一端有进程从消息队列中读消息。
6. 共享内存
共享内存使得多个进程可以直接读写同一块内存区域，是最快的IPC形式。内核空间留出一块共享内存区，可供需要的进程将其映射到自己的私有空间。由于多进程共享内存，因此需要一定的同步机制保证读写的正确性。
- $mmap(\ )$ 调用：进程之间通过映射同一个普通文件实现共享内存。普通文件在被映射到进程地址空间后，进程可以像访问普通内存一样对文件进行访问；
POSIX：POSIX共享内存需要先通过 $shm_-open$ 创建或打开一个POSIX共享内存对象，再通过 $mmap(\ )$ 将它映射到当前进程的地址空间。与直接使用 $mmap(\ )$ 的区别在于获取 $fd$ 的方式不同；System V：通过映射特殊文件系统 $shm$ 中的文件实现共享内存，也就是说每个共享内存区域对应 $shm$ 中的一个文件。
| 类型 | 原理 | 易失性 |
|---|---|---|
| $mmap$ | 利用文件 ( $open$ ) 映射共享内存区域 | 保存在磁盘上，不会丢失 |
POSIX |
利用 $/dev/shm$ 文件系统 ( $mmap$ ) 映射共享内存区域 | 随内核持续 |
System V |
利用 $/dev/shm$ 文件系统 ( $shmat$ ) 映射共享内存区域 | 随内核持续 |
$/dev/shm$ 使用了一种特殊的文件系统tmpfs，其中所有的文件都存在虚拟内存中。一块内存区域使用 $mmap$ 时，进程会把文件分别映射到自己的内存地址空间；使用 $shm$ 时，进程会把同一块共享内存映射到自己的内存空间。
7. 套接字
套接字是一种通信机制，通过套接字，进程间可以通过网络在不同机器上通信。