备考抄书日志，下面全部是概念，来源于《现代操作系统》

简要概述

进程间通信 ( Inter Process Communication，IPC )是一个很大的话题，这里仅仅记录了一些概念以及将要处理的的问题。需要处理的三个问题是：

1. 一个进程如何把信息传递给另一个进程。
2. 确保多个进程在关键活动中不会出现交叉。
3. 进程处理的结果与正确的顺序有关。

竞争条件

也就是两个或多个进程读写某些共享的数据，最后的结果取决于进程运行的精确时序，称为竞争条件。

假如说现有A,B两个进程，都会去读写一个队列。A 首先读取 指向队列的下一个空闲空间 in变量。CPU这时候认为A已经运行完分配给他的时间片了，然后切换运行B进程。B 也读取 指向队列下一个空闲空间的 in 变量， 并且B把自己的数据写进去，in++。切换回A进程后，A 把自己的数据写进 原来 in 指向的空间。这时候B的数据就被覆盖到。如果这是一个打印队列，那么B永远也不会有任何打印输出。

临界区

为了避免上述的竞争条件，我们要防止多个进程同时对一个共享数据进行读写，也就是需要互斥。设置临界区是解决竞争条件的一种方法。 那什么是临界区呢？

我们把对共享内存进行访问的程序片称作为临界区域（critical region）或 临界区 （critical section）。

临界区

如上图所示，B进程尝试进入临界区时，因为A进程还在临界区内而且还没离开临界区，所以B进程会被阻塞，直到A离开临界区后，B才可以进去。这就防止了A，B同时读写共享数据。

虽然这样的要求避免了竞争条件，但是还需要一个更好的方案保证使用共享数据能够正确和高效的进行协作。需要满足以下四个条件：

1. 任何两个进程不能同时在临界区内。
2. 不应该对CPU的数量和速度做任何假设。
3. 临界区外运行的进程不得阻塞其他进程。
4. 不得使进程无限期等待进入临界区。

忙等待的互斥

忙等待也就是说 当A进程在临界区内，B进程试图进入临界区，然后被阻塞，B一直在做循环检测，直到可以进入临界区。而他们的缺点就是忙等待。下面有几种 忙等待互斥 方案。

1.屏蔽中断错误解法

最简单的方法就是当一个进程进入临界区后立即屏蔽所有中断，直到进程离开临界区后再打开。但是这样的方法并不好。原因如下：

• 不应该把屏蔽中断的权利给用户进程。加入有进程屏蔽中断之后不在打开中断，这样整个系统的可能因此中止。

• 现在的系统都是多处理器系统了，屏蔽中断呢仅仅对执行disable指令的那个CPU有效。就是说，在运行在其他CPU的进程一样会出现同时读写共享变量的情况。

• 对于内核来说，屏蔽中断是很方便的。但是当就绪进程队列之类的数据状态不一致时发生中断，则将会导致竞争条件。

结论：屏蔽中断对于系统是一项很好的技术，但对于用户进程来讲，不是一个很好的互斥机制。

2.锁变量错误解法

• 这是利用一种软件的解决方案。首先有一个锁变量，一开始置为0，代表临界区内无进程。假如一个进程试图进入临界区，则获取锁变量，若锁变量值为0，则将锁变量设置为1，然后进入临界区。假如锁变量值为1，则等待其他进程释放锁。
• 但是这样一种办法还是存在问题。假如A进程试图进入临界区，获得锁变量的值为0，将要把这个锁变量设为1。这时候却刚好时间片用完，切换到B进程。B进程也取得这个锁变量，并且设为1。当A进程再次运行时，同样将锁变量设为1。这时候就有两个进程同时在临界区内。
• 如果把锁操作作为一个单一的，不可分割的原子操作，就可以避免上述问题。

3. 严格轮换法错误解法

先了解两个术语：
忙等待： 连续测试一个变量直到某个值出现为止。
自旋锁： 用于忙等待的锁。
临界区问题的另一个解法：

进程A：
    while(TRUE) {                                                         
      while(turn!=0);     /*循环，注意有个分号*/                           
      critical_region();  /*临界区*/                                     
      turn = 1;                                                             
      noncritical_region();  /*非临界区*/                                 
    }                                                                       

进程B：
    while(TRUE) {                                                         
      while(turn!=1);     /*循环，注意有个分号*/                           
      critical_region();  /*临界区*/                                     
      turn = 0;                                                             
      noncritical_region();  /*非临界区*/                                 
    }                                                                       

