Memory Allocation

In the virtual memory lesson every request was the same size: one page. Fixed size removes the placement problem — if a free physical page exists, every virtual page fits there, and which free page gets chosen does not change the outcome. A process’s heap is not like that. Requests come in different sizes, arrive out of order, are released out of order, and which free block they land in determines whether later requests fit at all.

The Memory Layout lesson in How Computers Work already defined the heap, the allocator, and fragmentation; this lesson does not repeat those definitions. What it adds is measurement: two placement policies run on the same event sequence, and the difference between them is counted in placed requests, bytes left free, and unusable remainder.

Baseline, Setup, and What Gets Measured

The baseline without an allocator is not an allocator at all: the heap holds a single boundary variable, every request pushes the boundary forward by its own size, and there is no such operation as releasing. This arrangement’s management cost is one addition; in exchange, freed memory is never reclaimed.

The setup adds releasing and reuse. The heap splits into blocks, each block either belongs to a name or is free, a released block returns to free, and adjacent free blocks are merged. What gets measured is this: how many requests does keeping this ledger save, and what does it leave behind.

• BD8 — The heap is 1024 bytes and starts as a single block. The allocator gives exactly the number of bytes requested; there is no alignment or header overhead, so internal fragmentation is zero in this lesson.
• BD9 — The event sequence comes from the common definition: six allocations, two releases, two more allocations. Total requested is 1254 bytes, that is, more than the heap; without releasing, not all of it fits.
• BD10 — Two placement policies are measured. First fit picks the first sufficient block in the list; best fit picks the smallest of the sufficient blocks.
• BD11 — At release, only adjacent free blocks merge; two free blocks apart from each other stay separate. No moving or compaction is performed.

"""M01/K05 common definition (excerpt): allocator, external fragmentation and the end-to-end baseline."""
HEAP = 1024
EVENTS = [("A", "a", 200), ("A", "b", 150), ("A", "c", 200), ("A", "d", 100),
          ("A", "e", 200), ("A", "f", 174),
          ("R", "b"), ("R", "d"),                  # two free blocks of 150 and 100 bytes
          ("A", "g", 90), ("A", "h", 140)]


def allocate(events, size=HEAP, policy="first_fit"):
    """events: ("A", name, size) allocate , ("R", name) release."""
    block = [{"name": None, "start": 0, "size": size}]      # name None means free
    placed = rejected = 0
    for event in events:
        if event[0] == "A":
            _, name, want = event
            candidates = [b for b in block if b["name"] is None and b["size"] >= want]
            if not candidates:
                rejected += 1
                continue
            chosen = candidates[0] if policy == "first_fit" else min(candidates, key=lambda b: b["size"])
            k = block.index(chosen)
            left = chosen["size"] - want
            block[k] = {"name": name, "start": chosen["start"], "size": want}
            if left:
                block.insert(k + 1, {"name": None, "start": chosen["start"] + want, "size": left})
            placed += 1
        else:
            for b in block:
                if b["name"] == event[1]:
                    b["name"] = None
            k = 0                                        # adjacent free blocks merge
            while k < len(block) - 1:
                if block[k]["name"] is None and block[k + 1]["name"] is None:
                    block[k]["size"] += block[k + 1]["size"]
                    block.pop(k + 1)
                else:
                    k += 1
    free = [b["size"] for b in block if b["name"] is None]
    return {"placed": placed, "rejected": rejected, "free": sum(free),
            "largest_free": max(free) if free else 0, "block": len(free),
            "layout": [(b["name"] or "-", b["start"], b["size"]) for b in block]}


def end_to_end(events, size=HEAP):
    """Baseline without allocator: no releasing , only a forward-moving boundary."""
    boundary, placed, rejected = 0, 0, 0
    for event in events:
        if event[0] == "A":
            if boundary + event[2] <= size:
                boundary, placed = boundary + event[2], placed + 1
            else:
                rejected += 1
    return placed, rejected


def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def long_sequence(seed, count=200):
    """Long event sequence: each step is either an allocation or a random release."""
    r = generator(seed)
    events, live, counter = [], [], 0
    for _ in range(count):
        if live and r(10) < 5:
            events.append(("R", live.pop(r(len(live)))))
        else:
            name = f"n{counter}"
            counter += 1
            events.append(("A", name, 16 + r(8) * 16))
            live.append(name)
    return events


print("heap", HEAP, "bytes | requests", sum(1 for o in EVENTS if o[0] == "A"),
      "| total requested", sum(o[2] for o in EVENTS if o[0] == "A"))
