Allocator
This is a game where you have to allocate and free contiguous memory blocks. You can hover or drag on free cells<br>to preview the allocated memory. If it's not possible to allocate a contiguous memory block, you lose and have<br>to start from the first level. If you succeed to allocate all the blocks, you win and can play the next level.<br>Each new level becomes more and more challenging.
Memory allocation reference
Memory allocation reference
A memory allocator manages a region of memory and decides where each new<br>allocation should go. When memory is allocated and freed over time, the free<br>space can become split into many small gaps. This is called<br>external fragmentation : there may be enough total free memory,<br>but not enough contiguous free memory for a request.
There is no universally best allocation strategy. Real allocators usually<br>balance speed, memory usage, fragmentation, and implementation complexity.
Common allocation strategies
Strategy<br>Idea<br>Pros<br>Cons
First fit<br>Place the request in the first free block large enough to hold it.<br>Simple and usually fast, because the search can stop early.<br>Can leave many small holes near the beginning of memory.
Best fit<br>Choose the smallest free block that is large enough.<br>Tries to avoid wasting large blocks.<br>Usually slower, and may create tiny leftover fragments.
Worst fit<br>Choose the largest available free block.<br>Tries to leave a remaining block that is still useful.<br>Often breaks up large blocks unnecessarily and can perform poorly.
Next fit<br>Like first fit, but continue searching from the previous allocation position.<br>Avoids repeatedly scanning from the start.<br>Can still fragment memory and may miss better earlier holes.
Buddy allocator<br>Split memory into power-of-two blocks and merge neighboring buddies when freed.<br>Fast splitting and merging.<br>Can waste space because requests are rounded up.
Pool / slab allocator<br>Keep fixed-size blocks for objects of the same size.<br>Very fast for repeated same-size allocations.<br>Less flexible for varied allocation sizes.
Key terms
Free block / hole: an unused region of memory.
Allocation: reserving memory for a request.
Deallocation / free: returning memory to the allocator.
Splitting: using part of a free block and leaving the rest free.
Coalescing: merging neighboring free blocks after deallocation.
Internal fragmentation: wasted space inside an allocated block.
External fragmentation: wasted space caused by free memory being split into small<br>non-contiguous pieces.
Further reading
Operating Systems: Main Memory
Doug Lea: A Memory Allocator