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 namedsqrtinside it. We store it in a function pointerroot(a variable that holds the address of a function) and call it.dlcloseunloads 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.
- 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 - 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 - 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 - 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
- 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).
- 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.
- What does the MMU do? Translates every logical address to a physical one, and checks it is legal (trapping otherwise).
- What are the relocation and limit registers? Relocation = the process's starting physical address; limit = its size. Physical = relocation + logical, if logical < limit.
- 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.
- 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.
- What is dynamic loading? Loading a routine only when it's first called (
dlopen), saving memory. - 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.
- Internal vs external fragmentation? Internal: wasted inside allocated blocks; external: free memory split into holes between blocks.
- What is compaction and when is it possible? Moving processes together to merge holes; only with execution-time (dynamic) relocation, and it is expensive.
- 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.
- 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.