Premium
Allocation without locking
Author(s) -
Appel Andrew W.
Publication year - 1989
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380190704
Subject(s) - semaphore , initialization , computer science , thread (computing) , concurrency , garbage collection , traverse , garbage , parallel computing , distributed computing , real time computing , operating system , programming language , geodesy , geography
In a programming environment with both concurrency and automatic garbage collection, the allocation and initialization of a new record is a sensitive matter: if it is interrupted half‐way through, the allocating process may be in a state that the garbage collector cannot understand. In particular, the collector will not know which words of the new record have been initialized and which are meaningless (and unsafe to traverse). For this reason, parallel implementations usually use a locking or semaphore mechanism to ensure that allocation is an atomic operation. The locking significantly adds to the cost of allocation. This paper shows how allocation can run extremely quickly even in a multi‐thread environment: open‐coded, without locking.