[CapROS-devel] Fast software-only mutex algorithm
Status: Beta
Brought to you by:
clandau
|
From: Matt <ma...@io...> - 2005-05-11 00:10:27
|
In 2003, a (grad?) student named Sankarapandian Vijayaraghavan wrote a paper on the fast + fair + software-only mutual exclusion algorithm he devised. To me it looks like Leslie Lamport's Bakery Algorithm squeezed into Lamport's own (non-fair) fast + software-only mutex algorithm. Vijay's algorithm is not FIFO but is fair; processes/threads/CPUs won't 'starve', waiting forever to get a lock. If anyone cares, I'll post a link to the paper (probably in PDF format) as soon as I can find it again... How fast is it? Most software mutexes (like the Bakery algorithm) take O(N) operations, regardless of lock contention. Lamport's and Vijay's mutexes take O(1) with no contention (the common case): something like 3 writes and 3 reads. (!) In the case of contention, Vijay's algorithm takes O(N) operations. Lamport's fast-mutex paper suggests that these algorithms are optimal. Anyway, here's a C implementation. I haven't tested this -- I don't even know how -- but I've done my best to reproduce the algorithm in code. Hopefully it can be worked into a real system without too much trouble. http://matt.ioioio.net/devel/os/sync/vijay2.c The generated assembly for the common case (no lock contention) should take no jumps. GCC doesn't know this, and I don't know how to tell it; the asm generated by these versions is too 'jumpy', even when I use -O2 or higher. It might be a good idea to take the generated code and streamline it by hand as I've attempted: http://matt.ioioio.net/devel/os/sync/vijay2.s Oh well. Would any of this mess be useful in CapROS? |