Contiguous Memory Allocation and Fragmentation: short notes (Operating Systems)

Revision mode

Introduction

Main memory must hold the kernel and several user processes at once. The simplest scheme gives each process one contiguous block of physical memory. The operating system then has to decide where each new process goes, protect processes from each other, and cope with the gaps that appear as processes come and go.

These gaps are fragmentation. Contiguous allocation suffers from both kinds: internal fragmentation when a process gets more than it asked for, and external fragmentation when enough memory is free in total but no single free block is large enough. External fragmentation is the problem that Paging, Page Tables and TLB removes, and it returns, in a milder form, in Segmentation.

Relocation and limit registers, fixed and variable partitions, the four placement strategies (first, best, worst and next fit), both kinds of fragmentation, compaction and swapping, and the bookkeeping structures for free memory are the standard facts.

Prerequisites

Processes, PCB and Process States: a process image (code, data, heap, stack) and the PCB, where the relocation and limit values are saved on a context switch.

Core concepts

Logical and physical addresses

The CPU generates a logical (virtual) address; the memory unit sees a physical address. The hardware that maps one to the other is the memory-management unit (MMU). Binding can happen at compile time (absolute code), load time (relocatable code fixed when loaded) or execution time. Execution-time binding permits relocation after execution starts, enabling compaction and swap-in at a different physical address. With compile-time/absolute or load-time binding, swapping can still work if the image returns to its original region.

Relocation and limit registers

With contiguous allocation the MMU needs two registers per running process:

the relocation (base) register $R$ : the smallest physical address of the process's block;
the limit register $L$ : the size of the block, so legal logical addresses are $0 \le a < L$ .

For every memory reference with logical address $a$ :

\text{physical}(a) = \begin{cases} R + a & \text{if } a < L,\\ \text{trap to the OS (addressing error)} & \text{otherwise.} \end{cases}

The comparison happens before the addition, on the logical address. Loading $R$ and $L$ is a privileged operation done by the dispatcher on each context switch, so a user process cannot widen its own range.

Limit convention. In these notes the limit register holds the size of the block, so the largest legal logical address is $L - 1$ . Some texts instead compare the physical address against a register holding the upper bound; read the question's definition before deciding whether an address on the boundary traps.

Partitions

Scheme	How memory is divided	Fragmentation	Degree of multiprogramming
Fixed (static) partitions	Sizes chosen at boot; one process per partition	Internal (unused tail of each partition), and external in the sense that a free partition may be too small	At most the number of partitions
Variable (dynamic) partitions	Each process gets exactly the size it asks for, carved from a free hole	External only (the leftover pieces of holes)	Limited only by memory

In variable partitioning the free memory is a set of holes. When a process arrives, the OS picks a hole that is large enough, allocates the front part and returns the rest to the set as a smaller hole. When a process ends, its block becomes a hole and is coalesced with any adjacent hole.

Internal and external fragmentation

Internal fragmentation: memory allocated to a process but not used by it, inside its partition. Fixed partitions and paging (the last page) cause it.
External fragmentation: free memory that exists in total but is split into holes, none big enough for the request. Variable partitions and segmentation cause it.

Allocators often round requests up to a multiple of a small unit (for example 8 bytes) because a hole of a few bytes would cost more to track than it is worth; that rounding is a small internal fragmentation even in a variable scheme.

How placement works

The four strategies

Given the list of holes in address order and a request of size $s$ :

Strategy	Chooses	Search cost	Behaviour
First fit	The first hole with size $\ge s$ , scanning from the lowest address	Stops early	Fast; small holes collect near the start of memory
Next fit	Like first fit, but the scan starts at the hole where the previous search ended and wraps round	Stops early	Spreads allocations; simulations show it slightly worse than first fit
Best fit	The smallest hole with size $\ge s$	Whole list unless sorted by size	Leaves the smallest leftovers, which are often too small to use
Worst fit	The largest hole	Whole list unless sorted by size	Leaves large leftovers but quickly destroys the big holes

Tie and pointer conventions. Ties in best and worst fit go to the lower address. In next fit the pointer stays on the hole that was last used (it may still have space after the allocation); some texts move it one hole further. When a question uses next fit, check which version it means.

None of the four is best for every request sequence. The usual comparison (Silberschatz 9.2) is that first fit and best fit beat worst fit in time and storage use, and first fit is generally faster than best fit.

A worked placement on one hole list

