11.2.1 Static Memory🔗

Static memory resides at a fixed location for the entire duration of program execution.

• Lifetime — lasts for the entire program execution

• Allocation — occurs once, before or at program start

• Allocator — handled by the compiler

• Recovery — automatically reclaimed when the program terminates

11.2.2 Stack (LIFO) Memory🔗

Stack memory operates in a last-in, first-out (LIFO) manner and is closely tied to function or method calls.

• Lifetime — limited to the duration of a function/method invocation

• Allocation — occurs when a function is called

• Allocator — usually managed by the compiler (sometimes influenced by the programmer)

• Recovery — automatically occurs when the function returns

11.2.3 Dynamic (Heap) Memory🔗

Dynamic memory is allocated at runtime from a region called the heap.

• Lifetime — persists as long as the program needs it

• Allocation — performed explicitly by the programmer or implicitly by the runtime/compiler

• Allocator — manages available space within the heap

• Recovery — handled either:

  • Manually (e.g., free in C)

  • Automatically via garbage collection

11.3.1 Manual Memory Management🔗

In manual memory management, the programmer is responsible for explicitly allocating and freeing memory.

Example (C):

#include <stdlib.h>

int main() {
    int *p = (int*) malloc(sizeof(int)); // allocate memory
    *p = 10;

    // forgot to free(p); → memory leak
    return 0;
}

Use-after-free example (dangerous):

free(p);
*p = 20;  //undefined behavior (dangling pointer)

These mistakes can lead to crashes or serious security vulnerabilities.

11.3.2 Automatic Memory Management (Garbage Collection)🔗

In automatic memory management, the system/runtime handles memory reclamation.

Example (Java):

public class Main {
    public static void main(String[] args) {
        String s = new String("hello"); // allocated on heap
        
        s = null; // object becomes unreachable
        // garbage collector will reclaim it automatically
    }
}

Example (Python):

def func():
    x = [1, 2, 3]  # allocated
    return

func()
# x is no longer reachable → automatically cleaned up

In modern software, automatic memory management is preferred for most applications, especially where safety and developer productivity matter.

11.4.1 Memory Management in C🔗

In C, local variables live on the stack:

• Allocated at function invocation time

• Deallocated when the function returns

• Storage space is reused after the function returns

Space on the heap is allocated with malloc() and must be explicitly freed with free(). This is called explicit or manual memory management — deletions must be performed by the programmer.

11.4.2 Memory Management in Java🔗

In Java, local variables also live on the stack, and storage is reclaimed when a method returns. However, objects live on the heap:

• Created with calls to Class.new (or equivalent)

• Objects are never explicitly freed — the runtime uses automatic memory management (garbage collection)

11.4.3 Memory Management in OCaml🔗

In OCaml, local variables live on the stack, but tuples, closures, and constructed types live on the heap:

let x = (3, 4)       (* heap-allocated *)
let f x y = x + y in f 3  (* result heap-allocated *)
type 'a t = None | Some of 'a
None      (* not on the heap — just a primitive *)
Some 37   (* heap-allocated *)

Data on the OCaml heap is reclaimed via garbage collection automatically.

11.5.1 Fragmentation🔗

Fragmentation is a serious problem independent of GC. It happens when free memory exists, but it is split into small pieces that are not usable for a single allocation. This is especially important in heap allocation systems without compaction.

Let’s walk through this example step by step. Assume we start with a contiguous memory block:

Memory (start → end)

+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+

We allocate:

allocate(a); allocate(x); allocate(y);

Result:

+----+----+----+----+----+
| a  | x  | y  |    |    |
+----+----+----+----+----+

Now we free a:

free(a);

+----+----+----+----+----+
|    | x  | y  |    |    |
+----+----+----+----+----+

Now we free x:

free(x);

+----+----+----+----+----+
|    |    | y  |    |    |
+----+----+----+----+----+

At this point, memory is fragmented: there are two free spaces, but they are separated. Now we try to allocate b, which needs 3 contiguous blocks:

allocate(b);  (* fails *)

11.5.2 Defragmentation🔗

Defragmentation is the process of reorganizing memory so that free space becomes contiguous again, instead of being split into small scattered holes. It moves allocated blocks together and merges free space into one large block.

Before defragmentation
+----+----+----+----+----+----+
| a  |    | x  |    | y  |    |
+----+----+----+----+----+----+

Defragmentation shifts live objects together:

After defragmentation (compaction)
+----+----+----+----+----+----+
| a  | x  | y  |    |    |    |
+----+----+----+----+----+----+

11.6.1 Determining Liveness🔗

