Operating Systems Module 7 – Memory management: addresses, segmentation and paging

Contiguous allocation and fragmentation

Place processes in one run of memory with first, best, worst and next fit, tell internal from external fragmentation, and see what each fit costs.

Beginner
15 minutes
Examples run with Python 3.14.8, Pyodide 314.0.7, Clang 21.0.0 and GCC 16.2.0
By MySmartCoPilot

Free: One run per process, and both kinds of partition waste memory · First, best, worst and next fit choose different holes · Practise: place requests with the four policies. With a pass: 2 in-depth parts and 3 interview answers, about 10 minutes.

What you will learn

Simulate first, best, worst and next fit on a sequence of requests, and predict which request each one refuses
Distinguish internal from external fragmentation, and compute both for a memory map
Compare the four policies by their refusals, the holes they leave and how far they search
Explain how compaction, swapping and overlays made room for a process, and what each one costs

Before you start

Linking, loading and address binding

What you’ll learn · Before you start

What you will learn

Simulate first, best, worst and next fit on a sequence of requests, and predict which request each one refuses
Distinguish internal from external fragmentation, and compute both for a memory map
Compare the four policies by their refusals, the holes they leave and how far they search
Explain how compaction, swapping and overlays made room for a process, and what each one costs

Before you start

Linking, loading and address binding

On this page

In the memory of this lesson, a request for 180 KiB is refused while 390 KiB are free, because no single hole holds 180 KiB. When every process must sit in one unbroken run of memory, free space breaks into pieces too small to use, and the hole chosen for each request decides how soon that happens.

You will place five requests with first, best, worst and next fit, tell the two kinds of fragmentation apart, and compute how much memory each one wastes.

One run per process, and both kinds of partition waste memory

In contiguous allocation: Giving each process one unbroken run of physical memory, described by a single base address and a single limit. each process gets one run of physical memory, which the base and limit registers of the previous lesson map. Early systems split memory in two ways, drawn here for a 1,024 KiB machine running A, B and C:

Fixed partitions waste space inside each block; variable partitions leave holes between blocks

Text description of the diagram

The figure has two columns, each one 1,024 KiB memory holding processes A (100 KiB), B (250 KiB) and C (180 KiB).

The left column uses four fixed partitions of 256 KiB each. 1. Partition 1 holds A and leaves 156 KiB unused inside it. 2. Partition 2 holds B and leaves 6 KiB unused inside it. 3. Partition 3 holds C and leaves 76 KiB unused inside it. 4. Partition 4 is empty, 256 KiB. Together 238 KiB are allocated but unused, and a process of 300 KiB could never run, because no partition is that large.

The right column uses variable partitions, each exactly as large as its process, after B has exited. 1. A occupies 0 to 100 KiB. 2. A hole of 250 KiB lies from 100 to 350 KiB, where B was. 3. C occupies 350 to 530 KiB. 4. A hole of 494 KiB lies from 530 to 1,024 KiB. Together 744 KiB are free, but a process of 600 KiB is refused, because neither hole is large enough.

With fixed partitions of 256 KiB, every process gets a whole partition, however small it is. A leaves 156 KiB unused inside its partition, B 6 and C 76: 238 KiB that nobody else can use. Waste inside an allocated block is internal fragmentation: Memory inside an allocated block that its owner does not use, because the block was rounded up to a fixed size such as a partition., and a 300 KiB process cannot run at all.

Variable partitions give each process exactly what it asks for, so the waste moves between the blocks. When B exits it leaves a hole: A run of free memory between allocated blocks. An allocator that places blocks in one piece each keeps a list of its holes. of 250 KiB, and with the 494 KiB at the top, 744 KiB are free. A process of 600 KiB is still refused, because neither hole is large enough. Free memory broken into pieces that are each too small is Free memory broken into holes between allocated blocks, each too small for a request although together they would be large enough..

Adding up the holes

A request fits when one hole is large enough, not when the holes add up to enough: 744 KiB free in two holes does not admit 600 KiB.

First, best, worst and next fit choose different holes

A variable-partition allocator keeps a list of holes, and its placement policy: The rule an allocator uses to choose a hole for each request, such as first fit, best fit, worst fit or next fit. picks one for each request:

First fit takes the first hole in address order that is large enough, and stops looking there.
Best fit takes the smallest hole that is large enough, so its remainder is as small as possible.
Worst fit takes the largest hole, so its remainder stays large, but the big holes go first.
Next fit searches like first fit but starts where the previous request was placed.

Take a 2,048 KiB memory with four holes, at 200 to 400, 500 to 700, 1000 to 1350 and 1650 to 1800 KiB, and five requests that arrive in this order: P1 needs 150 KiB, P2 290, P3 70, P4 180 and P5 130. Step through first fit on them, then compare all four policies, in 14 languages:

Interactive · step by step First fit placing five requests in four holes Step through the requests. Watch which hole each one goes to, and how the holes shrink.

The drawing shows the whole scene; its 7 steps are listed below.

Every step as text

Four holes. The memory has four holes with 900 KiB free in all, and the largest holds 350 KiB. First fit gives each request the lowest hole that is large enough.
P1 needs 150. The first hole holds 200 KiB, enough for P1, so P1 goes to 200. The hole keeps the 50 KiB above it.
P2 needs 290. The first hole has 50 KiB and the second 200, both too small. The third holds 350, so P2 goes to 1000 and leaves 60 KiB.
P3 needs 70. The first hole is still too small, but the second has 200 KiB. P3 goes to 500, and 130 KiB stay free there.
P4 is refused. The holes now hold 50, 130, 60 and 150 KiB, 390 KiB in all, but none of them 180. First fit refuses P4 although more than twice its size is free.
P5 needs 130. The first hole has 50 KiB, too few, and the second exactly 130. P5 goes to 570 and fills that hole completely.
What is left. Three holes are left, with 50, 60 and 150 KiB, 260 KiB free in all. P4 still could not be placed in any of them.

