Memory Allocation
Programs request memory when they need it and release it when they are done. Over time, free memory can become divided into smaller gaps. This is called fragmentation. When a program requests memory, the allocator must choose a suitable free gap. Try First Fit, Best Fit and Worst Fit with the same requests and compare how each method uses memory. This is a simplified example for learning. It is different from the custom memory manager I built at work.
Interactive workspace
Starts from the lowest address and picks the first free gap that is large enough. It can be faster because it stops searching as soon as it finds a suitable gap.
Enter a letter and size to allocate memory. For example, A5 means allocate 5 units to block A. Enter a minus sign and a letter to free a block. For example, -A frees block A.
Examples
Address space
addresses 0 to 32 (32 units)
solid colour: allocated blockdashed: free gap
Free memory and fragmentation
Free in total
32
of 32 units
Largest free block
32
Used
0%
0 units
Fragmentation
0%
The free memory, split by gap (1 gap). The accent part is the largest.
Fragmentation is how much of the free space is not in the largest gap. 0% means all free space is in one piece. Higher means it is split into smaller gaps that big requests cannot use.
Step-by-step explanation
0 of 9 steps
Press Next or Play to see where each memory block is placed or released and why.
Memory map
| Block | Start | End | Size | State |
|---|---|---|---|---|
| – | 0 | 32 | 32 | Free |
Design diagram: how this demo decides
Click any box to see what it does and why it is built that way.
Start
Next operation
- What it does
- The simulator reads the operations one at a time, such as A5 (allocate 5 units as block A) or -A (free block A).
- Where it lives
- simulateAllocator() in src/lib/allocator.ts
- Why it is built this way
- One operation is one step, so Next and Back match the data exactly.
Under the hood
From input to screen
The experiment follows this process. Select any box to see what it does and which function or component is behind it.
Pipeline: input, parsing, simulation, steps, visualization
Click any box to see what it does and why it is built that way.
Start
Input
- What it does
- You enter operations such as A5 or -A, choose the memory size and select First Fit, Best Fit or Worst Fit.
- Where it lives
- AllocatorDemo.tsx (text, memSize, fit)
- Why it is built this way
- Only the values you enter are stored. The memory layout and other results are calculated from them.
Technical notes
How Memory Allocation works
How the algorithm works
Memory is represented as a continuous space containing allocated blocks and free gaps. Each allocated block has a letter as its name. When a program requests memory, the allocator looks for one free gap large enough to hold the block. When a block is freed, its space becomes available again and is joined with any free gaps next to it.
The three methods choose a free gap differently. First Fit chooses the first suitable gap, starting from the lowest address. Best Fit chooses the smallest gap that can hold the requested block. Worst Fit chooses the largest available gap. If two gaps are equally suitable, the one at the lower address is selected. If a gap is larger than the requested size, the remaining space stays free.
Important steps
- 01Read the next operation.
- 02Decide whether it is an allocation or a free operation.
- 03If a block is being freed, release it and combine it with neighbouring free gaps.
- 04If memory is being allocated, check that the block name is not already in use.
- 05Find all free gaps that are large enough.
- 06Select a gap using First Fit, Best Fit or Worst Fit.
- 07Place the block and keep any remaining space as a free gap.
- 08Save the memory map and explain the result.
Relevant variables
- M
- Total memory size in units (16, 24, 32, 48 or 64).
- blocks[]
- The starting address, size and name of every block and free gap.
- k
- Number of operations, up to 30.
- free in total
- Sum of all free memory gaps.
- largest gap
- Size of the biggest free gap.
- fragmentation
- 1 − largest gap ÷ free in total, shown as a percentage.
Time and space complexity
| Algorithm | Time | Space |
|---|---|---|
| First Fit | O(k·m) | O(k·m) |
| Best Fit | O(k·m) | O(k·m) |
| Worst Fit | O(k·m) | O(k·m) |
k is the number of operations, and m is the number of blocks and free gaps. Each operation checks the block list. The walkthrough also saves a copy of the memory layout after every step.
Example input and output
Input
- Memory: 48 units
- Operations: A10 B2 C5 D2 E7 F2 G12 -A -C -E H6
Output
- First Fit: H is placed at address 0.
- Best Fit: H is placed at address 19, using the 7-unit gap.
- Worst Fit: H is placed at address 0, using the 10-unit gap.
Edge cases
- External fragmentation: Enough memory may be free in total, but if no single gap is large enough, the request fails.
- Exact fit: If a gap is exactly the requested size, no free space remains in that gap.
- Joining free gaps: Freeing neighbouring blocks combines them into one larger gap. For example, A10 B10 -A -B leaves one free gap.
- Invalid free operation: Trying to free a block that does not exist is reported.
- Duplicate block name: Allocating the same letter twice is reported.
- Oversized block: A block larger than the total memory size is rejected.
Where the code lives
- Enginesrc/lib/allocator.ts
- Workspacesrc/components/AllocatorDemo.tsx
- Checkstests/allocator.test.ts