Thursday, April 6, 2017

2-thread algorithms

Too busy to write a decent post so instead I'll put up a link to a paper we did a couple of years ago but wasn't yet accepted (we've been busy with other stuff).
It's 10 (yes, ten!) new algorithm to do mutual exclusion for the two-thread problem.
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/cr2t-2016.pdf

They're alternatives to Dekker's or Peterson's protocols. If you don't know what those are then take a look at wikipedia:
https://en.wikipedia.org/wiki/Dekker%27s_algorithm
https://en.wikipedia.org/wiki/Peterson%27s_algorithm

All of our 10 algorithms (did I say we had 10 of them?) have a minimum number of stores of 1 to acquire and another store to release the lock. This is something new in the world of 2-thread mutual exclusion:
 



Why does anyone even care about this stuff?
Well, before you can fly (make wait-free algorithms) you need to walk (make mutual exclusion locks), and some of these algorithms are the basis of reader-writer locks.

... ohhh, and they're all starvation-free   :)