Memory management: partitioning and fragmentation

Why it exists

Main memory is limited and many processes want it at once. The operating system has to decide where in memory each process goes, keep processes from touching each other's memory, and make good use of what exists. The oldest and simplest scheme gives each process one contiguous block of memory. It is easy to understand and is the setting for classic GATE questions on placement rules and fragmentation. Its weaknesses, wasted space and the need to find a big enough hole, are the reasons paging was invented (paging).

Prerequisites

No other concept page is needed. It helps to know that main memory is one level of the memory hierarchy, larger and slower than the cache, smaller and faster than the disk.

Precise definitions

Aims of memory management. Relocation (a program may be loaded anywhere), protection (a process cannot touch another's memory or the operating system's), sharing (controlled shared memory, shared code), logical organisation (modules, segments), and efficient use of physical memory.

Contiguous allocation. Each process occupies a single contiguous block. Memory is divided between the operating system (usually the low or the high end) and user processes.

• Fixed (static) partitioning: memory is divided in advance into partitions, of equal or different sizes. A process is loaded into a free partition that is large enough. The degree of multiprogramming is limited by the number of partitions.
• Variable (dynamic) partitioning: partitions are created as needed. A process gets exactly the memory it requests. When a process ends, its block becomes a hole; adjacent holes are merged (coalesced).

Fragmentation. Memory that is free but cannot be used.

• Internal fragmentation: wasted memory inside an allocated block, because the block is larger than the request. Typical of fixed partitions (a 130 KB process in a 200 KB partition wastes 70 KB), of the buddy system, and of paging (the last page of a process).
• External fragmentation: enough free memory in total, but split into holes that are each too small for the request. Typical of variable partitions and of segmentation.

Placement algorithms (for variable partitions). When a request of size $n$ arrives, choose a hole of size at least $n$:

In all of them the process takes the part of the hole at its low end and the rest remains a smaller hole. Best fit must search the whole list (unless it is sorted by size) and tends to leave many tiny, useless holes. First fit is usually fast and about as good as best fit in practice. Worst fit tends to break up the large holes that big requests need, and does worst in simulations. No rule is best for every request sequence: one may succeed where another fails, in either direction.

Compaction. Move the processes to one end of memory so that all the holes join into one large hole. It cures external fragmentation, but costs time (every moved process is copied) and works only if the processes can be relocated at run time (the addresses are bound at execution time; see process address space).

Swapping. A process can be moved temporarily out of memory to a backing store (a fast disk) and brought back later to continue. It lets the total memory demand exceed physical memory and makes room for higher-priority processes. The cost is dominated by the transfer: swap time $= \dfrac{\text{process size}}{\text{transfer rate}}$, once out and once in.

Buddy system. Memory of size $2^k$ is split in halves repeatedly. A request is rounded up to a power of two and served from a block of exactly that size, splitting a larger free block if necessary. When a block is freed it is merged with its buddy (the other half of the block it was split from) if the buddy is free too. Fast to find the buddy (the buddy of a block of size $s$ at address $a$ is at $a \oplus s$, the bitwise exclusive or), but it suffers internal fragmentation. Example: a request of 70 KB in a 1024 KB memory is rounded up to 128 KB, wasting 58 KB.

How it works

The animations apply each placement rule to the same memory and the same four requests. Memory is 2000 KB. Processes A to E are loaded and between them are five holes of 100, 450, 300, 550 and 250 KB. Four processes arrive in order, P1 (210 KB), P2 (480 KB), P3 (150 KB) and P4 (400 KB), and each needs one contiguous block. Watch which hole each rule picks and what is left.

First fit places P1 in the 450 KB hole, P2 in the 550 KB hole, P3 in the 240 KB remainder. P4 needs 400 KB; the holes are 100, 90, 300, 70 and 250: no single hole is large enough, although the total free memory is 810 KB. That is external fragmentation.

Best fit places P1 in the smallest hole that fits (250), P2 in 550, P3 in 300 and P4 in 450. Every request is satisfied.

Worst fit puts P1 in the largest hole (550), which leaves only 450 and 340 for P2 (needs 480): it fails; later P4 fails too.

Next fit continues the search from the last placement, so P3 is placed after P2 (in the last hole) and P4 fails like in first fit.

