Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 66 ยท Memory Management

Contiguous Memory Allocation and Fragmentation

Compare fixed and variable partitions, first-fit, best-fit, worst-fit and next-fit allocation, understand internal and external fragmentation and compaction.

The simplest way to give processes memory is contiguous allocation: each process occupies one continuous block of physical addresses. Combined with a base and limit register, it is easy to implement and fast. The challenge is where to put each process and what to do as the free space gets chopped into pieces.

Fixed partitions

In the oldest scheme, memory is divided at boot into fixed-size partitions (equal or unequal sizes). Each partition holds exactly one process. The degree of multiprogramming equals the number of partitions.

Problem: a process almost never fits its partition exactly. A 70 KB process in a 100 KB partition wastes 30 KB that no other process can use, because the partition is already assigned. Wasted space inside an allocated block is called internal fragmentation.

Python Internal fragmentation with fixed partitions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Variable partitions

To remove internal waste, the OS can create a partition of exactly the size the process needs, taken from a free region called a hole. When a process ends, its block returns to the pool and merges with neighbouring holes. The OS keeps a list of holes and, when a process arrives, must pick one that fits. That is the dynamic storage-allocation problem.

Strategy Rule Notes
First fit Take the first hole that is big enough Fast; tends to chew up the beginning of memory
Next fit Like first fit, but continue from where the last search ended Spreads allocations; often slightly worse than first fit
Best fit Take the smallest hole that is big enough Leaves the tiniest leftover, but scans everything and leaves many useless slivers
Worst fit Take the largest hole Leaves a large leftover that may still be usable; in practice not better

None is the clear winner in every workload. Simulations (and experience) show that first fit and best fit are better than worst fit in both time and utilization, and first fit is usually the fastest.

External fragmentation

With variable partitions, a new problem appears. After many allocations and frees, memory is full of small holes between used blocks. The total free space may be large, yet no single hole is big enough for the next request. That is external fragmentation: waste outside any allocated block.

flowchart LR
    A["OS 0-99"] --- B["P1 100-219"] --- H1["hole 40"] --- C["P3 260-379"] --- H2["hole 30"] --- D["P5 410-499"] --- H3["hole 50"]

120 units are free in total, but a process needing 60 cannot be placed: the largest hole is 50.

Statistical analysis for first fit shows that, for every N allocated blocks, about 0.5 N blocks are lost to fragmentation: roughly one third of memory may be unusable (the "50-percent rule").

The next experiment runs a random workload, many allocations and frees of random sizes in a 1,000-unit memory, with each of the four strategies. It counts requests that failed even though enough total free space existed (the signature of external fragmentation).

Python First, next, best and worst fit on one workload

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every strategy suffers some failures that are caused only by fragmentation. Your exact numbers depend on the workload; change the seed or the size range and the ranking will change, which is the point: no strategy wins everywhere.

Compaction

One cure for external fragmentation is compaction: slide all allocated blocks together so the free holes merge into one large hole. It is only possible if processes can be relocated, which means execution-time binding (change the base register after moving the data). It is also expensive: copying gigabytes of memory takes time during which processes must pause. Many systems therefore avoid it; the better answer is to remove the need for contiguity, which is exactly what paging does.

Python Compaction merges the holes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Other approaches to the same problem include swapping a process out to disk and back in at a different place, and allocating memory in power-of-two blocks (the buddy system), which makes merging holes trivial.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is internal fragmentation?

    When a process gets a block bigger than it needs, the extra space inside is wasted. It cannot be given to anyone else.
  2. 2. Which allocation strategy takes the smallest hole that is large enough?

    Best fit searches all holes for the smallest adequate one.
  3. 3. Total free memory is 200 KB, but a 150 KB request fails. What is this?

    The free space is split into holes smaller than 150 KB, so no single hole fits.
  4. 4. What must be true for compaction to work?

    Compaction moves processes, so their addresses must be bound at run time.
  5. 5. Which strategy is usually the fastest, since it stops at the first fit?

    First fit stops searching as soon as it finds a big enough hole.

Summary

  • Contiguous allocation gives each process one block; fixed partitions waste space inside blocks (internal fragmentation).
  • Variable partitions use holes and a placement policy: first, next, best or worst fit; first and best fit usually beat worst fit.
  • Many small holes cause external fragmentation: enough space in total, but not in one piece.
  • Compaction fixes it at a high copying cost and needs execution-time binding; paging avoids the problem.

Next: The Buddy System and Swapping