Next Fit Memory Allocation in OS
First fit with a memory. The scan restarts from wherever it last stopped, so allocations spread across the list instead of piling up at the front.
What Next Fit in OS Means
Next fit in OS is first fit with one addition: a roving pointer that remembers where the previous search ended. The next request resumes scanning from that position rather than from the head of the list, wrapping around to the start when it reaches the end.
The motivation is first fit's bias. Because every first-fit search begins at the front, small fragments accumulate there, and each later search walks over that debris before reaching usable holes.
Next fit never re-walks the same prefix. The pointer advances through the list, so allocations are distributed across the whole region instead of being concentrated at its beginning.
- Search cost: the shortest average of the four
- State: one pointer, carried between allocations
- Effect: allocations distributed, not clustered
Next Fit in OS — Worked Example
Take holes of 100, 500, 200, 300 and 600 KB and a 212 KB request, with the pointer starting at hole 1.
First request (212 KB). With the pointer at the head, next fit behaves exactly like first fit: hole 1 is too small, hole 2 (500 KB) fits. Allocate, leaving 288 KB. The pointer is left at hole 3.
Second request (112 KB). First fit would restart at hole 1 and re-examine 100 and 288 before finding a home. Next fit starts at hole 3 (200 KB), which fits immediately — one comparison instead of three. It leaves 88 KB and the pointer moves to hole 4.
Third request (180 KB). Resuming at hole 4 (300 KB), which fits at once, leaving 120 KB. Three requests have landed in three different regions of the list. The final free list is 100, 288, 88, 120, 600 KB.
- Searches: 2, then 1, then 1 comparison
- First fit would have used 2, then 3, then 4
- Allocations spread across three separate regions
Next Fit vs First Fit — What Spreading Costs
Distributing allocations is not free. Because the pointer keeps moving, next fit breaks up holes across the entire region rather than concentrating the damage in one place.
First fit leaves the far end of the list relatively untouched, so large holes survive there and large requests can still be served. Next fit chips at every part of the list in turn, and those large runs get consumed too.
The trade depends on the workload: next fit wins on search time and even distribution, first fit wins on preserving large contiguous runs. Simulations generally favour first fit overall, with next fit close behind — and both comfortably ahead of best fit and worst fit.
- Fastest searches, at the cost of spreading the damage
- Large holes at the far end stop surviving
- Both beat best fit and worst fit in practice
Next fit in OS — the pointer stays where the last search stopped
"""Next fit: first fit with a pointer that survives between allocations."""
class NextFitAllocator:
"""Allocates from a free list, resuming each scan where the last ended."""
def __init__(self, holes):
self.holes = list(holes)
self.pointer = 0
def allocate(self, size):
"""Place one request. Returns the hole index used, or -1 on failure."""
count = len(self.holes)
for step in range(count): # at most one full lap
i = (self.pointer + step) % count # wrap at the end of the list
if self.holes[i] >= size:
self.holes[i] -= size
self.pointer = i # resume here on the next request
return i
return -1
def main():
allocator = NextFitAllocator([100, 500, 200, 300, 600])
for request in (212, 112, 180):
index = allocator.allocate(request)
if index < 0:
print(f"{request} KB -> no hole large enough")
continue
print(f"{request} KB -> hole {index + 1}, "
f"leaves {allocator.holes[index]} KB")
print(f"final free list: {allocator.holes}")
if __name__ == "__main__":
main()
// Next fit: first fit with a pointer that survives between allocations.
#include <iostream>
#include <vector>
class NextFitAllocator {
public:
explicit NextFitAllocator(std::vector<int> holes)
: holes_(std::move(holes)) {
}
// Places one request. Returns the hole index used, or -1 on failure.
int allocate(int size) {
const int count = static_cast<int>(holes_.size());
for (int step = 0; step < count; ++step) { // one full lap maximum
const int i = (pointer_ + step) % count; // wrap at the end
if (holes_[i] >= size) {
holes_[i] -= size;
pointer_ = i; // resume here on the next request
return i;
}
}
return -1;
}
const std::vector<int>& holes() const {
return holes_;
}
private:
std::vector<int> holes_;
int pointer_ = 0;
};
int main() {
NextFitAllocator allocator({100, 500, 200, 300, 600});
for (int request : {212, 112, 180}) {
const int index = allocator.allocate(request);
if (index < 0) {
std::cout << request << " KB -> no hole large enough\n";
continue;
}
std::cout << request << " KB -> hole " << index + 1
<< ", leaves " << allocator.holes()[index] << " KB\n";
}
}// Next fit: first fit with a pointer that survives between allocations.
import java.util.Arrays;
public class NextFit {
private final int[] holes;
private int pointer = 0;
NextFit(int[] holes) {
this.holes = holes;
}
/** Places one request. Returns the hole index used, or -1 on failure. */
int allocate(int size) {
int count = holes.length;
for (int step = 0; step < count; step++) { // one full lap maximum
int i = (pointer + step) % count; // wrap at the end of the list
if (holes[i] >= size) {
holes[i] -= size;
pointer = i; // resume here on the next request
return i;
}
}
return -1;
}
public static void main(String[] args) {
NextFit allocator = new NextFit(new int[]{100, 500, 200, 300, 600});
for (int request : new int[]{212, 112, 180}) {
int index = allocator.allocate(request);
if (index < 0) {
System.out.println(request + " KB -> no hole large enough");
continue;
}
System.out.println(request + " KB -> hole " + (index + 1)
+ ", leaves " + allocator.holes[index] + " KB");
}
System.out.println("final free list: " + Arrays.toString(allocator.holes));
}
}Step through it
Running on free list [100, 500, 200, 300, 600] KB requests 212, 112, 180 KB
Read all 8 Steps
- the pointer starts at the head of the list Next fit is first fit plus a pointer marking where the last search ended. It starts at hole 1, so the first search is ordinary first fit.
- request 212 KB — hole 1 is too small 100 < 212 — move right. Nothing distinguishes it from first fit yet.
- hole 2 fits — allocate and leave the pointer behind 500 fits: allocate, 288 KB remains. Now the difference — the pointer stays at hole 3 instead of resetting.
- request 112 KB — resume at hole 3, not hole 1 Next request, 112 KB. First fit would restart at the head; next fit resumes at hole 3, which fits at once. One comparison instead of three.
- allocate hole 3, advance the pointer 200 - 112 = 88 KB, pointer moves to hole 4. Two requests, two different regions of the list.
- request 180 KB — resume at hole 4 180 KB fits hole 4 immediately. Four comparisons across three requests; first fit would have made nine.
- what wrapping means At the end of the list the pointer wraps to the start, so no region is permanently skipped.
- the trade: spread allocations, spread damage The cost: damage spreads across the whole list, so the large untouched runs at the far end stop surviving.