Sometimes you need to read information from an object in an operation that might take a fairly long period of time. You’ll need to lock the object so that the information you read is consistent, but you don’t necessarily need to prevent another thread from also reading data from the object at the same time: as long as all the threads are only reading the data, there’s no reason why they shouldn’t read the data in parallel, since this doesn’t affect the data each thread is reading.

In fact, the only time we need data locking is when the data is being changed; that is, when the data is being written. The change to the data introduces the possibility that a thread reading the data sees the data in an inconsistent state. Until now, we’ve been content to have a lock that allowed only a single thread to access that data whether the thread is reading or writing the data, based on the theory that the lock is only held for a short period of time.

If the lock needs to be held for a long period of time, it makes sense to consider the possibility of allowing multiple threads to read the data simultaneously so that these threads don’t need to compete against each other to acquire the lock. Of course, we must still allow only a single thread to write the data, and we must make sure that none of the threads that were reading the data are still active while our single writer thread is changing the internal state of the data.

Consider the case of a binary tree that contains some sort of information that is designed to be searched quite often by multiple threads. Depending on the amount of information contained in the binary tree, searching for a particular entry may require a long period of time. The interface for such a binary tree might look like this:

public class BTree {
    public synchronized boolean find(Object o) {
        // Perform time-consuming search, returning the object if
        // found or null if the object is not found
    }

    public synchronized void insert(Object o) {
        // Perform a time-consuming insert
    }
}

The problem here is that if two threads call the find() method at the same time, one of them blocks while it waits to acquire the lock; this thread remains blocked for a long time while the first thread continues to perform its search. If these two threads are operating in a timesliced environment, they won’t be able to timeslice since they’re competing for the same single lock; if they’re running on a machine with multiple CPUs, they won’t both be able to execute at the same time on separate CPUs. If this binary tree is part of a server that is to be accessed by multiple clients, we’d really like the threads calling the find() method to operate in parallel.

This is where the reader-writer lock comes in. If we have a lock that allows multiple threads to read a data structure simultaneously, we could use an interface that looks like this:

public class BTree {
    RWLock lock;
    public boolean find(Object o) {
        try {
            lock.lockRead();
            // Perform time-consuming search, returning the object
            // if found or null if the object is not found.
            return answer;
        } finally {
            lock.unlock();
        }
    }

    public void insert(Object o) {
        try {
            lock.lockWrite();
            // Perform a time-consuming insert.
        } finally {
            lock.unlock();
        }
    }
}

We now have the capability of allowing multiple threads to read the binary tree simultaneously, even though the binary tree still can be updated only by a single thread.

The bad news is that the Java API does not provide anything like reader-writer locks; the good news is that writing your own reader-writer lock is not difficult. We’ll now look at a simple implementation of a reader-writer lock:

import java.util.*;

class RWNode {
    static final int READER = 0;
    static final int WRITER = 1;
    Thread t;
    int state;
    int nAcquires;
    RWNode(Thread t, int state) {
        this.t = t;
        this.state = state;
        nAcquires = 0;
    }
}

public class RWLock {
    private Vector waiters;

    private int firstWriter() {
        Enumeration e;
        int index;
        for (index = 0, e = waiters.elements();
                                e.hasMoreElements(); index++) {
            RWNode node = (RWNode) e.nextElement();
            if (node.state == RWNode.WRITER)
                return index;
        }
        return Integer.MAX_VALUE;
    }

    private int getIndex(Thread t) {
        Enumeration e;
        int index;
        for (index = 0, e = waiters.elements();
                                e.hasMoreElements(); index++) {
            RWNode node = (RWNode) e.nextElement();
            if (node.t == t)
                return index;
        }
        return -1;
    }

    public RWLock() {
        waiters = new Vector();
    }

