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

A Lock-Free Algorithm for Concurrent Bags

Håkan Sundell ; Anders Gidenstam ; Marina Papatriantafilou (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers)) ; Philippas Tsigas (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers))
Göteborg : Chalmers University of Technology, 2011. - 22 s.
[Rapport]

A lock-free bag data structure supporting unordered buffering is presented in this paper. The algorithm supports multiple producers and multiple consumers, as well as dynamic collection sizes. To handle concurrency efficiently, the algorithm was designed to thrive for disjoint-access-parallelism for the supported semantics. Therefore, the algorithm exploits a distributed design combined with novel techniques for handling concurrent modifications of linked lists using double marks, detection of total emptiness, and efficient memory management. Experiments on a 24-way multi-core platform show significantly better performance for the new algorithm compared to previous algorithms of relevance. Keywords: concurrent; data structure; non-blocking; shared memory;

Nyckelord: concurrency; data structure; lock-freeness; shared memory;



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

Läs mer om Chalmers styrkeområden  

Denna post skapades 2011-02-22.
CPL Pubid: 137192