print("baseline (end-to-end , no releasing): placed %d rejected %d" % end_to_end(EVENTS))
print("policy        placed  rejected  free  largest free  blocks")
for y in ("first_fit", "best_fit"):
    a = allocate(EVENTS, HEAP, y)
    print(f"  {y:12s} {a['placed']:5d} {a['rejected']:10d} {a['free']:5d}"
          f" {a['largest_free']:14d} {a['block']:6d}")
    print("   ", " ".join(f"{name}@{start}+{size}" for name, start, size in a["layout"]))
print()
print("long sequence (200 events)   requests  first fit  best fit")
for seed in (20260218, 20260219):
    U = long_sequence(seed)
    requests = sum(1 for o in U if o[0] == "A")
    i = allocate(U, HEAP, "first_fit")
    e = allocate(U, HEAP, "best_fit")
    print(f"  seed {seed}    {requests:4d}  {i['placed']:9d}  {e['placed']:9d}")

heap 1024 bytes | requests 8 | total requested 1254
baseline (end-to-end , no releasing): placed 6 rejected 2
policy        placed  rejected  free  largest free  blocks
  first_fit        7          1   160            100      2
    a@0+200 g@200+90 -@290+60 c@350+200 -@550+100 e@650+200 f@850+174
  best_fit         8          0    20             10      2
    a@0+200 h@200+140 -@340+10 c@350+200 g@550+90 -@640+10 e@650+200 f@850+174

long sequence (200 events)   requests  first fit  best fit
  seed 20260218     119         96         98
  seed 20260219     114        100         99

Three numbers sit side by side. Baseline: end-to-end allocation, 6 placed, 2 rejected, and a single boundary variable. Setup: an allocator holding a block list, best fit places 8. Cost: a block list scanned on every request, a heap split into eight blocks, and two remaining gaps.

What releasing buys is plain: the baseline hands out its 1024 bytes once and is done, the allocator reuses the released 250 bytes and satisfies two more requests. But it does not get the full gain — the first-fit policy places only seven of the eight requests.

External Fragmentation Is a Cause of Rejection

When b and d are released, two free blocks of 150 and 100 bytes appear in the heap. Since neither is adjacent to the other, merging never triggers; 250 bytes are free in total, but no single block holds more than 150. This is called external fragmentation: the total of free memory is sufficient, a single block is not.

The result shows up in the last two requests. First fit places the 90-byte g request in the first sufficient block in the list — the 150-byte one — and leaves 60 bytes behind. The following 140-byte h request then finds 60- and 100-byte blocks left: 160 total, which is enough, but neither alone is.

"""External fragmentation: free total is enough , a single block is not. Layouts are the output of block 01."""
LAYOUT = {
    "first_fit": [("a", 200), ("g", 90), ("-", 60), ("c", 200),
                  ("-", 100), ("e", 200), ("f", 174)],
    "best_fit": [("a", 200), ("h", 140), ("-", 10), ("c", 200), ("g", 90),
                 ("-", 10), ("e", 200), ("f", 174)],
}
for name, layout in LAYOUT.items():
    gaps = sorted((b for n, b in layout if n == "-"), reverse=True)
    free, largest = sum(gaps), gaps[0]
    print(f"{name:12s} free {free:4d}  largest {largest:4d}  blocks {len(gaps)}"
          f"  external fragmentation ratio {1 - largest / free:.4f}")
    for want in (10, 60, 90, 140):
        print(f"    {want:4d}-byte request: free sufficient {free >= want}"
              f" , single block sufficient {largest >= want}")

first_fit    free  160  largest  100  blocks 2  external fragmentation ratio 0.3750
      10-byte request: free sufficient True , single block sufficient True
      60-byte request: free sufficient True , single block sufficient True
      90-byte request: free sufficient True , single block sufficient True
     140-byte request: free sufficient True , single block sufficient False
best_fit     free   20  largest   10  blocks 2  external fragmentation ratio 0.5000
      10-byte request: free sufficient True , single block sufficient True
      60-byte request: free sufficient False , single block sufficient False
      90-byte request: free sufficient False , single block sufficient False
     140-byte request: free sufficient False , single block sufficient False

First fit’s rejection is not a memory shortage; a 140-byte request is turned away while 160 bytes stand free. The external fragmentation ratio — the share of free memory outside the largest block — is 0.3750 here.

Best fit places both of the same requests. It puts the 90-byte g request into the 100-byte gap, leaving 10 bytes, and the 140-byte h request into the 150-byte gap, again leaving 10 bytes. All eight requests are placed, none rejected. But the two remaining gaps are 10 bytes each, and the external fragmentation ratio has climbed to 0.5000: 20 bytes appear free, yet not even an 11-byte request can be satisfied. Unusable memory is a different line item from unused memory, and a metric that looks only at the total of free bytes does not show it.