    public synchronized void lockRead() {
        RWNode node;
        Thread me = Thread.currentThread();
        int index = getIndex(me);
        if (index == -1) {
            node = new RWNode(me, RWNode.READER);
            waiters.addElement(node);
        }
        else node = (RWNode) waiters.elementAt(index);
        while (getIndex(me) > firstWriter()) {
            try {
                wait();
            } catch (Exception e) {}
        }
        node.nAcquires++;
    }
    public synchronized void lockWrite() {
        RWNode node;
        Thread me = Thread.currentThread();
        int index = getIndex(me);
        if (index == -1) {
            node = new RWNode(me, RWNode.WRITER);
            waiters.addElement(node);
        }
        else {
            node = (RWNode) waiters.elementAt(index);
            if (node.state == RWNode.READER)
                throw new IllegalArgumentException("Upgrade lock");
            node.state = RWNode.WRITER;
        }
        while (getIndex(me) != 0) {
            try {
                wait();
            } catch (Exception e) {}
        }
        node.nAcquires++;
    }

    public synchronized void unlock() {
        RWNode node;
        Thread me = Thread.currentThread();
        int index;
        index = getIndex(me);
        if (index  > firstWriter())
            throw new IllegalArgumentException("Lock not held");
        node = (RWNode) waiters.elementAt(index);
        node.nAcquires--;
        if (node.nAcquires == 0) {
            waiters.removeElementAt(index);
            notifyAll();
        }
    }
}

The interface to the reader-writer lock is very simple: there’s a method lockRead() to acquire the read lock, a method lockWrite() to acquire the write lock, and a method unlock() to release the lock (only a single unlock() method is required, for reasons we’ll explore in a moment). Just as in our QueuedBusyFlag class, threads attempting to acquire the lock are held in the waiters vector until they are first in line for the lock, but the definition of first in line has changed somewhat.

Because we need to keep track of how each thread wants to acquire the lock—whether it wants to acquire the read lock or the write lock—we need to create a class to encapsulate the information of the thread that made the request and the type of request it made. This is the RWNode class; our waiters queue now holds elements of type RWNode instead of the Thread elements that were present in the QueuedBusyFlag class.

The acquisition of the read lock is the same as the logic of the QueuedBusyFlag class except for the new definition of first in line. First in line for the read lock means that no other node ahead of us in the waiters queue wants to acquire the write lock. If the nodes that are ahead of us in the waiters queue want only to acquire the read lock, then we can go ahead and acquire the lock. Otherwise, we must wait until we are in position zero.

The acquisition of the write lock is stricter: we must be in position for the lock in order to acquire it, just as was required in our QueuedBusyFlag class.

The logic to keep track of the number of times a particular thread has acquired a lock has undergone a slight change. In the QueuedBusyFlag class, we were able to keep track of this number as a single instance variable. Since the read lock can be acquired by multiple threads simultaneously, we can no longer use a simple instance variable; we must associate the nAcquires count with each particular thread. This explains the new logic in both acquisition methods that checks to see if there is already a node associated with the calling thread.

Our reader-writer lock class does not have the notion of “upgrading” a lock; that is, if you hold the reader lock, you cannot acquire the writer lock. You must explicitly release the reader lock before you attempt to acquire the writer lock, or you will receive an IllegalArgumentException. If an upgrade feature were provided, the class itself would also have to release the reader lock before acquiring the writer lock. A true upgrade is not possible.

Finally, our reader-writer lock class contains some helper methods to search the waiters queue for the first node in the queue that represents a thread attempting to acquire the write lock (firstWriter()) and to find the index in the queue of the node associated with the calling thread (getIndex()). We can’t use the Vector class indexOf() method for this purpose because we’d have to pass the indexOf() method an object of type RWNode, but all we have is a thread.

Figure 8.3 shows the state of the waiters queue through several attempts at lock acquisition. Threads that have acquired the lock have a white background, whereas threads that are waiting to acquire the lock have a shaded background; each box notes whether the thread in question is attempting to acquire the read or the write lock.

Figure 8-3. Reader-writer lock queue

At point 1, thread T1 has acquired the read lock. Since it is the only thread in the waiters queue, the getIndex() method returns while the firstWriter() method returns MAX_VALUE. Since the index was less than the first writer, the lock is granted. At point 2, thread T2 has requested (and been granted) the read lock based on the same logic. Here’s a point at which two threads simultaneously have the read lock.

