Memory virtualization

In the beginning …

Early systems
  • Computers run one job at a time.
  • The OS was preloaded into memory and consisted of a set of routines.
  • There was one running program that uses the rest of memory.
Multiprogramming and time sharing
  • Demands for
    • Utilization
    • Efficiency
    • Interactivity
  • Multiple processes ready to run at a given time.
  • The OS switches between them.
  • One approach is to run one process at a time and still give it full access to all memory (just like the early days …).
  • This requires switching processes from memory.

Multiprogramming and time sharing

Recall: Running one process at a time with full memory access
  • This solution does not scale as memory grows.
System event Size Latency
CPU   <1ns
L1 cache 32KB 1ns
L2 cache 256KB 4ns
L3 cache >8MB 40ns
DDR RAM 4GB-1TB 80ns
What we want to do
  • Leave processes in memory and let OS implement an efficient time sharing/switching mechanism.
  • A new demand: protection (through isolation)

Address space

INFOAddress high to low
INFOAddress low to high

Image taken from Geeksforgeeks

Hands on: Where the stack grows?

stacktest.c 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

 
// user/stacktest.c
#include "kernel/types.h"
#include "user/user.h"

void f2() {
  int a = 5, b = 6;
  printf("In f2: &a = 0x%lx, &b = 0x%lx\n", (uint64)&a, (uint64)&b);
}

void f1() {
  int x = 3, y = 4;
  int arr[5];
  printf("In f1: &x = 0x%lx, &y = 0x%lx\n", (uint64)&x, (uint64)&y);
  printf("Address of arr       = 0x%lx\n", (uint64)arr);
  printf("Address of arr[0]    = 0x%lx\n", (uint64)&arr[0]);
  printf("Address of arr[1]    = 0x%lx\n", (uint64)&arr[1]);  f2();
}

int main() {
  int m = 1, n = 2;
  printf("In main: &m = 0x%lx, &n = 0x%lx\n", (uint64)&m, (uint64)&n);
  f1();
  exit(0);
}
Observe and discuss output

Hands on: where the heap grows?

arraytest.c 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

 
// user/arraytest.c
#include "kernel/types.h"
#include "user/user.h"

int main() {
int arr[10];
printf("[Stack]  &arr[0]     = 0x%lx\n", (uint64)&arr[0]);

int *h1 = (int *)sbrk(10 * sizeof(int));
int *h2 = (int *)sbrk(10 * sizeof(int));
int *h3 = (int *)sbrk(10 * sizeof(int));

printf("[Heap]   h1          = 0x%016lx\n", (uint64)h1);
printf("[Heap]   h2          = 0x%016lx\n", (uint64)h2);
printf("[Heap]   h3          = 0x%016lx\n", (uint64)h3);
exit(0);
}
Observe and discuss output
How the heap grows
SUCCESSAcknowledgement

This section is developed based on Ellis Weaverkreider’s question in Fall 2025

  • xv6’s explicitly write code in such a way that stack space is created immediately after the creation of EFL segments (text/bss/data).
INFOuvmalloc
  • Function implemented in vm.c 


1

 
uint64 uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
INFOStack: exec.c/kexec()
  • Source code
  • ELF and Program Data is loaded.
  • Empty page for security
  • Page is reserved for stack
INFOHeap: sysproc.c/sys_sbrk()
  • Source code
  • Starting from top of program size (myproc() -> sz)
  • Allocate additional memory for heap and move program size to that location.
INFOLinux comparison 


1
2
3

 
/* Do this so that we can load the interpreter, if need be.  We will
change some of these later */
retval = setup_arg_pages(bprm, randomize_stack_top(STACK_TOP), executable_stack);

What is address space, really?

Goals of memory virtualization