Memory virtualization

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

- __Address high to low__
- __Address low to high__
*Image taken from [Geeksforgeeks](https://www.geeksforgeeks.org/memory-layout-of-c-program/)*

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);
}


 


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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

 
stacktest

<details class="details details--default" data-variant="default"><summary>Observe and discuss output</summary>
<figure>
  <picture>
    <!-- Auto scaling with imagemagick -->
    <!--
      See https://www.debugbear.com/blog/responsive-images#w-descriptors-and-the-sizes-attribute and
      https://developer.mozilla.org/en-US/docs/Learn/HTML/Multimedia_and_embedding/Responsive_images for info on defining 'sizes' for responsive images
    -->
    
      
        <source class="responsive-img-srcset" srcset="/assets/img/courses/csc331/memory-virtualization/05-480.webp 480w,/assets/img/courses/csc331/memory-virtualization/05-800.webp 800w,/assets/img/courses/csc331/memory-virtualization/05-1400.webp 1400w," type="image/webp" sizes="95vw" />
      
    
    <img src="/assets/img/courses/csc331/memory-virtualization/05.png" width="50%" height="auto" data-zoomable="" loading="lazy" onerror="this.onerror=null; $('.responsive-img-srcset').remove();" />
  </picture>

  
</figure>

</details>
---

## Hands on: where the heap grows?


- Create `arraytest.c` inside the `user` directory, rebuild xv6.  

<details class="details details--default" data-variant="default"><summary>arraytest.c</summary>
<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><table class="rouge-table"><tbody><tr><td class="rouge-gutter gl"><pre class="lineno">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
</pre></td><td class="rouge-code"><pre><span class="c1">// user/arraytest.c</span>
<span class="cp">#include</span> <span class="cpf">"kernel/types.h"</span><span class="cp">
#include</span> <span class="cpf">"user/user.h"</span><span class="cp">
</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
<span class="kt">int</span> <span class="n">arr</span><span class="p">[</span><span class="mi">10</span><span class="p">];</span>
<span class="n">printf</span><span class="p">(</span><span class="s">"[Stack]  &amp;arr[0]     = 0x%lx</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="p">(</span><span class="n">uint64</span><span class="p">)</span><span class="o">&amp;</span><span class="n">arr</span><span class="p">[</span><span class="mi">0</span><span class="p">]);</span>

<span class="kt">int</span> <span class="o">*</span><span class="n">h1</span> <span class="o">=</span> <span class="p">(</span><span class="kt">int</span> <span class="o">*</span><span class="p">)</span><span class="n">sbrk</span><span class="p">(</span><span class="mi">10</span> <span class="o">*</span> <span class="k">sizeof</span><span class="p">(</span><span class="kt">int</span><span class="p">));</span>
<span class="kt">int</span> <span class="o">*</span><span class="n">h2</span> <span class="o">=</span> <span class="p">(</span><span class="kt">int</span> <span class="o">*</span><span class="p">)</span><span class="n">sbrk</span><span class="p">(</span><span class="mi">10</span> <span class="o">*</span> <span class="k">sizeof</span><span class="p">(</span><span class="kt">int</span><span class="p">));</span>
<span class="kt">int</span> <span class="o">*</span><span class="n">h3</span> <span class="o">=</span> <span class="p">(</span><span class="kt">int</span> <span class="o">*</span><span class="p">)</span><span class="n">sbrk</span><span class="p">(</span><span class="mi">10</span> <span class="o">*</span> <span class="k">sizeof</span><span class="p">(</span><span class="kt">int</span><span class="p">));</span>

<span class="n">printf</span><span class="p">(</span><span class="s">"[Heap]   h1          = 0x%016lx</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="p">(</span><span class="n">uint64</span><span class="p">)</span><span class="n">h1</span><span class="p">);</span>
<span class="n">printf</span><span class="p">(</span><span class="s">"[Heap]   h2          = 0x%016lx</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="p">(</span><span class="n">uint64</span><span class="p">)</span><span class="n">h2</span><span class="p">);</span>
<span class="n">printf</span><span class="p">(</span><span class="s">"[Heap]   h3          = 0x%016lx</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="p">(</span><span class="n">uint64</span><span class="p">)</span><span class="n">h3</span><span class="p">);</span>
<span class="n">exit</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
<span class="p">}</span>
</pre></td></tr></tbody></table></code></pre></div></div>

</details>
- Run `arraytest`. 

~~~bash
arraytest
Observe and discuss output
How the heap grows
Acknowledgement

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).
uvmalloc
  • Function implemented in vm.c 


1

 
uint64 uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
Stack: exec.c/kexec()
  • Source code
  • ELF and Program Data is loaded.
  • Empty page for security
  • Page is reserved for stack
Heap: 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.
Linux 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