CSC 322

SYSTEMS PROGRAMMING

VIRTUAL MEMORIES
(based on chapter 9)

Computer Systems: A Programmer’s Perspective 3rd Edition 1

 PREDISCUSSION

oProgram must be loaded into memory to run

• All necessary code (including ECF) and data must be resided in memory.
• But… consider a machine with 4 GB memory. How can we run 16 GB
program?
 Nowadays, program and programs could be larger than physical memory

o Keys for solution

• Code needs to be in memory to execute, but entire program rarely used
• Entire program code is not needed at same time
• ECF, unusual routines, large data structures
o Thus, consider ability to execute partially-loaded program
• Program no longer constrained by limits of physical memory
• Machine has a virtual memory, which can be much larger than memory.

Computer Systems: A Programmer’s Perspective 3rd Edition 2

 VIRTUAL MEMORY (VM)
o Separation of user logical memory from physical memory (PM)
• Only part of the program needs to be in memory for execution
• Logical address space can therefore be much larger than physical
address space
• Allows address spaces to be shared by several processes
o Benefits
• Allows for more efficient process creation
• More programs running concurrently
• Less I/O needed to load or swap processes
o Virtual memory can be implemented via:
• Demand paging

Computer Systems: A Programmer’s Perspective 3rd Edition 3

 MAPPING VM TO PHYSICAL MEMORY
page 0
Sum()
Mul() Mul()
Div()
Sub() Main()
Parse()

…
Exit() Load
Program- Print() necessary Sub()
Calculator Main() pages only
Print()

…
Page V

(empty)
Page v
Logical Memory Physical Memory
Disk (=Virtual memory) (=Main memory)

o Issues:
• How to allocate and recognize pages: address
• How to discover pages in main memory: page table
Computer Systems: A Programmer’s Perspective 3rd Edition 4
 AGENDA

oAddress spaces
oVM as a tool for caching
oVM as a tool for memory management and protection
oAddress translation
oMemory Mapping

Computer Systems: A Programmer’s Perspective 3rd Edition 5

ADDRESS SPACES

Computer Systems: A Programmer’s Perspective 3rd Edition 6

 WHY VIRTUAL MEMORY (VM)?

oUses main memory efficiently

• Use DRAM as a cache for parts of a virtual address space
oSimplifies memory management
• Each process gets the same uniform linear address space
oIsolates address spaces
• One process can’t interfere with another’s memory
• User program cannot access privileged kernel information and code

Computer Systems: A Programmer’s Perspective 3rd Edition 7

 A SYSTEM USING PHYSICAL ADDRESSING

oUsed in “simple” systems like embedded microcontrollers in

devices like cars, elevators, and digital picture frames
Main memory
0:
1:
Physical address 2:
(PA) 3:
CPU 4:
4
5:
6:
7:
8:

...
M-1:

Data word

Computer Systems: A Programmer’s Perspective 3rd Edition 8

 A SYSTEM USING VIRTUAL ADDRESSING

oUsed in all modern servers, laptops, and smart phones

oOne of the great ideas in computer science
Main memory
0:
CPU Chip 1:
2:
Virtual address Physical address
(VA) (PA)
3:
CPU MMU 4:
4100 4804100
5:
6:
7:
8:

...
M-1:

Data word

Computer Systems: A Programmer’s Perspective 3rd Edition 9

 ADDRESS SPACES

oLinear address space:

• Ordered set of contiguous non-negative integer addresses:
{0, 1, 2, 3 … }

oPhysical address space:

• Set of M = 2m physical addresses
{0, 1, 2, 3, …, M-1}

oVirtual address space:

• Set of N = 2n virtual addresses
{0, 1, 2, 3, …, N-1}

Computer Systems: A Programmer’s Perspective 3rd Edition 10

VM AS A TOOL FOR CACHING

Computer Systems: A Programmer’s Perspective 3rd Edition 11

 VM AS A TOOL FOR CACHING
