Wait-Free Multi-Word Compare-And-Swap using Greedy Helping and Grabbing
2009 (English)Conference paper (Refereed)
We present a new algorithm for implementing
a multi-word compare-and-swap functionality supporting the Read and CASN operations. The algorithm is wait-free under reasonable assumptions on execution history and benefits from new techniques to resolve conflicts between operations by using greedy helping and grabbing. Although the deterministic scheme for enabling grabbing somewhat sacrifices fairness, the effects are insignificant in practice. Moreover, unlike most of the previous results, the CASN operation does not require the list of
addresses to be sorted before calling, and the Read operation can read the current value without applying helping when the
word to be read is within an ongoing transaction. Experiments using micro-benchmarks varying important parameters in three dimensions have been performed on two multiprocessor platforms. The results show similar performance as the lock-free
algorithm by Harris et al. for most scenarios, and significantly better performance on scenarios with very high contention. This is altogether extraordinary good performance considering that the new algorithm is wait-free.
Place, publisher, year, edition, pages
CSREA Press , 2009.
wait-free, multi-thread, compare-and-swap, real-time, Parallel Programming
Computer and Information Science Computer and Information Science
IdentifiersURN: urn:nbn:se:hb:diva-6306Local ID: 2320/5914ISBN: 9781601321213ISBN: 9781601321220OAI: oai:DiVA.org:hb-6306DiVA: diva2:886993
The 2009 International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, Nevada, USA