Best Fit Does Not Always Pay Off

The gap between seven placed requests and eight invites reading best fit as a general rule. The last block of output tests that: the same allocator, on two separate 200-event sequences.

In the first workload, first fit places 96 of 119 allocation requests, best fit places 98. Best fit is two requests ahead. In the second workload, first fit places 100 of 114, best fit places 99; this time first fit is one request ahead. The ranking flips with the workload. The differences themselves are small too: two and one request, roughly a two-percent swing on about a hundred requests.

Taken together these two observations give a single conclusion: no advantage between the two policies has been established in this measurement. What has been established is that on the eight-event sequence, best fit places one more request and leaves behind a more unusable remainder in exchange. Which policy wins depends on the workload’s size distribution and release pattern; a ranking measured on a single sequence counts as unmeasured.

There is also a cost this model does not count. This implementation scans the entire block list on every request, so the two policies come out with equal search cost. A real first-fit implementation can stop as soon as it finds the first sufficient block; best fit cannot, because it can only know whether a smaller sufficient block exists once it has finished the list. This difference was not measured in this lesson, and because it was not measured, it is not written down as grounds for an advantage.

Why Compaction Is Not Free

External fragmentation has an exact fix: slide the resident blocks toward the start of the heap and collect all the gaps into one. This is called compaction, and it rescues the request first fit rejected.

• BD12 — Compaction is performed only as a measurement; moving a block counts as copying that block’s bytes to its new location.

"""The cost of compaction: how many bytes moving to collect gaps into one block costs."""
LAYOUT = [("a", 0, 200), ("g", 200, 90), ("-", 290, 60), ("c", 350, 200),
          ("-", 550, 100), ("e", 650, 200), ("f", 850, 174)]     # first-fit result

boundary, moved, moved_block = 0, 0, 0
for name, start, size in LAYOUT:
    if name == "-":
        continue
    if start != boundary:
        moved += size
        moved_block += 1
    boundary += size
print("resident bytes:", boundary, "| gap collapsed into one:", 1024 - boundary)
print("blocks moved:", moved_block, "| bytes moved:", moved)
print("does the 140-byte request fit after compaction:", 1024 - boundary >= 140)

resident bytes: 864 | gap collapsed into one: 160
blocks moved: 3 | bytes moved: 574
does the 140-byte request fit after compaction: True

The rejected request is rescued, but the cost is copying 574 bytes — two thirds of the 864 bytes resident in the heap. This is a task on a scale incomparable to allocation itself, and it is paid for a single request.

The second and heavier cost is not the copying. Every block that moves changes address, so every reference pointing to that block must change too. In a layout where addresses are held directly as numbers, there is no way to know which number is a pointer and which is data, so compaction cannot be applied. In layouts where it can be, a block is reached not directly but through an indirection table; then moving reduces to changing one row in the table, but from that point on every access pays one extra table read. The step the abstraction charges does not disappear, it only changes location.

Internal Fragmentation Does Not Enter Here

The allocator hands out exactly the number of bytes requested: request 90, get 90 bytes allocated. So internal fragmentation is zero in this lesson, and the table has no such column. It exists in every layout that works with fixed-size units — in the virtual memory lesson, a page not filled to its last byte is internal fragmentation, and in the file system, a block half left empty is too. The two fragmentations are each other’s counterpart: fixed size removes external fragmentation and puts internal fragmentation in its place; variable size removes internal fragmentation and puts external fragmentation in its place. The fourth lesson will measure the other end of this trade-off in bytes.

Summary

• The end-to-end baseline places 6 of 8 requests and never uses releasing; the allocator holding a block list reuses the released 250 bytes and satisfies one or two more requests.
• First fit places 7 requests and rejects one: a 140-byte request is turned away while 160 bytes stand free, because the largest single block is 100 bytes. That is external fragmentation.
• Best fit places all 8 requests but leaves behind two 10-byte gaps; the external fragmentation ratio climbs from 0.3750 to 0.5000 and the remaining 20 bytes are unusable.
• The ranking flips across two separate 200-event sequences: best fit is two requests ahead in the first workload, first fit is one request ahead in the second. No advantage between the two policies has been measured.
• In this model both policies scan the entire block list; the search-cost difference was not measured and is not used as grounds.

Next Step

In this lesson the program itself performed the releasing: b and d were released, their space reclaimed. A program that forgets to release leaks memory; one that releases too early uses a freed address. The next lesson models the arrangement that hands this decision from the program to the runtime: a collector working by a reachability criterion decides which of 40 objects stay alive, and the cost of that is a pause. The question to measure is whether the length of the pause is proportional to the garbage collected, or to the objects that survive.