[concurrency-interest] Multi-level locks

Khilan Gudka khilan at doc.ic.ac.uk
Mon Mar 15 11:19:09 EDT 2010


Dear all,

I'm looking to produce a high-performant implementation of multi-granularity
(a.k.a multi-level) locks. I'm basing my implementation on the paper
"Granularity of Locks in a Shared Data Base" by Gray et al. There are five
modes: Shared (S), Exclusive (X), Intention Shared (IS), Intention Exclusive
(IX) and Shared Intention Exclusive (SIX - this last mode can be represented
implicitly by non-zero counts for both S and IX).

I currently have an implementation whereby I use a long to represent state.
There is a global state for the lock that gives the status of the lock with
respect to all threads as well as per-thread state for a thread's count of
each of the above modes (minus the implicitly  represented mode SIX).
Determining whether a request from a thread can proceed is achieved by
subtracting the two (giving a so-called "group mode" of the other threads)
and then doing a bit-wise AND to determine compatibility of the request with
the group mode). I keep two queues (ConcurrentLinkedQueue) for upgrades and
new requests respectively. To keep the implementation simple, the lock and
unlock methods are synchronized. However, this doesn't perform very well.
For instance, 8 threads incrementing a counter 100000 times takes 10 seconds
compared with 0.2 seconds when using j.u.c.ReentrantReadWriteLock.

I've been looking at AbstractQueuedLongSynchronizer and noticed in the
javadoc comments that it's designed for this sort of thing. However, from
what I've seen it only supports the two modes S and X. Furthermore, it
doesn't seem trivial to extend the internal wait queue given that the Node
class is final? or is it?

If somebody could please give me some advice as to how to proceed, I would
be ever so grateful.

Thanks,
Khilan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20100315/25a83d89/attachment.html>


More information about the Concurrency-interest mailing list