[concurrency-interest] Multi-level locks

David Holmes davidcholmes at aapt.net.au
Mon Mar 15 18:51:06 EDT 2010


Khilan,

AbstractQueued[Long]Synchronizer is designed for this "kind of thing", though I don't know how well it will suit this particular case. The "shared" and "exclusive" modes are conceptual and don't have to map directly to the synchronizer being implemented - for example, all five or your modes might utilize the shared mode of AQS. However, the queuing is all internalized and it is not designed for extension or modification - and there is only one queue.

If you haven't seen it, check out Doug Lea's paper on AQS:

http://gee.cs.oswego.edu/dl/papers/aqs.pdf

There's also an example on using AQS to do Room Synchronization that we presented at various places, but for which I'm having trouble finding an actual link. :( Contact me if you'd like me to dig it up. I think there should be a JavaOne presentation with it in, somewhere.

HTH.

David Holmes
  -----Original Message-----
  From: concurrency-interest-bounces at cs.oswego.edu [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Khilan Gudka
  Sent: Tuesday, 16 March 2010 1:19 AM
  To: concurrency-interest at cs.oswego.edu
  Subject: [concurrency-interest] Multi-level locks


  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/20100316/46e5a714/attachment.html>


More information about the Concurrency-interest mailing list