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

Allocating memory in a lock-free manner

Anders Gidenstam (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers)) ; Marina Papatriantafilou (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers)) ; Philippas Tsigas (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers))
Proceedings of the 13th Annual European Symposium on Algorithms p. 329 -- 242. (2005)
[Konferensbidrag, refereegranskat]

The potential of multiprocessor systems is often not fully realized by their system services. Certain synchronization methods, such as lock-based ones, may limit the parallelism. It is significant to see the impact of wait/lock-free synchronization design in key services for multiprocessor systems, such as the memory allocation service. Efficient, scalable memory allocators for multithreaded applications on multiprocessors is a significant goal of recent research projects. We propose a lock-free memory allocator, to enhance the parallelism in the system. Its architecture is inspired by Hoard, a successful concurrent memory allocator, with a modular, scalable design that preserves scalability and helps avoiding false-sharing and heap blowup. Within our effort on designing appropriate lock-free algorithms to construct this system, we propose a new non-blocking data structure called flat-sets, supporting conventional ``internal'' operations as well as ``inter-object'' operations, for moving items between flat-sets. We implemented the memory allocator in a set of multiprocessor systems and studied its behaviour. The results show that the good properties of Hoard w.r.t. false-sharing and heap-blowup are preserved, while the scalability properties are enhanced even further with the help of lock-free synchronization.



Denna post skapades 2006-08-25.
CPL Pubid: 7249

 

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers) (2005-2007)

Ämnesområden

Information Technology

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:


Algorithms for synchronization and consistency in concurrent system services