Computers have been my hobby since I was 12. Now I'm a freelance Java developer. Like many other developers I am working on various private projects. Some are open source components (Butterfly Components - DI container, web ui, persistence api, mock test api etc.). Some are the tutorials at tutorials.jenkov.com. Yet others are web projects. I hold a bachelor degree in computer science and a master degree in IT focused on P2P networks. Jakob has posted 35 posts at DZone. You can read more from them at their website. View Full User Profile

Java Concurrency: Read / Write Locks

06.09.2008
| 39297 views |
  • submit to reddit

Read Reentrance

To make the ReadWriteLock reentrant 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 the lockRead() and unlockRead() 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 readers.get(callingThread) != null;
}

}
As you can see read reentrance is only granted if no threads are currently writing to the resource. As you can see, 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 the lockWrite() and unlockWrite() methods look after that little change:

public class ReadWriteLock{

private Map&lt;Thread, Integer&gt; readingThreads =
new HashMap&lt;Thread, Integer&gt();

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(writingThread != callingThread) return false;
return true;
}

private boolean hasReaders(){
return readingThreads.size() > 0;
}

}

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 the writeLock() 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(writingThread != callingThread) return false;
return true;
}

private boolean hasReaders(){
return readingThreads.size() > 0;
}

private boolean isOnlyReader(Thread thread){
return readers == 1 && readingThreads.get(callingThread) != null;
}

}

Now the ReadWriteLock class 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 read access no other threads can have read nor write access, so it is not dangerous. Here is how the canGrantReadAccess() 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 reentran ReadWriteLock implementation. 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 a ReadWriteLock, and the critical section may throw exceptions, it is important to call the readUnlock() and writeUnlock() methods from inside a finally-clause. Doing so makes sure that the ReadWriteLock is 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 the ReadWriteLock is unlocked in case an exception is thrown from the code in the critical section. If unlockWrite() was not called from inside a finally-clause, and an exception was thrown from the critical section, the ReadWriteLock would remain write locked forever, causing all threads calling lockRead() or lockWrite() on that ReadWriteLock instance to halt indefinately. The only thing that could unlock the ReadWriteLockagain would be if the ReadWriteLock is reentrant, and the thread that had it locked when the exception was thrown, later succeeds in locking it, executing the critical section and calling unlockWrite() again afterwards. That would unlock the ReadWriteLock again. But why wait for that to happen, if it happens? Calling unlockWrite() from a finally-clause is a much more robust solution.

References
Published at DZone with permission of its author, Jakob Jenkov. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Jakob Jenkov replied on Wed, 2008/06/11 - 4:31pm in response to: David Karr

Hmm... seems like it... I'll have to check what Holub wrote when I get near the book again.

Anyways, this just goes to show how many details there are to get 100% straight in Java Concurrency. That is why I am writing the trail -  as notes for myself and fellow developers. I have worked a reasonable amount with Java concurrency, but I am no where near the expertise of Doug Lea, Allen Holub, Brian Goetz etc. Any comments like this article has received are appreciated, and the texts in the tutorial will be updated to reflect any corrections pointed out.

Slava Imeshev replied on Wed, 2008/06/11 - 5:01pm in response to: Jakob Jenkov

[quote=jj83777]

Any comments like this article has received are appreciated, and the texts in the tutorial will be updated to reflect any corrections pointed out.

[/quote]

 

Yes, it does demonstrate that multithreading is hard to do right.

 As a friendly suggestion, I'd put a banner or a comment in the code stating that this code is to demonstrate approaches and should not be considered production quality. People tend to consider any cut'n'paste code that complies a production quiality and this one is not. Right now it does not keep track of nested reads deeper than one which will cause a self-deadlock.

 

Slava

Jakob Jenkov replied on Wed, 2008/06/11 - 5:08pm

Hi Slava, I am working on the correction as we speek which will correct the nested read and write lock errors. I'll post a comment when its ready for you to look at.

David Karr replied on Wed, 2008/06/11 - 5:37pm in response to: Slava Imeshev

So Slava, if an expert like you misses the fact that the nested read problem has already been noted and discussed (see the earlier comments), what hope do we have that beginners will read a boilerplate statement about "production quality" and take it to heart? ;)

Slava Imeshev replied on Wed, 2008/06/11 - 5:57pm in response to: David Karr

David,

You are right. The priority of spotting this problem belongs to you, indeed :)

I assume double-quoting the production quality bears certain irony which I fail to recognize, just as the references to beginners and experts :) To make sure we are on the same page, that's what I meant: http://tutor2u.net/business/gcse/production_quality_introduction.htm

To get practical and given that the promised fix is still not there, what would be your suggestions regarding addressing the nested read problem?

Slava

Cacheonix - Clustered Cache and Data Grid for Java

Jakob Jenkov replied on Wed, 2008/06/11 - 6:02pm

Impatience is a virtue ;-)

 

The updates are ready now, here on JavaLobby. I'll repost them on my own blog either later today or tomorrow. 

Slava Imeshev replied on Wed, 2008/06/11 - 6:17pm in response to: Jakob Jenkov

[quote=jj83777]

The updates are ready now, here on JavaLobby. I'll repost them on my own blog either later today or tomorrow.

[/quote]

 

Awesome! Do you think you could get rid of put access here?

 

else { readingThreads.put(callingThread, (accessCount -1)); }  

 

Slava

Jakob Jenkov replied on Thu, 2008/06/12 - 12:19am

It is probably possible to optimize the design for performance if you want to. For instance, if the read access counter was a class rather than just an int, you could just update the counter. For instance:

 

 

public class AccessCount{
  public int count = 0;
}

Then in the lockRead() and unlockRead() you could do something like this:

AccessCount accessCount = getReadAccessCount(callingThread);

if(accessCount == null){
  accessCount = new AccessCount();
  readingThreads.put(callingThread, accessCount);
}
accessCount.count++;

 

 





AccessCount accessCount = getReadAccessCount(callingThread);
if(accessCount.count == 1){
  readingThreads.remove(callingThread);
} else {
  accessCount.count--;
}

Slava Imeshev replied on Thu, 2008/06/12 - 2:59am

 

Exactly! Great job, Jacob!

Slava 

Vamsi Krishna replied on Sun, 2014/11/02 - 7:18am

Its really very nice thanks for the information ssc results 2015 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.