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

Lock-free Data Structures in Multicore Software Programming

Nhan Nguyen Dang (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) )
Göteborg : Chalmers University of Technology, 2012. - 95 s.
[Licentiatavhandling]

Lock-free data objects have been proven to have many advantages over their lock-based counter-parts such as high scalability, performance, and immunity to deadlocks and livelocks. Several lock-free implementations of fundamental data structures have been introduced in the literature, and used in practice. However, we found that lock-free data objects are not composable in term of progress guarantees. Therefore, we proposed a synchronization mechanism to enhance shared lock-free data objects so that they can provide progress guarantees, in a fair manner, to all objects using them. Using the proposed mechanism, a programmer can compose as many lock-free objects as needed and still ensure lock-freedom of individual object. We implemented and evaluated our synchronization mechanism with a lock-free queue. The evaluation result shows that there is a performance penalty of using the mechanism which mostly comes from the use of a software-based Double-Compare-And-Swap. The second part of this thesis presents our design of a concurrent mark-split garbage collector. The design addresses the challenge of handling concurrent updates to the list of free intervals by algorithmically introducing an efficient concurrency control mechanism. This mechanism is based on a lock-free skip-list design and supports an extended set of operations that allows, atomically and in a lock-free manner, to search and remove and also to insert two intervals at the same time. We have implemented the concurrent mark-split garbage collector, namely CoMarkSplit, in OpenJDK HotSpot Virtual Machine as a collector for the tenured generation. We performed experimental evaluation of CoMarkSplit and compared with the default concurrent mark-sweep present in OpenJDK HotSpot, using Dacapo benchmarks. The result shows that CoMarkSplit outperforms the concurrent mark-sweep in two out of four applications.

Nyckelord: Lock-free, Concurrent Data Structures, Composition, Garbage Collection, Concurrent Garbage Collector, Mark-Split, Java



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

Läs mer om Chalmers styrkeområden  

Denna post skapades 2012-03-28.
CPL Pubid: 156256

 

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Nätverk och system (Chalmers)

Ämnesområden

Informations- och kommunikationsteknik
Datalogi

Chalmers infrastruktur

Relaterade publikationer

Inkluderade delarbeten:


Progress guarantees when composing lock-free objects


CoMarkSplit: A Concurrent Mark-Split Garbage Collector


Examination

Datum: 2012-04-25
Tid: 10:15
Lokal: Room ED, Rännvägen 6, Chalmers
Opponent: Dr. Marc Shapiro, INRIA & LIP6, France

Ingår i serie

Technical report L - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University