United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-6281487 ReentrantReadWriteLock: readers repeatedly acquire lock while writer is waiting
JDK-6281487 : ReentrantReadWriteLock: readers repeatedly acquire lock while writer is waiting

Details
Type:
Bug
Submit Date:
2005-06-07
Status:
Resolved
Updated Date:
2011-02-16
Project Name:
JDK
Resolved Date:
2005-09-04
Component:
core-libs
OS:
windows_2000
Sub-Component:
java.util.concurrent
CPU:
x86
Priority:
P4
Resolution:
Fixed
Affected Versions:
5.0
Fixed Versions:

Related Reports
Relates:
Relates:
Relates:
Relates:

Sub Tasks

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 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
EVALUATION

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



Hardware and Software, Engineered to Work Together