"multi-mutex" algorithm pseudo-code for STM...

[Chris Thomasson]

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:

#define MUTEX_DEPTH 256

struct multi_mutex_t
{
size_t mutex;
};

#define MULTI_MUTEX_INIT( p1 ) ( ((ptrdiff_t)(p1)) % MUTEX_DEPTH )

static void multi_mutex_lock( multi_mutex_t*, size_t );
static void multi_mutex_unlock( multi_mutex_t*, size_t );

static void sys_multi_mutex_sort( multi_mutex_t*, size_t );
static void sys_multi_mutex_lock( size_t );
static int sys_multi_mutex_trylock( size_t );
static void sys_multi_mutex_unlock( size_t );

static pthread_mutex_t g_mutexs[MUTEX_DEPTH];

static void multi_mutex_lock( multi_mutex_t *_this, size_t depth )
{
size_t i;

sys_multi_mutex_sort( _this, depth );

for( i = 0; i < depth; ++i )
{
sys_multi_mutex_lock( _this[i].mutex );
}
}

static void multi_mutex_unlock( multi_mutex_t *_this, size_t depth )
{
size_t i;

for( i = depth - 1; i != ((size_t)-1); --i )
{
sys_multi_mutex_unlock( _this[i].mutex );
}
}

static void sys_multi_mutex_sort( multi_mutex_t *_this, size_t depth )
{
size_t i, x, tmp;

for( i = 0; i < depth; ++i )
{
for( x = i + 1; x < depth; ++x )
{
if ( _this[i].mutex > _this[x].mutex )
{
tmp = _this[i].mutex;
_this[i].mutex = _this[x].mutex;
_this[x].mutex = tmp;
}
}
}
}

static void sys_multi_mutex_lock( size_t i )
{
pthread_mutex_lock( &g_mutexs[i] );
}

static int sys_multi_mutex_trylock( size_t i )
{
return pthread_mutex_trylock( &g_mutexs[i] );
}

static void sys_multi_mutex_unlock( size_t i )
{
pthread_mutex_unlock( &g_mutexs[i] );
}

Here is a quick example of how you would use it:

static int g_shared1 = 1;
static int g_shared2 = 2;
static int g_shared3 = 3;
static int g_shared4 = 4;
static int g_shared5 = 5;
static int g_shared6 = 6;

int main()
{
multi_mutex_t lock[6] =
{ MULTI_MUTEX_INIT( &g_shared5 ),
MULTI_MUTEX_INIT( &g_shared2 ),
MULTI_MUTEX_INIT( &g_shared4 ),
MULTI_MUTEX_INIT( &g_shared6 ),
MULTI_MUTEX_INIT( &g_shared3 ),
MULTI_MUTEX_INIT( &g_shared1 ) };

multi_mutex_lock( lock, 6 );

/* g_shared1 -> g_shared6 are now fully locked */

multi_mutex_unlock( lock, 6 );

return 0;
}

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

Any thoughts?

[Torsten Robitzki]

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

[Chris Thomasson]

> 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).

Actually, there is a way around using try-lock's; however, it basically
reduces down to the same basic logic. I am going to post some pseudo-code
fairly soon. I am currently bogged down with a memory allocator design that
is based on some logic that I previously posted here:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/8245f4b48591fc69/e3efa5628aad4a82?tvc=1&hl=en#e3efa5628aad4a82

I will probably post the updated multi-mutex code along with the allocator.

> 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.

Good point. The updated code does consider this.

> I've assumed that you meant mutex_t and not size_t in the definition of
> multi_mutex_t, is this right?

I used a size_t because the multi_mutex_t::mutex member holds the "hashed"
value of a pointer to a shared object. The value is used as an index into
the global array of mutexs. The code sorts index in ascending order to
comply with the lock hierarchy.