reagents
reagents copied to clipboard
ocaml-multicore
Implement a better kCAS.
A description of what a better kCAS might entail:
A kCAS is roughly a list of (location, old, new) tuples, each representing a compare-and-swap operation. The whole set of compare-and-swaps is performed atomically, either all succeeding or all failing.
The implementation at the moment is to set each location to a sentinel "ongoing CAS" value if it contains the correct old value, and if that succeeds for each value to then update them all to the new values. Effectively, this implements a lightweight TATAS spinlock for each location.
To avoid blocking, a slightly different implemention can be used. Instead of a single "ongoing CAS" sentinel value, each location is set to a representation of the kCAS operation (i.e. the list of needed CAS tuples). Any thread that sees an ongoing kCAS, instead of spinning until it finishes, should actively attempt to complete the kCAS. So, as soon as a kCAS begins, all threads race to co-operatively complete it. This makes reactions lock-free (although not wait-free).
Reopening this issue. Unsurprisingly, it turns out implementing lock-free k-CAS is tricky. Helpfully, there is a paper about this very issue:
http://www.cl.cam.ac.uk/research/srg/netos/papers/2002-casn.pdf It takes 3n+1 CAS operations to do an n-word CAS (assuming no contention).
@stedolan
kcas is now based on the paper above (Practical Multi-Word Compare-and-Swap Operation), so I believe this is completed
