Which of the following heap memory allocation strategies is likely to exploit spatial locality of memory accesses in a program, the most?
- (A)
Best Fit
- (B)
First Fit
- (C)
Next Fit
- (D)
Last Fit
ISRO CS 2023 Q.9: solution and answer
Answer and solution
ANSWER
The answer is (c) Next Fit.
Official answer: CSource: ISRO's revised and final answer key of 16 February 2024
Spatial locality means that memory locations accessed close together in time are also close together in address, so a cache line or page that has just been loaded is likely to be used again.
Best Fit scans the whole free list for the smallest hole that is large enough. Consecutive requests can therefore be served from holes that are far apart, and the leftover pieces are tiny and scattered. Objects allocated together end up in distant places, so locality is poor.
First Fit starts every search at the head of the free list. Small leftover pieces collect near the front, and successive requests are scattered among them, so objects allocated around the same time are not kept together.
Next Fit resumes its search from the point where the previous allocation ended. Successive requests are therefore carved out one after another from the same region, so objects allocated around the same time sit next to each other in memory.
Objects that are allocated together are usually used together. Placing them side by side in adjacent addresses gives accesses to them the best spatial locality, so Next Fit exploits spatial locality the most of the listed strategies.
Last Fit is not a standard placement policy, and nothing in it keeps successive allocations adjacent.
Hence the answer is (c) Next Fit.
KEY IDEA
Next Fit continues searching from the point of the last allocation, so consecutive requests are placed in adjacent memory. Data allocated together sits together, which is spatial locality.
WATCH OUT FOR
Choosing First Fit or Best Fit because they are the familiar policies. First Fit keeps returning to the front of the list, where small remnants have piled up, and Best Fit hunts for the tightest hole anywhere in the list, so both scatter objects that are allocated at about the same time.
From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 3 ISRO Memory management questions, with notes