Wait-Free Multi-Word Compare-and-Swap Using Greedy Helping and Grabbing

摘要: We present a new algorithm for implementing multi-word compare-and-swap functionality supporting the Read and CASN operations. The is wait-free under reasonable assumptions on execution history benefits from techniques to resolve conflicts between operations by using greedy helping grabbing. Although deterministic scheme enabling grabbing somewhat sacrifices fairness, effects are insignificant in practice. Moreover, unlike most of previous results, operation does not require list addresses be sorted before invoked, can read current value without applying when word within an ongoing transaction. Experiments micro-benchmarks varying important parameters three dimensions have been performed two multiprocessor platforms. results show similar performance as lock-free Harris et al. scenarios, significantly better scenarios with very high contention. This altogether extraordinary good considering that wait-free.