Address Spaces

2026-11-18 · virtualisation memory

notes / Operating Systems / 01_vir

OS

The Abstraction: Address Spaces

Early Systems

Multiprogramming and Time Sharing

so now you have to context switch and stuff, where do you store program runtime memory?

Error

i/o to is disk slow as fuck, like seriously slow

how do you do this?

Contiguous Allocation

We could contiguously allocate chunks of memory for each program

Memory Isolation

people want protection of their context from other processes too, can't have your pokemon gameplay being overwritten by someone who forgot to free() their variables right, which feels like a very real possibility in a contiguous system

But one notices very quickly this does not scale. Suppose some programs died and freed their memory, would the free hole be enough to fit another program? Moving memory around is very expensive (called Defragmentation) and should not be considered an option.

In contiguous allocation systems one of 3 strategies is used to choose a free hole for a new process

ca hole

  1. First Fit (the first suitable hole is returned) which is fairly fast.
  2. Best Fit (the smallest suitable hole is returned)
  3. Worst Fit (the largest suitable hole is returned)

And each search method can either start from the beginning of memory every time or frome wherever it ended its the last time.

Every contiguous allocation system would suffer from the issue of External Fragmentation, where holes too small to be useful are left in the main memory. As a general rule

50% Rule

assuming N segments each of size S in the main memory, on average N/2 segments will be wasted on external fragmentation, this is massively inefficient.

The Address Space

first create an abstraction The ELF Format

what do you need in the memory assigned to a process?

how do you organise this?

Next, we have the two regions of the address space that may grow (and shrink) while the program runs. Those are the heap and the stack. We place them like this because each wishes to be able to grow, and by putting them at opposite ends of the address space, we can allow such growth: they just have to grow in opposite directions.

this is just a convention tho

Goals

The fundamental idea behind a "virtual memory" is the fact that large programs do not need their entire (possibly very large) memory loaded at the same time. What the cache is to the main memory, the main memory is to the disk, only storing the current working memory regions.

How do you ensure every program gets the memory they need? And in the most efficient manner possible?

and thus we come to the job of the OS, virtualize the memory to provide the user/process this abstraction. what are the objectives of such a virtual memory system?

  1. transparency (invisible): process should not know it's memory is virtualised
  2. efficiency: virtualization should not make the running program significantly slower
  3. protection: protect processes from one another

Tip

strive for isolation. the linux kernel is monolithic. microkernels are being designed

Every Address you See is Virtual

any address you can see as a programmer of a user-level program is a virtual address

check out

#include <stdio.h>
#include <stdlib.h>
int main(void) {
  printf("location of code: %p\n", main);
  printf("location of heap: %p\n", malloc(10e4));
  int x = 3;
  printf("location of stack: %p\n", &x);
  return x;
}
❯ ./va
location of code: 0x60cdcad5e159
location of heap: 0x60cdee9896b0
location of stack: 0x7ffcde430584

the output follows perfectly the layout of the address space

linked from