The Memory Management Glossary
R

 Contents | News | Glossary | FAQ | Articles | Bibliography | Links | Feedback

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

Our aim is for these entries to be accurate, comprehensible, and useful, and also to have an entry for all common memory management terms. If you can't find the term you're looking for, if our definition doesn't help you, or if you'd like to suggest corrections or additions, please let us know via our feedback page.

For an explanation of the structure of the entries, and information on how to link to definitions, please see the glossary help page.


RAM, random access memory

RAM (Random Access Memory) is a type of physical memory(2) that can be read from and written to.

Similar terms: main memory.
See also: ROM; static RAM; dynamic RAM.

raw (for full details, see unwrapped)

A value is unwrapped or raw if it is not encoded with type information.

reachable

An object is reachable if it is referred to by a root, or is referred to by a reachable object; that is, if it can be reached from the roots by following references.

Reachability is used as an approximation to liveness in tracing garbage collection.

In JavaTM, the reference objects together with ordinary references and finalization generate a hierarchy of reachability that guides the collector(1) on what to do when an object is about to die. There are six strengths:

Basically, an object is only as reachable as the weakest link in the strongest path from the roots. Note that the Java specification's description of the reachabilities is a bit patchy, but that's what it intends. It is unspecified where Java Native Interface's weak global references fit into this.

Similar terms: live.
Opposites: unreachable.
Other links: Java spec for reference objects; Reference Objects and Garbage Collection.

read barrier, read-barrier

A read barrier(1) is a block on reading from certain memory(2) locations by certain threads or processes.

Relevance to memory management: Read barriers are used for incremental or concurrent garbage collection.

See also: write barrier.

read fault

An exception which occurs when reading from an address in virtual memory(1).

This is probably either a page fault, an invalid page fault or a protection fault.

Similar terms: segmentation violation.
See also: write fault.

real memory(1)

A system with no virtual memory(1) capability can be said to have real memory.

Historical note: On older architectures, programs could only directly access data in real memory. Where this was inefficient, they had to store data on disk, and sometimes had alternate portions of program image called overlays.

Opposites: virtual memory(1).

real memory(2) (for full details, see physical memory(1))

Physical memory is memory(1) that is wired to directly to the processor, addressable by physical address.

reclaim

Reclaiming an object or the storage occupied by it is making it available for reuse after the object is no longer needed.

This word is usually used only in connection with automatic memory management.

Similar terms: recycle.

recycle

Recycling storage means making it available for reuse after it has been occupied by an object that is no longer needed.

In simple cases, this might simply involve adding a memory(2) block to the free list. Another possibility is unmapping memory so that the backing store can be allocated to another process.

Similar terms: reclaim.
Other links: Beginner's Guide: Recycling techniques.

reference

In memory management, a reference is the general term for a link from one object to another. Some programming languages have more specific meanings for the term.

The terms "pointer" and "reference" are often interchangeable, but some programming languages differentiate the two in subtle ways.

Similar terms: address; pointer.

reference counting

Reference counting systems perform automatic memory management by keeping a count in each object, usually in a header, of how many references there are to the object. Objects to which there are no references cannot be accessed by the mutator; they are therefore dead and may be reclaimed.

The reference count is incremented for each new reference, and is decremented if a reference is overwritten, or if the referring object is recycled. If a reference count falls to zero, then the object is no longer required and can be recycled.

There are four main problems with simple reference counting:

Garbage with non-zero reference counts
Diagram: Garbage with non-zero reference counts

Reference counting has the advantage that it can reclaim objects promptly, and for this reason it is often used to reclaim non-cyclic data structures in file systems, databases and operating system kernels. When there is a possibility of cyclic data structures, reference counting is sometimes used together with a tracing garbage collector that runs infrequently. Such combinations are generally less efficient than using a tracing collector by itself, but the promptness of reference counting may be important.

Pauses due to reference counting are typically fairly short, and it may be appropriate as a form of incremental garbage collection. But removing a single reference may cause the recycling of a large number of objects at once, so it is not suited to real-time systems where minimum pause times must be guaranteed. There are more complex variations of the technique that address this problem.

Reference counting is often used because it can be implemented without any support from the language or compiler. In C++ this can be encapsulated in a class, using a smart pointer. However, it would normally be more efficient to use a tracing garbage collector instead. The performance of reference counting can be improved substantially with compiler support, using refinements such as deferred reference counting, which has been successfully used in Smalltalk and other languages.

Despite the problems, reference counting is often used for distributed garbage collection. This is because refinements such as weighted reference counting require less inter-process communication than tracing.

