竞争条件，临界区，忙等待的互斥

一、竞争条件和临界区

在同一个应用程序中运行多个线程本身并不会引起问题。当多个线程访问相同的资源时才会出现问题。比如多个线程访问同一块内存区域（变量、数组、或对象）、系统（数据库、 web 服务等）或文件。事实上，只有一个或多个线程改写这些资源时才会出现问题。多个线程只读取而不会改变这些相同的资源时是安全的。

两个线程访问同一个资源而且与线程访问资源时的顺序有关的这样一种情形就叫竞争条件。 导致竞争条件发生的代码片段就叫临界区。在临界区中可以通过恰当的线程同步来消除竞争条件。

当两个线程竞争同一资源时，如果对资源的访问顺序敏感，就称存在竞争条件。导致竞争条件发生的代码称作临界区。

对共享内存进行访问的程序片段称作临界区。

对于一个好的实现互斥的解决方案，需要满足以下4个条件：

1) 任何两个进程不能同时处于其临界区。

2) 不应对CPU的速度和数量做任何假设。

3) 临界区外运行的进程不得阻塞其他进程。

4) 不得使进程无限期等待进入临界区。

二、忙等待的互斥

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

互斥：当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作。

临界区：对共享内存进行访问的程序片段成为临界区。

实现互斥，避免竞争条件的方法：

1 屏蔽中断

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

这个方案并不好，因为把屏蔽中断的权力交给用户进程是不明智的。设想一下，若一个进程屏蔽中断后不再打开中断，其结果将会如何？整个系统可能会因此终止。而且，如果系统是多处理器（有两个或可能更多的处理器），则屏蔽中断仅仅对执行disable指令的那个CPU有效。其他CPU仍将继续运行，并可以访问共享内存。

另一方面，对内核来说，当它在更新变量或列表的几条指令期间将中断屏蔽是很方便的。当就绪进程队列之类的数据状态不一致时发生中断，则将导致竞争条件。所以结论是：屏蔽中断对于操作系统本身而言是一项很有用的技术，但对于用户进程则不是一种合适的通用互斥机制。

2 锁变量

设想有一个共享（锁）变量，其初始值为0。当一个进程想进入其临界区时，它首先测试这把锁。如果该锁的值为0，则该进程将其设置为1并进入临界区。若这把锁的值已经为1，则该进程将等待直到其值变为0。于是，0就表示临界区内没有进程，1表示已经有某个进程进入临界区。

但是仍存在问题，当进程a把锁变量设为1之前恰好又有进程b进入临界区，临界区将有2个进程。（假设一个进程读出锁变量的值并发现它为0，而恰好在它将其值设置为1之前，另一个进程被调度运行，将该锁变量设置为1。当第一个进程再次能运行时，它同样也将该锁设置为1，则此时同时有两个进程进入临界区中）

可能读者会想，先读出锁变量，紧接着在改变其值之前再检查一遍它的值，这样便可以解决问题。但这实际上无济于事，如果第二个进程恰好在第一个进程完成第二次检查之后修改了锁变量的值，则同样还会发生竞争条件。

3 严格轮换法 

忙等待：连续测试一个变量直到某个值出现为止，称为忙等待。

自旋锁：用于忙等待的锁成为自旋锁。

原理：

整型变量turn，初始值为0，用于记录轮到哪个进程进入临界区，并检查或更新共享内存。开始时，进程0检查turn，发现其值为0，于是进入临界区。进程1也发现其值为0，所以在一个等待循环中不停地测试turn，看其值何时变为1（忙等待）。由于这种方式浪费CPU时间，所以通常应该避免。

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

 图2-23 临界区问题的一种解法（在两种情况下请注意分号终止了while语句）：a) 进程0；b) 进程1

整型变量turn初始为0，进程0进入临界区，进程1忙等待，直到进程0离开临界区，并将turn设为1，然后进程1进入临界区，当进程1也离开临界区时，又把turn设为0，接着进程0再次进入临界区，以此类推。由于这种方法需要两者交替进行，如果进程0退出临界区时，turn设为1，但是进程1一直在处理非临界区的工作，进程0只有一直忙等待，直到进程1将turn设为0。这说明，在一个进程比另一个进程慢很多的情况下，轮流进入临界区不是好方法。只有在有理由认为等待时间是非常短的情形下，才使用忙等待。

