Which type of fragmentation is most associated with First Fit allocation?

Concept. Fragmentation is memory that physically exists but cannot be put to work. The standard taxonomy has exactly two classes, separated by where the unusable space sits relative to an allocated block. Internal fragmentation is space wasted inside a block that was handed out: the allocator gives out a unit larger than the amount requested, so the surplus is charged to a process that never uses it. External fragmentation is space wasted outside the allocated blocks: the total free memory is sufficient for a request, but it is split into several non-adjacent holes and no single hole is large enough.

Which class an allocation scheme suffers from follows from one property of the scheme: whether it hands out fixed-size units (granularity is rounded up, so waste accumulates inside blocks) or variable-size units cut from one contiguous pool (blocks fit the request, so waste accumulates between blocks).

Application. First Fit is a dynamic contiguous-allocation strategy. It scans the free list from the beginning, stops at the first hole large enough for the request, splits that hole, gives the process exactly what it asked for, and returns the remainder to the free list as a smaller hole. Because the block is cut to size, almost nothing is wasted inside it; the remainders, however, accumulate. Trace one free list:

1. Free holes, in address order: 100 KB, 500 KB, 200 KB, 300 KB, 600 KB — 1700 KB free in total.

2. A 212 KB request arrives. Scanning from the start, the first hole that fits is 500 KB. It is split: 212 KB is allocated, a 288 KB hole remains.

3. A 417 KB request arrives. Scanning from the start again, 100 KB, 288 KB and 200 KB are all too small; the first hole that fits is 600 KB. It is split, leaving a 183 KB hole.

4. A 112 KB request arrives. The first hole that fits is the 288 KB remainder, leaving 176 KB.

5. The free list is now 100 KB, 176 KB, 200 KB, 300 KB, 183 KB — 959 KB still free, yet a single 500 KB request cannot be satisfied, because no one hole holds 500 KB.

That last state is the definition of external fragmentation being met: the memory is there, the contiguity is not. Every allocation splits a hole, and every release returns one — merging with a neighbouring hole when the neighbour happens to be free (coalescing), and otherwise adding a fresh hole to the list — so repeated cycles of differently sized requests drive the free list toward many small scattered holes. Notice that in the three allocations above the process received exactly the number of bytes it asked for, so no space was stranded inside any allocated block.

Cross-check by contrast. Comparing the two classes on the same two axes makes the mapping explicit:

First Fit is a variable-partition allocator cutting blocks from one contiguous pool, so its defining waste is the scattered-hole kind. Internal waste appears under First Fit only as a secondary implementation detail — some implementations refuse to split a hole when the leftover would be smaller than a minimum useful size and hand over the whole hole instead — and it is never the effect the strategy is characterised by. The standard remedies confirm the classification: compaction (sliding allocated blocks together to merge the holes) and paging (dropping the contiguity requirement) both target scattered holes, not surplus inside a block.

Therefore the fragmentation most associated with First Fit allocation is external fragmentation.