进程间的通信
进程间的通信（Inter Process Communication, IPC）问题主要有3个：
(1) 一个进程如何把信息传递给另一个进程；
(2) 确保两个或更多进程在关键活动中不会出现交叉；
(3) 有协作关系的进程的时序问题。
两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为
竞争条件（race condition）。我们把对共享内存进行访问的程序片段称作
临界区域（critical region）或临界区（critical section），如果我们能够保证两个进程不可能同时处于临界区中，就能避免竞争条件。为了避免竞争条件，以某种手段确保当前一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作，称为
互斥（mutual exclusion）。
一个好的互斥方案需要满足下面4个条件：
(1) 任何两个进程不能同时处于其临界区；
(2) 临界区外运行的进程不得阻塞其他进程；
(3) 不得使进程无限期等待进入临界区；
(4) 不应对CPU的速度和数量做任何假设。
下面将讨论几种实现互斥的方案。
1、忙等等（busy waiting）
1.1 屏蔽中断
在单处理器系统中，最简单的办法是使每个进程在刚刚进入临界区域后立即屏蔽所有中断，并在就要离开之前打开中断。在屏蔽中断之后，CPU将不会切换到其他进程。
但这个方案并不好，把屏蔽中断的权利交给用户进程会引发风险，如果进程中断屏蔽后不再打开，将使得整个系统终止。此外，在多CPU系统中，屏蔽中断仅仅对执行disable指令的那个CPU有效，其他CPU仍将继续运行，并可以访问共享内存。
1.2 锁变量
设想有一个共享锁变量，其初始值为0。0表示临界区没有进程，1表示已经有某个进程进入临界区。
当一个进程要进入临界区时，先测试这把锁，如果该锁的值为0，则该进程将其设置为1并进入临界区，若这把锁的值为1，则该进程将等待直到其值变为0。
锁变量的缺陷：如果一个进程读出锁变量的值为0，但在将它设置为1之前，另一个进程被调度运行，将该锁变量设置为1。当第一个进程再次能运行时，它同样也将该锁设置为1，则此时有两个进程进入临界区中。
1.3 严格轮转法
- //进程0
- while(True){
- while(turn != 0); //等待turn等于0
- critical_region();
- turn = 1; //离开临界区
- noncritical_region();
- }
- //进程1
- while(True){
- while(turn != 1); //等待turn等于1
- critical_region();
- turn = 0; //离开临界区
- noncritical_region();
- }
严格轮转法采用忙等待，即连续测试一个变量直到某个值出现为止，用于忙等待的锁称为自旋锁（spin lock），这种方式比较浪费CPU时间，通常应该避免。
代码说明：进程0离开临界区，将turn设置为1，以便允许进程1进入其临界区。假设进程1很快便离开临界区，则此时两个进程都处于临界区之外，turn的值又被设置为0。如果此时进程1突然结束了非临界区并且返回循环的开始，但是，这时它不能进入临界区，因为turn的值为0，而此时进程0还在忙于非临界区的操作，进程1只有继续while循环，直到进程0把turn的值改为1。这实际上违反了前面叙述的互斥条件(2)，即临界区外运行的进程不得阻塞其他进程。
1.4 Peterson解法
- #define N 2 //进程数量
- int turn; //锁变量
- int interested[N];
-
- void enter_region(int process){
- int other;
- other = 1 - process; //其他进程
- interested[process] = True;
- turn = process;
- while(turn==process && interested[other]==True); //等待other离开临界区
- }
-
- void leave_region(int process){
- interested[process] = False;
- }
代码说明：一开始，没有任何进程处于临界区，现在进程0调用enter_region，它通过设置数组元素和将turn置为0来表示它希望进入临界区。由于进程1并不处于临界区，enter_region很快便返回。如果此时进程1调用enter_region，进程1将在此处挂起直到interested[0]变成False，该事件只有在进程0调用leave_region退出临界区时才会发生。
1.5 TSL指令/XCHG指令
在某些计算机上，有下面这样的指令：
TSL RX, LOCK
TSL（Test and Set Lock）指令将一个内存字lock读入寄存器RX中，然后将该内存地址上存一个非零值。读字和写字操作保证是不可分割的，即该指令结束之前其他处理器均不允许访问该内存字。执行TSL指令的CPU将锁住内存总线，以禁止其他CPU在本指令结束之前访问内存。
- //用TSL指令进入和离开临界区
- enter_region:
- TSL REGISTER, LOCK ;复制锁变量到寄存器，并将锁设为1
- CMP REGISTER, #0
- JNE enter_region ;若锁不等于0，继续循环等待
- RET
-
- leave_region:
- MOVE LOCK, #0
- RET
从代码可以看出，进程在进入临界区之前先调用enter_region，这将导致忙等待，直到锁空闲为止，随和它获得该锁并返回。在进程从临界区返回时它调用leave_region，这将把锁设置为0。
一个可替代TSL指令的是XCHG，它原子性地交换两个位置的内容。
- //用XCHG指令进入和离开临界区
- enter_region:
- MOVE REGISTER, #1
- XCHG REGISTER, LOCK ;交换寄存器与锁变量的内容
- CMP REGISTER, #0 ;测试锁
- JNE enter_region ;若锁不等于0，继续循环等待
- RET
-
- leave_region:
- MOVE LOCK, #0
- RET
忙等待的缺点：当一个进程要进入临界区时，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止。
考虑一种情况：现在有两个进程H和L，H的优先级更高，L处于临界区，H处于就绪态。由于H的优先级高于L，L将不会被调度，因此也无法离开临界区，这时H将始终处于忙等待，这种情况称为优先级反转问题（priority inversion problem）。
睡眠是将一个无法进入临界区的进程阻塞，而不是忙等待，该进程被挂起，直到另外一个进程将其唤醒。
- #define N 100 //缓冲区大小
- int count = 0;
-
- //数据生产者
- void producer(void){
- int item;
- while(True){
- item = produce_item(); //产生下一新数据项
- if(count==N)sleep(); //如果缓冲区满，就进入休眠状态
- insert_item(item); //将新数据项放入缓冲区
- count++;
- if(count==1)wakeup(consumer);//唤醒消费者
- }
- }
-
- //数据消费者
- void consumer(void){
- int item;
- while(True){
- if(count==0)sleep(); //缓冲区为空，就进入休眠状态
- item = remove_item(); //从缓冲区取走一个数据项
- count--;
- if(count==N-1)wakeup(producer);//唤醒生产者
- consume_item(item);
- }
- }
代码说明：在生产者-消费者（producer-consumer）问题中，两个进程共享一个公共的固定大小的缓冲区（bounded-buffer），其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区取走信息。当缓冲区满时，让生产者睡眠，待消费者从缓冲区取出一个或多个数据项时再唤醒它。同样地，当消费者试图从空缓冲区取数据时，消费者就睡眠，直到生产者向其中放入一些数据项时再唤醒它。
不过上面的代码仍存在一个问题，其原因是对count的访问未加限制。这种情况是：当缓冲区为空时，消费者刚刚读取count的值为0，而此时调度程序恰好将消费者挂起，并启动生产者，生产者向缓冲区加入一个数据项，count加1。现在count的值为1，它推断认为由于count刚才为0，所以消费者一定在睡眠，于是生产者调用wakeup来唤醒消费者。但是，消费者此时在逻辑上并未睡眠，所以wakeup信号丢失。当消费者再次运行时，它将测试先前读到的count值，发现它为0，于是睡眠。这样生产者迟早会填满整个缓冲区，两个进程都将永远睡眠下去。
上面这个问题的实质在于给一个清醒的进程发送的wakeup信号被丢失了。我们可以设置一个唤醒等待位，当一个清醒的进程收到wakeup信号时，将唤醒等待为置为1，随后，如果该进程收到sleep信号，先检测唤醒等待位，如果唤醒等待位为1，则不睡眠，而只是将唤醒等待位清0。
3、信号量（semaphore）
信号量是设置一个整型变量来累计唤醒次数。对信号量有两种操作：down和up（一般化后的sleep和wankeup）。
对信号量执行down操作，则是先检查其值是否大于0，若该值大于0，则将其值减1并继续，若该值为0，则进程将睡眠。这里，检查数值、修改变量值以及可能发生的睡眠操作是一个原子操作（不会被中间打断）。
up操作对信号量加1，信号量的增值1和唤醒操作同样是不可分割的。
- #define N 100 //缓冲区大小
- typedef int semaphore;
- semaphore full = 0; //缓冲区已用数目
- semaphore empty = N; //缓冲区剩余数目
- semaphore mutex = 1; //控制对临界区的访问
-
- //数据生产者
- void producer(void){
- int item;
- while(True){
- item = produce_item(); //产生下一新数据项
- down(&empty);
- down(&mutex); //进入临界区
- insert_item(item);
- up(&mutex); //离开临界区
- up(&full);
- }
- }
-
- //数据消费者
- void consumer(void){
- int item;
- while(True){
- down(&full);
- down(&mutex);
- item = remove_item();
- up(&mutex);
- up(&empty);
- consume_item(item);
- }
- }
代码说明：mutex是一个二元信号量，每个进程在进入临界区前都对它执行一个down操作，离开临界区后执行一个up操作，就能够实现互斥。信号量的另一个作用是实现同步（synchronization），信号量full和empty用来保证当缓冲区满地时候生产者停止运行，以及当缓冲区空的时候消费者停止运行。
4、互斥量（mutex）
互斥量是一种退化的信号量，它只有两种状态：加锁和解锁，这样只要一个二进制位即可表示。
互斥量在实现用户级线程包时非常有用。当一个线程需要访问临界区时，调用mutex_lock，如果该互斥量当前是解锁的，此调用成功，调用线程可以自由进入临界区。如果该互斥量已经加锁，调用线程被阻塞，直到在临界区中的线程完成并调用mutex_unlock。如果多个线程被阻塞在该互斥量上，将随机选择一个线程并允许它获得锁。
- mutex_lock:
- TSL REGISTER, MUTEX
- CMP REGISTER, #0 ;测试互斥量
- JZE ok ;解锁
- CALL thread_yield ;互斥量忙，调度另一个线程
- JMP mutex_lock ;稍后再试
- ok: RET
-
- mutex_unlock:
- MOVE MUTEX, #0
- RET
可以看出，线程互斥量与1.5节中的TSL指令实现的进程互斥类似，但有一个关键区别：
当enter_region进入临界区失败时，它始终重复测试锁（忙等待）。实际上，由于时钟超时作用，会调度其他进程运行，这样迟早拥有锁的进程会进入运行并释放锁。
当mutex_lock进入临界区失败时，它调用thread_yield主动释放CPU给另外一个线程，这样就没有忙等待。这是因为线程没有时钟中断，通过忙等待的方式来获取锁的线程将永远循环下去，绝不会得到锁，而其他线程也没有机会运行了。
下面列出了几个与线程互斥量相关的调用
pthread_mutex_init | 创建一个互斥量 |
pthread_mutex_destroy | 撤销一个已经存在的互斥量 |
pthread_mutex_lock | 获得一个锁或阻塞 |
pthread_mutex_unlock | 解锁 |
pthread_mutex_trylock | 获得一个锁或失败 |
除互斥量外，pthread提供了另外一种同步机制——条件变量（condition variable）。互斥量允许或阻塞对临界区的访问，条件变量则允许线程由于一些未达到的条件而阻塞。条件变量和互斥量经常一起使用，这种模式用于让一个线程锁住一个互斥量，然后当它不能获得它期待的结果时等待一个条件变量。最后另一个线程会向他发信号，使它可以继续执行。注意：条件变量不会存在内存中，如果将一个信号量传递给一个没有线程在等待的条件变量，那么这个信号就会丢失。
下面列出了几个与条件变量相关的调用
pthread_cond_init | 创建一个条件变量 |
pthread_cond_destroy | 撤销一个条件变量 |
pthread_cond_wait | 阻塞调用线程直到另一个线程给它发信号 |
pthread_cond_signal | 向另一个线程发信号来唤醒它 |
pthread_cond_broadcast | 向多个线程发信号来让它们全部唤醒 |
5、管程（monitor）
6、消息传递（message passing）
消息传递使用的两条原语：send和receive，前一个调用向目标发送一条消息，后一个调用从一个给定的源接收一条消息。如果没有消息可用，则接收者可能被阻塞，直到下一条消息到达，或者带着一个错误码立即返回。
消息传递过程中可能发生消息丢失的现象，因此，一旦接收到消息，接收方应该回送一条确认消息（acknowledge），如果发送方在一段时间间隔内没有收到确认，则重发消息。而如果消息本身被正确接收，但返回给发送方的确认消息丢失，发送者将重发消息，这样将导致接收者接收到两次相同的消息。通常采用在每条原始消息中嵌入一个连续的序号来解决此问题，如果接收者接收到一条消息，并且它具有与前面某条消息一样的序号，就知道这条消息是重复的。
- #define N 100
-
- void producer(void){
- int item;
- message m;
- while(True){
- item = produce_item();
- receive(consumer, &m); //等待消费者发送空缓冲区
- build_message(&m, item);//建立一个待发送的信号
- send(consumer, &m); //发送数据项给消费者
- }
- }
-
- void consumer(void){
- int item;
- message m;
- for(int i=0; i<N; ++i)
- send(producer, &m); //发送N个空缓冲区
- while(True){
- receive(produce, &m); //接收包含数据项的消息
- item = extract_item(&m);//将数据项从消息中提取出来
- send(producer, &m); //将空缓冲区发送回生产者
- consume_item(item);
- }
- }
代码说明：消费者先将N条空消息发送给生产者，当生产者向消费者传递一个数据项时，它取走一条空消息并送回一条填充了内容的消息。通过这种方式，系统中的消息总数保持不变。如果生产者的速度比消费者快，所有消息都将被填满，等待消费者；相反，如果消费者速度比生产者快，所有消息均为空，等待生产者来填充它们，消费者被阻塞，以等待一条填充过的消息。
7、屏障（barrier）
屏障机制适用于进程组。在有些应用中划分了若干阶段，并且规定，除非所有进程都就绪准备着手下一个阶段，否则任何进程都不能进入下一个阶段。可以通过在每个阶段的结尾设置屏障来实现这种行为。如下图所示，在所有进程到达屏障前，先到达的进程会被挂起，只有当所有进程都就绪后，所有进程一起被释放。