One program · 14 languages Four placement policies on the same five requests one pass over the holes for each request

Python 3.14 · main.py

HOLES = [(200, 200), (500, 200), (1000, 350), (1650, 150)]  # (start, size) in KiB
REQUESTS = [150, 290, 70, 180, 130]  # P1 to P5


def pick(holes: list[list[int]], size: int, policy: str, last: int) -> int | None:
    chosen = None
    for k in range(len(holes)):
        i = (last + k) % len(holes) if policy == "next" else k
        room = holes[i][1]
        if room < size:
            continue
        if policy in ("first", "next"):
            return i
        # Ties keep the lower address.
        if (
            chosen is None
            or (policy == "best" and room < holes[chosen][1])
            or (policy == "worst" and room > holes[chosen][1])
        ):
            chosen = i
    return chosen


def summary(holes: list[list[int]]) -> str:
    sizes = [size for _, size in holes if size > 0]
    return f"{len(sizes)} holes, {sum(sizes)} free, largest {max(sizes)}"


for policy in ["first", "best", "worst", "next"]:
    holes = [[start, size] for start, size in HOLES]
    last = 0
    placed = []
    for n, size in enumerate(REQUESTS, start=1):
        i = pick(holes, size, policy, last)
        if i is None:
            placed.append(f"P{n} fails ({summary(holes)})")
            continue
        placed.append(f"P{n} at {holes[i][0]}")
        holes[i][0] += size
        holes[i][1] -= size
        last = i
    print(f"{policy} fit: {', '.join(placed)}")
    print(f"  left: {summary(holes)}")

In Python: pick returns None when no hole fits, and the caller tests for it with is None. Each policy starts from a fresh list of holes, because placing a request changes it.

Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py

JavaScript Node 24 · main.mjs

const HOLES = [
  [200, 200],
  [500, 200],
  [1000, 350],
  [1650, 150],
]; // [start, size] in KiB
const REQUESTS = [150, 290, 70, 180, 130]; // P1 to P5

function pick(holes, size, policy, last) {
  let chosen = null;
  for (let k = 0; k < holes.length; k++) {
    const i = policy === "next" ? (last + k) % holes.length : k;
    const room = holes[i].size;
    if (room < size) continue;
    if (policy === "first" || policy === "next") return i;
    // Ties keep the lower address.
    if (
      chosen === null ||
      (policy === "best" && room < holes[chosen].size) ||
      (policy === "worst" && room > holes[chosen].size)
    ) {
      chosen = i;
    }
  }
  return chosen;
}

function summary(holes) {
  const sizes = holes.map((hole) => hole.size).filter((size) => size > 0);
  const free = sizes.reduce((a, b) => a + b, 0);
  return `${sizes.length} holes, ${free} free, largest ${Math.max(...sizes)}`;
}

for (const policy of ["first", "best", "worst", "next"]) {
  const holes = HOLES.map(([start, size]) => ({ start, size }));
  let last = 0;
  const placed = REQUESTS.map((size, index) => {
    const i = pick(holes, size, policy, last);
    if (i === null) return `P${index + 1} fails (${summary(holes)})`;
    const start = holes[i].start;
    holes[i].start += size;
    holes[i].size -= size;
    last = i;
    return `P${index + 1} at ${start}`;
  });
  console.log(`${policy} fit: ${placed.join(", ")}`);
  console.log(`  left: ${summary(holes)}`);
}

In JavaScript: Each policy works on its own objects with start and size, and REQUESTS.map builds the line of placements while it changes them.

Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs

Java 25 LTS · Main.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
  static final int[][] HOLES = {{200, 200}, {500, 200}, {1000, 350}, {1650, 150}}; // start, size
  static final int[] REQUESTS = {150, 290, 70, 180, 130}; // P1 to P5

  static int pick(int[][] holes, int size, String policy, int last) {
    int chosen = -1;
    for (int k = 0; k < holes.length; k++) {
      int i = policy.equals("next") ? (last + k) % holes.length : k;
      int room = holes[i][1];
      if (room < size) {
        continue;
      }
      if (policy.equals("first") || policy.equals("next")) {
        return i;
      }
      // Ties keep the lower address.
      if (chosen == -1
          || (policy.equals("best") && room < holes[chosen][1])
          || (policy.equals("worst") && room > holes[chosen][1])) {
        chosen = i;
      }
    }
    return chosen;
  }

  static String summary(int[][] holes) {
    int[] sizes = Arrays.stream(holes).mapToInt(hole -> hole[1]).filter(s -> s > 0).toArray();
    int largest = Arrays.stream(sizes).max().orElse(0);
    return sizes.length + " holes, " + Arrays.stream(sizes).sum() + " free, largest " + largest;
  }

  public static void main(String[] args) {
    for (String policy : List.of("first", "best", "worst", "next")) {
      int[][] holes = Arrays.stream(HOLES).map(int[]::clone).toArray(int[][]::new);
      int last = 0;
      List<String> placed = new ArrayList<>();
      for (int n = 1; n <= REQUESTS.length; n++) {
        int size = REQUESTS[n - 1];
        int i = pick(holes, size, policy, last);
        if (i == -1) {
          placed.add("P" + n + " fails (" + summary(holes) + ")");
          continue;
        }
        placed.add("P" + n + " at " + holes[i][0]);
        holes[i][0] += size;
        holes[i][1] -= size;
        last = i;
      }
      System.out.println(policy + " fit: " + String.join(", ", placed));
      System.out.println("  left: " + summary(holes));
    }
  }
}