• 进程A刚离开临界区时，设turn=1，b并进入非临界区。进程B检测到turn==1，则进程B进入临界区。假设A很快离开非临界区，B离开临界区并设turn=0。A检测到turn==0，则进入临界区。当A离开临界区并设值后，进程A，进程B同时在非临界区。
• 但是，有个问题。假如进程A离开临界区并很快在非临界区执行完后，而进程B还在非临界区执行。则进程A要等到进程B设值turn=0，进程A才可以进入临界区。这样就违反了条件3，即临街区外进程不得阻碍其他进程。说明一个进程比另一个慢得多的情况下，轮流进入临界区不是一个好办法。

4. Peterson解法正确解法

这是由 G.L.Peterson 发现的一种简单的算法。代码如下：

#define FALSE 0
#define TRUE 1
#define N 2                      /*进程数量*/

int turn;                        /*轮到谁了*/
int interested[N];               /*所有值初始化为FALSE*/

void enter_region(int process)   /*进程是0或1*/
{
  int other = 1-process;         /*另外一个进程*/
  interested[process] = TRUE;    /*表示感兴趣*/
  turn = process;                /*设置标志*/
  while(turn == process && interested[other] == TRUE);  /*空语句*/
}

void leave_redion(int process)
{
  interested[process]=FALSE;     /*表示离开临界区*/
}

• 假如刚开始时，进程0和进程1都没有进入临界区。这时进程0要进入临界区了，turn=0且进程1不想进入临界区，则while条件判断为false，跳出并直接进入临界区。假设进程1进入了临界区，则进程0中的while将开始循环，直到进程1离开临界区。
• 假如进程0和进程1同时调用enter_region()。
  进程0先设置turn=0,进程1后设置turn=1，覆盖了进程0设置的值。
  然后进程0 因为循环为false,则立即进入临界区。进程1则进入循环阶段。
  当进程0离开临界区，进程1的while循环判断为false，进入临界区。

4.TSL指令正确解法

有需要硬件支持的一种方案，在多处理器计算机中，都有下面一条指令：

    TSL RX, LOCK

称为 测试并加锁（test and set lock），它将一个内存字lock读到寄存器RX中，然后在该内存地址上存一个非零值。读字和写字操作保证是不可分割的，即该指令结束之前其他处理器均不允许访问该内存字。执行TSL指令的CPU将锁住内存总线，以禁止其他CPU在本指令结束之前访问内存。

//进入临界区：
enter_region:
  TSL REGISTER, LOCK    // 首先将锁复制到寄存器，然后将锁设为1
  CMP REGISTER, #0      //判断保存到寄存器的锁值是否为0
  JNE enter_region    // 如果不是0，说明锁被设置了，开始循环
  RET                  //返回调用者，进入临界区。

//离开临界区：
leave_region:
  MOVE LOCK, #0        //将锁设为0
  RET

还有一个指令 XCHG 与指令TSL很相似，他原子性地交换了两个位置的内容。所有的Inter x86 CPU 在底层同步中使用XCHG指令。

5. 结论

这些解法的本质就是忙等待：当一个进程想进入临界区，先检查是否可以进入，如果不允许，则原地等待。这样不仅浪费了CPU的时间，而且还可能产生一些不可意料的结果。假如有两个进程，一个优先级较高的H进程，优先级较低的L进程。在某一时刻，L进程在临界区内，H进程到了就绪态。根据CPU调度，H进程马上得到执行，若想进入临界区，就得等到L进程离开临界区，H进程开始忙等待。但是由于当H在就绪态时，L不会被调度，也就无法离开临界区，则H一直进行忙等待。这种情况叫优先级反转问题。

睡眠与唤醒

首先看一下进程间通信原语 sleep和wakeup。

sleep是一个将引起调用进程阻塞的系统调用，也就是被挂起，知道其他进程将其唤醒。
wakeup有一个参数，就是要唤醒的进程。

我们先以一个简单的生产者和消费者问题来看看sleep和wakeup的工作方式。 假设 有一个 槽数 为N=100的马食槽，现在有一匹很能吃的马（消费者），还有一个对它很好的主人（生产者）。count记录有多少个槽位放了食物。当没有食物的时候，马为了保存体力就去睡觉。当主人看见槽位是空的，于是就不断添加食物进槽位并叫马哥起来吃饭。当主人看到没有多余的槽位放食物的时候也去睡觉了。如果马哥发现所有槽位从全满到不满的时候，马哥就会提醒主人有空位了。

这例子有点奇怪，哈哈哈。正式一点的，首先我们要追踪count变量，当生产者发现count==N,缓冲区满了就不能再放了，然后挂起。当count 0 -> 1,就唤醒消费者。同样的，消费者发现缓冲区 是空的 就被挂起。

生产者和消费者代码：

