javamultithreadingconcurrencyjvmreentrantlock

Prioritization on ReentrantLock's Condition


Problem: I have a set of Threads some of which must take a priority to other in acquiring ReentrantLock.

The solution: I can imagine to have a fair ReentrantLock with 2 Condition queues: lowPriority and highPriority. The point is highPriority is signalled before lowPriority. Taking into account fairness of ReentrantLock it must happen that Threads blocked in highPriority always go ahead of Threads blocked on lowPriority.

Implementation:

public class Main {
    public static final Lock lock = new ReentrantLock(true);
    public static final Condition lowPriority = lock.newCondition();
    public static final Condition highPriority = lock.newCondition();
    public static boolean cond;

    public static void lowPriority() throws InterruptedException {
        try {
            lock.lock();
            while(!cond) {
                lowPriority.await();
            }
            cond = false;
            System.out.println("low");
        } finally {
            lock.unlock();
        }
    }

    public static void highPriority() throws InterruptedException {
        try {
            lock.lock();
            while(!cond) {
                highPriority.await();
            }
            cond = false;
            System.out.println("high");
        } finally {
            lock.unlock();
        }
    }

    public static void setCond(){
        try{
            lock.lock();
            cond = true;
            highPriority.signalAll();
            lowPriority.signalAll();
        } finally {
            lock.unlock();
        }
    }
}

QUESTION: The problem that confused me about the solution is that I could not formally prove from JMM standpoint that as soon as there are Threads blocked on highPriority they always win Threads blocked on lowPriority.

Surely I ran a few experiments and high priority threads always won, but is it formally correct?


Solution

  • As I understand, for code

    highPriority.signalAll();
    lowPriority.signalAll();
    

    there is no guarantee that some thread waiting on highPriority will wake up before any thread waiting on lowPriority.
    Even when fairness==true threads can wake up in a random order 1:

    Note however, that fairness of locks does not guarantee fairness of thread scheduling. Thus, one of many threads using a fair lock may obtain it multiple times in succession while other active threads are not progressing and not currently holding the lock.

    Additionally, lowPriority.signalAll() will keep waking up all the low-priority threads even if a new high-priority thread appears in the middle of that process.

    So I would insert in the beginning of the lowPriority additional logic, which checks if there are any waiting high-priority threads and, if so, lets them run first.
    Something like that:

    public final class Main {
    
      private final Lock lock = new ReentrantLock();
      private final Condition lowPriority = lock.newCondition();
      private final Condition highPriority = lock.newCondition();
      private int numWaitingHighPriority = 0;
      private boolean cond;
    
      public void lowPriority() throws InterruptedException {
        lock.lock();
        try {
          while (!cond || (numWaitingHighPriority > 0)) {
            if (numWaitingHighPriority > 0) {
              highPriority.signal();
            }
            lowPriority.await();
          }
          cond = false;
          System.out.println("low");
        } finally {
          lock.unlock();
        }
      }
    
      public void highPriority() throws InterruptedException {
        lock.lock();
        try {
          numWaitingHighPriority++;
          try {
            while (!cond) {
              highPriority.await();
            }
          } finally {
            numWaitingHighPriority--;
          }
          cond = false;
          System.out.println("high");
        } finally {
          lock.unlock();
        }
      }
    
      public void setCond() {
        lock.lock();
        try {
          cond = true;
          ((numWaitingHighPriority > 0) ? highPriority : lowPriority).signal();
        } finally {
          lock.unlock();
        }
      }
    }