Six holes, in address order: H1 = 300 KB, H2 = 600 KB, H3 = 350 KB, H4 = 200 KB, H5 = 750 KB, H6 = 125 KB (total 2,325 KB). Requests arrive in order: P1 = 115 KB, P2 = 500 KB, P3 = 358 KB, P4 = 200 KB, P5 = 375 KB. Each allocation takes the front of the chosen hole.

Request	First fit	Best fit	Worst fit	Next fit
P1 115	H1 (185 left)	H6 (10 left)	H5 (635 left)	H1 (185 left)
P2 500	H2 (100 left)	H2 (100 left)	H5 (135 left)	H2 (100 left)
P3 358	H5 (392 left)	H5 (392 left)	H2 (242 left)	H5 (392 left)
P4 200	H3 (150 left)	H4 (0 left)	H3 (150 left)	H5 (192 left)
P5 375	H5 (17 left)	H5 (17 left)	fails	fails

First fit and best fit place all five processes.
Worst fit fails P5. The holes left are 300, 242, 150, 200, 135 and 125 KB: 1,152 KB free in total, but the largest hole is 300 KB.
Next fit also fails P5. After P4 the pointer is at H5 (192 KB left); the scan wraps round H6, H1, H2, H3 and H4 and finds nothing of 375 KB. The holes are 185, 100, 350, 200, 192 and 125 KB: again 1,152 KB free, largest hole 350 KB.

Both failures are pure external fragmentation: there is three times the needed memory, in pieces. Next fit differs from first fit at P4 because its scan starts at H5, where P3 was placed, and never looks back at H3.

First, best, worst and next fit on six holes — Figure 1. Holes of 300, 600, 350, 200, 750 and 125 KB receive requests of 115, 500, 358, 200 and 375 KB. First fit and best fit place all five; worst fit and next fit cannot place the 375 KB request although 1,152 KB is free in total, with largest holes of 300 KB and 350 KB.

The same requests with fixed partitions

Treat the six holes as fixed partitions, one process each, first fit. P1 goes to H1, P2 to H2, P3 to H5 and P4 to H3. P5 (375 KB) needs a free partition of at least 375 KB, but only H4 (200 KB) and H6 (125 KB) are free, so it waits. The internal fragmentation is

(300 - 115) + (600 - 500) + (750 - 358) + (350 - 200) = 185 + 100 + 392 + 150 = 827 \text{ KB}.

With best fit over the same partitions, P1 goes to H6 (10 KB wasted), P2 to H2 (100), P3 to H5 (392) and P4 to H4 (0); P5 again waits, because H1 (300 KB) and H3 (350 KB) are too small. The internal fragmentation drops to 502 KB, but the outcome for P5 is the same.

Algorithms and data structures for free memory

Free-space bookkeeping

Linked list of holes (and often of allocated segments), sorted by address so that a freed block can be merged with its neighbours in $O(1)$ once found. Each search for a hole is $O(h)$ for $h$ holes. Keeping a separate list sorted by size speeds best fit but makes coalescing slower, because a freed block's neighbours must also be found in the address order.
Bitmap (Tanenbaum 3.2.3): memory is cut into allocation units and one bit per unit records free or used. The map has a fixed size, but finding a run of $k$ free units means scanning for $k$ consecutive zero bits, which is slow.

Bitmap size. For 256 MB of memory and 4 KB allocation units there are $2^{28} / 2^{12} = 65{,}536$ units, so the bitmap needs 65,536 bits = 8 KB. A smaller unit makes the map larger; a larger unit wastes more memory in the last unit of each process (internal fragmentation of up to one unit minus one byte).

Pseudocode for first fit with coalescing

The hole list H is kept in address order; each hole has fields start and size.

Text

ALLOCATE-FIRST-FIT(H, s):
    for each hole h in H, in address order
        if h.size >= s then
            addr <- h.start
            h.start <- h.start + s
            h.size <- h.size - s
            if h.size = 0 then remove h from H
            return addr
    return FAIL                       -- external fragmentation, or memory full

FREE(H, addr, s):
    insert hole (addr, s) into H in address order
    if the previous hole ends at addr then merge it with the new hole
    if the next hole starts at addr + s then merge it with the new hole

First fit has best $\Theta(1)$ , worst $\Theta(h)$ search time for $h$ holes. Best and worst fit scan all holes in an unsorted list. Hole-list storage is $O(h)$ , with $O(1)$ auxiliary workspace. Freeing has $\Theta(h)$ worst-case position search and constant-time adjacent merging once found. No distribution-independent average is claimed.

Mathematical explanation

The 50-percent rule

