First Fit Memory Allocation in OS
Scan from the start, take the first hole large enough, and stop. The cheapest search there is — and measurements say it is also close to the best.
What First Fit in OS Means
First fit in OS is a contiguous memory allocation strategy: scan the free list from the beginning and allocate from the first hole large enough to hold the request. The moment a hole fits, the search stops — no later hole is examined and no comparison between candidates is made.
The allocator then splits that hole. The request takes what it needs and the remainder stays on the free list as a smaller hole.
The defining property is the early exit. Best fit and worst fit must both examine every hole before they can decide; first fit examines, on average, half the list.
- Search cost: O(n) worst case, about n/2 on average
- Leftover: whatever the first adequate hole had spare
- Bias: allocations cluster near the front of the list
First Fit in OS — Worked Example
Take holes of 100, 500, 200, 300 and 600 KB and a 212 KB request.
Hole 1 (100 KB) — 100 < 212, too small, move on. Hole 2 (500 KB) — 500 ≥ 212, it fits. Stop. Holes 3, 4 and 5 are never looked at.
The 500 KB hole is split: 212 KB is allocated and 500 − 212 = 288 KB goes back on the free list. Two comparisons were made in total.
The final free list is 100, 288, 200, 300, 600 KB. Note the shape of that 288 KB remainder — it is still large enough to serve a real request later, which is the quiet advantage first fit holds over best fit.
- Chosen hole: 2 (500 KB)
- Leftover: 288 KB — still usable
- Comparisons: 2 of 5 holes
Why First Fit Beats Its Reputation
Taking the first adequate hole rather than the best one sounds careless. The classic simulations disagree: first fit matches or beats best fit on both memory utilisation and speed.
The reason is the shape of what is left behind. Best fit's tightest hole leaves a sliver — on this list, 300 − 212 = 88 KB, too small for most later requests and effectively dead memory. First fit's 288 KB remains a usable block.
First fit does carry one structural bias. Because every search restarts at the head, small fragments accumulate at the front and later searches must walk over them. That specific cost is what next fit was designed to remove.
- Faster than best fit, and no worse on memory
- Leaves usable remainders instead of slivers
- Fragments the front of the list over time
First fit in OS — the scan stops at the first hole that fits
"""First fit: allocate from the first hole large enough, then stop."""
def first_fit(holes, size):
"""Return the index of the first hole that fits, or -1 if none does."""
for i, hole in enumerate(holes):
if hole >= size:
return i # stop here -- later holes are never examined
return -1
def allocate(holes, size):
"""Place one request, splitting the chosen hole. Returns the index used."""
i = first_fit(holes, size)
if i >= 0:
holes[i] -= size # the remainder stays on the free list
return i
def main():
holes = [100, 500, 200, 300, 600]
request = 212
index = allocate(holes, request)
if index < 0:
print(f"{request} KB -> no hole large enough")
return
print(f"{request} KB -> hole {index + 1}, leaves {holes[index]} KB")
print(f"final free list: {holes}")
if __name__ == "__main__":
main()
// First fit: allocate from the first hole large enough, then stop.
#include <iostream>
#include <vector>
// Returns the index of the first hole that fits, or -1 if none does.
int firstFit(const std::vector<int>& holes, int size) {
for (std::size_t i = 0; i < holes.size(); ++i) {
if (holes[i] >= size) {
return static_cast<int>(i); // later holes are never examined
}
}
return -1;
}
int main() {
std::vector<int> holes {
100, 500, 200, 300, 600
};
const int request = 212;
const int index = firstFit(holes, request);
if (index < 0) {
std::cout << request << " KB -> no hole large enough\n";
return 0;
}
holes[index] -= request; // the remainder stays on the free list
std::cout << request << " KB -> hole " << index + 1
<< ", leaves " << holes[index] << " KB\n";
std::cout << "final free list:";
for (int hole : holes) {
std::cout << ' ' << hole;
}
std::cout << '\n';
}// First fit: allocate from the first hole large enough, then stop.
import java.util.Arrays;
public class FirstFit {
/** Returns the index of the first hole that fits, or -1 if none does. */
static int firstFit(int[] holes, int size) {
for (int i = 0; i < holes.length; i++) {
if (holes[i] >= size) {
return i; // later holes are never examined
}
}
return -1;
}
public static void main(String[] args) {
int[] holes = {100, 500, 200, 300, 600};
int request = 212;
int index = firstFit(holes, request);
if (index < 0) {
System.out.println(request + " KB -> no hole large enough");
return;
}
holes[index] -= request; // the remainder stays on the free list
System.out.println(request + " KB -> hole " + (index + 1)
+ ", leaves " + holes[index] + " KB");
System.out.println("final free list: " + Arrays.toString(holes));
}
}Step through it
Running on free list [100, 500, 200, 300, 600] KB request 212 KB
Read all 6 Steps
- the free list before anything is allocated Five holes, 1700 KB free. A 212 KB request is coming. First fit walks left to right and stops at the first hole that fits.
- hole 1 — 100 KB, too small 100 < 212. Too small — move right. The only question asked is fits or does not fit.
- hole 2 — 500 KB, it fits 500 >= 212, so it fits. First fit takes it and stops here. Best fit would have carried on to compare 300 and 600.
- allocate and split the hole The hole is split: 212 KB allocated, 288 KB left over. That remainder is still large enough to serve a real request later.
- holes 3, 4 and 5 were never examined Two comparisons in total. Holes 3, 4 and 5 were never examined — that early exit is the whole performance argument.
- the cost: fragments collect at the front Every search restarts at the head, so fragments collect at the front and later scans walk over them. Next fit fixes exactly this.