Memory: addresses and allocation

Many processes share one memory. The OS must keep each one inside its own part, and find room for new ones.

Logical and physical addresses

The addresses a program uses are logical (or virtual) addresses. The address that goes out to the memory chips is physical. The memory-management unit (MMU), a part of the CPU, translates every logical address into a physical one, on every single access.

The simplest MMU has two registers, set by the OS each time it switches process:

• base: where the process starts in physical memory,
• limit: how big its part is.

For each logical address: if it is less than limit, the physical address is base + logical address; otherwise the MMU traps to the kernel with an addressing error. That one comparison keeps a process out of everyone else's memory.

#include <stdio.h>

int base = 30000, limit = 12000;   /* set by the OS for this process */

void access(int logical) {
    if (logical < 0 || logical >= limit) {
        printf("%5d -> trap: addressing error\n", logical);
        return;
    }
    int physical = base + logical;
    printf("%5d -> %d\n", logical, physical);
}

int main(void) {
    access(0);
    access(1024);
    access(11999);
    access(12000);   /* one past the end */
    return 0;
}

When an address is turned into a physical one is called address binding. It can happen when compiling (only if the program always loads at the same place), when loading, or, as on every modern system, while running, which lets the OS move a process.

Partitions

• Fixed partitions: memory is cut into parts of set sizes in advance. A process smaller than its part wastes the rest: internal fragmentation (waste inside an allocated part).
• Variable partitions: each process gets exactly what it asks for. As processes come and go, memory fills with free gaps (holes) between them. When enough memory is free in total, but no single hole is big enough, that is external fragmentation (waste between parts).

Compaction cures external fragmentation by moving processes together into one end of memory, but moving them takes time and needs binding while running.

Choosing a hole

The standard exercise: holes of 100, 500, 200, 300 and 600 KB, and processes of 212, 417, 112 and 426 KB, in that order:

#include <stdio.h>

#define HOLES 5
#define PROCS 4

int main(void) {
    int hole[HOLES] = {100, 500, 200, 300, 600};   /* free sizes, in KB */
    int proc[PROCS] = {212, 417, 112, 426};

    for (int p = 0; p < PROCS; p++) {
        int chosen = -1;
        for (int h = 0; h < HOLES; h++) {
            if (hole[h] >= proc[p]) {   /* the first hole that is big enough */
                chosen = h;
                break;
            }
        }
        if (chosen < 0) {
            printf("%d KB: must wait\n", proc[p]);
        } else {
            hole[chosen] -= proc[p];
            printf("%d KB: hole %d, %d KB left there\n", proc[p], chosen + 1, hole[chosen]);
        }
    }
    return 0;
}

The program does first fit. Change the condition to look for the smallest (or largest) hole that fits, and it does best (or worst) fit.

Paging, the next lesson, removes external fragmentation altogether by giving up on keeping a process in one piece.

Mark lesson complete