[boost] Re: Lock unification (shared vs. upgradable)

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2004-08-07 18:45:09

On Aug 7, 2004, at 2:41 PM, Alexander Terekhov wrote:

>
> Howard Hinnant wrote: ...
>
> void read_write(rw_mutex& m, which_t w) {
>   sharable_lock<rw_mutex, true> read_lock(m);
>   // May need access to many releated which_t's
>   if (compute_expensive_result(w)) {
>     // Upgrade (blocks upcoming readers while pending)
>     scoped_lock<rw_mutex> write_lock(upgrade(read_lock));
>     if (read_lock.atomic_upgrade()) {
>       modify_state(w);
>       if (write_lock.upgrade_pending())
>         register_change(w);
>     }
>     else if (!computation_invalidated(w) || // check registry
>              compute_expensive_result(w)) {
>       modify_state(w);
>       write_lock.upgrade_pending() ?
>         register_change(w) : clear_registry();
>     }
>     else if (!write_lock.upgrade_pending()) {
>       clear_registry();
>     }
>   }
> }
>
> Oder (verbosity aside for a moment)?

My current proposal ( 
http://home.twcny.rr.com/hinnant/cpp_extensions/threads.html ) already 
has the functionality of "fallible upgrade" but with slightly different 
semantics and syntax:

     scoped_lock<rw_mutex> write_lock(upgrade(read_lock));
     if (read_lock.atomic_upgrade())
     {
         ...
     }
     else
     {
          ...
     }

vs:

     scoped_lock<rw_mutex> write_lock(move(read_lock), try_lock);
     if (write_lock.locked())
     {
         ...
     }
     else
     {
          read_lock.unlock();
          write_lock.lock();
          ...
     }

Hmm... ok the functionality isn't exactly the same as you proposed.  
But it's pretty close.  The difference is your upgrade might block for 
a while during the try-upgrade operation in the hopes of making it 
atomic, whereas mine will give up immediately and then block for a 
non-atomic upgrade.  See further down on how I see your block-try 
semantics as counter productive in another scenario.

So I believe you could design code at least partly the way you've 
proposed with my current proposal.  Although I'm sure I'm not fully 
understanding the write_lock.upgrade_pending() functionality.  The way 
I currently have my rw_mutex implemented, this information is not 
known.  Actually my current implementation is based on your suggested 
"single entry gate" design.  So when the mutex is write locked, it has 
no idea who or if anyone is waiting outside the gate.  I liked the idea 
that the scheduler, not the mutex, decides if a reader or writer gets 
priority.  Anyway, I could see a "write lock pending" in the case that 
the mutex is currently in a read state.  But only a sharable 
(non-upgradable) lock could ever see that state.  Once an upgradable 
lock is active, even though it hasn't requested an upgrade, writers are 
locked behind the entry gate and not detectable.  And once a writer 
gets past the entry gate and is "pending", then upgradable locks are 
stuck behind the entry gate.

But I believe that in addition to the fallible upgrade there needs to 
be a "for-sure upgrade".  You don't always want to have to check for 
whether you got your upgrade (atomically or otherwise).  There is a 
code size hit in having to write the "else" branch.  And it would also 
become problematic to atomically pair an upgrade with an independent 
lock.

For example consider a function that takes two objects T and U, needs 
to read T, and if certain conditions are met then atomically upgrade T 
access from read to write, and lock U:

void foo(T& t, U& u)
{
     typedef T::mutex_t::upgradable_lock T_ReadLock;
     typedef T::mutex_t::scoped_lock T_WriteLock;
     typedef transfer_lock< T_WriteLock, T_ReadLock > T_Upgrade;
     typedef U::mutex_t::scoped_lock U_Lock;

     // read lock t
     T_ReadLock t_read_lock(t.mutex());
     ...
     if (...)
     {
          // upgrade t from read to write, and lock u
          T_WriteLock t_write_lock(t.mutex(), defer_lock);
          T_Upgrade t_upgrade(t_write_lock, t_read_lock, defer_lock);
          U_Lock u_lock(u.mutex(), defer_lock);
          lock(t_upgrade, u_lock);
          // ok, t upgraded and u locked, all atomically
     }
}

The transfer_lock<T_WriteLock, T_ReadLock> generic utility can make an 
upgrade look like a lock, but it really needs the "for sure atomic 
upgrade" semantics in order to pull it off.  And it also needs "try but 
retain read access on fail" semantics.  This is in contrast to your 
"try but do non-atomic upgrade on fail" semantics.  And then the 
lock(lock1,lock2) generic algorithm can atomically do the upgrade on t 
and lock on u.

Having said all that, a word of caution on the above example.  If 
U::mutex is a simple exclusive mutex, things are ok.  However if 
U::mutex is a read/write style mutex, then the above algorithm is in 
danger of deadlock.  If foo2(U& u, T& t) does the same thing as foo(T& 
t, U& u), but with the roles reversed:  read-lock u, atomically(upgrade 
u, lock t), then we're firmly in deadlock territory.  Threads 
simultaneously executing foo and foo2 would deadlock for sure.

The above paragraph is an argument against all-in-one mutex 
functionality that I hadn't thought of before (at least if you consider 
"all-in-one" to include read/write capability).  If a mutex existed, 
and did not include read/write capability, I suspect that the above foo 
could check that fact for U::mutex_t at compile time, and thus ensure 
that there was no danger of deadlock.

-Howard