Writing a one-at-a-time lock in Java

Question

Hi. I'm trying to implement a Java lock-type-thing which does the following:

1. By default, threads do not pass the lock. (Opposite from normal locks, where locks can be acquired as long as they are not held.)
2. If only one thread is waiting for the lock, execution in that thread stops
3. If more than one thread is waiting for the lock, the thread that has been waiting the longest is allowed to continue execution.

I'm working on implementing this on top of AbstractQueuedSynchronizer. The transition to allow the oldest thread to go through looks like this:

//inner class inside Lock
private static class Sync extends AbstractQueuedSynchronizer {
    public Sync(){
        setState(-1);
    }

    public boolean tryAcquire(int ignore) {
        if (getState() == 1) return false;

        Thread first = getFirstQueuedThread();
        if (first != null &&
            first != Thread.currentThread()) {
            setState(0);
            return false;
        }
        return compareAndSetState(0, 1);

The problem that I'm seeing is that when I call setState(0) but return false, the Sync object never has the first thread tryAcquire again. Do I need to use SharedMode? Is there a better solution to this problem?

This is part of an implementation of what I call a "Valve" which I want to use for long-polling AJAX responses. I've got the part where a thread waits for the valve to become "pressurized" -- there's data to send to the client) but getting the oldest thread to release seems hard unless I don't use AbstractQueuedSynchronizer, and I really don't want to write a ground-up lock implementation.

Answer 1

Have you looked at this link

A Fair Lock

Below is shown the previous Lock class turned into a fair lock called FairLock. You will notice that the implementation has changed a bit with respect to synchronization and wait() / notify() compared to the Lock class shown earlier.

Exactly how I arrived at this design beginning from the previous Lock class is a longer story involving several incremental design steps, each fixing the problem of the previous step: Nested Monitor Lockout, Slipped Conditions, and Missed Signals. That discussion is left out of this text to keep the text short, but each of the steps are discussed in the appropriate texts on the topic ( see the links above). What is important is, that every thread calling lock() is now queued, and only the first thread in the queue is allowed to lock the FairLock instance, if it is unlocked. All other threads are parked waiting until they reach the top of the queue.

Answer 2

Have a look at the ReentrantLock class (http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/locks/ReentrantLock.html).

You could keep this lock object as a private variable in your class and use it to do whatever you need to do. I'm not quite sure how you could implement this without more knowledge of your code, but this Lock object has all of the methods you require to provide the behavior you mentioned in your post.

To keep track of how long a thread has been waiting, you might have to hack something together to keep track of it. I don't think the Thread class provides that kind of functionality.