RE: [boost] Re: Boost.Threads: Do we need all those mutexes?

From: Glen Knowles (gknowles_at_[hidden])
Date: 2004-07-06 01:10:51

> From: Howard Hinnant
> 
> Exploring the case: throw exception if unable to atomically 
> promote read to write:
> 
> If an exception is not thrown, then you are guaranteed what 
> you previously read is still true, and all is well.  If an 
> exception is thrown, then you have to re-read to determine 
> current state.

First, to be clear, a promote() _must_ not be allowed to silently fail,
otherwise you break the contract and people will spend several days tracking
down the problem. If you want that behavior you should use try_promote().

I don't have a problem with it simply deadlocking, or, if that's
unacceptable don't have the blocking promote() function. The complexity
involved in determining a deadlock may be well beyond what you want to do at
this level in the library, I'll come back to this later. 

But for now, lets talk about throwing. In my mind the purpose of throwing is
to allow the other thread (or threads, with the database work I've been
doing multiple read locks on an object all trying to be promoted to write
locks at the same time happens more often then you might think) to proceed,
which it can't do unless you give up your _read_ lock. 

> 
> Hmm...
> 
> Given that when you have write privilege you also implicitly 
> have read privilege, this seems a little extreme.  Would it 
> not be both more efficient and easier to follow if you just 
> reaffirm your state under the write lock rather than assume 
> your state, and write a catch block to reassert it if it 
> happens to be false?  That is, this:
> 
> bool try_sale(rw_mutex& m)
> {
>    read_lock rl(m);
> 
>    long balance = get_balance();
>    long cost = get_total_cost();
> 
>    if (balance > cost)
>    {
>      write_lock wl(rl);
>      set_balance(balance - cost);
>      // ...
>      return true;
>    }
>    return false
> }
> 
> bool do_sale(rw_mutex& m)
> {
>    while (true)
>    {
>      try_again:
>      try {
>        return try_sale(m);
>      catch (rw_promotion_error&) {
>        // Try the whole thing again
>        // how is this implemented?
>        goto try_again;  // ?
>      }
>    }
> }
> 
> vs this:
> 
> void do_sale(rw_mutex& m)
> {
>    read_lock rl(m);
> 
>    long balance = get_balance();
>    long cost = get_total_cost();
> 
>    if (balance > cost)
>    {
>      rl.unlock(m);
>      write_lock wl(m);
>      set_balance(balance - cost);
>      wl.transfer_to_read_lock(rl);
>      balance = get_balance();
>    }
>    // ...
> }
> 
> My assertion is that you don't know a-priori if the 
> read-to-write promotion achieves anything or not.  If you 
> allow it to fail, by exception, or by error code, or by any 
> other means, then you have to write code to re-read the 
> current state.  If you don't allow it to fail, then you must 
> make it block until it succeeds.  The latter seems simpler in 
> logic, and smaller in code size.  The logic is quite simple:
> 
> read_lock to write_lock promotion is not atomic.
> 
> Once that is understood, the programmer can just deal with 
> it.  Trying to encapsulate this bit of reality only serves to 
> obfuscate the necessary logic.

The reason that "release read, acquire write" appears a complete alternative
to promotion is because your example is too simple. You may need the read
lock to keep the object alive in a cache, where it could be flushed to disk
and destroyed if you release it, forcing you to re-read it before getting
your write lock.

I think that the library should either commit to detecting deadlocks or
don't do it at all. Is it going to throw a promotion exception in this case?

Thread A: read lock x
Thread A: read lock y
Thread B: read lock y
Thread B: write lock x, blocks
Thread A: promote y to write lock, blocks

In order to detect things like this you essentially need to build a complete
conflict matrix of all held locks in the system, and if you do that I assume
you'd also use it to detect deadlocks of regular locks:

Thread A: lock x
Thread B: lock y
Thread A: lock y, blocks
Thread B: lock x, blocks

Glen