什么是进程间通信

进程间通信 InterProcess Communication, 简称IPC，的问题可以归纳为3类：

1. 进程间相互传递信息
   比如linux里的pipeline，前面进程的output是后面进程的input
2. 进程间不会妨碍彼此的运行
   订票系统的两个进程为不同用户抢同一张票
3. 进程按特定的顺序执行
   pipeline的例子也可以应用到这里

上述3类问题对线程通信也是一样的。

Race Conditions 和 Critical Regions

在一些操作系统里，进程需要读写公共资源，比如共享内存，文件。但是当多个进程同时读写一个资源时，就会发生竞争。一个进程不会一直去访问共享资源，我们把访问共享资源的那部分程序叫做critical region 临界区。避免竞争的关键在于在同一时刻只能由同一个进程读写共享数据，也叫做临界区的互斥访问。

设计原则

1. 同一时刻只有一个进程能够进入临界区
2. 不能对CPU的数量和执行速度做预设
3. 处在临界区之外的进程不能block其他进程
4. 任何一个进程都应该有机会进入它的临界区

如何实现进程间通信

禁止中断

在单处理器系统中，最简单的办法是在一个进程进入临界区之前关闭中断，离开之后再打开中断。缺点在于给进程的权限过大，如果进程不将中断恢复，OS就什么也做不了了；此外关闭中断只适用于单CPU的计算机，在多核或多处理器系统中起不到任何作用，违反了原则2.

Mutual Exclusion with Busy Waiting

忙等待就是程序不停地检查某个共享变量值，直到符合条件进入临界区，也叫自旋锁 spin lock。等待期间程序只是在空转，非常浪费CPU时间，适用于等待时间很短的情况。被检查的变量称作锁变量Lock. 接下来介绍利用忙等待实现互斥访问的几种方法。

Strict Alternation

// 放在共享内存区域
int turn= 0; 
// turn为0时运行
process1 {
  while(true) {
    while (turn !=0);
    critical_region();
    turn = 1;
    noncritical_region();
  }
}
// lock 为1时运行
process2 {
  while(true) {
    while (turn !=1);
    critical_region();
    turn = 0;
    noncritical_region();
  }
}

两个进程严格交替运行，lock的写操作必须是原子性的以避免读写冲突。调度顺序固定，浪费CPU时间。如果process1的noncritical_region执行时间非常长，足够process2执行完两次以上全部的程序，process2也只能等待。违反了原则3.

Peterson's Solution

Peterson算法是由软件实现的双线程互斥访问算法，引入了随机性，核心在于使用两个变量：

1. turn 表示轮到哪个进程进入临界区
2. interested数组 表示哪些进程已经准备好/想进入临界区

不同的教材中中对Peterson算法有不同的实现，此处举两个例子，分别来自于现代操作系统和操作系统概念。
现代操作系统版本

    int turn;
    int[] interested = {0, 0};

    public void enter_region(int process){
        int other = 1 - process;
        interested[process] = 0;
        turn = process;
        while(turn == process && interested[other] == 1);
    }

    public void leave_region(int process) {
        interested[process] = 0;
    }

这种实现属于拼手速，谁先抢到turn谁先执行。即使给turn赋值之后被另一个进程抢走CPU使用权，对方也不能进入临界区，只能等待。但有可能会出现一个进程等两次CPU切换才能进入临界区的情况（process1设置完interrested, 轮到process0执行设置完turn，进入while循环等待，process1设置turn也进入while等待，process0执行while条件false进入临界区）

操作系统概念版本
操作系统概念与现代操作系统中的实现差别仅在于对turn的赋值和进入临界区的条件判断

    public void enter_region(int process){
        int other = 1 - process;
        interested[process] = 0;
        turn = other;
        while(turn == other && interested[other] == 1);
    }

这种实现也被人叫谦让算法，只要对方准备好就将turn让给对方。

TSL Instruction

TSL（Test and Set Lock）依赖于硬件的实现。
TSL RX, LOCK
TSL指令将LOCK的内容读入寄存器RX，并将LOCK设置为一个非负数。指令执行期间，CPU锁定内存总线，防止其他CPU访存从而实现原子性。

enter_region:
  TSL REGISTER, LOCK  // copy lock to register and set lock to 1
  CMP REGISTER, #0  // was lock 0 ?
  JNE enter_region  // if it was not 0, lock was set, so loop 
  RET  // return to caller, critical region entered

leave_region:
  MOVE LOCK,#0  // store 0 in lock
  RET  // return to caller

硬件实现的另一种方式是使用XCHG指令，交换两个变量的值。Inter x86使用XCHG实现

enter_region:
  MOVE REGISTER, #1  // put 1 in register
  XCHG REGISTER, LOCK  // swap the contents of the register and lock variable
  CMP REGISTER, #0  // was lock 0 ?
  JNE enter_region  // if it was not 0, lock was set, so loop 
  RET  // return to caller, critical region entered

