进程间通信 (IPC)：忙等待的互斥方案

2018-04-10  本文已影响27人  拉普拉斯怪

并发程序的无关性

并发程序的无关性是进程的执行与时间无关的一个充分条件，在1966年由bernstein提出。只要满足Bernstein条件，并发执行的程序就可以保持封闭性和可再现性。

鉴于简书不支持LaTeX公式，有兴趣自己查吧，文字表述总是不如数学公式直观。

并发进程的交互

如果进程间不满足上面提及的Bernstein条件，那么他们就会因为共享计算机资源而存在竞争与协作关系(又称互斥与同步)

临界区

同上面的概念类似，两个或多个进程读写某些共享数据，而最后的结果取决于进程运行得精确时序(也就是这些进程不满足Bernstein条件)，我们把这种情况称为竞争条件。解决竞争条件的方法是实现互斥，即以某种手段确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。

我们把对共享内存进行访问的程序片段称为临界区，如果存在某些方案，使得两个进程不可能同时处于临界区中，就能够避免竞争条件。对于这些方案，需要满足一下4个条件

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

忙等待的互斥方案

本节将讨论几种实现互斥的方案。在这些方案中，当一个进程在临界区中更新共享内存时，其他进程将不会进入其临界区，也不会带来任何麻烦

1. 屏蔽中断

在单处理器系统中，最简单的方法就是使每个进程刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。屏蔽中断后，时钟中断也会被屏蔽。CPU只有发生时钟中断或其他中断时才会进行进程切换，这样，在屏蔽中断之后CPU将不会被切换到其他进程。于是，一旦某个进程屏蔽中断之后，他就可以检查和修改共享内存，而不必担心其他进程介入。

2.测试并加锁指令 TSL

某些计算机中，特别是那些设计为多处理器的计算机，都有以免一条指令：TSL RX, LOCK，称为测试并加锁(test and set lock)，它将一个内存字lock读到寄存器RX中，然后再该内存地址上存一个非零值。读字和写字操作保证是不可分割的，即该指令结束之前其他处理器均不允许访问该内存字。执行TSL指令的CPU将锁住内存总线，以禁止其他CPU在本指令结束之前访问内存。
为了使用TSL指令，要使用一个共享变量lock来协调对共享内存的访问。当lock为0时，任何进程都可以使用TSL指令将其设置为1，并读写共享内存。当操作结束是，进程用一条普通的move指令将lock的值重新设置为0.

enter_region:
  TSL REGISTER, LOCK  | 复制锁到寄存器并将锁设为1
  CMP REGISTER, #0      | 锁是零吗？
  JNE enter_region           | 若不是零，说明锁已被设置，所以循环
  RET                            |返回调用者，进入了临界区

leave_region:
  MOVE LOCK, #0  |在锁中存入0
  RET        |返回调用者

可以看出TSL也是一个忙等待方案：进程在进入临界区之前先调用enter_region，在锁空闲之前一直循环等待。

3.对换指令 XCHG

一个可替代TSL的指令是XCHG，它原子性地交换了两个位置的内容，例如，一个寄存器与一个存储器字。

enter_region:
  MOVE REGISTER, #1
  XCHG REGISTER, LOCK
  CMP REGISTER, #0
  JNE enter_region
  RET

leave_region:
  MOVE LOCK, #0
  RET

TSL和XCHG指令的函数形式描述在《操作系统教程》第五版有写，此处不详细描述。

4.严格轮询法
//进程0
while(True){
  while(turn != 0);  //循环
  critical_region();
  turn = 1;
  noncritical_region();
}

//进程1
while(True){
  while(turn !=1);  //循环
  critical_region();
  turn = 0;
  noncritical_region();
}

整型变量turn，初始值为0，用于记录轮到哪个进程进入临界区，并检查或更新共享内存。开始时，进程0检查turn，发现其值为0，于是进入临界区。进程也发现其值为0，所以在一个等待循环中不但测试turn，看其值何时变为1.连续测试一个变量直到某个值出现为止，称为忙等待。由于这种方式浪费CPU时间，所以通常应该避免。只有在有理由认为等待时间是非常短的情况下，才使用忙等待。用于忙等待的锁，称为自旋锁

这个算法的确避免了所有的竞争条件，但违反了临界区条件3（临界区外运行得进程不得阻塞其他进程），所以不是一个很好的方案。

5.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;  //表示离开临界区
}

在使用共享变量之前，各个进程使用其进程号0或1作为参数来调用enter_region。该调用在使用时将使进程等待，直到能安全地进入临界区。在完成对共享变量的操作之后，进程将调用leave_region，表示操作已完成，若其他的进程希望进入临界区，则现在就可以进入。

一开始，没有任何进程进入临界区中，现在进程0调用enter_region。它通过设置其数组元素和将turn置0来标识它希望进入临界区。由于进程1并不想进入临界区，所以enter_region很快便返回。如果进程1现在调用enter_region，进程1将在此处挂起直到interested[0]变成FALSE，该事件只有在进程0调用leave_region退出临界区时才会发生。

现在考虑两个进程几乎同时调用enter_region情况。它们都将自己的进程号存入turn，但只有后被保存进去的进程号才有效，前一个因被重写而丢失。假设进程1是后存入的，则turn为1。当两个进程都运行到while语句时，进程0将循环0次进入临界区，则进程1则将不断地循环而不能进入临界区，直到进程0退出临界区为止。

上一篇下一篇

猜你喜欢

热点阅读