java 之多线程 LOCK实现(四)

接lock实现（三），由于peterson lock实现只能解决双线程同步互斥，那么N线程互斥 如何做呢？看下文。。。

设计一个Level（N）的N个过滤空间，每个线程到达临界区需要走过所有的Level空间。所有的level 都必须满足以下两个条件：

    1）至少有一个尝试进入Level（N）的线程会成功。

    2）如果有多个线程尝试进入一个Leven（N），则至少有一个会被阻塞（继续在这个leven（N）外等待。）。

public class BakeryLock implements Lock{

  private int[] level;
  private int[] victim;

  public void init(int threadSize) {
      level = new int[threadSize];
      victim = new int[threadSize];
      for (int i = 0; i < threadSize; i++) {
          level[i] = 0;
      }
  }


   public void lock() {
      int currentThreadId = ThreadUtil.getCurrentId();
      
      for (int i = 1; i < level.length; i++) {
  
          level[currentThreadId] = i;
          victim[i] = currentThreadId;

          /**存在一个线程K，K != currentThreadId，使得level[k] >= i
           **/
          while(  (exist K != currentThreadId)(level[k] >= i && victim[i] == currentThreadId)  ) {


           }

      }

      public void unlock() {

          int currentThreadId = ThreadUtil.getCurrentId();
          level[currentThreadId] = 0
      }

   }

 

 

level[n] 是n个过滤空间（n个小屋子），如果一个线程要进入到临界区，必须得通过所有的小屋子，如果有超过1个线程同时进入到一个小屋子里，则至少有一个线程会被阻塞在while循环中，一直等待到找不到 这样的K，使得level[k] >=currentThreadId. 每个leve层 有一个冲突域victim，用来过滤出 某个线程，是这个线程不能进入下一层level[i + 1]

引理：对于 0 到N-1层中的 整数J，level[j]上最多有n - j个线程。

证明：归纳法：

         1）第0层，level[0]上最多有N个线程

         2）第1层，最多有N - 1个线程，因为有一个线程会被阻塞。

         3）假设第J-1层最多有N-j+1个线程，那么我们来做 第J层的推算。

             不失一般性，假如A是最后一个执行victim[j] = A, 那么

             write(B)(victim[j]) -> write(A)(victim[j])->read(B)(victime[j] == A)

             B先进入临界区，这个时候A肯定会读到 level[k] >= i 且 victim[i] == currentThreadId，所以在while处等待。