db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Knut Anders Hatlen (JIRA)" <j...@apache.org>
Subject [jira] Commented: (DERBY-2327) Reduce monitor contention in LockSet
Date Fri, 09 Mar 2007 14:13:24 GMT

    [ https://issues.apache.org/jira/browse/DERBY-2327?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12479595

Knut Anders Hatlen commented on DERBY-2327:

Here are my thoughts on how to attack this issue:

With the refactoring that improved the encapsulation of LockSet, it
should be possible to plug in another implementation of LockSet (say
ConcurrentLockSet) with very little need for changes in other
classes. The new implementation of LockSet will use a
ConcurrentHashMap instead of a HashMap, and it will not synchronize on
the LockSet object. With the exception of the creation of the
diagnostic lock table (VTI) and the deadlock detection, all the
synchronized blocks in LockSet touch only one entry in the lock table,
so I think the natural synchronization granularity is a single entry
(which corresponds to a single Lockable object).

For the parts of the code that only touch one entry, I think the new
implementation could basically be the same as the old one, only that
it synchronizes on the lock entry instead of on the LockSet. Since
they only lock one entry at a time, there shouldn't be any risk of a
Java-level deadlock.

One thing that becomes trickier with a ConcurrentHashMap, is that you
don't synchronize on the map so another thread might for instance
remove an entry from the map after you have fetched it and before you
have locked/synchronized on it. Therefore, the fetching from the map
must be performed in a loop where you fetch, lock and finally check
that no one has removed it.

In the current LockSet implementation, the creation of the virtual
lock table synchronizes on the LockSet. In order to guarantee that a
consistent snapshot of the lock table is made, some sort of global
synchronization is needed, but that would bring us back to square one
with regards to concurrency. However, the javadoc for the LockTable
VTI says that consistency is not a requirement:

> The LockTable virtual table takes a snap shot of the lock table
> while the system is in flux, so it is possible that some locks may
> be in transition state while the snap shot is taken. We choose to do
> this rather then impose extranous timing restrictions so that the
> use of this tool will not alter the normal timing and flow of
> execution in the application.

Therefore, I think it will be OK to just get an iterator from the
ConcurrentHashMap (whose javadoc says that the iterator is "weakly
consistent") and lock/synchronize the entries one by one.

On the other hand, the deadlock detection does require a certain
amount of consistency in the snapshot it's working on. To illustrate
it, consider this example:

  1. When the deadlock detection starts, A is waiting for B.
  2. The deadlock detection sees that A waits for B.
  3. B unlocks the object A is waiting for, and A can continue.
  4. B then tries to lock an object which A holds and must wait.
  5. The deadlock detection sees that B waits for A.

The deadlock detection then believes that A waits for B which waits
for A. That is, it believes we have a deadlock, when in fact A is not
waiting for B anymore. 

I think this problem can be avoided by following a two-phase locking
scheme when synchronizing on the entries of the lock table. That is,
we lock the entries one by one as we see them, but don't unlock any of
them until we have finished the traversal. This way, we know that all
the waiters we have seen while traversing the lock table are still
waiting. In the example above, it would mean that in (3) B would not
be allowed to unlock the object until the deadlock detection had
finished. It would therefore see that A was waiting for B, but not
that B was waiting for A, so it would (correctly) not report a
deadlock between A and B.

This approach does not ensure that the deadlock detection has a
complete and consistent wait-for graph, since ConcurrentHashMap's
iterator doesn't guarantee that concurrent modifications are visible,
but I think it will ensure that (a) all deadlocks present when the
deadlock detection starts will be detected, and (b) no false deadlocks
will be reported.

Since the iterator doesn't guarantee that the ordering will be the
same each time, we can only have one thread performing deadlock
detection at a time in order to avoid Java-level deadlocks. Also, no
thread can start deadlock detection when it is synchronized on an
entry in the lock table.

Are there any comments to this approach? Any false/suspicious
assumptions or anything I have forgotten?

> Reduce monitor contention in LockSet
> ------------------------------------
>                 Key: DERBY-2327
>                 URL: https://issues.apache.org/jira/browse/DERBY-2327
>             Project: Derby
>          Issue Type: Sub-task
>          Components: Performance, Services
>    Affects Versions:
>            Reporter: Knut Anders Hatlen
>         Assigned To: Knut Anders Hatlen
>            Priority: Minor
>         Attachments: ConcurrentHashMap.diff, derby-2327-1a.diff, derby-2327-1a.stat
> When multiple threads enter the lock manager, only one can access the hash table in LockSet.
To improve scalability on multiple CPUs, it should be possible to have more than one thread
accessing the lock table at the same time.

This message is automatically generated by JIRA.
You can reply to this email to add a comment to the issue online.

View raw message