Subj : "multi-mutex" algorithm pseudo-code for STM...
To   : comp.programming.threads
From : Chris Thomasson
Date : Tue Oct 11 2005 10:05 pm

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?

.