Compaction. First fit again, but when P4 fails the processes are slid together. All 810 KB of free memory become one hole and P4 fits.

Worked examples

#include <stdio.h>
 
#define NB 10                               /* blocks in memory: processes and holes in address order */
#define NR 4
 
struct block { const char *owner; int size; };           /* owner NULL means a hole */
 
static void run(const char *name, int algo) {
    struct block b[32] = {{0, 100}, {"A", 60}, {0, 450}, {"B", 80}, {0, 300}, {"C", 70}, {0, 550}, {"D", 90}, {0, 250}, {"E", 50}};
    int n = NB, last = 0;
    const char *rname[NR] = {"P1", "P2", "P3", "P4"};
    int rsize[NR] = {210, 480, 150, 400};
    printf("%-9s", name);
    for (int r = 0; r < NR; r++) {
        int pick = -1;
        for (int k = 0; k < n; k++) {
            int i = algo == 3 ? (last + k) % n : k;             /* next fit starts where the last placement was made */
            if (b[i].owner || b[i].size < rsize[r]) continue;
            if (algo == 0 || algo == 3) { pick = i; break; }
            if (pick < 0 || (algo == 1 && b[i].size < b[pick].size) || (algo == 2 && b[i].size > b[pick].size)) pick = i;
        }
        if (pick < 0) { printf("  %s: no hole", rname[r]); continue; }
        int start = 0;
        for (int i = 0; i < pick; i++) start += b[i].size;
        printf("  %s: at %d", rname[r], start);
        int rest = b[pick].size - rsize[r];
        b[pick].owner = rname[r]; b[pick].size = rsize[r];
        if (rest) {
            for (int i = n; i > pick + 1; i--) b[i] = b[i - 1];
            b[pick + 1].owner = 0; b[pick + 1].size = rest; n++;
        }
        last = pick;
    }
    int freeb = 0, largest = 0;
    for (int i = 0; i < n; i++) if (!b[i].owner) { freeb += b[i].size; if (b[i].size > largest) largest = b[i].size; }
    printf("   | free %d, largest hole %d\n", freeb, largest);
}
 
int main(void) {
    run("first", 0);
    run("best", 1);
    run("worst", 2);
    run("next", 3);
    return 0;
}

first      P1: at 160  P2: at 1060  P3: at 370  P4: no hole   | free 810, largest hole 300
best       P1: at 1700  P2: at 1060  P3: at 690  P4: at 160   | free 410, largest hole 150
worst      P1: at 1060  P2: no hole  P3: at 160  P4: no hole   | free 1290, largest hole 340
next       P1: at 160  P2: at 1060  P3: at 1700  P4: no hole   | free 810, largest hole 300

Cheat box

Traps and GATE patterns

Connections

Paging removes external fragmentation by letting a process occupy non-contiguous frames (paging); segmentation allows several contiguous pieces of varying sizes per process but brings back external fragmentation (segmentation). Compaction and swapping rely on addresses being bound at run time (process address space). Swapping a process in and out is a decision of the medium-term scheduler (CPU scheduling).

PYQs

Consider contiguous allocation of physical memory
to processes using a variable partitioning scheme.
Suppose there are 8 holes in the memory of sizes:

20 KB, 4 KB, 25 KB, 18 KB, 7 KB, 9 KB, 15 KB,
and 12 KB.

Assume that no two holes are adjacent.

Two processes arrive in order:
●
P1 = 16 KB
●
P2 = 9 KB

They are allocated memory using the best-fit
technique.

After allocating space to P1 and P2, the number of
holes of size less than 8 KB is ______.

Note: 1K = 210.

Consider allocation of memory to a new process.
Assume that none of the existing holes in the
memory will exactly fit the process's memory
requirement. Hence, a new hole of smaller size will
be created if allocation is made in any of the
existing holes. Which one of the following
statements is TRUE?

Consider six memory partitions of size 200 KB,
400 KB, 600 KB, 500 KB, 300 KB, and 250 KB,
where KB refers to kilobyte. These partitions need
to be allotted to four processes of sizes 357 KB, 210
KB, 468 KB and 491 KB in that order. If the best
fit algorithm is used, which partitions are NOT
allotted to any process?

Self-check

Revision card

References