Re: [boost] Design and documentation of Boost.Threads

From: Mac Murrett (mmurrett_at_[hidden])
Date: 2001-11-13 00:34:22

On 11/11/01 2:09 PM, "Kevin S. Van Horn" <kevin.vanhorn_at_[hidden]>
wrote:

> Weak mutexes are nearly useless.  As far as I can tell, it is impossible to
> build starvation-free synchronization mechanisms on top of them.  As one
> 

I believe that it is possible to build strong/fair-like (or at lease useful)
mutexes on top of weak mutexes.  To do this, create a central weak mutex to
represent the mutex, then a weak mutex for each thread that accesses the
strong mutex.  To lock the strong mutex, each thread locks and releases each
of the other threads' weak mutexes in sequence (with (timeout - time
elapsed) for the timeout parameter), then loops, trying to enter its own
mutex (polling with no timeout until it enters or time elapsed > timeout).
After this, the thread locks the central mutex (with (timeout - time
elapsed) for the timeout parameter).  Upon locking the central mutex, the
thread unlocks its mutex.  To unlock the strong mutex, the thread merely
unlocks the central weak mutex.  If another thread that wants the mutex is
given any time at all, it will have locked its own mutex, and so the first
thread will block on that before being able to grab the central mutex again.

An example:

ThA - thread A
ThB - thread B

m0 - the central mutex
m1 - thread A's mutex
m2 - thread B's mutex

ThA: lock m2
ThA: lock m3
ThA: lock m1
ThA: lock m0 **the strong mutex is locked**
ThA: unlock m1
ThB: lock m1
ThB: lock m3
ThB: lock m2
ThA: unlock m0 **the strong mutex is unlocked**
ThA: sleep on m2
ThB: lock m0 **the strong mutex is locked**
ThB: unlock m2
ThA: lock m2
ThA: lock m3
ThA: lock m1
ThA: sleep on m0
ThB: unlock m0 **the strong mutex is unlocked**
ThA: lock m0 **the strong mutex is locked**
...

Of course, this is a contrived case intended to show a single point, but I
cannot envision a scenario (with 2+ threads) in which a single thread could
monopolize a mutex unless other threads are simply not allowed execution
time.

Thanks, Mac.