[CapROS-devel] Fast software-only mutex algorithm

[Matt <ma...@io...>]

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?