In Java: The holes are int arrays of start and size. map(int[]::clone) copies every one of them, since cloning the outer array alone would share them. pick returns -1 for no hole, as indexOf does.

Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java

C++23 · main.cpp

#include <algorithm>
#include <array>
#include <optional>
#include <print>
#include <string_view>
#include <vector>

struct Hole {
  int start;
  int size;
};

constexpr std::array<Hole, 4> HOLES{
    {{200, 200}, {500, 200}, {1000, 350}, {1650, 150}}};       // KiB
constexpr std::array<int, 5> REQUESTS{150, 290, 70, 180, 130}; // P1 to P5

std::optional<std::size_t> pick(const std::vector<Hole> &holes, int size,
                                std::string_view policy, std::size_t last) {
  std::optional<std::size_t> chosen;
  for (std::size_t k = 0; k < holes.size(); k++) {
    const std::size_t i = policy == "next" ? (last + k) % holes.size() : k;
    const int room = holes[i].size;
    if (room < size) {
      continue;
    }
    if (policy == "first" || policy == "next") {
      return i;
    }
    // Ties keep the lower address.
    if (!chosen || (policy == "best" && room < holes[*chosen].size) ||
        (policy == "worst" && room > holes[*chosen].size)) {
      chosen = i;
    }
  }
  return chosen;
}

void print_summary(const std::vector<Hole> &holes) {
  int count = 0;
  int total = 0;
  int largest = 0;
  for (const auto &hole : holes) {
    count += hole.size > 0 ? 1 : 0;
    total += hole.size;
    largest = std::max(largest, hole.size);
  }
  std::print("{} holes, {} free, largest {}", count, total, largest);
}

int main() {
  for (const std::string_view policy : {"first", "best", "worst", "next"}) {
    std::vector<Hole> holes(HOLES.begin(), HOLES.end());
    std::size_t last = 0;
    std::print("{} fit:", policy);
    for (std::size_t n = 1; n <= REQUESTS.size(); n++) {
      const int size = REQUESTS[n - 1];
      std::print("{} P{} ", n > 1 ? "," : "", n);
      const auto i = pick(holes, size, policy, last);
      if (!i) {
        std::print("fails (");
        print_summary(holes);
        std::print(")");
        continue;
      }
      std::print("at {}", holes[*i].start);
      holes[*i].start += size;
      holes[*i].size -= size;
      last = *i;
    }
    std::print("\n  left: ");
    print_summary(holes);
    std::print("\n");
  }
}

In C++: pick returns std::optional<std::size_t>, empty when no hole is large enough, and *i reads the index inside it.

Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main

C# 14 · .NET 10 · app.cs

using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

(int Start, int Size)[] holesAtStart = [(200, 200), (500, 200), (1000, 350), (1650, 150)]; // KiB
int[] requests = [150, 290, 70, 180, 130]; // P1 to P5

foreach (string policy in new[] { "first", "best", "worst", "next" })
{
    var holes = ((int Start, int Size)[])holesAtStart.Clone();
    int last = 0;
    var placed = new List<string>();
    for (int n = 1; n <= requests.Length; n++)
    {
        int size = requests[n - 1];
        if (Pick(holes, size, policy, last) is not int i)
        {
            placed.Add($"P{n} fails ({Summary(holes)})");
            continue;
        }
        placed.Add($"P{n} at {holes[i].Start}");
        holes[i].Start += size;
        holes[i].Size -= size;
        last = i;
    }
    Console.WriteLine($"{policy} fit: {string.Join(", ", placed)}");
    Console.WriteLine($"  left: {Summary(holes)}");
}

static int? Pick((int Start, int Size)[] holes, int size, string policy, int last)
{
    int? chosen = null;
    for (int k = 0; k < holes.Length; k++)
    {
        int i = policy == "next" ? (last + k) % holes.Length : k;
        int room = holes[i].Size;
        if (room < size)
        {
            continue;
        }
        if (policy is "first" or "next")
        {
            return i;
        }
        // Ties keep the lower address.
        if (chosen is not int c
            || (policy == "best" && room < holes[c].Size)
            || (policy == "worst" && room > holes[c].Size))
        {
            chosen = i;
        }
    }
    return chosen;
}

static string Summary((int Start, int Size)[] holes)
{
    int[] sizes = holes.Select(h => h.Size).Where(s => s > 0).ToArray();
    return $"{sizes.Length} holes, {sizes.Sum()} free, largest {sizes.Max()}";
}

In C#: pick returns int?, and the pattern is not int i both detects a refused request and names the index. Clone copies an array of value-type tuples, so each policy has its own holes.

Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs

C23 · main.c

#include <stdio.h>
#include <string.h>

typedef struct {
  int start;
  int size;
} Hole;

enum { HOLES = 4, REQUESTS = 5 };

static const Hole START[HOLES] = {
    {200, 200}, {500, 200}, {1000, 350}, {1650, 150}};       // KiB
static const int SIZES[REQUESTS] = {150, 290, 70, 180, 130}; // P1 to P5

static int pick(const Hole holes[], int size, const char *policy, int last) {
  const bool next = strcmp(policy, "next") == 0;
  const bool best = strcmp(policy, "best") == 0;
  int chosen = -1;
  for (int k = 0; k < HOLES; k++) {
    const int i = next ? (last + k) % HOLES : k;
    const int room = holes[i].size;
    if (room < size) {
      continue;
    }
    if (next || strcmp(policy, "first") == 0) {
      return i;
    }
    // Ties keep the lower address.
    if (chosen == -1 ||
        (best ? room < holes[chosen].size : room > holes[chosen].size)) {
      chosen = i;
    }
  }
  return chosen;
}