Statistical analysis of first fit (Silberschatz 9.2) gives the 50-percent rule: given N allocated blocks, about another 0.5N blocks are lost to fragmentation, so up to one third of memory may be unusable. Knuth's form of the rule counts holes instead: in steady state there is about one hole for every two allocated blocks. The rule explains why external fragmentation is not a corner case: it is the normal state of a busy variable-partition system.

Compaction

Compaction moves all allocated blocks to one end of memory so that the holes merge into one. It is possible only with execution-time binding (the relocation register is simply reloaded) and costs time proportional to the bytes moved. In the worst-fit run above, compaction would produce one hole of 1,152 KB, enough for P5.

Swapping

A process can be swapped out to a backing store and back in later, possibly to a different address if binding is at execution time. The transfer time dominates: with a transfer rate of $r$ bytes per second, swapping a process of size $S$ out and another of size $S'$ in costs $(S + S')/r$ seconds plus latency. For two 100 MB processes at 50 MB/s, that is $200/50 = 4$ seconds of transfer alone, which is why standard whole-process swapping is rare in modern systems and swapping of pages is used instead (Silberschatz 9.5).

Worked examples

Relocation and limit check

A process runs with relocation register $R = 24{,}000$ and limit register $L = 6{,}000$ .

Logical address	Check	Result
0	$0 < 6000$	physical 24,000
4,250	$4250 < 6000$	physical 28,250
5,999	$5999 < 6000$	physical 29,999
6,000	$6000 \not< 6000$	trap
7,100	$7100 \not< 6000$	trap

The physical range of the process is 24,000 to 29,999. A physical address such as 28,250 is never checked against the limit; the logical address 4,250 is.

Which hole after a release?

Continue the first-fit run: P2 (500 KB, at the front of H2) ends. Its block merges with the 100 KB left at the end of H2, giving a 600 KB hole at H2's original place. A new request of 550 KB then goes to that hole under first fit, best fit and next fit alike; under worst fit it would also go there, because it is now the largest hole.

Important properties and observations

Fixed partitions cause internal fragmentation; variable partitions cause external fragmentation. Paging removes external fragmentation and keeps a little internal fragmentation (on average about half a page per process).
A request can fail under external fragmentation even when free memory is several times the request.
Compaction needs dynamic relocation and is expensive; paging and segmentation avoid most of the need for it.
First fit is usually the practical choice: fast and about as good as best fit in memory use.
The relocation and limit registers are part of the process context and are reloaded on every context switch.

Common misconceptions.

"Best fit minimises fragmentation." It minimises the leftover of each allocation, which creates many tiny useless holes.
"Worst fit avoids external fragmentation." It keeps leftovers large for a while, then fails large requests first, as P5 does above.
"The limit is checked on the physical address." In the base and limit scheme here, the logical address is checked against the limit before relocation.

GATE examination perspective

Placement traces. Keep a table of holes after each request; write the leftover beside each hole. Read whether the question means fixed or variable partitions, since that changes whether leftovers can be reused.
Next fit pointer. Ask where the scan resumes (same hole or the next one) and whether it wraps round.
Which request fails first? Run each strategy to the first failure; a question may ask which strategy satisfies all requests.
Internal versus external. Fixed partitions: add the unused tail of each occupied partition. Variable partitions: compare the total free memory with the largest hole.
Boundary addresses. With a size-valued limit, address $L$ itself traps.
Bitmap size. Number of allocation units equals bits; divide by 8 for bytes.

Summary

Contiguous allocation gives each process one block, protected by relocation and limit registers.
Physical address is $R + a$ when $a < L$ ; otherwise the hardware traps.
Fixed partitions waste space inside partitions (internal fragmentation); variable partitions waste it between blocks (external fragmentation).
First fit takes the first adequate hole, next fit resumes from the last one, best fit the smallest adequate, worst fit the largest.
No strategy wins on every input; first fit is fast and usually as good as best fit.
The 50-percent rule under first fit: for N allocated blocks, about 0.5N more are lost to fragmentation (about one hole for every two allocated blocks).
Compaction merges holes but needs execution-time binding; swapping moves whole processes to the backing store.
Free memory is tracked with a sorted hole list (easy coalescing) or a bitmap (fixed size, slow search for long runs).

Sources

A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10th ed., Wiley: Chapter 9 (9.1 Background, 9.2 Contiguous Memory Allocation, 9.5 Swapping).
A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4th ed., Pearson: Chapter 3 (3.2.3 Managing Free Memory).