oConceptually, virtual memory is an array of N contiguous bytes
stored on disk.
• The contents of the array on disk are cached in physical memory
(DRAM cache)
• These cache blocks are called pages (size is P = 2p bytes)
Virtual memory Physical memory
0
VP 0 Unallocated
0
VP 1 Cached Empty PP 0
Uncached PP 1
Unallocated Empty
Cached
Uncached Empty
Cached PP 2m-p-1
M-1
VP 2n-p-1 Uncached
N-1

Virtual pages (VPs) Physical pages (PPs)

stored on disk cached in DRAM

Computer Systems: A Programmer’s Perspective 3rd Edition 12

 DRAM CACHE ORGANIZATION
o DRAM cache organization driven by the enormous miss penalty
• DRAM is about 10x slower than SRAM
• Disk is about 10,000x slower than DRAM

o Consequences
• Large page (block) size: typically 4 KB, sometimes 4 MB
• Fully associative
 Any VP can be placed in any PP
 Requires a “large” mapping function – different from cache memories
• Highly sophisticated, expensive replacement algorithms
 Too complicated and open-ended to be implemented in hardware
• Write-back rather than write-through

Computer Systems: A Programmer’s Perspective 3rd Edition 13

 ENABLING DATA STRUCTURE: PAGE TABLE

o A page table is an array of Page Table Entries (PTEs) that maps

virtual pages to physical pages (PPs). (here 4 PPs are assigned)
• Per-process kernel data structure in DRAM
Physical memory
Physical page (DRAM)
number or
VP 1 PP 0
Valid disk address
unallocated
VP 2
PTE 0 0 memorynull VP 7
1 VP 4 PP 3
cached 1- oxAAB
0 uncached-ox1F
1 Virtual memory
0 null (disk)
0
VP 1
PTE 7 1
VP 2
Memory resident
page table VP 3
(DRAM) VP 4
o Note that page which is not allocated VP 6
has null value for the address! VP 7
Computer Systems: A Programmer’s Perspective 3rd Edition 14
 PAGE HIT

oReference to VM word that is in physical memory

• DRAM cache hit
Physical memory
Physical page
Virtual address (DRAM)
number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 4 PP 3
1
0
1
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
VP 6
VP 7
Computer Systems: A Programmer’s Perspective 3rd Edition 15
 PAGE MISS

oReference to VM word that is NOT in physical memory

• DRAM cache miss
Physical memory
Physical page
Virtual address (DRAM)
number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 4 PP 3
1
0
1
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
VP 6
VP 7
Computer Systems: A Programmer’s Perspective 3rd Edition 16
 HOW TO HANDLE PAGE FAULT

oPage miss causes page fault (an exception)

• Is it handled as a fault or an abort?
Physical memory
Physical page
Virtual address (DRAM)
number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 4 PP 3
1
0
1
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
VP 6
VP 7
Computer Systems: A Programmer’s Perspective 3rd Edition 17
 HOW TO HANDLE PAGE FAULT

oPage miss causes page fault (an exception)

• Page fault handler selects a victim to be evicted (e.g., VP 4)
Physical memory
Physical page
Virtual address (DRAM)
number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 4 PP 3
1
0
1
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
VP 6
VP 7
Computer Systems: A Programmer’s Perspective 3rd Edition 18
 HOW TO HANDLE PAGE FAULT

oPage miss causes page fault (an exception)

• Page fault handler selects a victim to be evicted (VP 4 in the example)
Physical memory
Physical page
Virtual address (DRAM)
number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 3 PP 3
1
1
0
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
o The missed page is copied (VP 3)
VP 6
• Offending instruction is restarted: page hit
VP 7
Computer Systems: A Programmer’s Perspective 3rd Edition 19
 DEMAND PAGING

oThis procedure is called

• System waits until the miss to copy the page to DRAM
Physical memory
Physical page
Virtual address (DRAM)
number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 3 PP 3
1
1
0
0 null Virtual memory
0 (disk)
PTE 7 1 VP 1
Memory resident VP 2
page table
VP 3
(DRAM)
VP 4
o Note that if there are free space for PP in DRAM,
VP 6
• there would be no need to replace. VP 7
Computer Systems: A Programmer’s Perspective 3rd Edition 20
 ALLOCATING PAGES

