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

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2004-08-05 13:38:37

On Aug 5, 2004, at 9:17 AM, Bronek Kozicki wrote:

> Howard Hinnant wrote:
>> The advantage of the separate upgradable_lock type is that when an
>> upgradable_lock transfers ownership to a scoped_lock, then the thread
>> can assume that what was read while holding upgradable ownership is
>> still valid (does not need to be re-read, re-computed) while holding
>> the scoped_lock.  This is true even if the thread had to block while
>> transferring mutex ownership from the upgradable_lock to the
>> scoped_lock.
>
> If we give this ability to shared_lock, would there be still need for
> separate class upgradable_lock? Or in other words : does 
> upgradable_lock
> have any ability that is conflicting with abilities that we need in
> shared_lock, so that we may not put all these abilities in one class 
> and
> drop the other one? I cannot see such conflict right now, which make me
> wonder why we need two classes (shared_lock and upgradable_lock) at 
> all?

Consider this code:

void read_write(rw_mutex& m)
{
     upgradable_lock<rw_mutex> read_lock(m);
     bool b = compute_expensve_result();
     if (b)
     {
         scoped_lock<rw_mutex> write_lock(move(read_lock));
         modify_state(b);
     }
}

This code works (under the design at 
http://home.twcny.rr.com/hinnant/cpp_extensions/threads.html ), 
allowing other threads to simultaneously lock a sharable_lock on the 
same mutex during this thread's execution of 
compute_expensive_result().  Under the write_lock in this example, the 
code assumes that the results of compute_expensive_result() are still 
valid (no other thread has obtained write access).

Now consider a variation:

void read_write(rw_mutex& m)
{
     sharable_lock<rw_mutex> read_lock(m);
     bool b = compute_expensve_result();
     if (b)
     {
         scoped_lock<rw_mutex> write_lock(move(read_lock));
         modify_state(b);
     }
}

Assuming this compiles and attempts to work the same way upgradable 
did, there is either a deadlock, or a logic problem, depending upon how 
rw_mutex is implemented.  If rw_mutex is implemented such that it will 
successfully negotiate multiple threads requesting upgrade from 
sharable_lock to scoped_lock, then the mutex must block all but one 
thread requesting such an upgrade.  The consequence of this is that "b" 
may no longer be valid under the write_lock.  Some other thread may 
have simultaneously upgraded m from sharable to exclusive, and changed 
the protected data.  In order to protect against this possibility, the 
author of read_write must now code:

void read_write(rw_mutex& m)
{
     sharable_lock<rw_mutex> read_lock(m);
     bool b = compute_expensve_result();
     if (b)
     {
         scoped_lock<rw_mutex> write_lock(move(read_lock));
         modify_state(compute_expensve_result());
     }
}

I.e. compute_expensve_result() has been defensively executed twice.

If on the other hand rw_mutex guarantees that upgrading a shared_lock 
to a scoped_lock will not invalidate previously read information, then 
the rw_mutex has no choice but to deadlock if two threads 
semi-simultaneously request that upgrade.

Consider:

Both thread A and thread B hold a shared_lock on the same mutex.  
Thread A requests an upgrade.  It must block until all other threads 
release their shared_lock (i.e. thread B).  But instead of releasing 
its shared_lock, thread B decides to upgrade it.  It must block until 
all other threads release their shared_lock (i.e. thread A).  The mutex 
can give exclusive access atomically to thread A or thread B, but not 
to both.

upgradable_lock doesn't suffer this defect of sharable_lock, but it 
pays a price for this ability:  Only one thread can hold an 
upgradable_lock at a time.  But other threads can simultaneously hold 
sharable_locks with the unique upgradable_lock, so an upgradable_lock 
is "more friendly" than an exclusive lock.

-Howard