java 之多线程 LOCK实现(一)

一，前言

   众所周知，一个可靠的多线程程序必须要能够坐到无死锁，无饥饿。

   什么叫做无饥饿：如果一个线程需要获得一个Lock，那么这个操作在一个有限时间内最终会获得成功（不论时间长短）。

那么我们现在就来实现只有两个线程的Lock。

 

二，Lock接口 
 

public interface Lock{
   public void lock();
   public void unlock();
}

三，只有两个线程的Lock实现

 

public class TwoThreadLockImpl implements Lock {
   
       private boolean[] flag = new boolean[2];
       public void lock() {

           /**获得当前线程Id（0或者1）
           **/
           int threadId = ThreadUtil.getCurrentThread();          step 1

           flag[threadId ] = true;                                        step 2
         
           /**循环等待另一个线程将标志位设置为false;
           **/
           while(!flag[1- threadId] ) {                                  step 3
           }

           /**
           这个地方标志着一个线程已经获得这个Lock
           **/

      }

       public void unlock() {

             int threadId = ThreadUtil.getCurrentThread();
             将标志位设置为false，让另外一个线程可以获得这个锁。
             boolean[threadId ] = false;

       }

}

 

 

但是这个Lock实现有个缺陷，如果执行方式如下：

 

                      线程A            线程B

  1                 step 1              

  2                                     step1

  3                 step 2

  4                                      step 2

  5                 step 3

  6                                      step 3

 

在执行第5,6两步的时候 会发生死锁。即两个线程谁也永远不能得到这个锁。

 

 

四，这个实现是个正确的实现吗？即这个实现满足互斥特性吗？

     定义如下，如果一个线程在一获得锁与释放锁之间的执行时间为Ca，定义两个线程在时间上的 偏序为Ca > Cb表示 Ca在Cb之前先发生。一个正确的锁必须满足互斥，要么Ca>Cb要么Cb > Ca。

     这个a,b表示线程ID

     证明如下：

          假设这个Lock实现不满足互斥特性：即Ca Cb没有时间上的偏序关系。

          即Ca Cb之间有交集

 

                                            |-----------Ca--------------------------|

 

-----------------------------------|----------------------|------------------|-------------------------|-----

 

                                                                         |----------------------Cb------------------|

 

         红色的部分为时间交集。

 

          通过阅读代码可以得到：

   线程a:     write(a)(flag(a) = true) > read(a)(flag(b) == false) > Ca          -----------1

  线程b:      write(b)(flag(b) = true) > read(b)(flag(a) == false) > Cb          -----------2

  我们又注意到，在标志位被设置为true 到 释放锁之前不会被重置。即：

  如果a想获得lock必须得等到b执行flag(b) = false之后，才会读取到read(a)(flag(b) == false)-------->即a想获得锁必须得等到b执行完unlock之后，反过来b想获得锁也得等到a执行完unlock之后，即要么Ca > Cb要么Cb > Ca.与证明假设矛盾。即此lock实现满足互斥特性。

 

 

   

 

 

  

 

 

评论

2 楼 johnnyking 2012-09-07  

zhaoxjmail 写道

楼主,有些看不明白,boolean[threadId ] = false;是不是应该是flag[threadId]=false;

?

是的，已修正。

1 楼 zhaoxjmail 2012-09-07  

楼主,有些看不明白,boolean[threadId ] = false;是不是应该是flag[threadId]=false;

?