oAllocating a new page (VP 5) of virtual memory.

• Call malloc
Physical memory
Physical page (DRAM)
number or
VP 1 PP 0
Valid disk address
VP 2
PTE 0 0 null
VP 7
1 VP 3 PP 3
1
1
0 Virtual memory
0 (disk)
0 VP 1
PTE 7 1
VP 2
Memory resident
VP 3
page table
(DRAM) VP 4
VP 5
VP 6
VP 7
Computer Systems: A Programmer’s Perspective 3rd Edition 21
 LOCALITY TO THE RESCUE AGAIN

oVirtual memory seems terribly inefficient, but it works because

of locality.
oAt any point in time, programs tend to access a set of active
virtual pages called the working set
• Programs with better temporal locality will have smaller working sets
• If (working set size < main memory size)
 Good performance for one process after compulsory misses
• If (SUM(working set sizes) > main memory size )
 Thrashing: Performance meltdown where pages are swapped (copied) in
and out continuously

Computer Systems: A Programmer’s Perspective 3rd Edition 22

VM AS A TOOL FOR MEMORY
MANAGEMENT AND
PROTECTION

Computer Systems: A Programmer’s Perspective 3rd Edition 23

 MEMORY MANAGEMENT
o Key idea: each process has its own virtual address space
• It can view memory as a simple linear array
• Mapping function scatters addresses through physical memory
 Well-chosen mappings can improve locality

0 Address 0
Virtual Physical
Address Space
translation Address
VP 1
for Process 1: VP 2 PP 2
Space
... (DRAM)

N-1
(e.g., read-only
PP 6
• Each virtual page can be mapped to library code)

any physical page

• A virtual page can be stored in different ...
physical pages at different times
M-1
Computer Systems: A Programmer’s Perspective 3rd Edition 24
 MEMORY MANAGEMENT - SHARING
o Suppose that another process needs to be loaded
• In which PPs will they be loaded?
o Sharing code and data among processes
• Map virtual pages to the same physical page (here: PP 6)

0 Address 0
Virtual Physical
Address Space
translation Address
VP 1
for Process 1: VP 2 PP 2
Space
... (DRAM)

N-1
(e.g., read-only
PP 6
library code)
0
Virtual
PP 8
Address Space VP 1
for Process 2: VP 2
... ...
N-1 M-1
Computer Systems: A Programmer’s Perspective 3rd Edition 25
 SIMPLIFYING LINKING AND LOADING
oLinking
• Each program has similar virtual Kernel virtual memory
Memory
invisible to
address space User stack user code
• Code, data, and heap always start (created at runtime)
%rsp
at the same addresses. (stack
pointer)

oLoading Memory-mapped region for

•
shared libraries
execve allocates virtual pages
for .text and .data sections &
creates PTEs marked as invalid
brk
• The .text and .data sections Run-time heap
(created by malloc)
are copied, page by page, on
Read/write segment
demand by the virtual memory (.data, .bss) Loaded from
system Read-only segment the executable
(.init, .text, .rodata) file
0x400000
Unused
0

Computer Systems: A Programmer’s Perspective 3rd Edition 26

 MEMORY PROTECTION

oExtend PTEs with permission bits

• MMU checks these bits on each access
Physical
Process i: SUP READ WRITE EXEC Address Address Space
VP 0: No Yes No Yes PP 6
VP 1: No Yes Yes Yes PP 4
VP 2: PP 2
Yes Yes Yes No PP 2
•
• PP 4
•
PP 6
Process j: SUP READ WRITE EXEC Address
PP 8
VP 0: No Yes No Yes PP 9 PP 9
VP 1: Yes Yes Yes Yes PP 6
VP 2: No Yes Yes Yes PP 11 PP 11

Computer Systems: A Programmer’s Perspective 3rd Edition 27

ADDRESS TRANSLATION

Computer Systems: A Programmer’s Perspective 3rd Edition 28

 VM ADDRESS TRANSLATION
