Sunday, May 11, 2014

C11 Atomics and MPSC Mutual Exclusion Lock

PS: Many thanks to David Dice for pointing out that this is just a small variation on the CLH lock.
That's what I get for not paying attention to "The Art of Multiprocessor Programming"!

To celebrate the release of GCC 4.9.0, with its full support for the C11 Memory Model and its Atomics, we implemented a new Mutual Exclusion Lock a variant of the CLH lock using C11 Atomics, which you can get from github:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/C11/locks/mpsc_mutex.h
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/C11/locks/mpsc_mutex.c
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/Presentations/MPSC-Mutex.pptx





GCC 4.9.0 is not yet widely available, but if you're like me and don't to want to build it yourself, you can get if in Arch Linux by doing pacman -S gcc:
https://www.archlinux.org/download/

The CLH lock is "fair" and "starvation-free", assuming that the run-time/OS can provide that kind of guarantee, and it works more or less like this:

init():

A new node of the linked list is created, and the head and tail are set to reference it.

lock():

1. A thread wishing to acquire the lock starts by creating a new node that it will insert in the tail of the queue, using an atomic_exchange() on the tail.
2. The atomic_exchange() operation will return a pointer to the previous node to which tail was pointing, and now this thread can set the "next" of that node to point to its own node, using an atomic_store().
3. We now loop until the head reaches the node previous to our own.

unlock():

1. We assume that if unlock() is being called, it is because the current thread is holding the lock, which means that the node to which "head" points to is the one previous to the node created by the current thread, so now all that needs to be done is to advance the head to the next node and free() the memory of the previous which is now inaccessible, and it's "next" field will never be de-referenced by any other thread.

1 comment:

  1. Hi Pedro,

    The MPSC lock seems like CLH, but with local spinning removed.

    Dave Dice

    ReplyDelete