Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
NBmalloc: Allocating Memory in a Lock-Free Manner
University of Borås, School of Business and IT. (CSL@BS)
2010 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 58, no 2, 304-338 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer New York LLC , 2010. Vol. 58, no 2, 304-338 p.
Keyword [en]
memory allocation, lock-free synchronisation, non-blocking synchronisation, multithreaded applications, Parallel Programming
National Category
Computer Science Computer and Information Science
Identifiers
URN: urn:nbn:se:hb:diva-2741DOI: 10.1007/s00453-008-9268-xLocal ID: 2320/5970OAI: oai:DiVA.org:hb-2741DiVA: diva2:870835
Funder
National Supercomputer Centre (NSC), Sweden
Note

Publicerad i Algorithmica Online First. Väntar på att publiceras i ett nummer av Algorithmica.

Sponsorship:

This work was supported by computational resources provided by the Swedish National Supercomputer Centre (NSC).

Available from: 2015-11-13 Created: 2015-11-13 Last updated: 2016-11-20Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Gidenstam, Anders
By organisation
School of Business and IT
In the same journal
Algorithmica
Computer ScienceComputer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 65 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf