8.3. OPERATING SYSTEMS
This section under major construction.
Memory management. In many languages, including C and C++, the programmer is responsible to manage memory consumption and explicitly free it when it is no longer in use. "Micro-managed" memory can be more efficient if done properly, but it is tedious and error-prone. Automatic memory collection can be almost as efficient in common applications, and requires less development time.
Garbage collection. Invented by John McCarthy in 1958 as part of LISP. Idea = determine which objects are reachable via references by other reachable objects; free up unreachable objects (garbage). Here are some common garbage collection techniques.
- Reference counting. Count number of references to each object. When it hits zero, can free the object. Drawback - does not work for cyclic linked structures, requires frequent updating of count fields.
- Mark-sweep algorithm. Mark all objects as garbage. Scan through all reachable objects and mark as reachable. After scan, anything still marked as garbage can be eliminated. Drawback - active memory becomes fragmented, must scan every object in memory.
- Copying. Do mark-sweep, but copy all non-garbage objects to a contiguous block of memory. Eliminates fragmention. Drawback - persistent objects get copied back-and-forth, requires twice as much memory.
- Mark compact. Copy objects to the same part of memory. Persistent objects are infrequently copied.
- Generational. Divide objects into several "generations" depending on how long they have been active. Initially objects are placed in the "youngest" generation, as they persist, they move to "older" generations.