22. Virtual Memory: Basics
EECS 370 – Introduction to Computer Organization – Fall 2020
Satish Narayanasamy
EECS Department
University of Michigan in Ann Arbor, USA
© Narayanasamy 2020
The material in this presentation cannot be copied in any form without written permission
Announcement
Project 3 due date extended to Tuesday November 17 11:59PM EST
2
Interactive Cache Simulator
http://vhosts.eecs.umich.edu/370simulators/cache/simulator.html
3
Go check cache organization in your computer!
For Linux you can use following command:
$:sudo dmidecode -t cache
DMI—desktop management interface
(you may need to install dmidecode on your machine)
4
3 Levels of Caches on a Modern Computer
5
Memory System: Learning objective
LC2k program
MIPS program
ARM64 or x86-64 program
can access can access can access
218 bytes of memory
232 bytes of memory
264 bytes of memory (18 billion billion bytes!)
Problem: No one memory technology is both fast and big to store all of program’s data Goal: Design a fast, big, and cheap memory system to store a program’s data.
6
Recap from Lecture 17
Memory Pyramid
done
Cost Expensive Size Small
Fast
Cache (SRAM)
Main memory (DRAM)
SSD (flash, PCM) Hard disk
today
Slow
Cost Cheap Size Big
7
Recap from Lecture 17
A modern computing system is composed of several memory devices
Main memory (DRAM)
SSD Flash Hard disk
Processor
w/ three levels of caches
Focus today: Virtual Memory
8
Virtual Memory
9
What is Virtual Memory?
An operating system (OS) functionality that enables multiple concurrently running programs to share physical memory and swap disk space.
Hardware (TLB – a special cache) helps OS efficiently implement this functionality
10
Virtual Memory Roles
Capacity: Main memory is not enough
Problem:
Modern systems can afford ~128 GBs DRAM space = 2^37 bytes. Programs written in 64-bit ISA need 2^64 bytes! Need to run many programs simultaneously on the same machine. Each program may require GBs of memory.
Solution:
Provide an illusion of storage large enough for 2^64 bytes of data for all concurrently running programs Manage main memory like an exclusive fully-associative cache. Spills to disk.
Security features
Isolation
Permissions
Programs may want to share data and code (e.g., library)
Programs may want to disable read/write permissions to some portions of memory
e.g., mark instructions are read-only, no read/write permission for unallocated heap
Unrelated programs must not have access to each other’s data
11
How to be not limited by DRAM capacity?
Use disk as “extra” space in case main memory capacity is exhausted This space in disk is called swap partition in Linux-based systems
For fun check swap space in a linux system by:
$: top
13
How to be not limited by DRAM capacity?
Virtual Memory (defined by ISA)
Page Table
(OS data structure)
0x5000 0x0000
DRAM
(physical memory)
0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 0x6000 0x7000 0x8000 0x9000
0x0000 0x1000
0xF000 0x10000
0x9000
2^64
14
D1000
DISK
D1000
0x1A000
Grand illusion of virtual memory:
DRAM size + swap disk size << 2^64 bytes
No memory is enough for a 64-bit ISA (ARM64) program
Hard disk cost for storing all addresses accessible to a ARM64 program $760 million for 2^64 bytes
Don’t provision 264 bytes of storage (even a hard disk is too expensive!)
Fake it. Use “virtual memory” to provide an illusion that ISA’s entire address space is available. A few TB is enough for most desktop machines today, or a smartphone in a few years Computer “crashes” if your program exceeds machine’s available swap space on disk
15
Recap from Lecture 17
Central to Virtual memory: Address translation
Address produced by executing a load or store is a “virtual address”
In 64-bit ISA, it is a 64-bit address, capable of addressing 2^64 bytes
Virtual memory is a hardware and software co-designed system that dynamically translates a load/store’s
0x800
virtual address
(which the programmer (load/store) sees as an array of bytes) to a
physical address
Disk ID 803C4
(which the hardware uses to either index DRAM or identify where the storage resides on disk)
16
What are Pages?
Divide memory in chunks of Pages (e.g., 4KB for x86)
Size of physical page = size of virtual page
A virtual address consists of
- A virtual page number
- A page offset field (low order bits of the address)
Virtual address
63 11 0
Virtual page number
Page offset
Physical page number
Page offset
Physical address
29
11 0
Virtual Page accesses that are not found in physical memory (DRAM) are called Page Faults
17
Data structure used for address translation: Page Table Each process has its own page table
maintained by the operating system Page table contains address translation
i.e., virtual page number ➔ physical page number Page tables are stored in memory.
OS knows the physical address of a program’s page table.
No address translation is required by the OS for accessing the page tables
18
Address translation using Page table
Page table register
The Page table register points to the beginning of the page table
Virtual Address
Page Table
Virtual page number
Page offset
valid
Physical page number
1
Physical page number
Physical page number
Page offset
Physical Address
19
Address translation: Example
Page table register
Virtual address = 0x000040F3
valid
Physical page number
1
0x00004
0x020C0
0x0F3
Physical address = 0x020C00F3
0x020C0
0x0F3
20
Page faults
Page table register
Physical page number
valid
0x00002
0x082
0
Disk address
Exception: page fault (handled by OS)
Page faults :: main memory similar to
Cache miss :: processor caches
21
1. Stop this process
2. Pick page to replace 3. Write back data
4. Get referenced page 5. Update page table 6. Reschedule process
How do we find it on disk?
That is not a hardware problem! Go take EECS 482!
This is the operating system’s job. Most operating systems partition the disk into logical devices
(C: , D: , /home, etc.)
They also have a hidden partition to support the disk portion of virtual memory Swap partition on UNIX machines
You then index into the correct page in the swap partition.
22
Operating System handles Page faults
Slide credit: Operating System Concepts Silberschatz, Galvin and Gagne
23
Who implements Virtual Memory (VM)?
When OS creates a process, it allocates a page table to it.
OS (page fault handler) makes changes to a page table Includes page replacement
Moves data from main memory to and fro swap space on disk
Address translation is needed for every load/store:
Reading from the page table every load/store would be expensive Processor provides special support (TLB) to speed this up
VM is a good example for hardware-software co-design
*(do not confuse VM for “Virtual Machine”, which is another concept entirely)
24
Main memory Vs Cache : Similarities and Differences
Data granularity:
Cache: “cache block”
Main memory: “page”
Who decides where to store and what to replace?
Cache:
Main memory:
On a “miss” Cache:
Main memory:
Processor Operating system
Go to main memory. Processor fetches data. Go to disk. OS page fault handler fetches data.
OS treats main memory like an exclusive fully-associative “cache”
Instead of searching by comparing tags, OS uses page table to find a page’s storage location Exclusive: Data is either in main memory or in disk, not both
Processor’s last-level caches are inclusive set-associative
25
Class Problem
Assume the following:
20-bit byte-addressable ISA (virtual address space) Physical memory size : 16 KB Page size : 4 KB LRU replacement policy for main memory
Assume the following initial page-table state:
Page table
Virtual page 0
Virtual page 1
Other physical pages are invalid.
physical page 0. Can never be evicted (pinned) physical page 1.
physical page 2.
Answer the following:
# physical pages = ________________________
# virtual pages = ___________________________ Page offset size = ___________________________ Fill in the table on the next slide for each reference
26
is in is in is in
Class Problem
Assume the following:
20-bit byte-addressable ISA (virtual address space) Physical memory size : 16 KB Page size : 4 KB LRU replacement policy for main memory
Assume the following initial page-table state:
Page table
Virtual page 0
Virtual page 1
Other physical pages are invalid.
physical page 0. Can never be evicted (pinned) physical page 1.
physical page 2.
is in is in is in
Answer the following:
# physical pages = 16 KB / 4 KB = 4 pages.
# virtual pages = 2^20 / 4 KB = 2^8 = 256 pages. # entries in page table = 256 Page offset size = log(4 KB) = 12 bits
Fill in the table on the next slide for each reference
27
Class Problem: Illustration – Initial state
Page size = 4 KB
Virtual memory
(2^20 bytes = 256 pages)
Physical Memory (16 KB = 4 pages)
Virtual address Physical address
Virtual page number Page offset
20 11 0
Virtual memory: 2^20 bytes 2^20 / 4 KB = 256 pages
Page Table (256 entries)
Physical page number Page offset
13 11 0
Physical Memory: 16 KB (16 KB / 4 KB = 4 pages)
Disk
(swap partition)
28
Class Problem (continued)
Virt addr
Virt page
Page fault?
Phys addr
0x00F0C
0x01F0C
0x20F0C
0x00100
0x00200
0x30000
0x01FFF
0x00200
Class Problem (continued)
Virt addr
Virt page
Page fault?
Phys addr
0x00F0C
0x0
N
0x1F0C
0x01F0C
0x20F0C
0x00100
0x00200
0x30000
0x01FFF
0x00200
Class Problem (continued)
Virt addr
Virt page
Page fault?
Phys addr
0x00F0C
0x0
N
0x1F0C
0x01F0C
0x1
N
0x2F0C
0x20F0C
0x00100
0x00200
0x30000
0x01FFF
0x00200
Class Problem (continued)
Virt addr
Virt page
Page fault?
Phys addr
0x00F0C
0x0
N
0x1F0C
0x01F0C
0x1
N
0x2F0C
0x20F0C
0x20
Y (into 3)
0x3F0C
0x00100
0x00200
0x30000
0x01FFF
0x00200
Class Problem (continued)
Virt addr
Virt page
Page fault?
Phys addr
0x00F0C
0x00
N
0x1F0C
0x01F0C
0x01
N
0x2F0C
0x20F0C
0x20
Y (into 3)
0x3F0C
0x00100
0x00
N
0x1100
0x00200
0x00
N
0x1200
0x30000
0x30
Y (into 2)
0x2000
0x01FFF
0x01
Y (into 3)
0x3FFF
0x00200
0x00
N
0x1200
Virtual Memory Roles
Capacity: Main memory is not enough
Problem:
Modern systems can afford ~128 GBs DRAM space = 2^37 bytes. Programs written in 64-bit ISA need 2^64 bytes! Need to run many programs simultaneously on the same machine. Each program may require GBs of memory.
Solution:
Provide an illusion of storage large enough for 2^64 bytes of data for all concurrently running programs Manage main memory like an exclusive fully-associative cache. Spills to disk.
Security features
Permissions
Programs may want to share data and code (e.g., library)
Programs may want to disable read/write permissions to some portions of memory
e.g., mark instructions are read-only, no read/write permission for unallocated heap
34
Isolation
Unrelated programs must not have access to each other’s data
Processes and threads on my computer
35
Revisit real system view—multitasking
Code
Static Data
Heap Data
Stack
Code
Static Data
Heap Data
Stack
Code
Static Data
Heap Data
Stack
...
Processor
Physical Memory (DRAM)
Smaller than the sum of all programs’ memory
36
How to achieve isolation?
37
How to achieve isolation?
38
How to achieve isolation?
39
Some pages may be swapped out to disk
Page table for Chrome
0x0000 0x1000
0x0000 0x1000
0x5000
0x0000
0x1A000
D1000
0x1F000
0x2000
0x8000
0xF000
0x10000
DISK
0x0000 0x1000
D1000
0xF000 Virtual address space
(2^64 locations)
Page table for Word
0x1F000 DRAM
40
Virtual Memory Roles
Capacity: Main memory is not enough
Problem:
Modern systems can afford ~128 GBs DRAM space = 2^37 bytes. Programs written in 64-bit ISA need 2^64 bytes! Need to run many programs simultaneously on the same machine. Each program may require GBs of memory.
Solution:
Provide an illusion of storage large enough for 2^64 bytes of data for all concurrently running programs Manage main memory like an exclusive fully-associative cache. Spills to disk.
Security features
Isolation
Permissions
Programs may want to share data and code (e.g., library)
Programs may want to disable read/write permissions to some portions of memory
e.g., mark instructions are read-only, no read/write permission for unallocated heap
Unrelated programs must not have access to each other’s data
41
Some pages can be shared between programs; Permissions per page: invalid, read-only, not-execute, etc.
Page table for Chrome
0x5000 0x0000
0x2000
0xF000 0x1A000 0x10000 D1000
0x0000 0x1F000 0x1000 0x2000
0x0000 0x1000
0x0000 0x1000
0xF000 0x8000 Virtual address space Page table for Word
0x1F000 DRAM
(2^64 locations)
Permission bits Read-only
42
Not-execute
DISK
D1000
VM integration with processor caches (to be discussed later)
VM systems give us two different addresses: virtual and physical
Which address should we use to access the data cache? • Virtual address (before VM translation).
- Fasteraccess.
- More complex.
• Physical address (after VM translations).
- Delayedaccess.
43
Check your computer
44