See also: limited-field reference count; one-bit reference count.

reference object

In JavaTM, a reference object (java.lang.ref.Reference) encapsulates a reference to some other object, in order to make the garbage collector handle it specially. In particular, a Java program can use this to detect when the referent becomes unreachable.

Basically, the encapsulated reference is a weak reference(1); it will be cleared by the collector(1) when all other references to the referent have disappeared. However, in order to better control what happens at the end of an object's lifetime, Java 1.2 provides three classes of reference objects, each with its own peculiarities: SoftReference, WeakReference, and PhantomReference. Each of these classes has its uses in managing memory. The reference objects together with ordinary references and finalization generate a hierarchy of reachability (q.v.) that guides the collector on what to do when an object is about to die.

A reference object can be registered with a queue, and it will be enqueued when the collector determines that the referent is softly, weakly or phantom reachable, as the case may be. A program can use these queues to perform some action when an object is dying. This allows finer control than the older finalization mechanism alone.

Historical note: This feature was introduced in Java 1.2 (confusingly, part of the JavaTM 2 Platform).

See also: soft reference; weak reference(2); phantom reference.
Other links: Java spec for reference objects; Reference Objects and Garbage Collection.

Related publications:


region inference

Region inference is a technique for determining when objects become dead (even if they are reachable) by a static analysis of the program.

Region inference infers a region for each object. When a region dies, all the objects in it are known to be dead, whether reachable or not. Regions obey a strict stack discipline; that is, when a region dies, all younger regions also die. In this way, region inference occupies a middle ground between stack allocation and heap allocation.

Related publications:


register

Definition not yet available. Please see our feedback page for submission information.

register set partitioning

Run-time systems for garbage-collected languages sometimes partition the set of machine registers a priori into two categories: those always traced and updated by the garbage collector and those ignored by it.

The former are always maintained in a format understood by the collector; the latter are never used to hold references to collectable objects. More complicated schemes are also possible.

This partitioning provides a separation of concerns between the compiler and the garbage collector. The compiler can generate code that produces values the garbage collector would not be able to handle (say, because they have no tags), as long as those values are kept in the ignored registers. The garbage collector can trust that the registers it looks at always contain valid data, and can perform exact garbage collection.

Register set partitioning increases the demand for registers (register pressure), but may reduce the amount of boxing needed.

relocation

Relocating means moving data from one location to another and updating all references.

Relocation is often performed to avoid external fragmentation.

Program loading sometimes relocates code and static data.

Similar terms: moving.
See also: compaction; moving memory manager.

remembered set

A remembered set is the technique of keeping a separate list of interesting references between two sets of objects, so you don't have to find them by scanning.

Many memory management algorithms depend on partitioning the objects and require special handling for references between partitions. Keeping track of such references in a remembered set eliminates the need to scan the originating partition to find them.

A typical use in generational garbage collection is remembering references from an older generation to a younger one.

Similar terms: entry table(2).

Related publications:


replicating garbage collector

A variant of copying garbage collection, which does not destroy the original object when making a copy.

This is useful in an incremental or concurrent collector(1), as no read-barrier is required; the mutator can continue to use old objects. The collector uses a write-barrier to replicate the writes to the new copies.

See also: copying garbage collection; broken heart.

Related publications:


reserved

In a virtual memory(1) system, it is usually possible to hold range of virtual addresses reserved without making it mapped.

Reserving addresses prevents other components of the program using the same addresses, without consuming swap space. This technique is often used in BIBOP schemes, where one might want to reserve a large amount of address space but only sparsely map it.

On some systems there are special calls for reserving; on others one can create mappings that don't need backing store, e.g., on some Unix® systems, mmap /dev/zero with no access.

See also: mapping.

resident

In a cache(2) system, that part of the cached storage which currently has a copy in the cache is called resident. Ideally, the working set should be resident.

See also: cache(2); storage hierarchy; resident set.

resident set

In a virtual memory(1) system, a process' resident set is that part of a process' address space which is currently in main memory. If this does not include all of the process' working set, the system may thrash.

ROM, read-only memory

ROM (read-only memory) is a type of physical memory(2) that can be read from, but not written to. The contents of ROM are usually set in the factory.

See also: RAM.

root

In tracing garbage collection, a root holds a reference or set of references to objects that are a priori reachable. The root set is used as the starting point in determining all reachable data.

Roots basically comprise the references in the state of the mutator. Typical roots are global variables, other static data, and the control stack.

See also: weak root; strong root; ambiguous root; exact root.

root set

The root set is the collection of roots that the mutator declares to the collector(2).

See also: garbage collection.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help