[concurrency-interest] ReadWriteLock Deadlock Detection Flaws?

Sam Berlin sberlin at gmail.com
Mon Jun 29 10:09:44 EDT 2009


Thanks for the reply, Martin.  Do you think it would be possible to amend
the description in the javadocs saying that the current detection is based
on exlusive locks and does not work properly with ReadWriteLocks when the
ReadLock is held first?  Without that, it's a little misleading when the
descriptions say that deadlock can be detected, but deadlock isn't always
detected.

That, or revisit the model and fix it. :-)   (This would be my first
choice!)

The VM does seem to have knowledge that shared AbstractOwnableSynchronizers
are acquired (they are reported in thread dumps as LockInfos on ThreadInfo),
so it doesn't seem to be an insurmountable task.  In the absence of built-in
VM support, how possible do you think it would be to traverse ThreadInfo
objects and look at the LockInfo[] of what's locked & LockInfo of what it's
waiting on for each ThreadInfo to deduce a deadlock?

Sam

On Sun, Jun 28, 2009 at 12:31 PM, Martin Buchholz <martinrb at google.com>wrote:

> The deadlock detection is based on traditional exclusive locks,
> where a lock can only have one locker.
>
> I think the behavior can be understood by thinking about how
> the libraries communicate their state to hotspot.
> - whenever a lock is acquired _exclusively_
>   AbstractOwnableSynchronizer
> - whenever a thread is waiting to acquire a lock.
>   LockSupport.park(lockObject)
>
> In the case of T1 holding the read lock while T2 tries to acquire
> the write lock,  hotspot is aware of T2's state,
> but is not notified that T1 is  preventing it.
>
> Fixing this would require revisiting the monitoring model,
> which is unlikely to happen.
>
> Martin
>
> On Fri, Jun 26, 2009 at 07:13, Sam Berlin <sberlin at gmail.com> wrote:
>
>> There seem to be some classic scenarios of deadlock where the VM doesn't
>> detect deadlock.  With the following two threads:
>>
>>    new Thread(new Runnable() {  // Thread 1
>>             @Override
>>             public void run() {
>>                 System.out.println("t1 locking a");
>>                 a.lock();
>>                 try {
>>                     System.out.println("t1 locked a");
>>                     try {Thread.sleep(1000); } catch(Exception e) {}
>>                     System.out.println("t1 locking b");
>>                     b.lock();
>>                     try {
>>                         System.out.println("t1 locked b");
>>                         try {Thread.sleep(100000); } catch(Exception e) {}
>>                     } finally {
>>                         b.unlock();
>>                     }
>>                 } finally {
>>                     a.unlock();
>>                 }
>>             }
>>         }).start();
>>
>>         new Thread(new Runnable() {  // Thread 2
>>             @Override
>>             public void run() {
>>                 System.out.println("t2 locking b");
>>                 b.lock();
>>                 try {
>>                     System.out.println("t2 locked b");
>>                     System.out.println("t2 locking a");
>>                     a.lock();
>>                     try {
>>                         System.out.println("t2 locked a");
>>                         try {Thread.sleep(100000); } catch(Exception e) {}
>>                     } finally {
>>                         a.unlock();
>>                     }
>>                 } finally {
>>                     b.unlock();
>>                 }
>>             }
>>         }).start();
>>
>> This prints out:
>>  t1 locking a
>>  t1 locked a
>>  t2 locking b
>>  t2 locked b
>>  t2 locking a
>>  t1 locking b
>>  [and flow halts because of deadlock]
>>
>> In the simple case of 'a' and 'b' being simple ReentrantLocks (or Objects
>> and using synchronize()), the VM correctly finds a deadlock.  If 'a' and 'b'
>> are ReentrantReadWriteLocks, there are some conditions where it will not
>> find a deadlock.
>>
>> Here's the possible deadlocking scenarios and the result:
>>   Thread 1 & Thread 2 all lock writeLock ---> VM finds deadlock
>>   Thread 1 locks all writeLocks, Thread 2 'b' locks writeLock, 'a' locks
>> readLock --> VM finds deadlock
>>   Thread 1 locks all writeLocks, Thread 2 'b' locks readLock , 'a' locks
>> writeLock--> NO DEADLOCK FOUND
>>   Thread 1 locks all writeLocks, Thread 2 locks all readLocks --> NO
>> DEADLOCK FOUND
>>   Thread 1 'a' locks writeLock, 'b' locks readLock, Thread 2 locks all
>> writeLocks --> VM Finds deadlock
>>   Thread 1 'a' locks readLock, 'b' locks writeLock, Thread 2 locks all
>> writeLocks --> NO DEADLOCK FOUND
>>   Thread 1 locks all readLocks, Thread 2 locks all writeLocks --> NO
>> DEADLOCK FOUND
>>   Thread 1 'a' locks writeLock, 'b' locks readLock, Thread 2 'b' locks
>> writeLock, 'a' locks readLock --> VM finds deadlock
>>   Thread 1 'a' locks readLock, 'b' locks writeLock, Thread 2 'b' locks
>> readLock, 'a' locks writeLock --> NO DEADLOCK FOUND
>>
>> The pattern seems to be that whenever a deadlock would be encountered due
>> to out-of-order locking, if the readLock was locked before a
>> deadlock-inducing writeLock, then no deadlock is found.  Conversely, if the
>> writeLock is locked before the deadlock-inducing readLock, the VM does find
>> deadlock.
>>
>> This is with JDK 1.6.0_12-b04.
>>
>> Is this a known issue, a bug, or something else?
>>
>> Thanks much,
>>  Sam
>>
>>
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20090629/daf75960/attachment.html>


More information about the Concurrency-interest mailing list