An Oracle blog about Transactional locks

Fixing the Krieger read-write lock

Dave Dice
Senior Research Scientist

Using Hardware Transactional Memory to Correct and Simplify a Readers-Writer Lock Algorithm will appear in PPoPP 2013.

Join the discussion

Comments ( 5 )
  • Arch Robison Wednesday, February 6, 2013

    We ran into the KSUH bug back in 2005 when implementing TBB's tbb::queuing_rw_mutex (which is based on KSUH). The TBB interface uses stack-allocated nodes as part of a RAII scheme. After intermittent failures, we tracked down the issue to freeing of nodes before their last access. Now paranoid, we looked around for a checker and discovered the Spin model checker was what we needed. Spin confirmed the problem and we became big fans of Spin. Our fix in the tbb::queueing_rw_mutex seems to be different than the fix described in the PPoPP 2013 paper.

  • guest Thursday, February 7, 2013

    Hi Arch, do you have a concise description of the work-around you used in TBB? Regards, -Dave

  • Arch Robison Thursday, February 7, 2013

    We fixed the write issue by changing "spin" to a three-state variable. The extra state is like "spin=0", but warns of a pending write to "pred". We write the special spin value, do the pending write, and then write "spin=0". After a reader or writer performs an unlock, it waits until spin is not in the extra state. I like your fix better since it adds code only on the path for unlocking readers, and your fix is non-blocking.

    Here are more notes if someone wants to look over the TBB sources, which are downloadable from http://threadingbuildingblocks.org/download . The relevant file is src/tbb/queuing_rw_mutex.cpp. In addition to fixing the late-write bug, we also made improvements to fix a situation where readers block readers, fit the mutex in a single word, and added upgrade/downgrade. We flipped the polarity of "spin" (it's called "going" in our sources) for naming consistency with our queuing_mutex. The RAII-style "scoped_lock" object acts as the node.

    So it's a little tricky to match up with the original KSUH. Nonetheless the KSUH algorithm is there. The sequence that warns about late writes looks like:

    __TBB_store_relaxed(n->my_going, 2); // protect next queue node from being destroyed too early

    if( n->my_state==STATE_UPGRADE_WAITING ) {


    } else {

    ... some assertions...

    __TBB_store_relaxed(n->my_prev, (scoped_lock*)0);



    and the waiting is done by:

    spin_wait_while_eq( my_going, 2 );

  • guest Monday, February 11, 2013

    Hi Arch, thanks for the description of your fix -- that looks like a good approach. As an aside, I found the bug when some sanity and lightweight integrity checks would fail when benchmarking RW lock algorithms for my other PPoPP 2013 paper. Initially, it'd fail about once every 2-3 days on very large system, but with judicious insertion of random delays I could get it down to under 1 second.

    Regards, -Dave

  • Claudio Miranda Tuesday, March 5, 2013

    Hi Dave, I see you work about JVM related subjects, can you please inform how to have access to an oracle hotspot 1.6 VM that prints java frames in hs_err files ?

    The detailed description is in the following forum post. Sorry to bother here, but I asked there and stackoverflow and nobody stepped in.




Please enter your name.Please provide a valid email address.Please enter a comment.CAPTCHA challenge response provided was incorrect. Please try again.