Prioritzing acquisition of a fair ReentrantLock where it could potentially be locked

Question

I have a ReentrantLock that a bunch of operations are locking on, that was created as fair with new ReentrantLock(true). Is there a way for a thread to "barge in" onto the lock and acquire it after it's released but before any other threads?

I have considered various combinations of timed and untimed tryLock:

• tryLock() by itself will barge in on the lock if it is already unlocked and threads are waiting, but will not wait for the lock to become available.
• The same method with the timeout is fair.
• Combining both won't work since if it's locked at the beginning the timeout-based tryLock will fall back to fair scheduling.

Or am I wrong?

Answer 1

As you can see here, the ReentrantLock uses AbstractQueuedSynchronizer as the actual thread queue implementation. Seeing how none of it's methods are overridable, you cannot do this easily, i.e. replace the standard thread queue with a priority queue.

But as it says in the documentation: "This class provides an efficient and scalable basis for synchronization in part by specializing its range of use to synchronizers that can rely on int state, acquire, and release parameters, and an internal FIFO wait queue. When this does not suffice, you can build synchronizers from a lower level using atomic classes, your own custom java.util.Queue classes, and LockSupport blocking support."

So that is what you need to do: Build your own lock. Your primary goal there is to let the release method use a priority queue to make the decision. If performance is not an issue, you can just use the standard PriorityQueue where you can just make its reads and writes thread-safe with synchronized, ReentrantLock or any other standard lock available. Thread-safe priority queues are hard to come by. However, if performance is important, this paper from 2003 might be of interest to you.

However, since the user can modify the thread's priority at any given time, it might be the easiest to just use a basic queue and use stable sort (as to not mess up order of threads with equal priority) before getting the next guy. Of course, performance will be bad if you want to use it for high-contention critical sections.