o Virtual Address Space
• 𝑉 = {0, 1, … , 𝑁– 1} N= P
n

o Physical Address Space m

• M=P P = 2n-p
𝑃 = {0, 1, … , 𝑀– 1}

o Address Translation
• 𝑴𝑨𝑷: 𝑽 → 𝑷 𝑼 {∅}
• For virtual address a:
 𝑴𝑨𝑷(𝒂) = 𝒂’ if data at virtual address a is at physical address a’ in P
 𝑴𝑨𝑷(𝒂) = ∅ if data at virtual address a is not in physical memory
 Either invalid or stored on disk

Computer Systems: A Programmer’s Perspective 3rd Edition 29

 ADDRESS TRANSLATION SYMBOLS
o Basic Parameters
• N = 2n : Number of addresses in virtual address space
• M = 2m : Number of addresses in physical address space
• P = 2p : Page size (bytes)
o Components of the virtual address (VA)
• TLBI: TLB index
• TLBT: TLB tag
• VPO: Virtual page offset
• VPN: Virtual page number
o Components of the physical address (PA)
• PPO: Physical page offset (same as VPO)
• PPN: Physical page number

Computer Systems: A Programmer’s Perspective 3rd Edition 30

 ADDRESS TRANSLATION WITH A PAGE TABLE
Virtual address
Page table n-1 p p-1 0
base register Virtual page number (VPN) Virtual page offset (VPO)
(PTBR)

Page table
Valid Physical page number (PPN)
Physical page table
address for the current
process

Valid bit = 0:
Page not in memory
Valid bit = 1
(page fault)

m-1 p p-1 0
Physical page number (PPN) Physical page offset (PPO)
Physical address

Computer Systems: A Programmer’s Perspective 3rd Edition 31

 ADDRESS TRANSLATION IN PAGE HIT
2
CPU Chip PTEA
1
PTE
VA
CPU MMU 3
Cache/
PA Memory
4

Data
5

1) Processor sends virtual address to MMU

2-3) MMU fetches PTE from page table in memory

4) MMU sends physical address to cache/memory

5) Cache/memory sends data word to processor

Computer Systems: A Programmer’s Perspective 3rd Edition 32
 ADDRESS TRANSLATION IN PAGE FAULT
Exception
Page fault handler
4

2
CPU Chip PTEA Victim page
1
5
VA PTE Cache/
CPU MMU Disk
7 3 Memory
New page
6

1) Processor sends virtual address to MMU

2-3) MMU fetches PTE from page table in memory
4) Valid bit is zero, so MMU triggers page fault exception
5) Handler identifies victim (and, if dirty, pages it out to disk)
6) Handler pages in new page and updates PTE in memory
7) Handler returns to original process, restarting faulting instruction
Computer Systems: A Programmer’s Perspective 3rd Edition 33
 INTEGRATING VM AND CACHE

PTE

CPU Chip PTEA

PTE
hit

PTEA PTEA PTEA

miss
CPU L1
VA MMU cache Memory
PA PA PA
miss

PA Data
hit

Data

Computer Systems: A Programmer’s Perspective 3rd Edition 34

 SPEEDING UP TRANSLATION WITH A TLB

oPage table entries (PTEs) are cached in L1 like any other

memory word
• PTEs may be evicted by other data references
• PTE hit still requires a small L1 delay
oSolution: Translation Lookaside Buffer (TLB)
• Small set-associative hardware cache in MMU
• Maps virtual page numbers to physical page numbers
• Contains complete page table entries for small number of pages

Computer Systems: A Programmer’s Perspective 3rd Edition 35

 ACCESSING THE TLB

oMMU uses the VPN portion of the virtual address to access

the TLB: T = 2t sets
VPN
TLBT matches tag of
n-1 p+t p+t-1 p p-1 0
line within set
TLB tag (TLBT) TLB index (TLBI) VPO

Set 0 v tag PTE v tag PTE TLBI selects the set

Set 1 v tag PTE v tag PTE

…

Set T-1 v tag PTE v tag PTE

