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:

Any thread participating in multi-CAS must call smc_init() first. It's always safe to call smc_init() if you've already called it, but the call is not guaranteed to be lock-free on all platforms.
Any field that may be subject to multi-CAS should only be read or written using smc_read() or smc_write().
The smallest CASable unit is an aligned double-pointer field. Guaranteeing alignment is up to the user.
For lock-freedom to be guaranteed, the user must order the fields in some way - similar to a locking order for deadlock prevention. Additionally, the user should actually read any field that is CASed, before CASing it (this requirement is somewhat superfluous, given that Stochastic Multi-CAS is a weak CAS). If these two requirements are not met, at worst the implementation will be obstruction-free.
The user must not trust that the operations provided will always work - afterall, they are probabilistic. But the probability of failure is infinitesimal.

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