At point 3, thread T3 attempts to acquire the write lock. Because the index of T3 in the queue is 2, it cannot grab the lock and instead executes the wait() method inside the lockWrite() method. Then at point 4, thread T1 releases the read lock. The unlock() method calls notifyAll(), which wakes up T3, but because T3’s index in the queue is now 1, it again executes the wait() method.

At point 5, thread T1 again attempts to acquire the read lock, but this time, because its index in the queue (2) is greater than the index of the first writer (1), it does not immediately get the lock and instead executes the wait() method inside the lockRead() method. We might be tempted at this point to allow T1 to acquire the read lock since T2 already has the read lock and we generally allow multiple simultaneous acquisitions of the read lock. But if we implement that logic, we will starve the threads attempting to acquire the write lock: we could have multiple threads acquiring the read lock, and even though they might individually give up the lock frequently, one of them could always prevent a thread from acquiring the write lock. That’s the rationale for always putting the requesting thread into the waiters queue and then testing its index against other threads in the queue, as happens again at point 6.

At point 7, thread T2 releases the read lock, notifying all other threads that the lock is free. Because T3 is a writer lock with an index of 0, the lockWrite() method gives it the lock while the other threads in the lockRead() method execute wait().

Finally, at point 8, thread T3 releases the lock. This time when the two remaining threads are notified that the lock is free, they are both able to acquire it, as their indices are less than MAX_VALUE (the integer returned when there are no threads attempting to acquire the write lock). Once again we have multiple threads that have simultaneous access to the read lock. This is also a case where the notifyAll() method makes it easy to wake up multiple threads at once.

The last example that we’ll look at in this section is the starvation that is associated with priority inversion. On the virtual machines that we’ve looked at, priority inversion is solved by priority inheritance.

But what if we need to use the BusyFlag class to lock at a large scope in our program? How does priority inheritance affect our BusyFlag class? Not surprisingly, it does not have any affect on the behavior of this class, because we are only simulating a lock, and are using Java’s synchronization locks only to protect against the race conditions that occur within this task. Once a BusyFlag is acquired and the getBusyFlag() method exits, the synchronization lock protecting the getBusyFlag() method is released. As far as the Java virtual machine is concerned, no synchronization locks are held at this point.

A low-priority thread that holds a BusyFlag will never have its priority adjusted by the virtual machine if a high-priority flag attempts to acquire the same BusyFlag: because they never attempt to execute the same synchronized method at the same time, the virtual machine is unaware that they are competing with each other at all.

We can easily implement a version of the BusyFlag class that has support for priority inheritance:

public class PriorityBusyFlag extends BusyFlag {
    protected int currentPriority;

    public synchronized void getBusyFlag() {
        while (tryGetBusyFlag() == false) {
            Thread prevOwner = getBusyFlagOwner();
            try {
                int curP = Thread.currentThread().getPriority();
                if (curP > prevOwner.getPriority()) {
                    prevOwner.setPriority(curP);
                }
                wait();
            } catch (Exception e) {}
        }
    }

    public synchronized boolean tryGetBusyFlag() {
        boolean succeed = super.tryGetBusyFlag();
        if (succeed)
            currentPriority = Thread.currentThread().getPriority();
        return succeed;
    }

    public synchronized void freeBusyFlag() {
        if (getBusyFlagOwner() == Thread.currentThread()) {
            super.freeBusyFlag();
            if (getBusyFlagOwner() == null) {
                Thread.currentThread().setPriority(currentPriority);
                notifyAll();
            }
        }
    }
}

Usage of the PriorityBusyFlag class is similar to usage of the BusyFlag class. The two differences are that the requesting thread will raise the priority of the thread that already owns the BusyFlag if the priority of the requesting thread is higher than the priority of the owning thread, and the original priority of the thread will be restored when the BusyFlag is freed.

This behavior is functionally identical to native-threading systems that support priority inheritance. However, in a virtual machine, these details are handled internally. The best that we can do is to use the PriorityBusyFlag class in a cooperative manner by using the setPriority() method. If another thread also changes the priority of threads, or the threads themselves are changing their priority, this cooperative technique will not work.