static void summary(const Hole holes[]) {
  int count = 0;
  int total = 0;
  int largest = 0;
  for (int i = 0; i < HOLES; i++) {
    count += holes[i].size > 0;
    total += holes[i].size;
    largest = holes[i].size > largest ? holes[i].size : largest;
  }
  printf("%d holes, %d free, largest %d", count, total, largest);
}

int main(void) {
  static const char *const POLICIES[] = {"first", "best", "worst", "next"};
  for (int p = 0; p < 4; p++) {
    Hole holes[HOLES];
    memcpy(holes, START, sizeof holes);
    int last = 0;
    printf("%s fit:", POLICIES[p]);
    for (int n = 1; n <= REQUESTS; n++) {
      const int i = pick(holes, SIZES[n - 1], POLICIES[p], last);
      printf("%s P%d ", n > 1 ? "," : "", n);
      if (i == -1) {
        printf("fails (");
        summary(holes);
        printf(")");
        continue;
      }
      printf("at %d", holes[i].start);
      holes[i].start += SIZES[n - 1];
      holes[i].size -= SIZES[n - 1];
      last = i;
    }
    printf("\n  left: ");
    summary(holes);
    printf("\n");
  }
  return 0;
}

In C: pick returns -1 when no hole fits, and memcpy gives each policy a fresh copy of the starting holes. summary prints its counts directly instead of returning text.

Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main

PHP 8.5 · main.php

<?php

declare(strict_types=1);

const HOLES = [[200, 200], [500, 200], [1000, 350], [1650, 150]]; // start, size in KiB
const REQUESTS = [150, 290, 70, 180, 130]; // P1 to P5

/**
 * @param list<array{int, int}> $holes
 */
function pick(array $holes, int $size, string $policy, int $last): ?int
{
    $chosen = null;
    $count = count($holes);
    for ($k = 0; $k < $count; $k++) {
        $i = $policy === 'next' ? ($last + $k) % $count : $k;
        $room = $holes[$i][1];
        if ($room < $size) {
            continue;
        }
        if ($policy === 'first' || $policy === 'next') {
            return $i;
        }
        // Ties keep the lower address.
        if ($chosen === null
            || ($policy === 'best' && $room < $holes[$chosen][1])
            || ($policy === 'worst' && $room > $holes[$chosen][1])) {
            $chosen = $i;
        }
    }
    return $chosen;
}

/** @param list<array{int, int}> $holes */
function summary(array $holes): string
{
    $sizes = array_filter(array_column($holes, 1), fn(int $size): bool => $size > 0);
    return count($sizes) . ' holes, ' . array_sum($sizes) . ' free, largest ' . max($sizes);
}

foreach (['first', 'best', 'worst', 'next'] as $policy) {
    $holes = HOLES;
    $last = 0;
    $placed = [];
    foreach (REQUESTS as $index => $size) {
        $n = $index + 1;
        $i = pick($holes, $size, $policy, $last);
        if ($i === null) {
            $placed[] = "P{$n} fails (" . summary($holes) . ')';
            continue;
        }
        $placed[] = "P{$n} at {$holes[$i][0]}";
        $holes[$i][0] += $size;
        $holes[$i][1] -= $size;
        $last = $i;
    }
    echo "{$policy} fit: " . implode(', ', $placed) . "\n";
    echo '  left: ' . summary($holes) . "\n";
}

In PHP: Arrays are copied when assigned, so $holes = HOLES gives each policy a fresh map, and pick returns ?int, null when no hole fits.

Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. It runs in your browser with php-wasm 0.2.0 (PHP 8.5.2). To run it yourself: php main.php

Rust 1.99 · main.rs

// Each hole is (start, size) in KiB.
const HOLES: [(u32, u32); 4] = [(200, 200), (500, 200), (1000, 350), (1650, 150)];
const REQUESTS: [u32; 5] = [150, 290, 70, 180, 130]; // P1 to P5

fn pick(holes: &[(u32, u32)], size: u32, policy: &str, last: usize) -> Option<usize> {
    let mut chosen: Option<usize> = None;
    for k in 0..holes.len() {
        let i = if policy == "next" {
            (last + k) % holes.len()
        } else {
            k
        };
        let room = holes[i].1;
        if room < size {
            continue;
        }
        if policy == "first" || policy == "next" {
            return Some(i);
        }
        // Ties keep the lower address.
        let better = chosen.is_none_or(|c| {
            (policy == "best" && room < holes[c].1) || (policy == "worst" && room > holes[c].1)
        });
        if better {
            chosen = Some(i);
        }
    }
    chosen
}

fn summary(holes: &[(u32, u32)]) -> String {
    let sizes: Vec<u32> = holes
        .iter()
        .map(|&(_, size)| size)
        .filter(|&s| s > 0)
        .collect();
    let largest = sizes.iter().max().unwrap_or(&0);
    let free: u32 = sizes.iter().sum();
    format!("{} holes, {free} free, largest {largest}", sizes.len())
}

fn main() {
    for policy in ["first", "best", "worst", "next"] {
        let mut holes = HOLES.to_vec();
        let mut last = 0;
        let mut placed = Vec::new();
        for (n, size) in (1..).zip(REQUESTS) {
            let Some(i) = pick(&holes, size, policy, last) else {
                placed.push(format!("P{n} fails ({})", summary(&holes)));
                continue;
            };
            placed.push(format!("P{n} at {}", holes[i].0));
            holes[i].0 += size;
            holes[i].1 -= size;
            last = i;
        }
        println!("{policy} fit: {}", placed.join(", "));
        println!("  left: {}", summary(&holes));
    }
}