Computer Systems: A Programmer’s Perspective 3rd Edition 36

 TLB HIT
oA TLB hit eliminates a memory access

CPU Chip
TLB
2 PTE
VPN 3

1
VA PA
CPU MMU
4 Cache/
Memory

Data
5

Computer Systems: A Programmer’s Perspective 3rd Edition 37

 TLB MISS

oA TLB miss incurs an additional memory access (the PTE)

• Fortunately, TLB misses are rare.

CPU Chip
TLB
4
2 PTE
VPN

1 3
VA PTEA
CPU MMU
Cache/
PA Memory
5

Data
6

Computer Systems: A Programmer’s Perspective 3rd Edition 38

 MULTI-LEVEL PAGE TABLES
Level 2
oSuppose: Tables
• 4KB (212) page size, 48-bit address space, 8-byte PTE
oProblem:
• Would need a 512 GB page table! Level 1
Table
 248 * 2-12 * 23 = 239 bytes

oCommon solution: Multi-level page table

...
oExample: 2-level page table
• Level 1 table: each PTE points to a page table

...
(always memory resident)
• Level 2 table: each PTE points to a page
(paged in and out like any other data)

Computer Systems: A Programmer’s Perspective 3rd Edition 39

 A TWO-LEVEL PAGE TABLE HIERARCHY
Level 1 Level 2 Virtual
page table page tables memory
0
VP 0

PTE 0 ...
PTE 0
... VP 1023 2K allocated VM pages
PTE 1 for code and data
PTE 1023 VP 1024
PTE 2 (null)
...
PTE 3 (null)
VP 2047
PTE 4 (null) PTE 0
PTE 5 (null) ...
PTE 6 (null) PTE 1023
PTE 7 (null) Gap 6K unallocated VM pages

PTE 8
1023 null
(1K - 9) PTEs
null PTEs PTE 1023 1023
unallocated 1023 unallocated pages
pages
VP 9215 1 allocated VM page
32 bit addresses, 4KB pages, 4-byte PTEs for the stack
...
Computer Systems: A Programmer’s Perspective 3rd Edition 40
 TRANSLATING WITH A K-LEVEL PAGE TABLE

Page table
base register
(PTBR)
VIRTUAL ADDRESS
n-1 p-1 0
VPN 1 VPN 2 ... VPN k VPO

Level 1 Level 2 Level k

page table page table page table
... ...

PPN

m-1 p-1 0
PPN PPO
PHYSICAL ADDRESS

Computer Systems: A Programmer’s Perspective 3rd Edition 41

MEMORY MAPPING

Computer Systems: A Programmer’s Perspective 3rd Edition 42

 MEMORY MAPPING

oVM areas initialized by associating them with disk objects.

• Process is known as memory mapping.
oArea can be backed by (i.e., get its initial values from) :
• Regular file on disk (e.g., an executable object file)
 Initial page bytes come from a section of a file
• Anonymous file (e.g., nothing)
 First fault will allocate a physical page full of 0's (demand-zero page)
 Once the page is written to (dirtied), it is like any other page

oDirty pages are copied back and forth between memory and
a special swap file.

Computer Systems: A Programmer’s Perspective 3rd Edition 43

 MAPPING OBJECTS
o Process 1 maps an object.
Process 1 Physical Process 2
memory virtual memory
• What if the object can be
virtual memory
shared with Process 2?

Shared
object

Computer Systems: A Programmer’s Perspective 3rd Edition 44

 MAPPING SHARED OBJECTS
o Process 2 maps the shared
Process 1 Physical Process 2 object.
virtual memory memory virtual memory

o Notice how the virtual

addresses can be different.

Shared
object

Computer Systems: A Programmer’s Perspective 3rd Edition 45

 SHARING REVISITED: PRIVATE COW OBJECTS

o Two processes mapping a

Process 1 Physical Process 2 private copy-on-write
virtual memory memory virtual memory
(COW) object.
• Area flagged as private
copy-on-write

o PTEs in private areas are

Private flagged as read-only
copy-on-write
area

