Contiguous Memory Allocation

Analogy categoryAnalogies

Introduction

In contiguous memory allocation, each process is placed in one continuous block of physical memory. This is the simplest scheme to reason about and implement: a base register holds the starting physical address of the process, and a limit register holds the length of the process's address space, so the MMU only has to check 0 <= logical_address < limit and then compute physical_address = logical_address + base.

🏏

Cricket analogy: Contiguous allocation is like assigning each touring team one unbroken block of hotel rooms with a base room number and a room count, so the front desk just checks whether a requested room number falls within that team's block plus its base offset.

Explanation

As processes are loaded and removed, memory develops holes of free space between allocated blocks. When a new process needs to be placed, the OS must pick a hole using an allocation strategy: First-Fit scans from the start and picks the first hole big enough, which is fast but can leave many awkward small fragments near the front. Best-Fit scans every hole and picks the smallest one that still fits, minimizing wasted space per allocation but tending to create many unusably tiny leftover holes and requiring a full scan. Worst-Fit picks the largest available hole, leaving a large leftover fragment that is more likely to be useful later, but empirically it performs worst overall for both time and space. These strategies produce external fragmentation: free memory exists in total but is split into pieces too small individually to satisfy a request. This differs from internal fragmentation, where memory is allocated in fixed-size chunks (e.g., rounding every request up to the next 4KB) and the unused space inside an allocated block is wasted.

🏏

Cricket analogy: As tours come and go, hotel room blocks free up unevenly, so the travel manager can pick First-Fit (book the first block big enough, fast but leaves awkward small gaps), Best-Fit (scan all blocks for the tightest fit, minimizing waste but leaving tiny unusable leftover rooms), or Worst-Fit (book the biggest block, leaving a large usable leftover but performing worst overall).

Example

/* Simplified simulation of first-fit vs best-fit over a list of holes. */
#include <stdio.h>

#define NUM_HOLES 4

int find_first_fit(int holes[], int n, int request) {
    for (int i = 0; i < n; i++)
        if (holes[i] >= request) return i;   /* first hole that fits */
    return -1;
}

int find_best_fit(int holes[], int n, int request) {
    int best = -1;
    for (int i = 0; i < n; i++) {
        if (holes[i] >= request) {
            if (best == -1 || holes[i] < holes[best]) best = i;
        }
    }
    return best;   /* smallest hole that still fits */
}

int main(void) {
    int holes[NUM_HOLES] = {100, 500, 200, 300};  /* KB, in address order */
    int request = 212;                             /* process needs 212 KB */

    int ff = find_first_fit(holes, NUM_HOLES, request);
    int bf = find_best_fit(holes, NUM_HOLES, request);

    printf("First-Fit chooses hole index %d (size %d KB)\n", ff, holes[ff]);
    printf("Best-Fit  chooses hole index %d (size %d KB)\n", bf, holes[bf]);
    return 0;
}

Output

For holes {100, 500, 200, 300} KB and a request of 212 KB: First-Fit skips the 100 KB hole (too small) and picks the 500 KB hole at index 1, leaving a 288 KB fragment there. Best-Fit scans all holes and finds that 300 KB (index 3) is the smallest hole that still satisfies 212 KB, leaving only an 88 KB fragment. This shows the classic trade-off: First-Fit is O(n) in the worst case but stops early and can waste large holes on small requests; Best-Fit inspects every hole (also O(n) but with more work per call in general implementations) and wastes less space per request, at the cost of leaving many small, often useless, fragments scattered around memory over time.

🏏

Cricket analogy: With free room blocks of {100, 500, 200, 300} and a touring squad needing 212 rooms, First-Fit skips the 100-room hotel and books the 500-room one, leaving a 288-room gap, while Best-Fit scans all four and picks the 300-room hotel, leaving only an 88-room gap - less waste but a full scan required.

Key Takeaways

Contiguous allocation gives each process one unbroken block, checked cheaply via base and limit registers.
External fragmentation is free memory split into holes too small to satisfy requests, even though total free space is sufficient.
Internal fragmentation is wasted space inside an allocated block due to fixed-size allocation granularity.
First-Fit is fast; Best-Fit minimizes leftover space per allocation but scans everything and fragments memory into small unusable pieces; Worst-Fit generally performs worst.
Compaction (shifting processes to merge holes) can eliminate external fragmentation but is expensive and requires relocatable code.

Practice what you learned

1. What is external fragmentation?

2. Which allocation strategy scans the entire list of holes and picks the smallest one that still satisfies the request?

3. Given holes of size 100 KB, 500 KB, 200 KB, 300 KB (in that address order) and a request for 212 KB, which hole does First-Fit select?

4. What technique can eliminate external fragmentation by shifting processes so all free memory forms one large block?

Was this page helpful?

Memory Management Basics

Paging

Topics covered

#OperatingSystemsStudyNotes#OperatingSystems#ContiguousMemoryAllocation#Contiguous#Memory#Allocation#Explanation#StudyNotes#SkillVeris#ExamPrep