Topic: memory management by reference counting

topics > computer science > operating system > Group: memory management

disk allocation
heap memory management
memory management by garbage collection
register allocation by usage counts


Reference counting is an efficient technique for managing memory. When memory is allocated or referenced, its reference count is incremented. When a reference goes out of scope, the corresponding reference count is decremented. When the reference count is zero, the memory is deallocated.

Reference counting can avoid deep copies, with a copy only occuring on write. Reference counting is useful for garbage collection. (cbb 12/07)

Subtopic: group reference counting up

Quote: methods for group reference counting; used in memory management for reentrant structures [»bobrDG7_1980, OK]
Quote: manage memory for reentrant structures by a reference count for the group as a whole; internal references not counted [»bobrDG7_1980]
Quote: a fast, cyclic reference counting algorithm based on partial traces and sub-graphs; total execution time is similar [»linCY3_2007]

Subtopic: reference counting of files up

Quote: segment freed in the backing store server when its reference count becomes zero; counts Inames in indices [»birrAD9_1980]

Subtopic: reference count as deep copy up

Quote: increment reference count instead of sending deep copies over a channel; requires immutable objects [»kumaS6_2001]

Subtopic: examples up

Quote: in ESP, memory safety is a local property of each process; reference counting of link/unlink; communicates immutable, acyclic objects; easily verified by SPIN [»kumaS6_2001]
Quote: Smalltalk-80 uses reference-counting for garbage collection [»krasG8_1981]
Quote: Oberon's modules only released by explicit command; imported modules released by reference counting (no reference cycles) [»wirtN9_1989]
Quote: Euclid allocates storage from collections with optional reference counting for automatic deallocation; may specify storage management module [»shawM3_1980]

Subtopic: owned objects up

Quote: use single-bit reference count for owned objects; e.g., most list cells in Lisp [»abduSE9_1998]

Subtopic: pointer rotations up

Quote: pointer rotation preserves the number of pointers to a record; reference counts are preserved [»suzuN_1980]
Quote: linear lists and trees have reference counts of one; pointer rotation preserves this; prevents circularity or shared cells [»suzuN_1980]
Quote: if a computation preserves reference counts and number of reachable records, then is implemented solely by pointer rotations [»suzuN_1980]

Subtopic: reference counting with garbage collecting up

Quote: tracing and reference counting are algorithmic duals for garbage collection; live vs. dead objects, anti-operations [»bacoDF10_2004]
Quote: tracing and reference counting are duals -- tracing the object graph, scanning an object [»bacoDF10_2004]
Quote: garbage collect if a reference count becomes negative; indicates an allocation cycle [»birrAD9_1980]
Quote: manage memory with reference counting and a sweep algorithm for circular structures; provides benefits of garbage collection at low cost [»dorwSM1_1997]
Quote: use reference counting and local mark-scan to detect cyclic structures [»abduSE9_1998]
Quote: Recycler multiprocessor garbage collector with low pause times; loosely synchronized, concurrent reference counting; local, concurrent cycle detection [»bacoDF6_2001]

Subtopic: performance of reference counting up

Quote: multiprocessor, reference counting without synchronized operations; 100x reduction in maximal response time for garbage collection [»levaY10_2001]

Subtopic: avoid reference-counting up

Quote: can eliminate reference-counting for stack-based allocations [»abduSE9_1998]
Quote: most high-performance, general-purpose systems use tracing garbage collectors instead of reference counting [»wilsPR9_1992]
Quote: reference counting is expensive, especially with cache memory

Related Topics up

Topic: disk allocation (32 items)
Topic: heap memory management (33 items)
Topic: memory management by garbage collection (116 items)
Topic: register allocation by usage counts
(12 items)

Updated barberCB 3/06
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.