Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #499 > unrolled thread

mutex and condition variable implementation using futex

Back to article view | Back to comp.programming.threads

Contents

  mutex and condition variable implementation using futex Sudhanshu Shukla <sudhan345@gmail.com> - 2011-08-09 14:06 -0700
    Re: mutex and condition variable implementation using futex Alexander Terekhov <terekhov@web.de> - 2011-08-15 11:31 +0200

#499 — mutex and condition variable implementation using futex

Hi All,

I have implemented mutex and condition variables using futex syscall. I think my implementation is correct, but if some one could verify the correctness of my implementation it would be great.

Any hints for further optimizing the mutex and condition variables would be greatly appreciated.

--------------------------------------------------------------------------------
typedef UINT32 mutex;
typedef struct condvar condvar;

struct condvar	{
	mutex *m;
	int seq;
};

void mutex_init(mutex *m)	{
	*m = 0;
}

void mutex_destroy(mutex *m)	{
	*m = 0;
};

void mutex_lock(mutex *m)	{
	UINT32 c;
	if((c = __sync_val_compare_and_swap(m, 0, 1)) != 0)	{
		do	{
			if((c == 2) || __sync_val_compare_and_swap(m, 1, 2) != 0)
				syscall(SYS_futex, m, FUTEX_WAIT_PRIVATE, 2, NULL, NULL, 0);
		} while((c = __sync_val_compare_and_swap(m, 0, 2)) != 0);
	}
};

void mutex_unlock(mutex *m)	{
	if(__sync_fetch_and_sub(m, 1) != 1)	{
		*m = 0;
		syscall(SYS_futex, m, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
	}
}

void cond_init(condvar *c, mutex *m)	{
	c->m = m;
	c->seq = 0;
}

void cond_destroy(condvar *c)	{
	c->m = NULL;
	c->seq = 0;
};

void cond_signal(condvar *c)	{
	__sync_fetch_and_add(&(c->seq), 1);
	syscall(SYS_futex, &(c->seq), FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
}

void cond_broadcast(condvar *c)	{
	__sync_fetch_and_add(&(c->seq), 1);
	syscall(SYS_futex, &(c->seq), FUTEX_REQUEUE_PRIVATE, 1, (void *) INT_MAX, c->m, 0);
}

void cond_wait(condvar *c)	{
	UINT32 oldSeq = c->seq;
	mutex_unlock(c->m);
	syscall(SYS_futex, &(c->seq), FUTEX_WAIT_PRIVATE, oldSeq, NULL, NULL, 0);
	while (xchg32(c->m, 2))	{
		syscall(SYS_futex, c->m, FUTEX_WAIT_PRIVATE, 2, NULL, NULL, 0);
	}
}
--------------------------------------------------------------------------------


Thanks 

Sudhanshu

[toc] | [next] | [standalone]

#513

Sudhanshu Shukla wrote:
[...]
> Any hints for further optimizing the mutex and condition variables 
> would be greatly appreciated.

Linux's futex interface isn't really optimal for mutexes and condvars
because the kernel doesn't maintain 'waiters bit' (e.g. 0x80000000)
indicating that there are queued waiters.

With waiters bit, mutex would be simply

  WHILE atomic_bit_test_set_hlb(&lock, 1) // efficient 'acquire' 
    lock_queue_wait(&lock, 1) // wait if locked bit is set

for lock() and

   uintptr_t lock_queue;
   IF atomic_decrement_rel(lock_queue = &lock)
     THEN lock_queue_wake(lock_queue, 1) 

for unlock.

For condvar, it is better to let the kernel set waiters bit and then
unlock the associated mutex.

The signal would be simply

   IF cv_queue 
     THEN cv_queue_wake(&cv_queue, 1) 

and broadcast

   IF cv_queue 
     THEN cv_queue_wake(&cv_queue, UINT_MAX) 

regards,
alexander.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web