5a2
Subj : Re: "multi-mutex" algorithm pseudo-code for STM...
To   : comp.programming.threads
From : Torsten Robitzki
Date : Fri Oct 14 2005 08:59 pm

Chris Thomasson wrote:
> You can use a single global static array of mutexs to allow a thread to 
> atomically lock an arbitrary number of objects. This algorithm doesn't 
> require any object metadata. It's not two-phase locking because it doesn't 
> need to back-off and retry if a lock is already acquired. It is guaranteed 
> not to deadlock because it follows a strict locking hierarchy. A simple 
> sorting algorithm enforces the hierarchy. Here is some pseudo-code:

<snip>

> It looks like my algorithm could be used as a simple from of lock-based 
> software transactional memory...
> 
> 
> Any thoughts? 

If one have really static objects like in your example defining the 
locking hierarchy can be static too. If you have to lock more than one 
dynamic object one have to define the locking hierarchy dynamic too (or 
have to use try-locks). If the addresses of the objects doesn't change 
and all objects to be locked are known from the beginning, the approach 
is good. The sorting could be improved by using a better algorithm and 
by relying on the fact that the array should still be sorted at the 
unlocking side. I've assumed that you meant mutex_t and not size_t in 
the definition of multi_mutex_t, is this right?

best regards
Torsten

.

0