In Rust: Each hole is a (start, size) tuple, so HOLES.to_vec() copies the map, and let Some(i) = ... else names the index or skips the request.

Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main

TypeScript 6.0 · main.ts

type Policy = "first" | "best" | "worst" | "next";
type Hole = { start: number; size: number };

const HOLES: readonly (readonly [number, number])[] = [
  [200, 200],
  [500, 200],
  [1000, 350],
  [1650, 150],
]; // [start, size] in KiB
const REQUESTS: readonly number[] = [150, 290, 70, 180, 130]; // P1 to P5

function pick(holes: Hole[], size: number, policy: Policy, last: number): number | null {
  let chosen: number | null = null;
  for (let k = 0; k < holes.length; k++) {
    const i = policy === "next" ? (last + k) % holes.length : k;
    const room = holes[i].size;
    if (room < size) continue;
    if (policy === "first" || policy === "next") return i;
    // Ties keep the lower address.
    if (
      chosen === null ||
      (policy === "best" && room < holes[chosen].size) ||
      (policy === "worst" && room > holes[chosen].size)
    ) {
      chosen = i;
    }
  }
  return chosen;
}

function summary(holes: Hole[]): string {
  const sizes = holes.map((hole) => hole.size).filter((size) => size > 0);
  const free = sizes.reduce((a, b) => a + b, 0);
  return `${sizes.length} holes, ${free} free, largest ${Math.max(...sizes)}`;
}

const policies: Policy[] = ["first", "best", "worst", "next"];
for (const policy of policies) {
  const holes: Hole[] = HOLES.map(([start, size]) => ({ start, size }));
  let last = 0;
  const placed = REQUESTS.map((size, index) => {
    const i = pick(holes, size, policy, last);
    if (i === null) return `P${index + 1} fails (${summary(holes)})`;
    const start = holes[i].start;
    holes[i].start += size;
    holes[i].size -= size;
    last = i;
    return `P${index + 1} at ${start}`;
  });
  console.log(`${policy} fit: ${placed.join(", ")}`);
  console.log(`  left: ${summary(holes)}`);
}

In TypeScript: Policy is a union of four string literals, so a misspelt policy name is a compile-time error rather than a run that places nothing.

Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts

Go 1.27 · main.go

package main

import (
	"fmt"
	"strings"
)

type hole struct{ start, size int }

var holesAtStart = []hole{{200, 200}, {500, 200}, {1000, 350}, {1650, 150}} // KiB
var requests = []int{150, 290, 70, 180, 130}                                // P1 to P5

func pick(holes []hole, size int, policy string, last int) (int, bool) {
	chosen := -1
	for k := range holes {
		i := k
		if policy == "next" {
			i = (last + k) % len(holes)
		}
		room := holes[i].size
		if room < size {
			continue
		}
		if policy == "first" || policy == "next" {
			return i, true
		}
		// Ties keep the lower address.
		if chosen == -1 || (policy == "best" && room < holes[chosen].size) ||
			(policy == "worst" && room > holes[chosen].size) {
			chosen = i
		}
	}
	return chosen, chosen != -1
}

func summary(holes []hole) string {
	count, total, largest := 0, 0, 0
	for _, h := range holes {
		if h.size > 0 {
			count++
		}
		total += h.size
		largest = max(largest, h.size)
	}
	return fmt.Sprintf("%d holes, %d free, largest %d", count, total, largest)
}

func main() {
	for _, policy := range []string{"first", "best", "worst", "next"} {
		holes := append([]hole(nil), holesAtStart...)
		last := 0
		var placed []string
		for n, size := range requests {
			i, ok := pick(holes, size, policy, last)
			if !ok {
				placed = append(placed, fmt.Sprintf("P%d fails (%s)", n+1, summary(holes)))
				continue
			}
			placed = append(placed, fmt.Sprintf("P%d at %d", n+1, holes[i].start))
			holes[i].start += size
			holes[i].size -= size
			last = i
		}
		fmt.Printf("%s fit: %s\n", policy, strings.Join(placed, ", "))
		fmt.Printf("  left: %s\n", summary(holes))
	}
}

In Go: pick returns the index and a bool, Go's way of saying that no hole fits, and append([]hole(nil), holesAtStart...) copies the starting map.

Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go

Swift 6.4 · main.swift

// Sizes and addresses in KiB.
let holesAtStart: [(start: Int, size: Int)] = [(200, 200), (500, 200), (1000, 350), (1650, 150)]
let requests = [150, 290, 70, 180, 130]  // P1 to P5

func pick(_ holes: [(start: Int, size: Int)], size: Int, policy: String, last: Int) -> Int? {
  var chosen: Int?
  for k in holes.indices {
    let i = policy == "next" ? (last + k) % holes.count : k
    let room = holes[i].size
    guard room >= size else { continue }
    if policy == "first" || policy == "next" {
      return i
    }
    // Ties keep the lower address.
    if let current = chosen {
      let held = holes[current].size
      if policy == "best" && room < held || policy == "worst" && room > held {
        chosen = i
      }
    } else {
      chosen = i
    }
  }
  return chosen
}

func summary(_ holes: [(start: Int, size: Int)]) -> String {
  let sizes = holes.map(\.size).filter { $0 > 0 }
  return "\(sizes.count) holes, \(sizes.reduce(0, +)) free, largest \(sizes.max() ?? 0)"
}

