ReentrantLockがこのデモコードで不公平を示していない理由を教えてください。

Question

私はReentrantLockの不公平を示すコードを作成しようとしていました（ctorがfair = falseに渡されたとき）。私の驚いたことに、ReentrantLockは完全に公正でした。

私のテストは、以下のロジックを持っています：0から19までの "id"を持つ20のスレッドを生成する。すべてのスレッドはReentrantLockを共有します。次に、時間順に：

• スレッド0はロックをロックします。
• スレッド1から19までのブロックロック（）、1、2、3、..、19の順にアクセスします。
• スレッド0はロックを解除します。これは公平性の最初のテストです。ロックが正しければ、スレッド1はその後にそれを取得する必要があります。
• スレッド1にロックがある場合は、スレッドも解放します。フェアネスの2番目のテスト：スレッド2は今それを取得する必要があります。
• など

私は時々、スレッドが実際に長く待っていた別の1の前にロックを取得することを期待していました。ロック解除が呼び出されたとき、私は、スレッドがロックを解除するために再びそれを取得しようとしない、と仮定し

package jma.test; 

import java.util.LinkedList; 
import java.util.Queue; 
import java.util.concurrent.locks.ReentrantLock; 

class ThreadTest extends Thread { 
    private final int id; 
    private final int totalNbThreads; 
    private final ReentrantLock lock1; 
    private final LinkedList<Integer> checkOrder; 

    ThreadTest(int id, int totalNbThreads, ReentrantLock lock, LinkedList<Integer> checkOrder) { 
     this.id = id; 
     this.totalNbThreads = totalNbThreads; 
     this.lock1 = lock; 
     this.checkOrder = checkOrder; 
    } 

    public void run() { 
     try { 
      // This if is to force threads to get to lock() call below in order of their ids. 
      // Thread 0 should call lock() first, then threads 1, 2, 3, 4 ... 
      if (this.id == 1) { 
       while (!lock1.isLocked()) { 
        // wait for thread 0 to lock it 
       } 
      } else if (this.id > 1) { 
       while (lock1.getQueueLength() != (this.id - 1)) { 
        // íf we are thread n, we wait for thread 1 to n-1 to enter the wait queue. 
       } 
      } 

      lock1.lock(); 
      if (this.id == 0) { 
       while (lock1.getQueueLength() != (totalNbThreads - 1)) { 
        // Wait for all other threads to bloc on lock1.lock() before releasing lock 
       } 
      } 
      checkOrder.add(this.id); 
     } finally { 
      lock1.unlock(); 
     } 

    } 
} 

public class Main { 
    private static final int NB_THREADS = 20; // at least 2 

    // change the boolean to switch between fair or not-fair lock 
    private static final ReentrantLock lock = new ReentrantLock(false); 

    private static boolean isLockFair() { 
     Queue<Thread> allThreads = new LinkedList<>(); 
     LinkedList<Integer> checkOrder = new LinkedList<>(); 

     for (int id=0; id < NB_THREADS; id++) { 
      allThreads.add(new ThreadTest(id, NB_THREADS, lock, checkOrder)); 
     } 

     for (Thread t : allThreads) { 
      t.start(); 
     } 

     for (Thread t : allThreads) { 
      try { 
       t.join(); 
      } catch (InterruptedException e) { 
       e.printStackTrace(); 
      } 
     } 

     int previous = -1; 
     for (int i : checkOrder) { 
      if (i != previous + 1) { 
       System.out.println("not fair: " + i + " got the lock after " + previous); 
       return false; 
      } 
      previous = i; 
     } 
     return true; 
    } 

    public static void main(String[] args) { 
     int ctrUnfair = 0; 
     int nbTest = 10000; 

     for (int i=0; i<nbTest; i++) { 
      if (!isLockFair()) 
       ctrUnfair++; 
     } 

     System.out.println("unfairness: " + ctrUnfair + "/" + nbTest); 
    } 
} 

、実行中のスレッドとの間には同時性はありません。しかし、決して

コードが起こりませんスレッドをブロックするので、ロックを取得するスレッドは必ず待機キューから来て、待機キューの実装はおそらくFIFOです。それは説明ですか？

Answer 1

私は時にはスレッドがロックを取得してから実際に長い時間待っていることを期待していました。しかしそれは決して起こりません。

私の理解では、これは以下の場合に起こります。

1.Threadコールロック解除、後unparkSuccessor、スレッドのスケジューリングが発生し、実行するスレッドBの開始前tryReleaseを実行しますが。

2.Thread Bコールロック、それはどれもフェアロックであれば、それが呼び出すcompareAndSetStateと、他のスレッドがロックを待機しても成功は、あなたが見るが、スレッドBはそれを得たが、それならばします現在のスレッドがロックを待っている最初のスレッドであるかどうかをテストします。hasQueuedPredecessorsを参照してください。

これらはすべてソースコードAQSとReentrantLockから得られます。

コードに戻ると、スレッド0ができる前にロックを解除する、他のすべてのスレッドは待ち行列にありますので、上記の場合とは異なります。これがうまくいけば幸いです。