这种情况违反了前面叙述的条件3：进程0被一个临界区之外的进程阻塞。再回到前面假脱机目录的问题，如果我们现在将临界区与读写假脱机目录相联系，则进程0有可能因为进程1在做其他事情而被禁止打印另一个文件。

实际上，该方案要求两个进程严格地轮流进入它们的临界区，如假脱机文件等。任何一个进程都不可能在一轮中打印两个文件。尽管该算法的确避免了所有的竞争条件，但由于它违反了条件3，所以不能作为一个很好的备选方案。

4、peterson解法

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

开始时临界区中无进程，假设进程0想进入临界区，进程1不想进入临界区，则进程0调用enter_region()后直接进入临界区，现在进程1想进入临界区，它要在此处挂起并等到进程0调用leave_region()离开临界区后才能进入临界区。如果两个进程同时想进入临界区并调用enter_region()，都把自己的进程号存入turn，则后存入的进程号会覆盖前写入的turn，则前进入的进程会进入临界区。 后进入的进程忙等待直到前一个进程退出临界区。 假设进程1是后存入的，则turn为1。当两个进程都运行到while语句时，进程0将循环0次并进入临界区，而进程1则将不停地循环且不能进入临界区，直到进程0退出临界区为止。

图2-24   完成互斥的Peterson解法

5 TSL指令（测试并加锁）

某些计算机中，特别是那些设计为多处理器的计算机，都有下面一条指令：

1. TSL RX, LOCK 

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

锁住存储总线不同于屏蔽中断。屏蔽中断，然后在读内存字之后跟着写操作并不能阻止总线上的第二个处理器在读操作和写操作之间访问该内存字。事实上，在处理器1上屏蔽中断对处理器2根本没有任何影响。让处理器2远离内存直到处理器1完成的惟一方法就是锁住总线，这需要一个特殊的硬件设施（基本上，一根总线就可以确保总线由锁住它的处理器使用，而其他的处理器不能用）。

为了使用TSL指令，要使用一个共享变量lock来协调对共享内存的访问。当lock 为0时，任何进程都可以使用TSL指令将其设置为1，并读写共享内存。当操作结束时，进程用一条普通的move指令将lock的值重新设置为0。

这条指令如何防止两个进程同时进入临界区呢？解决方案如图2-25所示。假定（但很典型）存在如下共4条指令的汇编语言子程序。第一条指令将lock 原来的值复制到寄存器中并将lock 设置为1，随后这个原来的值与0相比较。如果它非零，则说明以前已被加锁，则程序将回到开始并再次测试。经过或长或短的一段时间后，该值将变为0（当前处于临界区中的进程退出临界区时），于是过程返回，此时已加锁。要清除这个锁非常简单，程序只需将0存入lock即可，不需要特殊的同步指令。

图2-25   用TSL指令进入和离开临界区

现在有一种很明确的解法了。进程在进入临界区之前先调用enter_region，这将导致忙等待，直到锁空闲为止，随后它获得该锁并返回。在进程从临界区返回时它调用 leave_region，这将把lock设置为0。与基于临界区问题的所有解法一样，进程必须在正确的时间调用enter_region和 leave_region，解法才能奏效。如果一个进程有欺诈行为，则互斥将会失败。

一个可替代TSL的指令是XCHG，它原子性地交换了两个位置的内容，例如，一个寄存器与一个存储器字。代码如图2-26所示，而且就像可以看到的那样，它本质上与TSL的解决办法一样。所有的Intel x86 CPU在低层同步中使用XCHG指令。

1. enter_region:  
2. MOVE REGISTER,#1    | 在寄存器中放一个1  
3. XCHG REGISTER,LOCK  | 交换寄存器与锁变量的内容  
4. CMP REGISTER,#0 |锁是零吗？  
5. JNE enter_region    | 若不是零，说明锁已被设置，因此循环  
6. RET | 返回调用者，进入临界区  
7. leave_region:  
8. MOVE LOCK,#0    | 在锁中存入0  
9. RET | 返回调用者 

图2-26   用XCHG指令进入和离开临界区

一个可替代TSL指令的是XCHG指令，原子性的交换两个位置的内容。本质上和TSL解法一样。

peterson，TSL或XCHG都是正确的，但是它们都有忙等待的缺点：

1 浪费cpu时间

2 优先级反转问题：例如H进程优先级高，L进程优先级低 ，假设L处于临界区中，H这时转到就绪态想进入临界区，H需要忙等待直到L退出临界区，但是H就绪时L不能调度，L由于不能调度无法退出临界区，所以H永远等待下去。