JDK-6281487 : ReentrantReadWriteLock: readers repeatedly acquire lock while writer is waiting
  • Type: Bug
  • Status: Resolved
  • Resolution: Fixed
  • Component: core-libs
  • Sub-Component: java.util.concurrent
  • Priority: P4
  • Affected Version: 5.0
  • OS: windows_2000
  • CPU: x86
  • Submit Date: 2005-06-07
  • Updated Date: 2011-02-16
  • Resolved Date: 2005-09-04
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availabitlity Release.

To download the current JDK release, click here.
JDK 6
6 b51Resolved
Related Reports
Relates :  
Relates :  
Relates :  
Relates :  
Description
FULL PRODUCT VERSION :
java version "1.5.0"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0-b64)
Java HotSpot(TM) Client VM (build 1.5.0-b64, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows 2000 [Version 5.00.2195]

EXTRA RELEVANT SYSTEM CONFIGURATION :
Single CPU Machine

A DESCRIPTION OF THE PROBLEM :
The documentation for ReentrantReadWriteLock states:

"In either case, if readers are active and a writer enters the lock then no subsequent readers will  be granted the read lock until after that writer has acquired and  released the write lock."

In the sample code below (for the NON-FAIR policy),  the readers consistantly release and reobtain  the lock despite the fact that the writer is waiting to enter.
What actually happens in this example is that the writer is completely starved and cannot enter until there are no longer any reader threads present at all.

When using the FAIR policy this does not happen.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Run the source code below.

 The code creates two reader threads which in a loop obtain and release the shared lock, and one writer thread which attempts to obtain and release the exclusive lock.

The log printouts outputted by the program  show the approximate order and number of times that each thread obtains and releases the lock.



EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
After running the example and examining the output, we should have seen that sometime after this line is printed:
             Writer: WAIT FOR LOCK
the reader threads would wait for the lock, and the writer thread would obtain it.

ACTUAL -
The actual output when run on my machine was:

Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 1)
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 1)
Writer: WAIT FOR LOCK
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 2)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 2)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 3)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 3)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 4)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 4)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 5)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 5)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 6)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 6)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 7)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 7)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 8)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 8)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 9)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 9)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 10)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 10)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 11)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 11)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 12)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 12)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 13)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 13)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 14)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 14)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 15)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 15)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 16)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 16)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 17)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 17)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 18)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 18)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 19)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 19)
Reader1: RELEASED LOCK
Reader1: WAIT FOR LOCK
Reader1: RECEIVED LOCK (count: 20)
Reader2: RELEASED LOCK
Reader2: WAIT FOR LOCK
Reader2: RECEIVED LOCK (count: 20)
Reader1: RELEASED LOCK
Reader1: EXIT LOOP
Writer: RECEIVED LOCK (count: 1)
Reader2: RELEASED LOCK
Reader2: EXIT LOOP
Writer: RELEASED LOCK
Writer: EXIT LOOP

You can see that both reader threads entered and exited  the lock 20 times, without allowing the writer to enter even once.  Line 5 of the output shows that the writer thread is waiting to enter the lock during this entire period.

I have tried increasing the time period for running the test, and playing with the number of threads etc. but consistantly the writer never enters the lock until all reader threads have completed.


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
// Code to reproduce
import java.util.concurrent.locks.*;
/**
 * Test ReentrantReadWrite Lock.
 * This code shows how the reader threads consistantly enter the lock despite the fact that the writer thread is waiting
 * to enter.
 * This contradicts documention of ReentrantReadWriteLock and causes the writer to never receive CPU until all readers are finished
 */
public class TestReaderWriter extends Thread {

    public void run() {
        // loop for specified time
        while (System.currentTimeMillis() < stoptime) {
            // aquire lock
            log("WAIT FOR LOCK");
            lock.lock();
            // increment counter and wait a bit
            count++;
            log("RECEIVED LOCK (count: "+count+")");

            try { Thread.sleep(500);  }
            catch (InterruptedException e) {}

            // release lock
            finally {
                lock.unlock();
                log("RELEASED LOCK");
            }
        }
        log("EXIT LOOP");
    }

    void log(String s) {
        System.out.println(getName() + ": " + s);
    }

    public TestReaderWriter(String name, Lock lock) {
        super(name);
        this.lock = lock;
    }

    Lock   lock;
    long count;
    static long stoptime;

    public static void main(String[] args) {
        // run this for approximately 10 seconds
        stoptime = System.currentTimeMillis() + 10000;

        ReentrantReadWriteLock rwlock = new ReentrantReadWriteLock(false);

        // start 2 readers threads
        for (int i = 1; i <= 2; i++) {
            new Thread(new TestReaderWriter("Reader"+ i, rwlock.readLock())).start();
        }
        // start 1 writer thread
        new Thread(new TestReaderWriter("Writer", rwlock.writeLock())).start();
    }
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Using the FAIR policy fixes this problem.
###@###.### 2005-06-07 12:11:48 GMT

Comments
EVALUATION Doug Lea reevaluated the spec and implementation of ReentrantReadWriteLock, and is providing a fix.
2005-08-02

EVALUATION Doug Lea wries: "This is not a bug. It might be a quality of implementation issue. The spec specifically does not promise how long it will take for a writer to "enter the lock", and a scheduler is free to indefinitely postpone its progress. In practice, on a multiprocessor, the writer will usually be able to enter soon. On a uniprocessor, it may be starved out for a very long time. Since Java makes no progress guarantees, there is not even a maximum time bound. As the submitter seemed to realize, the reason that "fair" mode exists is so that programmers can avoid starvation problems when they occur. In general, they may occur (mainly on uniprocessors) if the stream of readers is continuous so reader threads do not ever block and become descheduled on their own while not holding lock, in which case the only opportunities for the writer to enter are due to rare random interactions with OS-level thread scheduling." I plan to close this as "not a defect" eventually, but I'll keep it open for a while in case some clever person comes up with a way to provide a better Quality Of Implementation. ###@###.### 2005-06-07 16:02:48 GMT
2005-06-07