for policy in ["first", "best", "worst", "next"] {
  var holes = holesAtStart
  var last = 0
  var placed: [String] = []
  for (index, size) in requests.enumerated() {
    guard let i = pick(holes, size: size, policy: policy, last: last) else {
      placed.append("P\(index + 1) fails (\(summary(holes)))")
      continue
    }
    placed.append("P\(index + 1) at \(holes[i].start)")
    holes[i].start += size
    holes[i].size -= size
    last = i
  }
  print("\(policy) fit: \(placed.joined(separator: ", "))")
  print("  left: \(summary(holes))")
}

In Swift: The holes are labelled tuples, which are values, so var holes = holesAtStart copies them, and guard let skips a refused request.

Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main

Ruby 4.0 · main.rb

# frozen_string_literal: true

Hole = Struct.new(:start, :space)

HOLES = [[200, 200], [500, 200], [1000, 350], [1650, 150]].freeze # start, size in KiB
REQUESTS = [150, 290, 70, 180, 130].freeze # P1 to P5

def scan_order(holes, policy, last)
  holes.each_index.map { |k| policy == 'next' ? (last + k) % holes.size : k }
end

def better?(policy, room, held)
  policy == 'best' ? room < held : room > held
end

def pick(holes, size, policy, last)
  fitting = scan_order(holes, policy, last).lazy.select { |i| holes[i].space >= size }
  return fitting.first if %w[first next].include?(policy)

  # Ties keep the lower address.
  fitting.reduce { |chosen, i| better?(policy, holes[i].space, holes[chosen].space) ? i : chosen }
end

def summary(holes)
  sizes = holes.map(&:space).select(&:positive?)
  "#{sizes.size} holes, #{sizes.sum} free, largest #{sizes.max}"
end

def place(holes, policy)
  last = 0
  REQUESTS.each_with_index.map do |size, index|
    i = pick(holes, size, policy, last)
    next "P#{index + 1} fails (#{summary(holes)})" if i.nil?

    start = holes[i].start
    holes[i].start += size
    holes[i].space -= size
    last = i
    "P#{index + 1} at #{start}"
  end
end

%w[first best worst next].each do |policy|
  holes = HOLES.map { |start, size| Hole.new(start, size) }
  puts "#{policy} fit: #{place(holes, policy).join(', ')}"
  puts "  left: #{summary(holes)}"
end

In Ruby: pick selects the holes that fit in scanning order and reduce keeps the better of each pair, so a tie stays with the lower address. The member is space, since a Struct already has a size method.

Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb

Kotlin 2.4 · Main.kt

data class Hole(
    var start: Int,
    var size: Int,
)

val holesAtStart = listOf(200 to 200, 500 to 200, 1000 to 350, 1650 to 150) // start, size in KiB
val requests = intArrayOf(150, 290, 70, 180, 130) // P1 to P5

fun pick(
    holes: List<Hole>,
    size: Int,
    policy: String,
    last: Int,
): Int? {
    var chosen: Int? = null
    for (k in holes.indices) {
        val i = if (policy == "next") (last + k) % holes.size else k
        val room = holes[i].size
        if (room < size) continue
        if (policy == "first" || policy == "next") return i
        // Ties keep the lower address.
        val current = chosen
        if (current == null ||
            (policy == "best" && room < holes[current].size) ||
            (policy == "worst" && room > holes[current].size)
        ) {
            chosen = i
        }
    }
    return chosen
}

fun summary(holes: List<Hole>): String {
    val sizes = holes.map { it.size }.filter { it > 0 }
    return "${sizes.size} holes, ${sizes.sum()} free, largest ${sizes.max()}"
}

fun main() {
    for (policy in listOf("first", "best", "worst", "next")) {
        val holes = holesAtStart.map { (start, size) -> Hole(start, size) }
        var last = 0
        val placed = mutableListOf<String>()
        for ((index, size) in requests.withIndex()) {
            val i = pick(holes, size, policy, last)
            if (i == null) {
                placed += "P${index + 1} fails (${summary(holes)})"
                continue
            }
            placed += "P${index + 1} at ${holes[i].start}"
            holes[i].start += size
            holes[i].size -= size
            last = i
        }
        println("$policy fit: ${placed.joinToString(", ")}")
        println("  left: ${summary(holes)}")
    }
}

In Kotlin: Hole is a data class with var fields, because placing a request changes it, and pick returns Int?, null when no hole fits.

Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar

Dart 3.13 · main.dart

const holesAtStart = [
  (200, 200),
  (500, 200),
  (1000, 350),
  (1650, 150),
]; // (start, size) in KiB
const requests = [150, 290, 70, 180, 130]; // P1 to P5

int? pick(List<List<int>> holes, int size, String policy, int last) {
  int? chosen;
  for (var k = 0; k < holes.length; k++) {
    final i = policy == 'next' ? (last + k) % holes.length : k;
    final room = holes[i][1];
    if (room < size) continue;
    if (policy == 'first' || policy == 'next') return i;
    // Ties keep the lower address.
    final current = chosen;
    if (current == null ||
        policy == 'best' && room < holes[current][1] ||
        policy == 'worst' && room > holes[current][1]) {
      chosen = i;
    }
  }
  return chosen;
}

String summary(List<List<int>> holes) {
  final sizes = [
    for (final [_, size] in holes)
      if (size > 0) size,
  ];
  final largest = sizes.reduce((a, b) => a > b ? a : b);
  return '${sizes.length} holes, ${sizes.reduce((a, b) => a + b)} free, largest $largest';
}

