进程间通信核心概念

1 竞争条件：类似于上述情况，即两个或者多个进程读写某些共享数据，而最后的结果取决于进程的运行的   精确时序，称为竞争条件。
2 互斥：互斥是一种手段，它使共享数据的进程无法同时对其共享的数据进行处理。
3 临界区：即访问共享内存的程序片。也就是说，通过合理的安排，使得两个进程不可能同时处在临界区中，就能避免竞争条件。
4 忙等待：连续[测试]一个变量直至某值出现位止。
5 自旋锁：用于忙等待的锁。

互斥的方案

#使用忙等待的方案
1. 屏蔽中断

   1.1 原理：进程进入临界区自后，屏蔽所有中断，离开的时候，打开所有中断
   1.2 缺点：a、多核的系统无效（其他进程任然可以占用其他的CPU继续访问公共内存）
        b、用户程序来控制中断会很危险
   1.3 结论：屏蔽中断对系统本身是一项很有用的技术，但对用户进程不是一种合适的通用互斥机制。

2. 设置一个共享锁

   2.1 原理：初始值设置为0，进程进入，先测试锁，为0，则设置为1，然后进入

   2.2 假定一个共享（锁）变量，初值为0，代表临界区内无进程，进程进入临                
       界区后将其改变为1，代表临界区内有进程；倘若进程在进入临界区之前，              
       锁变量值为1，该进程将等待其值变为0。

   2.3 未能实现的原因：与假脱机目录的疏漏一样，如果一个进程进入临界区，但是在       
       它把锁变量置1之前被中断，另一个进程进入临界区后将0置1，这样，
       当前一个进程再次运行时它也将锁变量置1，这样临界区内依然存在两个进程。

3. Peterson解法
   3.1 原理:使用共享变量，enter_region和leave_region函数控制
   3.2 Peterson解法实现细节
     a、进程0通过调用enter_region()进入临界区，此时1也想调用enter_region() 
     来进入临界区，但interested[0]为TRUE，因此被while循环挂起，当进程0出临
     界区时调用leave_region()，将interested[0]设为FALSE，进程1即可及时进入临界
     区。
      b、当进程0在调用enter_region()过程的任意时刻被中断，进程1进入临界区
      后进程0再次进行时，依然会被挂起。（实际上while循环体中的两条判断句就 
      保证了，当一个进程在临界区中时，另一个想进入临界区的进程必然会被挂起）。

4. TSL指令
   TSL RX,LOCK 测试并加锁，讲一个内存字lock读到寄存器中，然后在改内存地址上存一个非0值。
   执行TSL指令的CPU将会锁住内存总线，禁止其他CPU在本指令结束之前访问内存。

5. 严格轮换

   5.1 原理：共享turn变量，用来记录轮到那个进程进入临界区。
   5.2 当turn=0时，只有进程0能进入临界区，进程0在离开临界区前将turn  置1，从而标志，轮到进程1进入临界区。
       缺点：严格地轮换，可能导致临界区外的进程阻塞需要进入临界区的进程
       总结：当一个进程比另一个进程慢了许多的情况下，不宜用这种方式。
5. 总结
    要想拟定一个方案，使它既能避免竞争条件，又能保证进程运行与协作的效率，必须要满足4个条件。
     (1)、任何两个进程不能同时处于临界区
     (2)、不应对CPU的速度和数量做任何假定
     (3)、临界区外运行的进程不能阻塞其他进程
     (4)、不得使进程无限期等待进入临界区

信号量

1. 它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目 .
   信号允许多个线程同时使用共享资源，它指出了同时访问共享资源的线程最大数目。它允许多个线
   程在同一时刻访问同一资源。
   信号量S是一个整数，S大于等于零时代表可供并发进程使用的资源实体数，但S小于零时则表示
   正在等待   使用共享资源的进程数。
   
  P操作申请资源：
  （1）S减1；
  （2）若S减1后仍大于等于零，则进程继续执行；
  （3）若S减1后小于零, 则该进程被阻塞后进入与该信号相对应的队列中，然后转入进程调度。
   
  V操作 释放资源：
   （1）S加1；
   （2）若相加结果大于零，则进程继续执行；
   （3）若相加结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转入进程调度。

互斥量

互斥量是信号量的简化版本，是一个可处于两态之间的变量，解锁和加锁，用一个二进制位表示。

互斥量.png

管程

#管程定义
. 是一种特殊的模块
. 每一个管程有一个名字
. 由关于共享资源的数据结构 及在其上操作的一组过程组成

#进程与管程
 进程只能通过调用管程中的结构来间接地访问管程中的数据结构

#管程需要解决两个问题
 1) 互斥：管程是互斥进入的。管程的互斥性是由编译器负责保证的
 2) 同步：管程中设置条件变量及等待/唤醒操作以解决同步问题

消息传递

  在消息传递系统中，进程间的数据交换是以格式化的消息(Message)为单位的。
  若通信的进程之间不存在可直接访问的共享空间，则必须利用操作系统提供的
  消息传递方法实现进程通信。进程通过系统提供的发送消息和接收消息两个原语进行数据交换。

1)  直接通信方式：发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列
    上，接收进程从消息缓冲队列中取得消息。

2)  间接通信方式：发送进程把消息发送到某个中间实体中，接收进程从中间实体中取得消息。
    这种中间实体一般称为信箱，这种通信方式又称为信箱通信方式。该通信方式广泛应用于计
    算机网络中，相应的通信系统称为电子邮件系统。

屏障

用于进程组，除非进程组的所有进程都就绪准备下一个阶段，否则任何进程都不能进入下一个阶段

经典的IPC问题

哲学家就餐问题

<code>
#define N 5
#define LEFT (i)
#define RIGHT (i+1)/N
#define EATTING 2
#define HUNGRY 1
#define THINKING 0
int state[N];
semaphore mutex;
semaphore s[N];
void philosopher(i){
think(i);
take_forks(i); //吃饭前先等待两只叉子
eatting();
put_forks(i); //放下叉子，查看左右邻居是否两只叉子都空闲，如果空闲提醒邻居拿起叉子
}
void take_forks(i){
P(mutex)
state[i] = HUNGRY; //代表当前哲学家正在等待叉子
test_take_left_right_forks(i); //尝试是否能拿到叉子
V(mutex);
P(s[i]); //如果拿不到叉子就阻塞
}
void test_take_left_right_forks(i){
if(state[i] == HUNGRY && state[LEFT] != EATTING && state[RIGTH] != EATTING)
{
state[i] = EATTING; //用EATTING代表当前哲学家能拿到两只叉子
V(s[i]); //如果能够拿到两只叉子，唤醒当前线程
}
}
void putdown(i){
P(mutex)
state[i] = THINKING; //代表当前不需要叉子
test_take_left_right_forks(LEFT);
test_take_left_right_forks(RIGHT);
V(mutex);
}
void thinking(i){
P(mutex);
state[i] = THINKING;
V(mutex);
}
</code>