SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 30
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 30 of 90

Memory management 1: address binding and contiguous allocation

address binding (compile, load, execution time)logical vs physical addressMMUrelocation and limit registersstatic vs dynamic loadingstatic vs dynamic linkingshared librariescontiguous allocationfixed and variable partitioningfirst fitbest fitnext fitworst fitinternal fragmentation

These are the notes for CS Fundamentals for Placements, episode 30. We've finished processes, threads, synchronization and deadlocks. Now the second big job of an operating system: managing memory. Today: address binding (compile, load and execution time), logical vs physical addresses, the MMU with its relocation and limit registers, static vs dynamic loading, static vs dynamic linking and shared libraries, and contiguous allocation: fixed and variable partitioning, first, next, best and worst fit, internal and external fragmentation, compaction and the buddy system, with numericals. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.

All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags: gcc -O2 -Wno-unused-result main.c -o main -lm) and run on Linux x86-64 on 4 November 2026. The address-printing program prints different addresses on every run (that's the point), so its output below is one example run.

Two words first

  • Main memory (RAM) is one long row of bytes. Each byte has a number, starting at 0: its address, like a house number on a very long street.
  • Every variable and every instruction of your program sits at some address. The question today: who decides which address, and when?

Addresses that change

#include <stdio.h>
int total = 0;                        // a global variable
int main(void) {
    int marks = 90;                   // a local variable
    printf("main()  is at %p\n", (void *)main);
    printf("total   is at %p\n", (void *)&total);
    printf("marks   is at %p\n", (void *)&marks);
}

%p prints an address (a pointer value) in hexadecimal (base 16, episode 2). (void *) converts it to a generic pointer, which is what %p expects.

Two runs of the exact same program:

main()  is at 0x561f16e59080
total   is at 0x561f16e5c014
marks   is at 0x7fffea466004
main()  is at 0x5556ec701080
total   is at 0x5556ec704014
marks   is at 0x7ffe22a4fae4

Every address changed. But look at the distance between main and total: 0x...c014 - 0x...9080 = 0x2f94 in both runs. The whole program block was simply placed somewhere new. (Linux does this on purpose for security: ASLR, address space layout randomization, places the program, stack and libraries at random addresses each run so attackers can't guess them. The last three hex digits of main and total stay the same because the program is moved in whole 4 KB pages; more on pages next episode.)

Address binding

Address binding is fixing which real memory address a name in your program (a variable like total, a function like main) will use. A program's addresses go through stages:

source code (names: total, main)
   → compiler → object code (relocatable: "offset 0x2f94 from my start")
   → linker   → executable
   → loader   → in memory (real addresses)

The loader is the part of the OS that copies a program from disk into RAM and starts it.

When What happens Pros / cons
Compile time The compiler knows where the program will live and writes the final addresses into the code: absolute code Must always load at the same place; to move it, recompile
Load time The compiler writes relocatable code (addresses counted from the start of the program); the loader adds the real starting address when loading Can load anywhere, but can't move once running
Execution time The real address is computed on every memory access, while the program runs Can be placed anywhere and moved later (swapping, compaction); needs hardware: the MMU. Used by modern OSes

Logical vs physical addresses

The story: your seat in a wedding hall

Your family's card says seat 46, counted inside your family's block. The hall numbers all its seats from the entrance, and your real seat is 1446. The usher knows your block starts at 1400 and adds: 1400 + 46 = 1446. Your block has only 60 seats; if someone walks to seat 75, the usher stops them.

Wedding hall Memory
Seat 46 on your card Logical (virtual) address: what the program uses
Hall seat 1446 Physical address: the real byte in the RAM chips
The usher who adds 1400 The MMU with its relocation (base) register
"Your block has 60 seats" The limit register
Stopping someone at seat 75 A trap to the OS
  • The logical address is generated by the CPU while running the program. Every address our program printed was a logical address.
  • The physical address is the one the memory hardware actually sees.
  • The MMU (memory management unit) is hardware in the CPU that translates every logical address into a physical one.
  • The relocation register (base register) holds where the process starts in physical memory.
  • The limit register holds the size of the process; any logical address ≥ limit is illegal.
  • A trap is an interrupt caused by the running program (episode 15): the CPU stops the program and hands control to the OS.
logical address ──▶ [ < limit ? ] ──no──▶ TRAP (addressing error) → OS
                         │ yes
                         ▼
                    [ + relocation ] ──▶ physical address ──▶ RAM

The set of all logical addresses a program can use is its logical address space; the set of all physical addresses is the physical address space.

Important subtlety: with compile-time and load-time binding, logical and physical addresses are the same. Only with execution-time binding do they differ, and that's when the MMU translates.

Logical (virtual) Physical
Generated by the CPU, while running the program the MMU
Seen by the program the memory hardware
Set of all logical address space physical address space
Changes when the process is moved? no yes

The MMU, simulated

#include <stdio.h>
// What the MMU does on EVERY memory access, for one process
int relocation = 14000;               // where the OS loaded this process
int limit = 3000;                     // how big the process is
void mmu(int logical) {
    if (logical < 0 || logical >= limit) {
        printf("logical %4d -> TRAP: addressing error, OS stops the process\n", logical);
        return;
    }
    printf("logical %4d -> physical %d\n", logical, relocation + logical);
}
int main(void) {
    mmu(0); mmu(346); mmu(2999); mmu(3500);
    relocation = 50000;               // OS moves the process (swap out and back in)
    printf("moved to 50000:\n");
    mmu(346);
}

Output:

logical    0 -> physical 14000
logical  346 -> physical 14346
logical 2999 -> physical 16999
logical 3500 -> TRAP: addressing error, OS stops the process
moved to 50000:
logical  346 -> physical 50346

After the move, the program still uses logical address 346; only the relocation register changed. That is why execution-time binding allows moving processes.

The real MMU catches a bad address

#include <stdio.h>
int main(void) {
    int *p = (int *)16;               // an address this process does not own
    printf("about to read address 16...\n");
    fflush(stdout);
    printf("%d\n", *p);               // the MMU checks it: outside our memory
}

Output:

about to read address 16...
Segmentation fault

Address 16 isn't part of our process's memory. The hardware caught it, trapped into the OS, and the OS stopped the program with the signal SIGSEGV; the shell reports it as Segmentation fault (exit status 139 = 128 + 11, where 11 is SIGSEGV's number). fflush(stdout) makes sure the first line is printed before the crash.

Loading and linking

Static vs dynamic loading

  • Static loading: the whole program, every function, is loaded into RAM before it starts. Even error-handling code that never runs uses memory.
  • Dynamic loading: a routine stays on disk and is loaded only the first time it's actually called. Memory is used only for code that runs.
#include <stdio.h>
#include <dlfcn.h>
int main(void) {
    printf("program started, math library not loaded yet\n");
    void *lib = dlopen("libm.so.6", RTLD_NOW);       // load it NOW, at run time
    if (!lib) { printf("could not load: %s\n", dlerror()); return 1; }
    double (*root)(double) = (double (*)(double))dlsym(lib, "sqrt");
    printf("loaded libm, sqrt(144) = %.0f\n", root(144));
    dlclose(lib);
}

Output:

program started, math library not loaded yet
loaded libm, sqrt(144) = 12
  • dlopen("libm.so.6", RTLD_NOW) loads the math library file at run time (RTLD_NOW: resolve all its symbols immediately) and returns a handle to it.
  • dlsym(lib, "sqrt") finds the address of the function named sqrt inside it. We store it in a function pointer root (a variable that holds the address of a function) and call it.
  • dlclose unloads it. These functions are declared in <dlfcn.h>.
  • Plugins in browsers, editors and games are loaded this way.

Static vs dynamic linking, and shared libraries

A library is ready-made code you call, like printf or sqrt. Linking is joining your code with the library code it calls, so every call knows where to jump. The linker is the tool that does it.

Static linking Dynamic linking
What goes in your executable A copy of the library code A small stub that finds the library function at run time
Executable size Large Small
RAM with 100 programs using printf 100 copies 1 shared copy
Library bug fix Rebuild every program Replace the library file once
Risk None at run time Library missing or wrong version ("DLL hell")
Linux file libc.a (archive) libc.so.6 (shared object)
Windows file .lib .dll (dynamic-link library)

A shared library is a library loaded into RAM once and used by every program that needs it. With dynamic linking, the OS maps the same physical copy into many processes.

Contiguous allocation

The story: parking buses in a depot

A bus needs several parking bays side by side; you can't park it in three scattered bays. The simplest memory scheme works the same way: contiguous allocation gives each process one unbroken stretch of RAM (the OS itself usually sits in low memory and user processes above it).

Fixed partitioning

RAM is cut into fixed partitions in advance (all equal, or a few fixed sizes), and each partition holds one process.

Numerical: 4 partitions of 100 K each. P1 = 70 K, P2 = 95 K, P3 = 40 K.

Process Size Partition Wasted inside
P1 70 K 100 K 30 K
P2 95 K 100 K 5 K
P3 40 K 100 K 60 K
Total 95 K
  • Internal fragmentation: space wasted inside a block that was given to a process (because the block is bigger than needed).
  • A process bigger than the largest partition (here 120 K) can never run.
  • The number of partitions caps the degree of multiprogramming (how many processes can be in memory at once, episode 17).

Variable partitioning

Give each process exactly what it needs. As processes finish, they leave free gaps of various sizes called holes. The OS keeps a list of holes, and when a process arrives, it must pick a hole. (A hole bigger than needed is split: the process takes the first part, and the rest stays a smaller hole.)

Which hole? First, next, best and worst fit

Strategy Rule Notes
First fit The first hole (from the start of memory) that is big enough Fast: stops at the first match
Next fit Like first fit, but start scanning from where the last search stopped Spreads allocations through memory
Best fit The smallest hole that is big enough Least leftover per allocation, but tends to leave tiny useless holes; must search the whole list (unless it's sorted by size)
Worst fit The largest hole Leftover is big enough to be useful; but it breaks up big holes

Which one wins depends on the data: first fit is better for some systems, best fit for others, and first fit is quicker because it stops at the first match.

Numerical

Holes (in order in memory): 150 K, 400 K, 220 K, 350 K, 500 K. Requests, in order: 210 K, 380 K, 120 K, 400 K. (Hole numbers start at 0.)

First fit: - 210 → hole 1 (400 → 190 left) - 380 → hole 4 (500 → 120 left) - 120 → hole 0 (150 → 30 left) - 400 → holes are now 30, 190, 220, 350, 120: fails

Next fit (starts where the last one stopped): - 210 → hole 1 (190 left); 380 → from hole 1: 190 no, 220 no, 350 no, 500 yes → hole 4 (120 left) - 120 → from hole 4: 120 yes → hole 4 (0 left) - 400 → none: fails

Best fit: - 210 → hole 2 (220, smallest that fits; 10 left) - 380 → hole 1 (400; 20 left) - 120 → hole 0 (150; 30 left) - 400 → hole 4 (500; 100 left): all placed

Worst fit: - 210 → hole 4 (500, largest; 290 left) - 380 → hole 1 (400; 20 left) - 120 → hole 3 (350, now the largest; 230 left) - 400 → largest is 290: fails

The four strategies in C

#include <stdio.h>
#include <string.h>
int holes[5];                                   // free holes in RAM, in KB
int pick(char how, int size, int start) {      // which hole? -1 = none fits
    int best = -1;
    for (int k = 0; k < 5; k++) {
        int i = (start + k) % 5;                // next fit: start where we stopped
        if (holes[i] < size) continue;          // too small
        if (how == 'f' || how == 'n') return i; // first (or next) one that fits
        if (best < 0 || (how == 'b' ? holes[i] < holes[best]     // best: smallest
                                    : holes[i] > holes[best])) best = i;  // worst: largest
    }
    return best;
}
void simulate(char how, const char *name) {
    int start[5] = {150, 400, 220, 350, 500}, req[4] = {210, 380, 120, 400}, last = 0;
    memcpy(holes, start, sizeof start); printf("%-6s", name);
    for (int r = 0; r < 4; r++) {
        int i = pick(how, req[r], how == 'n' ? last : 0);
        if (i < 0) { printf("  %dK FAILS", req[r]); continue; }
        printf("  %dK->hole%d", req[r], i); holes[i] -= req[r]; last = i;
    }
    printf("\n");
}
int main(void) { simulate('f', "first"); simulate('n', "next");
                 simulate('b', "best");  simulate('w', "worst"); }

Output:

first   210K->hole1  380K->hole4  120K->hole0  400K FAILS
next    210K->hole1  380K->hole4  120K->hole4  400K FAILS
best    210K->hole2  380K->hole1  120K->hole0  400K->hole4
worst   210K->hole4  380K->hole1  120K->hole3  400K FAILS

printf("%-6s", name) prints the name left-aligned in 6 characters, so the columns line up. memcpy (from <string.h>) copies the starting holes into holes for each strategy.

External fragmentation and compaction

1000 K of RAM holds A (300 K), B (200 K), C (300 K), D (200 K), one after another. B and D finish:

| A 300K | hole 200K | C 300K | hole 200K |
0        300         500      800        1000

400 K is free in total, but a 350 K program can't run: no single hole is big enough. This is external fragmentation: free memory split into pieces between processes. (Internal = wasted inside a block; external = wasted between blocks.)

How bad is it? Statistical analysis of first fit gives the 50-percent rule: given N allocated blocks, another 0.5 N blocks are lost to fragmentation, so up to one-third of memory may be unusable.

Compaction moves processes together so that all the free space joins into one big hole.

#include <stdio.h>
// RAM = 1000K, filled by 4 programs one after another
char name[4] = {'A', 'B', 'C', 'D'};
int base[4]  = {0, 300, 500, 800};          // where each program starts (K)
int size[4]  = {300, 200, 300, 200};
int alive[4] = {1, 1, 1, 1};
void show(int want) {
    int total = 0, largest = 0, hole = 0, pos = 0;
    for (int i = 0; i <= 4; i++) {          // walk RAM, measure the gaps
        int start = (i < 4) ? base[i] : 1000;
        if (i < 4 && !alive[i]) continue;
        hole = start - pos; total += hole; if (hole > largest) largest = hole;
        if (i < 4) pos = base[i] + size[i];
    }
    printf("free %dK in total, largest hole %dK -> %dK %s\n",
           total, largest, want, largest >= want ? "fits" : "FAILS");
}
int main(void) {
    alive[1] = alive[3] = 0;                // B and D finish
    show(350);
    int pos = 0;                            // compaction: slide every live program down
    for (int i = 0; i < 4; i++) if (alive[i]) { base[i] = pos; pos += size[i]; }
    printf("after compaction: A at %dK, C at %dK\n", base[0], base[2]);
    show(350);
}

Output:

free 400K in total, largest hole 200K -> 350K FAILS
after compaction: A at 0K, C at 300K
free 400K in total, largest hole 400K -> 350K fits

Limits of compaction: - It is possible only with execution-time binding (dynamic relocation): the OS copies a process and changes its relocation register. If relocation is static (done at assembly or load time), compaction can't be done. - It is slow: copying hundreds of megabytes while processes wait. - The real cure is to let a process live in non-contiguous pieces: paging (next episode) and segmentation.

Internal fragmentation External fragmentation
Where the waste is Inside an allocated block Between allocated blocks
Caused by Fixed-size blocks bigger than needed Variable-size allocations leaving holes
Seen in Fixed partitions, buddy system, paging (last page) Variable partitions, segmentation
Fix Smaller / better-sized blocks Compaction, paging

The buddy system

Like cutting a big paratha for guests: you may only cut a piece exactly in half.

  • Memory is managed in blocks whose sizes are powers of two (1, 2, 4, 8, ... K).
  • To serve a request of size S: start from a free block; while half of it is still ≥ S, split it into two halves, called buddies; give the smallest block that fits.
  • When a block is freed, if its buddy is also free, the two merge (coalesce) into the bigger block, and this repeats upward.
  • Buddies are found quickly: a block of size 2^k at address a has its buddy at address a XOR 2^k (the addresses differ in exactly one bit).

The buddy system was invented in 1963 by Harry Markowitz and first described in print by Kenneth C. Knowlton in 1965. The Linux kernel also uses the buddy system, with further changes to reduce external fragmentation.

#include <stdio.h>
// Buddy system: blocks are powers of two. Each request starts from a free 1024K.
int main(void) {
    int total = 1024, want[3] = {70, 35, 260};      // KB
    for (int r = 0; r < 3; r++) {
        int block = total;
        printf("%3dK: ", want[r]);
        while (block / 2 >= want[r]) {               // half still big enough? split
            printf("%d -> ", block);
            block /= 2;                              // two "buddies" of half size
        }
        printf("%dK block, wasted %dK\n", block, block - want[r]);
    }
}

Output:

 70K: 1024 -> 512 -> 256 -> 128K block, wasted 58K
 35K: 1024 -> 512 -> 256 -> 128 -> 64K block, wasted 29K
260K: 1024 -> 512K block, wasted 252K

(Each request here starts from a fresh, empty 1024 K memory.) The buddy system is fast to split and merge, but rounding up to a power of two causes internal fragmentation: up to almost half the block (260 K wasted 252 K).

Buddy numerical with a full memory map

1024 K memory. Requests in order: A = 70 K, B = 35 K, C = 80 K; then A is freed.

  1. A (70 K): split 1024 → 512 + 512 → 256 + 256 → 128 + 128. A gets the first 128 (at 0). Map: A 128 | free 128 | free 256 | free 512
  2. B (35 K): take the free 128 at 128, split → 64 + 64; B gets 64 at 128. Map: A 128 | B 64 | free 64 | free 256 | free 512
  3. C (80 K): needs 128; split the free 256 at 256 → 128 + 128; C gets 128 at 256. Map: A 128 | B 64 | free 64 | C 128 | free 128 | free 512
  4. Free A: its buddy (the 128 at 128) is split (B is in it), so no merge. Map: free 128 | B 64 | free 64 | C 128 | free 128 | free 512

Internal fragmentation now: B 64 - 35 = 29 K, C 128 - 80 = 48 K.

The whole chain

Step Obvious attempt What broke Fix
1 Fix addresses at compile time Program can't move Execution-time binding: logical → MMU → physical
2 Let any address through Programs could read each other's memory Limit register + trap (Segmentation fault)
3 Load and link everything statically Wasted RAM, 100 copies of printf Dynamic loading, dynamic linking, shared libraries
4 Fixed partitions Waste inside (internal fragmentation) Variable partitions
5 Any hole will do 400K FAILS for three strategies Choose wisely; but still:
6 Variable partitions 350K FAILS with 400 K free (external) Compaction (slow), buddy system, then paging

Common mistakes

Mistake What you see Why Fix
Reading an address you don't own Segmentation fault The MMU's check traps it Only use memory you allocated
Comparing logical address ≤ limit (instead of <) Off-by-one in numericals Valid logical addresses are 0 .. limit - 1 Legal iff 0 ≤ logical < limit
Mixing up internal and external fragmentation Wrong theory answer Inside a block vs between blocks Fixed/buddy → internal; variable → external
Next fit scanning from the start Wrong placements Next fit resumes where it stopped Keep a pointer to the last hole used
Forgetting to shrink a hole after placing Two programs in one hole The leftover is a smaller hole Hole size -= request
"Best fit always wins" False in general It leaves tiny useless holes Work it out on the given data
Compaction with load-time binding Not possible Addresses were fixed at load Needs execution-time binding

Mini project: a memory allocator simulator

Write a simulator that reads commands from stdin: alloc NAME SIZE and free NAME, over a 1000 K memory, using a strategy chosen on the first line (first, next, best or worst). After each command, print the memory map (| A 300K | hole 200K | ...), merging neighbouring holes when a process is freed. Add a compact command. Then feed the same 30 random commands to all four strategies and count how many allocations fail with each.

Practice

1. Redo today's fit numerical with holes 300, 600, 350, 200, 750, 125 K and requests 115, 500, 358, 200, 375 K.

Solution
  • First fit: 115 → 300 (185 left); 500 → 600 (100); 358 → 750 (392); 200 → 350 (150); 375 → 392 (17). All placed.
  • Best fit: 115 → 125 (10); 500 → 600 (100); 358 → 750 (392); 200 → 200 (0); 375 → 392 (17). All placed.
  • Worst fit: 115 → 750 (635); 500 → 635 (135); 358 → 600 (242); 200 → 350 (150); 375 → largest is 300: fails.
  • Next fit: 115 → 300 (185, hole 0); 500 → from hole 0: 185 no, 600 yes (100, hole 1); 358 → from hole 1: 100, 350 no, 200 no, 750 yes (392, hole 4); 200 → from hole 4: 392 yes (192); 375 → from hole 4: 192, 125, 185, 100, 350, 200: fails.

2. Relocation = 3000, limit = 500. Map logical addresses 120, 499 and 500.

Solution

120 → 3120. 499 → 3499 (the last legal byte). 500 is not < 500 → trap (addressing error).

3. Buddy system, 512 K memory: allocate 100 K, 30 K, 60 K. Show the blocks and internal fragmentation.

Solution

100 K: 512 → 256 + 256 → 128 + 128; gets 128 (28 K wasted). 30 K: the free 128 → 64 + 64 → 32 + 32; gets 32 (2 K wasted). 60 K: the free 64; gets 64 (4 K wasted). Free left: one 32 K block and one 256 K block. Total internal fragmentation 34 K.

4. Why can't load-time binding support compaction?

Solution

With load-time binding, the loader wrote the real addresses into the program's code and data when it loaded it. Moving the program would leave all those addresses pointing at the old place. Compaction needs execution-time binding, where moving a process means changing only its relocation register.

5. 6 fixed partitions of 200 K each; processes of 150, 80, 200, 190 K. Internal fragmentation?

Solution

50 + 120 + 0 + 10 = 180 K. Two partitions are empty (they are free, not internal fragmentation).

6. A process has logical addresses 0 to 9999 and is loaded at physical 40000. What are the relocation and limit registers?

Solution

Relocation = 40000, limit = 10000 (the size; legal logical addresses are 0 to 9999).

Quick quiz

relocation register = 5000
limit register      = 1200
// the CPU generates logical address 1150.
// what does the MMU do?

A. Trap: 1150 is too big B. Physical address 6150 C. Physical address 3850 D. Physical address 1150

Answer

B. 1150 < 1200, so it is legal, and physical = 5000 + 1150 = 6150. Logical 1200 or more would trap.

Interview questions

  1. What is address binding? When can it happen? Mapping program names to memory addresses; at compile time (absolute code), load time (relocatable code) or execution time (needs an MMU).
  2. Logical vs physical address? Logical is generated by the CPU/program; physical is what the memory unit sees. They differ only with execution-time binding.
  3. What does the MMU do? Translates every logical address to a physical one, and checks it is legal (trapping otherwise).
  4. What are the relocation and limit registers? Relocation = the process's starting physical address; limit = its size. Physical = relocation + logical, if logical < limit.
  5. Why does a program crash with a segmentation fault? It accessed an address outside its memory (or with the wrong permission); the MMU traps and the OS sends SIGSEGV.
  6. Static vs dynamic linking? Static copies library code into the executable; dynamic links at run time to a shared library, one copy in RAM for all programs.
  7. What is dynamic loading? Loading a routine only when it's first called (dlopen), saving memory.
  8. First, best, worst and next fit? First: first hole that fits; next: same but resume from the last position; best: smallest that fits; worst: largest.
  9. Internal vs external fragmentation? Internal: wasted inside allocated blocks; external: free memory split into holes between blocks.
  10. What is compaction and when is it possible? Moving processes together to merge holes; only with execution-time (dynamic) relocation, and it is expensive.
  11. How does the buddy system work? Power-of-two blocks, split in halves until the smallest fitting block, merge freed buddies; fast, but internal fragmentation. Linux uses a buddy allocator.
  12. What is ASLR? Address space layout randomization: placing a program's parts at random addresses each run, so attackers can't predict them.

Glossary

Term Meaning in plain words Example
Main memory (RAM) One long row of numbered bytes where running programs live 8 GB of RAM
Address The number of a byte in memory 14000
Pointer A variable holding an address int *p
Hexadecimal Base-16 notation used for addresses 0x2f94
%p printf format that prints a pointer printf("%p", &x)
ASLR Random placement of a program's parts each run addresses change
Address binding Fixing which real address a name uses total → 0x...c014
Compile-time binding Final addresses written by the compiler absolute code
Absolute code Code with fixed, final addresses must load at one place
Load-time binding Loader adds the start address while loading relocatable code
Relocatable code Addresses counted from the program's start "offset 0x2f94"
Loader OS part that copies a program into RAM and starts it
Execution-time binding Address computed on every access while running modern OSes
Logical (virtual) address Address generated by the CPU/program seat 46
Physical address Address seen by the memory hardware seat 1446
Logical address space All logical addresses a program can use 0 .. limit - 1
Physical address space All real RAM addresses
MMU Hardware that translates logical to physical addresses the usher
Relocation (base) register Where the process starts in physical memory 14000
Limit register The process's size; logical must be below it 3000
Trap An interrupt caused by the running program, handing control to the OS address 3500
Segmentation fault (SIGSEGV) The OS stopping a program that touched memory it doesn't own *p at address 16
Static loading Load the whole program before it starts
Dynamic loading Load a routine when it's first called dlopen
dlopen / dlsym / dlclose Load a library / find a function in it / unload it <dlfcn.h>
Function pointer A variable holding a function's address double (*root)(double)
Library Ready-made code you call libm (math)
Linking Joining your code with library code the linker
Static linking Library code copied into the executable libc.a
Dynamic linking Library joined at run time via a stub libc.so.6
Stub Small code that finds the real library function at run time
Shared library One copy in RAM used by all programs .so, .dll
Contiguous allocation Each process gets one unbroken stretch of RAM a bus in side-by-side bays
Fixed partitioning RAM cut into fixed partitions in advance 4 × 100 K
Variable partitioning Each process gets exactly its size
Hole A free gap in memory 200 K free between A and C
First fit First hole big enough
Next fit First fit, resuming from the last position
Best fit Smallest hole big enough
Worst fit Largest hole
Internal fragmentation Wasted space inside an allocated block 30 K in a 100 K partition
External fragmentation Free space split into holes between blocks 400 K free, 350 K fails
50-percent rule With first fit, N blocks lose about 0.5 N to fragmentation
Compaction Moving processes together so holes merge A at 0, C at 300
Degree of multiprogramming How many processes are in memory at once capped by partitions
Buddy system Power-of-two blocks split in halves and merged back 1024 → 512 → 256 → 128
Buddies The two halves of one split block two 128 K blocks
Coalescing Merging free buddies into a bigger block 128 + 128 → 256

Summary

  • Address binding happens at compile, load or execution time. Modern OSes bind at execution time, so the same program gets different addresses each run (live, with ASLR) while distances inside it stay the same.
  • The program uses logical addresses; the MMU turns them into physical addresses: physical = relocation + logical, if logical < limit, else trap (live: Segmentation fault).
  • Dynamic loading (dlopen, live: sqrt(144) = 12) and dynamic linking with shared libraries save memory.
  • Contiguous allocation: fixed partitions → internal fragmentation; variable partitions → holes, chosen by first, next, best or worst fit (live: best fit placed all four; the others failed 400 K) → external fragmentation (live: 400 K free, 350 K fails) → compaction (live: fits) or the buddy system (live: 70 K → 128 K block).

Next episode: Paging and the TLB with numericals: pages, frames, page tables, address translation, the TLB and effective access time.