void main() {
  for (final policy in ['first', 'best', 'worst', 'next']) {
    final holes = [
      for (final (start, size) in holesAtStart) [start, size],
    ];
    var last = 0;
    final placed = <String>[];
    for (final (index, size) in requests.indexed) {
      final i = pick(holes, size, policy, last);
      if (i == null) {
        placed.add('P${index + 1} fails (${summary(holes)})');
        continue;
      }
      placed.add('P${index + 1} at ${holes[i][0]}');
      holes[i][0] += size;
      holes[i][1] -= size;
      last = i;
    }
    print('$policy fit: ${placed.join(', ')}');
    print('  left: ${summary(holes)}');
  }
}

In Dart: The holes are lists of start and size, since a Dart record cannot change, and the list pattern [_, size] reads a hole's size in summary.

Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart

What every language printed

first fit: P1 at 200, P2 at 1000, P3 at 500, P4 fails (4 holes, 390 free, largest 150), P5 at 570
  left: 3 holes, 260 free, largest 150
best fit: P1 at 1650, P2 at 1000, P3 at 200, P4 at 500, P5 at 270
  left: 2 holes, 80 free, largest 60
worst fit: P1 at 1000, P2 fails (4 holes, 750 free, largest 200), P3 at 200, P4 at 500, P5 at 1150
  left: 4 holes, 370 free, largest 150
next fit: P1 at 200, P2 at 1000, P3 at 1650, P4 at 500, P5 fails (4 holes, 210 free, largest 80)
  left: 4 holes, 210 free, largest 80

Each policy that fails does so with memory to spare: first fit refuses P4 with 390 KiB free, worst fit refuses P2 with 750 KiB free, and next fit refuses P5 with 210 KiB free. Best fit placed all five, but left two holes of 20 and 60 KiB. Another order of requests ranks them differently, so one example decides nothing.

A system that finds no hole large enough has three classic ways to make room, each at a price:

Compaction slides the blocks in use together, so that all the free memory becomes one hole.
Swapping writes a whole process out to disk, which frees its block for other processes.
Overlays let one program reuse its own memory for parts of it that never run at the same time.

Key idea

A contiguous allocator fails when no single hole is large enough, however much memory is free in total.

Checkpoint

Check: Internal and external fragmentation · First, best, worst and next fit

Question 1 of 2 Fixed partitions of 256 KiB hold processes of 100, 250 and 180 KiB, one in each. How many KiB are allocated but unused inside the three partitions?
Type a number.
Your answer KiB

A hint

Subtract each process from its partition.

Show the answer: Question 1 of 2

Answer: 238 KiB

156 + 6 + 76 = 238 KiB. That waste is inside allocated blocks, so it is internal fragmentation, and no other process can use it.
Question 2 of 2 After P1 and P2, best fit has holes of 200 KiB at 200, 200 KiB at 500 and 60 KiB at 1290. Where does it place P3, which needs 70 KiB?
Choose one answer.

At 200 At 1290 It is refused At 500

Show the answer: Question 2 of 2

Answer: At 200

Best fit looks at every hole that is large enough and takes the smallest. Here two tie, and the block's output shows P3 at 200.

Practise: place requests with the four policies

Write the four policies as one function. Its sample tests use the five requests above.

Exercise · Medium · Python

Place requests with first, best, worst and next fit

Write allocate(holes, requests, policy) in fits.py. holes is a list of (start, size) pairs in address order, requests a list of sizes, and policy one of "first", "best", "worst" and "next". Return a list with one entry per request: the address where it was placed, or None when no hole was large enough.

A placed request takes the low end of its hole, and the hole keeps what is left.
Best and worst fit look at every hole that is large enough; on a tie the lower address wins.
Next fit starts its search at the hole where the previous request was placed and wraps around to the start.
Do not change the list that was passed in.

With the lesson's holes and requests, first fit returns [200, 1000, 500, None, 570].

Starter code · fits.py

def allocate(holes, requests, policy):
    """Where each request is placed under the policy, or None when it does not fit."""
    # Replace this line with your code.
    return [None for _ in requests]

The sample tests · test_fits.py

from fits import allocate

HOLES = [(200, 200), (500, 200), (1000, 350), (1650, 150)]
REQUESTS = [150, 290, 70, 180, 130]


def test_first_fit_refuses_p4():
    """places four requests and refuses the fourth, as in the lesson"""
    assert allocate(HOLES, REQUESTS, "first") == [200, 1000, 500, None, 570]


def test_best_fit_places_all():
    """uses the smallest hole that fits and places all five"""
    assert allocate(HOLES, REQUESTS, "best") == [1650, 1000, 200, 500, 270]


def test_worst_fit_refuses_p2():
    """splits the largest hole first and then cannot place 290"""
    assert allocate(HOLES, REQUESTS, "worst") == [1000, None, 200, 500, 1150]


def test_next_fit_wraps_around():
    """continues from the last hole used and wraps to the start"""
    assert allocate(HOLES, REQUESTS, "next") == [200, 1000, 1650, 500, None]


def test_holes_unchanged():
    """leaves the caller's list of holes as it was"""
    holes = list(HOLES)
    allocate(holes, REQUESTS, "best")
    assert holes == HOLES

A hint

Copy the holes into a list of [start, size] lists, so that a placement can change them. Next fit needs one more variable, the index of the hole it used last, and its search visits the indexes (last + k) % len(holes) for k from 0 upwards.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Then answer the questions on partitions and on the four policies, one at a time.

Fragmentation measured, and which fit refuses most Pro: opens with a Pro, Premium or Ultimate pass

One example decides nothing, so this part measures. It turns external fragmentation into a number, then runs the four policies on 40 seeded streams of 2,000 requests each and compares their refusals, their holes and their search lengths.

In this part:

A number for external fragmentation, from the largest hole
Forty request streams: refusals, the fifty-percent rule and search length