leave_region:
  MOVE LOCK,#0  // store 0 in lock
  RET  // return to caller

上述的严格交替算法，Peterson算法，TSL指令都采用忙等待的方式，不只浪费CPU时间，而且可能导致优先级反转 priority inversion problem 的问题。如两个进程H和L，H有高优先级，L是低优先级。如果此时L已经在临界区内，H刚准备好进入临界区，CPU将使用权交给H，H开始忙等待，而L由于获取不到CPU无法释放锁，导致低优先级的进程block了高优先级进程的运行。

Sleep and Wakeup

sleep和wakeup是一组system call, sleep导致进程block, wakeup唤醒进程。
生产者消费者问题
producer-consumer问题也叫有界缓存bounded-buffer问题。两个进程共享一个固定大小的缓冲区，producer向buffer放入item，consumer从buffer取item。buffer满的时候producer应该停止工作直到consumer从走取走一个item，buffer空时consumer停止工作直到producer放入一个item。

    int N = 100;
    int count = 0;

    producer(){
        while(true){
            item = produceItem();
            if(count == N)
                sleep();
            insertItem(item);
            count = count + 1;
            if(count== 1)
                wakeup(consumer);
        }
    }

    consumer(){
        while(true){
            if(count ==0)
                sleep();
            item = removeItem();
            count = count - 1;
            if(count == N-1)
                wakeup(producer);
            consumeItem();
        }
    }

这个实现的问题是可能会造成死锁。如producer刚判断完count==N,在sleep之前CPU调度consumer开始执行，消费一个完一个item后，count编程N-1，调用了wakeup，但此时producer还没有sleep, 这个wakeup信号丢失，导致producer再也接收不到wakeup信号而sleep forever。解决方案是加一个wakeup waiting 位，如果此时没有sleep的进程，将wakeup信号保存起来，到producer要sleep的时候去检查wakeup waiting位，如果有就不sleep了。第二种方案是要count的条件判断与sleep/wakeup在原子操作内完成。

Semaphores

semaphore是一个变量类型，其实就是一个integer变量，用来记录可供未来使用的wakeup的数量。semaphore支持两个操作down(P)和up(V), 如果semaphore为0，进程在完成down操作之前sleep。整个down/up操作的检查变量值，修改，potential sleep是在原子操作内完成的。up操作要么使semaphore值加1，要么使sleep在该semaphore上的进程数减1. PV操作的原子性是通过TSL/XCHG指令保护的锁变量实现的。
用semaphore解决producer-consumer问题

    #define N 100  
    typedef int semaphoer;
    semaphore mutex = 1;  // controls access to critical region
    semaphore full = 0;  // counts full buffer slots
    semaphore empty = N;  // counts empty buffer slots

    producer(){
        while(true){
            item = produceItem();
            down(&empty);
            down(&mutex);
            insertItem(item);
            up(&mutex);
            up(&full);
        }
    }

    consumer(){
        while(true){
            down(&full);
            down(&mutex);
            item = removeItem();
            up(&mutex);
            up(&empty);
            consumeItem();
        }
    }

mutex用来实现互斥访问，empty和full用来实现同步操作。
Semaphore是在内核态实现的，进程结束后仍然存在。内核态和用户态的切换耗时导致semaphore的使用开销较大。

Mutexes

如果不需要semaphore的同步功能，我们可以使用mutex实现互斥操作。mutex是一个只有两种状态的变量，1 locked或0 unlocked. 进程（线程）访问临界区之前，调用mutex_lock，如果此时mutex unlocked，调用成功，否则进程block直到另一个线程退出临界区调用mutex_unlock. mutex很容易在用户态使用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提供了很多mutex的方法

Condition Variables
Pthread提供的同步机制叫做condition variable，处理线程由于某些条件无法满足而不能继续执行的情况。

Mutex和Semaphore的区别

Monitors

Monitor是对OS PV操作的封装，是在编程语言层面实现的，编译器会实现对monitor的互斥访问，一般使用mutex或两位的semaphore。在同一时刻只有一个进程可以执行monitor程序。java种的synchronized就是monitor的一种实现。monitor的一般结构如下：

monitor example
  integer i;
  condition c;

  procedure producer();
  ...
  end;

  procedure consumer();
  ...
  end;
end monitor;

Message Passing

message passing主要用来解决两个机器上的进程通信速度不匹配的问题。为了保证信息传递的完整性，准确性和安全性，采用编号，确认和认证机制。message passing使用两个system call.
send(destination, &message)
receive(source, &message)
message passing 用在Socket编程和message queue里。

Barriers

用来处理多个进程要同时去执行的情况，特别是并行计算中控制不同阶段多任务的同步性。

Avoiding Locks: Read-Copy-Update