#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;    //缓冲区内项目数加1
    if(count == 1) wakeup(consumer); //缓冲区的项目数从没有到有，唤醒消费者
  }

}


void consumer(void)
{
  int item;
  while(TRUE){
    if(count == 0) sleep();    //缓冲区空，进入休眠状态
    item = remove_item();    //从缓冲区取出一个数据项
    count = count - 1;    //缓冲区数据项减1
    if(count == N-1) wakeup(producer);  // 缓冲区的项目数由 满 到 不满时，唤醒生产者。
    consume_item(item);      //处理数据项
  }
}

很遗憾的是，这是含有严重竞争条件的生产者-消费者问题，原因是没有对count的访问进行限制。会出现以下状况：缓冲区为空，消费者刚刚读取count值发现为0，也就是刚执行完汇编的cmpq。此时调度程序觉得暂停消费者启动生产者。生产者加入一个数据项，count加1，并唤醒消费者。但是这时候的消费者没有进入真正意义上的睡眠，也就是这个唤醒信号丢失。消费者下一次运行时，就会根据之前cmpq指令的结果，就跳转到sleep睡眠。生产者迟早会填充满缓冲区，然后进入睡眠。这样一来两个进程将永远睡眠下去。
有一种快速弥补方法是修改规则，加上一个唤醒等待位。若生产者给一个清醒的消费者发送一个wakeup信号，就将唤醒等待位置为1。消费者将要睡眠的时候，先检查唤醒等待位，若为1，则置0，继续保持清醒状态。若有更多的进程，则需要跟多的等待位，这并没有从根本上解决问题。

信号量

E.W.Dijkstra 提出了一个方法，并引入了一个新的变量类型，称作信号量 (semaphore)。他建议两种操作：down和up操作（原来叫叫P和V操作）。down操作检查其值是否大于0。若该值大于0，则将其值减1，并继续，可以进入临界区。若该值为0，则令进程睡眠，但down操作还没结束。up操作对信号量的值加1.如果一个或多个进程在该信号量上睡眠，无法完成down操作，则由系统选择其中一个完成它的down操作（即可以进入临界区了）。于是，有一个进程在其上睡眠的信号量上执性一次up操作，该信号量的值还是0，但在其睡眠上的进程少了一个。为了确保信号量可以正确工作，最重要是采用原子操作。通常将up和down作为系统调用，而且操作系统只需在执行以下操作时暂时屏蔽全部中断：测试信号量，更新信号量和在需要时某个进程进行睡眠。

用信号量解决 生产者-消费者 问题
#define N 100        //缓冲区槽数目
typedef int semaphore    //信号量是一种特殊的整形数据
semaphore mutex    //控制对临界区的访问
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
  }
}

互斥量

如果不需要信号量的计数功能，可以用简化版的信号量，称为互斥量（mutex）。互斥量是一个处于两态之一的变量：加锁和解锁。用于用户级线程包的mutex_lock和mutex_unlock代码如下。和XCHG的解法在本质上是相同的。

mutex_lock:
  TSL REGISTER,MUTEX    //将互斥量信号复制到寄存器，并且将互斥信号量置为1
  CMP REGISTER,#0      //互斥信号量是0吗？
  JZE ok                //如果是0，可以进入临界区，所以返回
  CALL thread_yield      //如果不是0，说明有其他进程在临界区内，所以调度另一个线程
  JMP mutex_lock        //稍后再尝试获取锁
ok: RET            //返回调用者，进入临界区

mutex_unlock:
  MOVE MUTEX,#0      //解锁，将互斥信号量置0
  RET                 //返回调用者

消息传递

消息传递使用两条原语send和receive，他们是系统调用而不是语言成分。例如：

send(destination,&message)
receive(source,&message)

send给定一个目标发送一条消息，source从给定的源读取一条消息。如果没有消息可以接收，接受者可能被阻塞，直到一条消息到达，或者带着一个错误码立即返回。

消息传递设计要点：

• 消息可能被网络丢失。为了防止丢失，只要接收方收到信息，就要立马返回一条确认信息。在一定时间没收到则重发。
• 若有重传消息，则要区别新老消息，防止重复消息。
• 身份验证问题。

用消息传递解决 生产者-消费者 问题：

#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,i;
  message m;

  for(i=0;i<N;i++)   send(producer,&m);    //发送N个缓冲区
  while(TRUE) {
    receive(producer,&m);      //接送包含数据的消息
    item = extract_item(&m);    //将 数据 从消息提取出来
    send(producer,&m);      //将空缓冲区发送给生产者
    consume_item(item);    //处理数据
  } 
}

除了上述几种，还有 管程，屏障，避免锁...

-- 完 --