Private
copy-on-write object

Computer Systems: A Programmer’s Perspective 3rd Edition 46

 PRIVATE COPY-ON-WRITE (COW) OBJECTS

o Instruction writing to
Process 1 Physical Process 2
virtual memory memory virtual memory
private page triggers
protection fault.
Copy-on-write
• Handler creates new R/W
page.
• Instruction restarts upon
handler return.
Write to private
copy-on-write
page
o Copying deferred as long
as possible!

Private
copy-on-write object

Computer Systems: A Programmer’s Perspective 3rd Edition 47

 THE FORK FUNCTION REVISITED
o VM and memory mapping explain how fork provides private address
space for each process.
o To create virtual address for new new process
• Create exact copies of current mm_struct, vm_area_struct, and page
tables.
• Flag each page in both processes as read-only
• Flag each vm_area_struct in both processes as private COW

o On return, each process has exact copy of virtual memory

o Subsequent writes create new pages using COW mechanism.
o Issue: copying a page is expensive!
• vfork() may skip duplicate of parent’s address space in a condition: child
process calls only exec().

Computer Systems: A Programmer’s Perspective 3rd Edition 48

 THE EXECVE FUNCTION REVISITED
User stack Private, demand-zero o To load and run a new program
a.out in the current process
using execve:
libc.so
.data Memory mapped region
o Free vm_area_struct’s
Shared, file-backed and page tables for old areas
.text for shared libraries

o Create vm_area_struct’s
and page tables for new areas
Runtime heap (via malloc) Private, demand-zero • Programs and initialized data
backed by object files.

a.out
Uninitialized data (.bss) Private, demand-zero
• .bss and stack backed by
.data Initialized data (.data) anonymous files .
Private, file-backed
.text Program text (.text) o Set PC to entry point in .text
0 • Linux will fault in code and
data pages as needed.

Computer Systems: A Programmer’s Perspective 3rd Edition 49

 USER-LEVEL MEMORY MAPPING
void *mmap(void *start, int len,
int prot, int flags, int fd, int offset)
o Map len bytes starting at offset offset of the file specified by file
description fd, preferably at address start
• start: may be 0 for “pick an address”
• prot: PROT_READ, PROT_WRITE, ...
• flags: MAP_ANON, MAP_PRIVATE, MAP_SHARED, ...

o Return a pointer to start of mapped area (may not be start)

Computer Systems: A Programmer’s Perspective 3rd Edition 50

 USER-LEVEL MEMORY MAPPING
void *mmap(void *start, int len,
int prot, int flags, int fd, int offset)

len bytes

start
(or address
len bytes chosen by kernel)

offset
(bytes)

0 0
Disk file specified by Process virtual memory
file descriptor fd
Computer Systems: A Programmer’s Perspective 3rd Edition 51
 USING MMAP TO COPY FILES

oCopying a file to stdout without transferring data to user

space .
#include "csapp.h" /* mmapcopy driver */
int main(int argc, char **argv)
void mmapcopy(int fd, int size) {
{ struct stat stat;
int fd;
/* Ptr to memory mapped area */
char *bufp; /* Check for required cmd line arg */
if (argc != 2) {
bufp = Mmap(NULL, size, printf("usage: %s <filename>\n",
PROT_READ, argv[0]);
MAP_PRIVATE, exit(0);
fd, 0); }
Write(1, bufp, size);
return; /* Copy input file to stdout */
} fd = Open(argv[1], O_RDONLY, 0);
Fstat(fd, &stat);
mmapcopy(fd, stat.st_size);
exit(0);
}

Computer Systems: A Programmer’s Perspective 3rd Edition 52

 SUMMARY

oProgrammer’s view of virtual memory

• Each process has its own private linear address space
• Cannot be corrupted by other processes
oSystem view of virtual memory
• Uses memory efficiently by caching virtual memory pages
 Efficient only because of locality
• Simplifies memory management and programming
• Simplifies protection by providing a convenient interpositioning point to
check permissions

Computer Systems: A Programmer’s Perspective 3rd Edition 53