CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Help-optimal and Language-portable Lock-free Concurrent Data Structures

Bapi Chatterjee (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers)) ; Ivan Walulya (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) ) ; Philippas Tsigas (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers))
2016. - 14 s.

Helping is the most common mechanism to guarantee lock-freedom in many concurrent data structures. An optimized helping strategy improves the overall performance of a lock-free algorithm. In this paper, we propose help-optimality, which essentially implies that no operation step is accounted for exclusive helping in the lock-free synchronization of concurrent operations. To describe the concept, we revisit the designs of a lock-free linked-list and a lock-free binary search tree and present improved algorithms. Our algorithms employ atomic single- word compare-and-swap (CAS) primitives and are linearizable. Additionally, we do not use a language/platform speci?c mechanism to modulate helping, speci?cally, we use neither bit-stealing from a pointer nor runtime type introspection of objects, making the algorithms language-portable. Further, to optimize the amortized number of steps per operation, if a CAS execution to modify a shared pointer fails, we obtain a fresh set of thread-local variables without restarting an operation from scratch. We use several micro-benchmarks in both C/C++ and Java to validate the e?ciency of our algorithms against existing state-of-the-art. The experiments show that the algorithms are scalable. Our implementations perform on a par with highly optimized ones and in many cases yield 10%-50% higher throughput.

Nyckelord: concurrent data structure, linked-list, binary search tree, lock-free, linearizability, help, language-portable

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2016-03-18. Senast ändrad 2016-04-06.
CPL Pubid: 233407