In most languages, we cannot know for certain which objects are truly live or dead at runtime. This is undecidable — analogous to solving the halting problem.

Therefore, GC must make a safe approximation:

• It is safe to decide something is live when it is not (conservative overapproximation)

• It is not safe to deallocate an object that will be used later

11.6.2 Liveness by Reachability🔗

The standard safe approximation is reachability. An object is reachable if it can be accessed by following ("chasing") pointers from live data.

The safe policy is: delete unreachable objects.

• An unreachable object can never be accessed again by the program — it is definitely garbage

• A reachable object may be accessed in the future — it could be garbage but will be retained anyway, which can lead to memory leaks

11.7.1 Step-by-Step Walkthrough🔗

Step 1: Initial Allocation (root → A)

A single object A is allocated. The variable root points to A.

Reference counts:
A = 1  (from root)

Only one object exists, and it is reachable.

Step 2: Allocating B (A → B)

A new object B is created. A now holds a reference to B. The object graph starts to grow.

Reference counts:
A = 1  (from root)
B = 1  (from A)

Step 3: Shared Reference (x → B)

A new variable x is introduced that also points to B, demonstrating shared ownership — multiple references to the same object.

Reference counts:
B = 2  (from A and x)

Step 4 — Allocating C (B → C)

A new object C is allocated. B points to C. We now have the chain root → A → B → C, plus x → B.

Reference counts:
C = 1  (from B)

Step 5 — Removing root (A becomes unreachable)

root is set to null. A loses its only incoming reference:

• A’s count drops to 0 → freed immediately

• B retains 1 reference (from x) — not freed

• C retains 1 reference (from B) — not freed

Freeing A does not free B because B is still referenced by x.

Step 6 — Removing x (B loses its external reference)

x is set to null. B loses one incoming reference.

• B’s count drops from 1 to 0 → freed

Step 7 — Cascade Deletion (B → C freed)

When B’s reference count drops to 0 and B is freed, its outgoing reference to C is removed as well.

• B is freed

• B’s reference to C is released

• C’s count drops to 0 → freed

This triggers a cascade: freeing one object automatically frees all objects reachable only through it.

11.7.2 Where Reference Counting Is Used🔗

11.7.3 Rust Rc Example🔗

Rust’s Rc<T> type provides reference-counted shared ownership:

use std::rc::Rc;
fn main() {
    let s = String::from("hello");
    let r1 = Rc::new(&s);
    {
        let r2 = Rc::clone(&r1);
        println!("r1 = {}", Rc::strong_count(&r1));  // r1 = 2
        println!("r2 = {}", Rc::strong_count(&r2));  // r2 = 2
    }
    // r2 is out of scope
    println!("r1 = {}", Rc::strong_count(&r1));      // r1 = 1
}

When r2 goes out of scope, its reference is dropped and the count decrements to 1. When r1 goes out of scope, the count reaches 0 and the allocation is freed.

11.7.4 Reference Counting Tradeoffs🔗

Advantages:

• Incremental technique — generally a small, constant amount of work per memory write; with more effort, running time can even be bounded

• Immediate reclamation — objects are freed as soon as their count drops to 0

Disadvantages:

• Cascading decrements can be expensive — freeing one object may trigger a chain of reference count decrements

• Requires extra storage for reference counts

• Cannot collect cycles — if a set of objects form a cycle, their counts never reach 0 even when they are unreachable from the roots; a separate cycle-detection mechanism is needed

11.9.1 Mark and Sweep Advantages🔗

• No problem with cycles — reachability-based tracing handles cyclic structures correctly

• Non-moving — live objects stay in place, which makes conservative GC possible (used when it is uncertain whether a value is a pointer or an integer, e.g., in C)

11.9.2 Mark and Sweep Disadvantages🔗

• Fragmentation — available space may be broken up into many small pieces; many mark-and-sweep implementations add a compaction phase (like defragmenting a disk)

• Cost proportional to heap size — the sweep phase traverses the entire heap, touching dead memory in order to put it back on the free list

11.10.1 Copying GC Tradeoffs🔗

Advantages:

• Only touches live data — cost is proportional to the amount of live data, not heap size

• No fragmentation — copying automatically compacts live objects, which tends to increase cache locality

Disadvantages:

• Requires twice the memory space — only half the heap is usable at any time

11.12.1 Java HotSpot SDK 1.4.2 Collector🔗

Java’s HotSpot JVM uses a multi-generational, hybrid collector:

• Young generation — stop-and-copy collector

• Tenured generation — mark and sweep collector

• Permanent generation — no collection (stores class metadata)