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
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.
Hi Pedro,
ReplyDeleteThe MPSC lock seems like CLH, but with local spinning removed.
Dave Dice