A read / write lock is more sophisticated lock than theLockimplementations shown in the textLocks in Java. Imagine you have an application that reads and writes some resource, but writing it is not done as much as reading it is. Two threads reading the same resource does not cause problems for each other, so multiple threads that want to read the resource are granted access at the same time, overlapping. But, if a single thread wants to write to the resource, no other reads nor writes must be in progress at the same time. To solve this problem of allowing multiple readers but only one writer, you will need a read / write lock.
Java 5 comes with read / write lock implementations in thejava.util.concurrentpackage. Even so, it may still be useful to know the theory behind their implementation.
Read / Write Lock Java Implementation
First let's summarize the conditions for getting read and write access to the resource:
| Read Access | If no threads are writing, and no threads have requested write access. |
|---|---|
| Write Access | If no threads are reading or writing. |
If a thread wants to read the resource, it is okay as long as no threads are writing to it, and no threads have requested write access to the resource. By up-prioritizing write-access requests we assume that write requests are more important than read-requests. Besides, if reads are what happens most often, and we did not up-prioritize writes,starvationcould occur. Threads requesting write access would be blocked until all readers had unlocked theReadWriteLock. If new threads were constantly granted read access the thread waiting for write access would remain blocked indefinately, resulting instarvation. Therefore a thread can only be granted read access if no thread has currently locked theReadWriteLockfor writing, or requested it locked for writing.
A thread that wants write access to the resource can be granted so when no threads are reading nor writing to the resource. It doesn't matter how many threads have requested write access or in what sequence, unless you want to guarantee fairness between threads requesting write access.
With these simple rules in mind we can implement aReadWriteLockas shown below:
public class ReadWriteLock{
private int readers = 0;
private int writers = 0;
private int writeRequests = 0;
public synchronized void lockRead() throws InterruptedException{
while(writers > 0 || writeRequests > 0){
wait();
}
readers++;
}
public synchronized void unlockRead(){
readers--;
notifyAll();
}
public synchronized void lockWrite() throws InterruptedException{
writeRequests++;
while(readers > 0 || writers > 0){
wait();
}
writeRequests--;
writers++;
}
public synchronized void unlockWrite() throws InterruptedException{
writers--;
notifyAll();
}
}
TheReadWriteLockhas two lock methods and two unlock methods. One lock and unlock method for read access and one lock and unlock for write access.
The rules for read access are implemented in thelockRead()method. All threads get read access unless there is a thread with write access, or one or more threads have requested write access.
The rules for write access are implemented in thelockWrite()method. A thread that wants write access starts out by requesting write access (writeRequests++). Then it will check if it can actually get write access. A thread can get write access if there are no threads with read access to the resource, and no threads with write access to the resource. How many threads have requested write access doesn't matter.
It is worth noting that bothunlockRead()andunlockWrite()callsnotifyAll()rather thannotify(). To explain why that is, imagine the following situation:
Inside the ReadWriteLock there are threads waiting for read access, and threads waiting for write access. If a thread awakened bynotify()was a read access thread, it would be put back to waiting because there are threads waiting for write access. However, none of the threads awaiting write access are awakened, so nothing more happens. No threads gain neither read nor write access. By callingnoftifyAll()all waiting threads are awakened and check if they can get the desired access.
CallingnotifyAll()also has another advantage. If multiple threads are waiting for read access and none for write access, andunlockWrite()is called, all threads waiting for read access are granted read access at once - not one by one.
Read / Write Lock Reentrance
TheReadWriteLockclass shown earlier is notreentrant. If a thread that has write access requests it again, it will block because there is already one writer - itself. Furthermore, consider this case:
- Thread 1 gets read access
- Thread 2 requests write access but is blocked because there is one reader.
- Thread 1 re-requests read access (re-enters the lock), but is blocked because there is a write request
In this situation the previousReadWriteLockwould lock up - a situation similar to deadlock. No threads requesting neither read nor write access would be granted so.
To make theReadWriteLockreentrant it is necessary to make a few changes. Reentrance for readers and writers will be dealt with separately.
Read Reentrance
To make theReadWriteLockreentrant for readers we will first establish the rules for read reentrance:
- A thread is granted read reentrance if it can get read access (no writers or write requests), or if it already has read access (regardless of write requests).
To determine if a thread has read access already a reference to each thread granted read access is kept in a Map along with how many times it has acquired read lock. When determing if read access can be granted this Map will be checked for a reference to the calling thread. Here is how thelockRead()andunlockRead()methods looks after that change:
public class ReadWriteLock{
private Map<Thread, Integer> readingThreads =
new HashMap<Thread, Integer>();
private int writers = 0;
private int writeRequests = 0;
public synchronized void lockRead() throws InterruptedException{
Thread callingThread = Thread.currentThread();
while(! canGrantReadAccess(callingThread)){
wait();
}
readingThreads.put(callingThread,
(getAccessCount(callingThread) + 1));
}
public synchronized void unlockRead(){
Thread callingThread = Thread.currentThread();
int accessCount = getAccessCount(callingThread);
if(accessCount == 1){ readingThreads.remove(callingThread); }
else { readingThreads.put(callingThread, (accessCount -1)); }
notifyAll();
}
private boolean canGrantReadAccess(Thread callingThread){
if(writers > 0) return false;
if(isReader(callingThread) return true;
if(writeRequests > 0) return false;
return true;
}
private int getReadAccessCount(Thread callingThread){
Integer accessCount = readingThreads.get(callingThread);
if(accessCount == null) return 0;
return accessCount.intValue();
}
private boolean isReader(Thread callingThread){
return readingThreads.get(callingThread) != null;
}
}
As you can see read reentrance is only granted if no threads are currently writing to the resource. Additionally, if the calling thread already has read access this takes precedence over any writeRequests.
Write Reentrance
Write reentrance is granted only if the thread has already write access. Here is how thelockWrite()andunlockWrite()methods look after that change:
public class ReadWriteLock{
private Map<Thread, Integer> readingThreads =
new HashMap<Thread, Integer>();
private int writeAccesses = 0;
private int writeRequests = 0;
private Thread writingThread = null;
public synchronized void lockWrite() throws InterruptedException{
writeRequests++;
Thread callingThread = Thread.currentThread();
while(! canGrantWriteAccess(callingThread)){
wait();
}
writeRequests--;
writeAccesses++;
writingThread = callingThread;
}
public synchronized void unlockWrite() throws InterruptedException{
writeAccesses--;
if(writeAccesses == 0){
writingThread = null;
}
notifyAll();
}
private boolean canGrantWriteAccess(Thread callingThread){
if(hasReaders()) return false;
if(writingThread == null) return true;
if(!isWriter(callingThread)) return false;
return true;
}
private boolean hasReaders(){
return readingThreads.size() > 0;
}
private boolean isWriter(Thread callingThread){
return writingThread == callingThread;
}
}
Notice how the thread currently holding the write lock is now taken into account when determining if the calling thread can get write access.
Read to Write Reentrance
Sometimes it is necessary for a thread that have read access to also obtain write access. For this to be allowed the thread must be the only reader. To achieve this thewriteLock()method should be changed a bit. Here is what it would look like:
public class ReadWriteLock{
private Map<Thread, Integer> readingThreads =
new HashMap<Thread, Integer>();
private int writeAccesses = 0;
private int writeRequests = 0;
private Thread writingThread = null;
public synchronized void lockWrite() throws InterruptedException{
writeRequests++;
Thread callingThread = Thread.currentThread();
while(! canGrantWriteAccess(callingThread)){
wait();
}
writeRequests--;
writeAccesses++;
writingThread = callingThread;
}
public synchronized void unlockWrite() throws InterruptedException{
writeAccesses--;
if(writeAccesses == 0){
writingThread = null;
}
notifyAll();
}
private boolean canGrantWriteAccess(Thread callingThread){
if(isOnlyReader(callingThread)) return true;
if(hasReaders()) return false;
if(writingThread == null) return true;
if(!isWriter(callingThread)) return false;
return true;
}
private boolean hasReaders(){
return readingThreads.size() > 0;
}
private boolean isWriter(Thread callingThread){
return writingThread == callingThread;
}
private boolean isOnlyReader(Thread thread){
return readers == 1 && readingThreads.get(callingThread) != null;
}
}
Now theReadWriteLockclass is read-to-write access reentrant.
Write to Read Reentrance
Sometimes a thread that has write access needs read access too. A writer should always be granted read access if requested. If a thread has write access no other threads can have read nor write access, so it is not dangerous. Here is how thecanGrantReadAccess()method will look with that change:
public class ReadWriteLock{
private boolean canGrantReadAccess(Thread callingThread){
if(isWriter(callingThread)) return true;
if(writingThread != null) return false;
if(isReader(callingThread) return true;
if(writeRequests > 0) return false;
return true;
}
}
Fully Reentrant ReadWriteLock
Below is the fully reentranReadWriteLockimplementation. I have made a few refactorings to the access conditions to make them easier to read, and thereby easier to convince yourself that they are correct.
public class ReadWriteLock{
private Map<Thread, Integer> readingThreads =
new HashMap<Thread, Integer>();
private int writeAccesses = 0;
private int writeRequests = 0;
private Thread writingThread = null;
public synchronized void lockRead() throws InterruptedException{
Thread callingThread = Thread.currentThread();
while(! canGrantReadAccess(callingThread)){
wait();
}
readingThreads.put(callingThread,
(getReadAccessCount(callingThread) + 1));
}
private boolean canGrantReadAccess(Thread callingThread){
if( isWriter(callingThread) ) return true;
if( hasWriter() ) return false;
if( isReader(callingThread) ) return true;
if( hasWriteRequests() ) return false;
return true;
}
public synchronized void unlockRead(){
Thread callingThread = Thread.currentThread();
if(!isReader(callingThread)){
throw new IllegalMonitorStateException("Calling Thread does not" +
" hold a read lock on this ReadWriteLock");
}
int accessCount = getReadAccessCount(callingThread);
if(accessCount == 1){ readingThreads.remove(callingThread); }
else { readingThreads.put(callingThread, (accessCount -1)); }
notifyAll();
}
public synchronized void lockWrite() throws InterruptedException{
writeRequests++;
Thread callingThread = Thread.currentThread();
while(! canGrantWriteAccess(callingThread)){
wait();
}
writeRequests--;
writeAccesses++;
writingThread = callingThread;
}
public synchronized void unlockWrite() throws InterruptedException{
if(!isWriter(Thread.currentThread()){
throw new IllegalMonitorStateException("Calling Thread does not" +
" hold the write lock on this ReadWriteLock");
}
writeAccesses--;
if(writeAccesses == 0){
writingThread = null;
}
notifyAll();
}
private boolean canGrantWriteAccess(Thread callingThread){
if(isOnlyReader(callingThread)) return true;
if(hasReaders()) return false;
if(writingThread == null) return true;
if(!isWriter(callingThread)) return false;
return true;
}
private int getReadAccessCount(Thread callingThread){
Integer accessCount = readingThreads.get(callingThread);
if(accessCount == null) return 0;
return accessCount.intValue();
}
private boolean hasReaders(){
return readingThreads.size() > 0;
}
private boolean isReader(Thread callingThread){
return readingThreads.get(callingThread) != null;
}
private boolean isOnlyReader(Thread callingThread){
return readingThreads.size() == 1 &&
readingThreads.get(callingThread) != null;
}
private boolean hasWriter(){
return writingThread != null;
}
private boolean isWriter(Thread callingThread){
return writingThread == callingThread;
}
private boolean hasWriteRequests(){
return this.writeRequests > 0;
}
}
Calling unlock() From a finally-clause
When guarding a critical section with aReadWriteLock, and the critical section may throw exceptions, it is important to call thereadUnlock()andwriteUnlock()methods from inside afinally-clause. Doing so makes sure that theReadWriteLockis unlocked so other threads can lock it. Here is an example:
lock.lockWrite();
try{
//do critical section code, which may throw exception
} finally {
lock.unlockWrite();
}
This little construct makes sure that theReadWriteLockis unlocked in case an exception is thrown from the code in the critical section. IfunlockWrite()was not called from inside afinally-clause, and an exception was thrown from the critical section, theReadWriteLockwould remain write locked forever, causing all threads callinglockRead()orlockWrite()on thatReadWriteLockinstance to halt indefinately. The only thing that could unlock theReadWriteLockagain would be if theReadWriteLockis reentrant, and the thread that had it locked when the exception was thrown, later succeeds in locking it, executing the critical section and callingunlockWrite()again afterwards. That would unlock theReadWriteLockagain. But why wait for that to happen,ifit happens? CallingunlockWrite()from afinally-clause is a much more robust solution.