Problem: I have a set of Thread
s 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 Thread
s blocked in highPriority
always go ahead of Thread
s 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 Thread
s blocked on highPriority
they always win Thread
s blocked on lowPriority
.
Surely I ran a few experiments and high priority threads always won, but is it formally correct?
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();
}
}
}