1 runnable example (Python) · about 5 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Compaction, swapping and overlays, and what each one costs Pro: opens with a Pro, Premium or Ultimate pass

When no hole is large enough, a system can make one. This part works out what compaction, moving one block and swapping a process out each cost in the memory that first fit left, explains overlays, and shows where the same problem returns in today’s kernels and allocators.

In this part:

Compaction copies 1,438 KiB to admit a 180 KiB request
Moving one block, or swapping one process out, costs far less
Overlays: one program reusing its own memory
Where holes come back: kernel compaction and malloc

1 runnable example (Python) · about 8 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Interview questions

The first question is answered below. The other three are about memory that grows while live data stays flat, a device that must allocate for years, and when compaction pays; their model answers are in the module’s question bank.

Fresher to mid · Warm-up

What is the difference between internal and external fragmentation? Give an example of each.

Internal fragmentation is memory wasted inside an allocated block: the block is larger than what was asked for, because sizes are rounded up to a partition, a page or a fixed unit. A 100 KiB process in a 256 KiB fixed partition wastes 156 KiB that no other process can use. External fragmentation is free memory wasted between blocks: there is enough free memory in total, but it lies in holes that are each too small. With holes of 250 and 494 KiB, 744 KiB are free, yet a request for 600 KiB is refused. Fixed-size units such as partitions trade external fragmentation for internal, because equal blocks always fit each other's holes; blocks of exactly the requested size do the opposite. A good answer names where each kind of waste sits, inside blocks or between them.
Mid to senior

A long-running service keeps about 2 GB of live objects, yet its resident memory grows from 3 GB to 6 GB over a week and never falls back. A heap profile shows no leak. How could fragmentation explain this, and what would you check and change?

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Mid to staff

A medical device without an MMU must run for five years without a restart, and it allocates and frees network buffers of five different sizes all day. Would you give it a first-fit heap? Explain the risk and design the allocation.

Model answer, Pro. First step and follow-ups
Senior to staff

An allocator manages a 1 GiB region of long-lived objects, and requests start failing with 300 MiB free in small holes. You could stop the program and compact the region. How would you decide whether compaction pays, with numbers?

Model answer, Pro. First step and follow-ups

Key takeaways

Contiguous allocation gives each process one run of memory: fixed partitions waste space inside blocks, internal fragmentation, and variable partitions leave holes between blocks, external fragmentation.
First fit takes the first hole that fits, best fit the smallest, worst fit the largest, and next fit continues from where it placed the previous request.
On the lesson’s five requests, three of the four policies refused one request while enough memory was free in total, because no single hole was large enough.

Terms in this lesson

contiguous allocation: Giving each process one unbroken run of physical memory, described by a single base address and a single limit.
hole: A run of free memory between allocated blocks. An allocator that places blocks in one piece each keeps a list of its holes.
internal fragmentation: Memory inside an allocated block that its owner does not use, because the block was rounded up to a fixed size such as a partition.
placement policy: The rule an allocator uses to choose a hole for each request, such as first fit, best fit, worst fit or next fit.

References

A fast storage allocator (Communications of the ACM) (ACM (Kenneth C. Knowlton))
The Art of Computer Programming, Volume 1: Fundamental Algorithms, section 2.5 Dynamic Storage Allocation (Addison-Wesley (Donald E. Knuth))
Operating Systems: Three Easy Pieces, chapter 17: Free-Space Management (University of Wisconsin-Madison (Arpaci-Dusseau))
Documentation for /proc/sys/vm/: compact_memory, compaction_proactiveness, extfrag_threshold (The Linux Kernel Organization)
The GNU linker: Overlay Description (GNU Project (GNU Binutils))
malloc(3): allocate and free dynamic memory (Linux man-pages project (man7.org))
Computer Science Curricula 2023: Operating Systems knowledge area (Version Gamma) (ACM, IEEE Computer Society and AAAI (CS2023 Task Force))
GATE 2027 syllabus for Computer Science and Information Technology (CS) (Indian Institute of Technology Madras (GATE 2027))

Report a problem with this lesson

In this module: Memory management: addresses, segmentation and paging

Linking, loading and address binding Free lesson, Pro answers: 20 minutes
Contiguous allocation and fragmentation Free core, Pro depth: 5 of 15 minutes free
Segmentation and segment tables Free core, Pro depth: 5 of 15 minutes free
Paging: pages, frames and page tables Free core, Pro depth: 6 of 15 minutes free
Allocating memory: buddy, slab and malloc Free core, Pro depth: 6 of 20 minutes free

Your country

Contiguous allocation and fragmentation

What you will learn

Before you start

What you will learn

Before you start

One run per process, and both kinds of partition waste memory

First, best, worst and next fit choose different holes

Practise: place requests with the four policies

Place requests with first, best, worst and next fit

Results of the sample tests

Fragmentation measured, and which fit refuses most Pro: opens with a Pro, Premium or Ultimate pass

Compaction, swapping and overlays, and what each one costs Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What is the difference between internal and external fragmentation? Give an example of each.

A long-running service keeps about 2 GB of live objects, yet its resident memory grows from 3 GB to 6 GB over a week and never falls back. A heap profile shows no leak. How could fragmentation explain this, and what would you check and change?

A medical device without an MMU must run for five years without a restart, and it allocates and frees network buffers of five different sizes all day. Would you give it a first-fit heap? Explain the risk and design the allocation.

An allocator manages a 1 GiB region of long-lived objects, and requests start failing with 300 MiB free in small holes. You could stop the program and compact the region. How would you decide whether compaction pays, with numbers?

Key takeaways

References