Placement-algorithm questions are bookkeeping questions disguised as theory. One missed update to a free hole changes every later allocation, so guessing from the algorithm's name is dangerous.
The safe method is mechanical: preserve address order, process requests in order, choose a hole by the stated rule, and immediately replace that hole with its leftover.
1. The dynamic-partitioning setup
In contiguous dynamic partitioning, each process occupies one continuous region of physical memory. Free regions between allocated processes are called holes. Their sizes change as processes arrive and leave.
When a process of size P is placed in a hole of size H, the leftover is:
New hole size = H - P
If H = P, that hole disappears. If no individual hole is at least as large as the request, the process cannot be allocated even when total free memory is sufficient.
Keep holes in address order for First Fit. Best Fit and Worst Fit choose by size, but the original identities still matter because the question may ask where a process lands. If equal candidates exist and the stem gives no tie rule, a common convention is to choose the first one in address order and state that assumption.
2. First Fit, Best Fit and Worst Fit in one line each
First Fit: scan from the beginning of the hole list and choose the first hole large enough. It usually examines fewer holes.
Best Fit: choose the smallest hole large enough. It minimises the immediate leftover, but can create many tiny unusable holes.
Worst Fit: choose the largest available hole. Its aim is to leave a large remainder that may still serve a later request.
“Best” and “Worst” are names, not universal performance guarantees. Best Fit can win on one request stream and lose on another. The numerical must be traced.
3. Worked example: one request stream, all three algorithms
Start with these free holes in address order:
H1 = 100 KB, H2 = 500 KB, H3 = 200 KB, H4 = 300 KB, H5 = 600 KB
Process these requests in order:
P1 = 212 KB, P2 = 417 KB, P3 = 112 KB, P4 = 426 KB
The initial free total is:
100 + 500 + 200 + 300 + 600 = 1700 KB
First Fit trace
For P1 = 212, H1 is too small and H2 is the first fit:
H2 leftover = 500 - 212 = 288 KB
The holes are now [100, 288, 200, 300, 600].
For P2 = 417, only H5 fits:
H5 leftover = 600 - 417 = 183 KB
The holes become [100, 288, 200, 300, 183].
For P3 = 112, H1 is too small and the current H2 is the first fit:
H2 leftover = 288 - 112 = 176 KB
The final holes before P4 are [100, 176, 200, 300, 183]. None is at least 426 KB, so P4 must wait.
Best Fit trace
For P1, the smallest fitting hole is H4 at 300 KB:
300 - 212 = 88 KB
For P2, the smallest fitting hole is H2 at 500 KB:
500 - 417 = 83 KB
For P3, the fitting original holes are H3 at 200 KB and H5 at 600 KB. H3 is smaller:
200 - 112 = 88 KB
For P4, H5 at 600 KB fits:
600 - 426 = 174 KB
The final hole sizes are [100, 83, 88, 88, 174], and all four processes are allocated.
Worst Fit trace
P1 goes into H5, the largest hole:
600 - 212 = 388 KB
P2 then goes into H2, now the largest fitting hole:
500 - 417 = 83 KB
P3 goes back into H5's 388 KB remainder because it is the largest current hole:
388 - 112 = 276 KB
The holes are [100, 83, 200, 300, 276]. No hole can hold P4, so P4 must wait.
Algorithm | P1 | P2 | P3 | P4 | Result |
|---|---|---|---|---|---|
First Fit | H2 | H5 | H2 remainder | Wait | 3 allocated |
Best Fit | H4 | H2 | H3 | H5 | 4 allocated |
Worst Fit | H5 | H2 | H5 remainder | Wait | 3 allocated |
4. Fragmentation: why these algorithms matter
After the First Fit trace, the free holes are 100, 176, 200, 300 and 183 KB. Their total is:
100 + 176 + 200 + 300 + 183 = 959 KB
P4 needs only 426 KB, yet the largest individual hole is 300 KB. The request fails because free space is split across non-contiguous regions. That is external fragmentation.
The same 959 KB total remains after the Worst Fit trace because both algorithms allocated the same first three process sizes:
1700 - (212 + 417 + 112) = 1700 - 741 = 959 KB
Allocation placement changes the largest available hole, not the total left after the same requests.
Internal fragmentation is different. It is unused space inside an allocated fixed-size block or partition. Dynamic contiguous allocation mainly suffers from external fragmentation. Compaction can move processes together to combine scattered holes, but moving memory has a cost. Paging removes the need for one contiguous physical hole, as explained in Memory Management: Paging and Segmentation.
5. Traps GATE plants in allocation questions
Process requests must be handled in the given order. Do not reorder them to improve the result.
Update a hole immediately after allocation. A later process sees the remainder, not the original size.
First Fit scans in address order, not ascending size order.
Best Fit is the smallest hole that can satisfy the request, not the smallest hole overall.
A Worst Fit remainder stays in the hole list and can be selected again, as H5 is for P3.
Total free memory does not decide whether a contiguous request fits. The largest individual hole does.
Do not assume Best Fit always allocates the most processes. It happens to win for this stream.
For more drills that distinguish paging, segmentation and fragmentation, use Operating Systems Memory Management and Paging MCQs.
6. How GATE tests placement algorithms
A question may ask where a process lands, which algorithm serves every request, the final size of a named hole, the largest remaining hole, or whether a failure represents internal or external fragmentation. The only dependable answer is the updated trace.
More than 2,000 Operating System questions are available in KnowledgeGate for practice in this area. Subject weightage and paper details can change, so verify them on the official GATE portal. The placement rules themselves remain stable.
7. Short version and next step
First Fit takes the first suitable hole, Best Fit the smallest suitable hole, and Worst Fit the largest. Run requests in order, subtract immediately, and keep every remainder in the list.
Now repeat the trace without looking at the table. Then work a timed Operating Systems set in the GATE Test Series, build the surrounding theory through GATE Guidance by Sanchit Sir, and use the GATE preparation category to continue into paging and virtual memory.
