Week 46 of 125
TAOCP 2.5 Dynamic Storage Allocation
Sign up or sign in to tick these off and give this week a due date.
-
How malloc-style allocators work: first-fit versus best-fit, splitting and merging free blocks, boundary tags for fast coalescing, the buddy system, and empirical results on fragmentation.
Time About 9 hours this week
Why it matters
Every malloc, every arena and every slab allocator uses these ideas. Understanding fragmentation helps you debug memory blowups in long-running services.
Before you start
- 2.2.3 Linked Allocation
- C malloc/free (clox)
How to approach it
Implement a tiny first-fit allocator with boundary tags over a static byte array in C, then a buddy allocator. Write a test that does random allocate/free and checks no block overlaps.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Forgetting to merge with both neighbors on free.
- Alignment. Real allocators must return aligned addresses; Knuth's model ignores this.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.