Stochastic Multi-CAS

Stochastic Multi-CAS is a probabilistic software implementation of multi-word lock-free atomic compare-and-swap based on the IA-32 (x86) cmpxchg8b or Intel64 (or AMD64) cmpxchg16b instruction. What is provided is a simple C library that requires very little of the user:

Note that this implementation uses /dev/random to pick a random number, and does so only once per program run. This is perfectly fine except if a program is "searching" through integers, in which case there might be badness eventually. Further, this implementation is only known to work on IA-32 and Intel64 (or on AMD64 in 32-bit mode). The AMD64 boxes I have access to don't support cmpxchg16b, which is kind of pathetic. It should be possible, though, to port the code to systems that don't have double-word CAS, in which case it could be used on AMD64 in 64-bit mode (but without getting the higher probability of correctness that Intel64 gets).

Click here to download the latest implementation.
Click here to download the implementation that was current at the time of my ISMM 2007 "crazy idea talk".
Click here for the ISMM 2007 "crazy idea talk" slides.

Back to Filip Pizlo's Homepage