Operating Systems CMPSC 473
Virtual Memory Management Lectures 9-12
Feb. 18, 23, 25, Mar. 2, 2021 Instructor: Bhuvan Urgaonkar
Carnegie Mellon
Administrivia
¢ Changed office hours § Thursdays 1:30-2:30 § Fridays: 3-4
¢ Project 2 released
§ Please pay attention to multiple deadlines § Make sure to pick up updated description § Hope tutorials offered by TAs were useful
¢ CSAPP accessibility on canvas (under Modules->Reading Materials)
¢ Check: registration required for every lecture?
¢ Interrupt me at 1:20 pm sharp!
Carnegie Mellon
Quiz 8.3 Revisited
#include
#include
int main () {
int i;
char *c;
c = (char *) malloc (sizeof (char)); while (1) {
c[i] = ‘c’;
printf (“succeeded in writing to c[%d]\n”, i++); }
}
¢ How many pages did malloc end up procuring from the OS?
¢ Which of the following statements accurately describes the behavior of the above program?
§ It will encounter a segmentation fault
§ It will not encounter a segmentation fault
§ It may encounter a segmentation fault (it depends)
Carnegie Mellon
Quiz 8.3 (contd.)
Carnegie Mellon
Quiz 8.4
#include
#include
int main () {
char *a, *b;
int *c, *d;
a = (char *) malloc (sizeof (char));
b = (char *) malloc (sizeof (char));
printf (“Address of a: %p; address of b: %p\n”, a, b); c = (int *) malloc (sizeof (int));
d = (int *) malloc (sizeof (int));
printf (“Address of c: %p; address of d: %p\n”, c, d);
}
¢ What gaps do you expect to see between the virtual Error in recorded lecture: In
addresses for a vs b? c vs d?
responding to a student question, I said 32 bytes instead of 32 bits
Carnegie Mellon
Quiz 9.1
¢ Which of these are contributors to internal fragmentation in the heap?
§ The need to align objects to word boundaries
§ Metadata such as header and footer tags
§ The inability to move allocated blocks around so they are adjacent to each other
Carnegie Mellon
Recap: what’s where in the address space
kernel
Carnegie Mellon
user
Recap: what’s where in the address space
kernel
Carnegie Mellon
user code+data
data
– Global variables – C static variables
libraries
– Shared (DLLs) – Static
code written by us – main
– foo
-…
user
Recap: what’s where in the address space
kernel
user stack
stack pointer (SP)
user
Carnegie Mellon
frame for main
frame for foo
user code+data
Recap: what’s where in the address space
kernel
user stack
stack pointer (SP)
user
Carnegie Mellon
frame for main
frame for foo
user heap
user code+data
Recap: what’s where in the address
space
Managed by malloc/free
Carnegie Mellon
frame for main
frame for foo
user heap
user code+data
free
padding
data
data
meta-data
free
free
padding
data
data
meta-data
kernel
user stack
stack pointer (SP)
user
Recap: what’s where in the address space
kernel
Carnegie Mellon
kernel code+data
dynamically loaded modules – e.g., USB driver
virtual memory manager kmalloc/kfree
CPU scheduler
context switching
trap handlers
– system call handlers
interrupt handlers
Recap: what’s where in the address space
kernel
Carnegie Mellon
kernel stack
kernel heap
kernel code+data
Recap: what’s where in the address
space
Managed by kmalloc/kfree
kernel
Carnegie Mellon
kernel stack
kernel heap
kernel code+data
process control block (A) – PID
– privileged registers -…
process control block (B) – PID
– privileged registers -…
kstack (A)
kstack (B)
page table for A
page table for B
…
Latency numbers every programmer should know
Carnegie Mellon
Carnegie Mellon
Enabling Data Structure: Page Table
¢ A page table is an array of page table entries (PTEs) that maps virtual pages to physical pages.
§ Per-process kernel data structure in DRAM
VP 1
VP 2
VP 7
VP 4
Valid
PTE 0
Physical page number or disk address
Physical memory (DRAM)
PP 0
PP 3
Carnegie Mellon
0
null
1
1
0
1
0
null
0
1
PTE 7
Virtual memory (disk)
VP 1
VP 2
VP 3
VP 4
VP 6
VP 7
Memory resident page table (DRAM)
Page Hit
¢ Page hit: reference to VM word that is in physical memory (DRAM cache hit)
Carnegie Mellon
Virtual address
Physical page number or disk address
Physical memory (DRAM)
PP 0
PP 3
VP 1
VP 2
VP 7
VP 4
Valid
PTE 0
0
null
1
1
0
1
0
null
0
1
PTE 7
Virtual memory (disk)
VP 1
VP 2
VP 3
VP 4
VP 6
VP 7
Memory resident page table (DRAM)
Page Fault
¢ Page fault: reference to VM word that is not in physical memory (DRAM cache miss)
Carnegie Mellon
Virtual address
Physical page number or disk address
Physical memory (DRAM)
VP 1
VP 2
VP 7
VP 4
Valid
PTE 0
PP 0
PP 3
0
null
1
1
0
1
0
null
0
1
PTE 7
Virtual memory (disk)
VP 1
VP 2
VP 3
VP 4
VP 6
VP 7
Memory resident page table (DRAM)
Handling Page Fault
¢ Pagemisscausespagefault(atrap)
Carnegie Mellon
Virtual address
Physical page number or disk address
Physical memory (DRAM)
VP 1
VP 2
VP 7
VP 4
Valid
PTE 0
PP 0
PP 3
0
null
1
1
0
1
0
null
0
1
PTE 7
Virtual memory (disk)
VP 1
VP 2
VP 3
VP 4
VP 6
VP 7
Memory resident page table (DRAM)
Handling Page Fault
¢ Pagemisscausespagefault(atrap)
¢ Pagefaulthandlerselectsavictimtobeevicted(hereVP4)
Carnegie Mellon
Virtual address
Physical page number or disk address
Physical memory (DRAM)
VP 1
VP 2
VP 7
VP 4
Valid
PTE 0
PP 0
PP 3
0
null
1
1
0
1
0
null
0
1
PTE 7
Virtual memory (disk)
VP 1
VP 2
VP 3
VP 4
VP 6
VP 7
Memory resident page table (DRAM)
Handling Page Fault
¢ Pagemisscausespagefault(atrap)
¢ Pagefaulthandlerselectsavictimtobeevicted(hereVP4)
Virtual address
Physical page number or disk address
Physical memory (DRAM)
VP 1 VP 2
VP 7 VP 3
Virtual memory (disk)
VP 1 VP 2 VP 3 VP 4 VP 6 VP 7
PP 0
PP 3
PTE 0
0 null 1
1
1
0
0 null 0
PTE7 1
Valid
Memory resident page table (DRAM)
Carnegie Mellon
Handling Page Fault
¢ Pagemisscausespagefault(atrap)
¢ Pagefaulthandlerselectsavictimtobeevicted(hereVP4)
¢ Offendinginstructionisrestarted:pagehit!
Physical memory (DRAM)
Virtual address
Physical page number or disk address
PP 0
PP 3
Carnegie Mellon
VP 1
VP 2
VP 7
VP 3
Valid
PTE 0
0
null
1
1
1
0
0
null
0
1
Virtual memory (disk)
PTE 7
VP 1
VP 2
VP 3
VP 4
VP 6
VP 7
Key point: Waiting until the miss to copy the page to DRAM is known as demand paging
Memory resident page table (DRAM)
Allocating Pages
¢ Allocating a new page (VP 5) of virtual memory.
Physical page number or disk address
Physical memory (DRAM)
Carnegie Mellon
VP 1
VP 2
VP 7
VP 3
Valid
PTE 0
PP 0
PP 3
0
null
1
1
1
0
0
0
1
Virtual memory (disk)
PTE 7
VP 1
VP 2
VP 3
VP 4
VP 5
VP 6
VP 7
Memory resident page table (DRAM)
VM as a Tool for Memory Management ¢ Each process has its own virtual address space
§ It can view memory as a simple linear array
Virtual Address
0
Address 0 translation
Physical Address Space (DRAM)
(e.g., read-only library code)
Carnegie Mellon
PP 2
PP 6
PP 8
VP 1
Space for Process 1:
VP 2
Virtual Address
Space for Process 2:
N-1 0
…
VP 1
VP 2
…
N-1
M-1
…
VM as a Tool for Memory Management
¢ Simplifying memory allocation
§ Each virtual page can be mapped to any physical page
§ A virtual page can be stored in different physical pages at different times
¢ Sharing code and data among processes
§ Map virtual pages to the same physical page (here: PP 6)
Virtual Address
0
Address 0 translation
Physical Address Space (DRAM)
(e.g., read-only library code)
Carnegie Mellon
PP 2
PP 6
PP 8
VP 1
Space for Process 1:
VP 2
Virtual Address
Space for Process 2:
N-1 0
…
VP 1
VP 2
…
N-1
M-1
…
Simplifying Linking and Loading ¢ Linking
Memory invisible to user code
§ Each program has similar virtual %rsp address space (stack
Carnegie Mellon
Kernel virtual memory
User stack (created at runtime)
Memory-mapped region for shared libraries
Run-time heap (created by malloc)
Read/write segment (.data, .bss)
Read-only segment (.init, .text, .rodata)
Unused
§ Code, data, and heap always start at the same addresses.
¢ Loading
§ execve allocates virtual pages for .text and .data sections & creates PTEs marked as invalid
§The.text and.data sections are copied, page by page, on demand by the virtual memory system
0x400000
pointer)
brk
Loaded from
the executable file
0
VM as a Tool for Memory Protection
¢ Extend PTEs with permission bits
¢ MMU checks these bits on each access
Process i: SUP VP0: No
READ WRITE EXEC
Yes No Yes PP6
Physical Address Space
PP 2
PP4
PP 6
PP 8 PP 9
PP 11
VP 1: VP 2:
Process j:
VP0: No VP 1: Yes VP2: No
No Yes Yes Yes PP4 Yes Yes Yes No PP2
• SUP READ WRITE EXEC
Address Yes No Yes PP9 Yes Yes Yes PP 6
Yes Yes Yes PP 11
Address
Carnegie Mellon
Quiz 9.2
¢ Why is there a page table per process and not a single page table for the entire system?
¢ Why is the page table inside the kernel part of the address space?
Carnegie Mellon
Operating Systems CMPSC 473
CPU/memory virtualization February 23, 2021 – Lecture 10 Instructor: Bhuvan Urgaonkar
Carnegie Mellon
VM Address Translation ¢ Virtual Address Space
§ V = {0, 1, …, N–1}
¢ Physical Address Space
§ P = {0, 1, …, M–1}
¢ Address Translation §MAP: V® P U {Æ} § For virtual address a:
§ MAP(a) = a’ if data at virtual address a is at physical address a’ in P § MAP(a) = Æ if data at virtual address a is not in physical memory
– Either invalid or stored on disk
Carnegie Mellon
Quiz 10.1
¢ If a page has never been allocated by the OS to a process (or was allocated but has since been released back), an access to it will cause:
§ a page fault trap
§ a segmentation fault § both of the above
§ depends (on what?)
Carnegie Mellon
Quiz 10.2
¢ If an object hasn’t been explicitly allocated by malloc but ends up being on a page that has been mapped into the address space, an access to it:
§ will result in a page fault trap
§ will result in a segmentation fault § will go undetected by the MMU
Carnegie Mellon
Quiz 10.3
¢ WherearethepagetableentriesfortheOSheld?* § in a separate page table
§ within each process’s page table
*alternatives possible
Carnegie Mellon
Quiz 10.4
¢ If the page table entries for the OS are contained in a process page table, how is the process prevented from accessing OS memory?
Carnegie Mellon
Quiz 10.5
¢ Assume the code segment does not begin at page 0 (Linux and VAX/VM do this, see OSTEP 23). Describe the behavior of the following code
int *ptr = NULL; *ptr = 1;
Carnegie Mellon
Summary of Address Translation Symbols
¢ 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)
¢ Components of the virtual address (VA) § TLBI: TLB index
§ TLBT: TLB tag
§ VPO: Virtual page offset
§ VPN: Virtual page number
¢ Components of the physical address (PA) § PPO: Physical page offset (same as VPO)
§ PPN: Physical page number
Carnegie Mellon
Address Translation With a Page Table
Page table base register (PTBR)
Physical page table address for the current process
Valid bit = 0: Page not in memory (page fault)
Virtual address
n-1
Virtual page number (VPN)
Page table
p p-1 0
Virtual page offset (VPO)
Valid
Physical page number (PPN)
Valid bit = 1
m-1
Physical page number (PPN)
Physical address
p p-1 0
Physical page offset (PPO)
Carnegie Mellon
Carnegie Mellon
Carnegie Mellon
Carnegie Mellon
Address Translation: Page Hit
2
PTEA PTE 3
PA
4
Carnegie Mellon
CPU Chip
CPU
1
VA
MMU
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
Data
5
Cache/ Memory
Address Translation: Page Fault
Exception
4
2
PTEA PTE
3
Page fault handler
Victim page
5
New page
6
Carnegie Mellon
CPU Chip
CPU
1
VA
7
MMU
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
Cache/ Memory
Disk
Why/when does VM work well?
¢ When there is good locality in program memory accesses § Temporal
§ Spatial
¢ At 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
Carnegie Mellon
Overheads of page tables
¢ How to lower the additional time needed to access address translations?
§ Translation lookaside buffer (TLB)
¢ How to lower the memory needs of the page tables themselves?
§ Multi-level page tables
§ Others (on your own, see Chapter 20)
§ Larger pages
§ Segmentation + Paging
Carnegie Mellon
Speeding up Translation with a TLB
¢ Also see OSTEP Chapter 19
¢ Page table entries (PTEs) are cached in L1 like any other memory word
Carnegie Mellon
Integrating VM and Cache
PTE
PTEA
PTE
Carnegie Mellon
CPU Chip
PTEA hit
PTEA miss
PA miss
PA hit
CPU
VA
MMU
PA
PTEA
Memory
PA
Data
Data
L1 cache
VA: virtual address, PA: physical address, PTE: page table entry, PTEA = PTE address
Speeding up Translation with a TLB
¢ Also see OSTEP Chapter 19
¢ Page 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
Carnegie Mellon
Speeding up Translation with a TLB
¢ Also see OSTEP Chapter 19
¢ Page 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
¢ Solution: 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 a small number of pages
Carnegie Mellon
Accessing the TLB
¢ MMU uses the VPN portion of the virtual address to access the TLB:
T = 2t sets
p p-1 0
Carnegie Mellon
TLBT matches tag of line within set
VPN n-1 p+t p+t-1
TLB tag (TLBT)
TLB index (TLBI)
VPO
v tag PTE v tag PTE
Set 0 Set 1
Set T-1
TLBI selects the set
v tag PTE v tag PTE
v tag PTE v tag PTE
…
TLB Hit
Carnegie Mellon
CPU Chip
TLB
PTE
3
2
VPN
CPU
1
VA
MMU
PA
4
Cache/ Memory
Data
5
A TLB hit eliminates a memory access
TLB Miss
Carnegie Mellon
CPU Chip
TLB
2
VPN
CPU
1
VA
MMU
4
PTE
3
PTEA
PA
5
Data
6
A TLB miss incurs an additional memory access (the PTE)
Fortunately, TLB misses are rare. Why?
Cache/ Memory
Quiz 10.6
¢ Consider a virtual memory system on a computer with no hardware caches, ignore pipelining. Calculate the average cycles per instruction (CPI) using the following information about this system:
§ 1 cycle = 1 ns.
§ non-memory instructions take 1 ns each.
§ Jeff Dean’s numbers for latency to DRAM (100 ns) and disk (10,000,000 ns).
§ page fault rate of 1%.
§ 20% of the instructions executed are memory accesses
(loads/stores).
§ page tables are always in DRAM.
Carnegie Mellon
Carnegie Mellon
Quiz 10.7
¢ Consider a virtual memory system on a computer with no hardware caches, ignore pipelining. Calculate the average cycles per instruction (CPI) using the following information about this system:
§ 1 cycle = 1 ns.
§ non-memory instructions take 1 ns each.
§ Jeff Dean’s numbers for latency to DRAM (100 ns) and disk (10,000,000 ns).
§ page fault rate of 1%.
§ 20% of the instructions executed are memory accesses
(loads/stores).
§ page tables are always in DRAM.
§ TLB latency = 1 ns, hit ratio of 90%.
Carnegie Mellon
Quiz 10.8 (Option)
¢ Can page tables be paged out to disk? § See OSTEP 20.5, 23.1
Carnegie Mellon
Carnegie Mellon
Carnegie Mellon
Carnegie Mellon
Carnegie Mellon
Error in recorded lecture: a student and the instructor say 1 Mega Byte for 1 Meg (i.e., 1024*1024)
Carnegie Mellon
Review of Symbols
¢ Basic Parameters
§ N = 2n : Number of addresses in virtual address space
§ M = 2m : Number of addresses in physical address space §P=2p :Pagesize(bytes)
¢ Components of the virtual address (VA) § TLBI: TLB index
§ TLBT: TLB tag
§ VPO: Virtual page offset
§ VPN: Virtual page number
¢ Components of the physical address (PA) § PPO: Physical page offset (same as VPO)
§ PPN: Physical page number
§ CO: Byte offset within cache line
§ CI: Cache index § CT: Cache tag
Carnegie Mellon
CMPSC 473 Project 1 Histogram
Carnegie Mellon
Percentage Grade
Number of Students
Quiz 12.1: Simple Memory System Example
¢ Addressing
§ 14-bit virtual addresses § 12-bit physical address § Page size = 64 bytes
13 12 11 10 9 8 7 6 5 4 3 2 1 0 VPN VPO
Virtual Page Number Virtual Page Offset
11 10 9 8 7 6 5 4 3 2 1 0
PPN PPO
Physical Page Number
Carnegie Mellon
Physical Page Offset
Quiz 12.1 (contd.): Simple Memory System Page Table
Only show first 16 entries (out of 256)
Carnegie Mellon
VPN
PPN
Valid
00
28
1
01
–
0
02
33
1
03
02
1
04
–
0
05
16
1
06
–
0
07
–
0
VPN
PPN
Valid
08
13
1
09
17
1
0A
09
1
0B
–
0
0C
–
0
0D
2D
1
0E
11
1
0F
0D
1
Quiz 12.1 (contd.): Simple Memory System TLB ¢ 16 entries
¢ 4-way associative
TLBT TLBI
Decides the set
Carnegie Mellon
13 12 11 10 9 8 7 6 5 4 3 2 1 0
VPN VPO
Set Tag PPN Valid Tag PPN Valid Tag PPN Valid Tag PPN Valid
0 03 – 0 09 0D 1 00 – 0 07 02 1 1 03 2D 1 02 – 0 04 – 0 0A – 0 2 02 – 0 08 – 0 06 – 0 03 – 0 3 07 – 0 03 0D 1 0A 34 1 02 – 0
Quiz 12.1 (contd.): Simple Memory System Cache
¢ 16 lines, 4-byte block size ¢ Physically addressed
¢ Direct mapped
CT CI CO 11 10 9 8 7 6 5 4 3 2 1 0
Carnegie Mellon
PPN
Idx Tag Valid B0 B1 B2 B3
019199112311
1 15 0 – – – – 9 2D 0 – – – – 21B100020408 A 2D 1 93 15 DA 3B 3 36 0 – – – – B 0B 0 – – – –
PPO
Idx Tag Valid B0 B1 B2 B3
8 24 1 3A 00 51 89
4 32 1 43 6D 8F 09
50D13672F01D 6 31 0 – – – – 716111C2DF03
C 12 0 – – – –
D 16 1 04 96 34 15 E 13 1 83 77 1B D3 F 14 0 – – – –
Quiz 12.1 (contd.): Address Translation Example #1 Virtual Address: 0x03D4
TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0
00001111010100
VPN VPO
VPN ___ TLBI ___ TLBT ____ TLB Hit? __ Page Fault? __ PPN: ____
Physical Address
CT CI CO
11 10 9 8 7 6 5 4 3 2 1 0
001101010100
PPN PPO
CO ___ CI___ CT ____ Hit? __ Byte: ____
Carnegie Mellon
Quiz 12.1 (contd.): Address Translation Example #1 Virtual Address: 0x03D4
TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0
VPN ___ TLBI ___ TLBT ____
TLB Hit? __
Page Fault? __ PPN: ____
Y
Carnegie Mellon
0
0
0
0
1
1
1
1
0
1
0
1
0
0
VPN
0x0F 0x3 0x03
Physical Address
VPO
N 0x0D
CT CI CO
11 10 9 8 7 6 5 4 3 2 1 0
0
0
1
1
0
1
0
1
0
1
0
0
PPN
PPO
0 0x5 0x0D
Y
0x36
CO ___ CI___ CT ____
Hit? __
Byte: ____
Quiz 12.1 (contd.): Address Translation Example #2 Virtual Address: 0x0020
TLBT TLBI
13 12 11 10 9 8 7 6 5 4 3 2 1 0
VPN VPO
0x00 0 0x00 N N 0x28
Physical Address
CT CI CO
11 10 9 8 7 6 5 4 3 2 1 0
PPN PPO
Carnegie Mellon
0
0
0
0
0
0
0
0
1
0
0
0
0
0
VPN ___ TLBI ___ TLBT ____ TLB Hit? __ Page Fault? __ PPN: ____
1
0
1
0
0
0
1
0
0
0
0
0
0 0x8 0x28 N Mem
CO___ CI___ CT ____ Hit? __ Byte: ____
Quiz 12.2: Impact of p, n, m
¢ For each of the following quantities, describe if increasing p (for a fixed n, m) causes the quantity to increase or decrease or if the answer is more complex. If more complex, describe the factors affecting your answer.
§ Wastage of virtual memory due to internal fragmentation
§ Wastage of physical memory due to internal fragmentation
§ Probability of erroneous memory accesses that the MMU is unable to catch
§ Size of a single-level page table § Equivalently, #PTEs
§ “TLB reach” (how much of the virtual address space each TLB entry is able to capture)
§ TLB hit rate
Carnegie Mellon
Quiz 12.3: Impact of p, n, m
¢ For each of the following quantities, describe if increasing n (for a fixed p, m) causes the quantity to increase or decrease or if the answer is more complex. If more complex, describe the factors affecting your answer.
Carnegie Mellon
Quiz 12.4: Impact of p, n, m
¢ For each of the following quantities, describe if increasing m (for a fixed p, n) causes the quantity to increase or decrease or if the answer is more complex. If more complex, describe the factors affecting your answer.
Carnegie Mellon
Quiz 12.5
Carnegie Mellon
Quiz 12.5
Carnegie Mellon
Multi-Level Page Tables
¢ Also see OSTEP Chapter 20 ¢ Suppose:
§ 4KB (212) page size, 48-bit address space, 8-byte PTE
Level 2 Tables
Carnegie Mellon
¢ Problem:
§ Would need a 512 GB page table!
§248 *2-12 *23 =239 bytes
Level 1 Table
¢ Example: 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)
¢ Common solution: Multi-level page table
…
…
A Two-Level Page Table Hierarchy
Level 1 page table
Level 2 page tables
Virtual memory
0
Carnegie Mellon
VP 0
…
VP 1023
VP 1024
…
VP 2047
Gap
1023 unallocated pages
VP 9215
PTE 0
…
PTE 1023
PTE 0
2K allocated VM pages for code and data
PTE 1
PTE 2 (null)
PTE 3 (null)
PTE 4 (null)
PTE 0
…
PTE 1023
PTE 5 (null)
PTE 6 (null)
6K unallocated VM pages
PTE 7 (null)
PTE 8
1023 null PTEs
(1K – 9) null PTEs
PTE 1023
32 bit addresses, 4KB pages, 4-byte PTEs
1023 unallocated pages
1 allocated VM page for the stack
…
Translating with a k-level Page Table
Carnegie Mellon
Page table base register (PTBR)
n-1
VIRTUAL ADDRESS
p-1 0 VPN k VPO
VPN 1
Level 1 page table
VPN 2
Level 2 page table
…
… …
Level k page table
PPN
m-1
p-1 0 PPO
PPN
PHYSICAL ADDRESS
An example from OSTEP, Chapter 20
Carnegie Mellon
Quiz 12.6
Carnegie Mellon
Quiz 12.6
Carnegie Mellon
Quiz 12.7: Impact of #levels in a page table
¢ For a given (p, n, m), for each of the following quantities, describe if increasing the number of levels in a multi-level page causes the quantity to increase or decrease or if the answer depends on other factors. If the answer depends on other factors, identify them.
§ Memory needed by OS for the page tables of a “small” process
§ Memory needed by OS for the page tables of a “large” process
§ Memory needed by OS for the page tables of a general process
§ Number of memory accesses needed to translate a virtual address § TLB hit rate
§ TLB miss servicing time
Carnegie Mellon
Quiz 12.8: Multi-level page table size
¢ Consideravirtualmemorysystemusinga4-levelpagetablewherethe parameters n and p are 48 and 12, respectively. The size of the DRAM is 4GB. The number of bits of virtual address used for indexing into the first-, the second-, and third-level page tables are 8, 8, and 10, respectively. Suppose each page table entry in the outermost level is 8 bytes long. How much memory is required for the page tables translating the user portion of the address space when the process address space looks as follows:
§ The code+data segment grows upwards starting from address 0x000000000000 and is of size 4 MB.
§ The heap grows upwards from address 0x000D00000000 and is of size 12 MB. § The stack grows downwards from address 0xC00000000000 and is of size 1 MB.
Carnegie Mellon
Quiz 12.9: Average CPI
¢ Calculate the average CPI for a virtual memory-based computer system with the following properties:
§ CPU speed is 1 GHz
§ non-memory instructions take 1 cycle each due to pipelining
§ TLB hit rate is 0.98
§ There is an L1 cache offering a hit rate of 0.95. There are no other hardware caches
§ The roundtrip latencies between relevant elements are as follows: § CPU to TLB: 1 ns
§ CPU to L1: 2 ns
§ CPU to DRAM: 100 ns
§ CPU/DRAM to swap disk: 10,000,000 ns
Carnegie Mellon
Topics for further study on your own (not on the syllabus)
¢ Swapping out page tables
¢ Other types of page tables § Hashed page tables
§ Inverted page table
¢ Segmentation
¢ Software-managed TLBs
¢ Large pages
§ TLB reach vs. internal fragmentation
¢ VAX/VMS and Linux case studies § OSTEP Chapter 23
Carnegie Mellon
Memory Mapping
¢ VM areas initialized by associating them with disk objects.
§ Process is known as memory mapping.
¢ Area 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
¢ Dirty pages are copied back and forth between memory and a special swap file.
Carnegie Mellon
Sharing Revisited: Shared Objects
Process 1 virtual memory
Physical memory
Process 2 virtual memory
¢ Process 1 maps the shared
object.
Carnegie Mellon
Shared object
Sharing Revisited: Shared Objects
Process 1 virtual memory
Physical memory
Process 2 virtual memory
¢ Process 2 maps the shared
object.
¢ Notice how the virtual
addresses can be different.
Carnegie Mellon
Shared object
Sharing Revisited:
Private Copy-on-write (COW) Objects
Process 1 virtual memory
Physical memory
Process 2 virtual memory
Private copy-on-write area
¢ Two processes mapping a private copy-on-write (COW) object.
¢ Area flagged as private copy-on- write
¢ PTEs in private areas are flagged as read-only
Carnegie Mellon
Private copy-on-write object
Sharing Revisited:
Private Copy-on-write (COW) Objects
Process 1 virtual memory
Physical Process 2 memory virtual memory
¢ Instruction writing to private page triggers protection fault.
¢ Handler creates new R/W page.
¢ Instruction restarts upon handler return.
¢ Copying deferred as long as
possible!
Carnegie Mellon
Copy-on-write
Write to private copy-on-write page
Private copy-on-write object
The fork System Call
¢ VM and memory mapping explain how fork provides private
address space for each process.
¢ 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
¢ On return, each process has exact copy of virtual memory
¢ Subsequent writes create new pages using COW mechanism.
Carnegie Mellon
The execve System Call Private, demand-zero
¢
Toloadandrunanew program a.out in the
libc.so
current process using execve:
Carnegie Mellon
User stack
Memory mapped region for shared libraries
Runtime heap (via malloc)
Uninitialized data (.bss)
Initialized data (.data)
Program text (.text)
.data
.text
Shared, file-backed
¢
¢
Free vm_area_struct’s and page tables for old areas
Createvm_area_struct’s and page tables for new areas
§ Programs and initialized data backed by object files.
§ .bss and stack backed by anonymous files .
SetPCtoentrypointin
.text
§ Linux will fault in code and data pages as needed.
a.out
Private, demand-zero Private, demand-zero
Private, file-backed
.data
.text
0
¢
User-Level Memory Mapping
void *mmap(void *start, int len,
int prot, int flags, int fd, int offset)
¢ 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, …
¢ Return a pointer to start of mapped area (may not be start)
Carnegie Mellon
User-Level Memory Mapping
void *mmap(void *start, int len,
int prot, int flags, int fd, int offset)
Carnegie Mellon
len bytes offset
(bytes)
len bytes start
(or address chosen by kernel)
0
0
Disk file specified by file descriptor fd
Process virtual memory
Example: Using mmap to Copy Files
¢ Copying a file to stdout without transferring data to user space .
Carnegie Mellon
#include “csapp.h”
void mmapcopy(int fd, int size)
{
/* Ptr to memory mapped area */
char *bufp;
bufp = mmap(NULL, size,
PROT_READ,
MAP_PRIVATE,
fd, 0);
write(1, bufp, size);
return; }
mmapcopy.c
/* mmapcopy driver */
int main(int argc, char **argv)
{
struct stat stat;
int fd;
/* Check for required cmd line arg */
if (argc != 2) {
printf(“usage: %s
argv[0]);
exit(0);
}
/* Copy input file to stdout */
fd = open(argv[1], O_RDONLY, 0);
fstat(fd, &stat);
mmapcopy(fd, stat.st_size);
exit(0);
}
mmapcopy.c