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

NBmalloc: Allocating Memory in a Lock-Free Manner

A. Gidenstam ; Marina Papatriantafilou (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) ) ; Philippas Tsigas (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) )
Algorithmica (0178-4617). Vol. 58 (2010), 2, p. 304-338.
[Artikel, refereegranskad vetenskaplig]

Efficient, scalable memory allocation for multithreaded applications on multiprocessors is a significant goal of recent research. In the distributed computing literature it has been emphasized that lock-based synchronization and concurrency-control may limit the parallelism in multiprocessor systems. Thus, system services that employ such methods can hinder reaching the full potential of these systems. A natural research question is the pertinence and the impact of lock-free concurrency control in key services for multiprocessors, such as in the memory allocation service, which is the theme of this work. We show the design and implementation of NBmalloc, a lock-free memory allocator designed to enhance the parallelism in the system. The architecture of NBmalloc is inspired by Hoard, a well-known concurrent memory allocator, with modular design that preserves scalability and helps avoiding false-sharing and heap-blowup. Within our effort to design appropriate lock-free algorithms for NBmalloc, we propose and show a lock-free implementation of a new data structure, flat-set, supporting conventional "internal" set operations as well as "inter-object" operations, for moving items between flat-sets. The design of NBmalloc also involved a series of other algorithmic problems, which are discussed in the paper. Further, we present the implementation of NBmalloc and a study of its behaviour in a set of multiprocessor systems. The results show that the good properties of Hoard w.r.t. false-sharing and heap-blowup are preserved.

Nyckelord: Memory allocation, Lock-free synchronization, Non-blocking, synchronization, Multithreaded applications, synchronization, objects

Denna post skapades 2010-07-26.
CPL Pubid: 123960


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

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


Information Technology

Chalmers infrastruktur