CSCI 2021: Virtual Memory
Last Updated:
Wed Dec 8 02:20:19 PM CST 2021
1
Logistics
Reading Bryant/O’Hallaron
▶ Ch 9: Virtual Memory
▶ Ch 7: Linking (next)
P5
▶ 1 Required Problem
▶ Employ Memory Mapping to
traverse binary file
Goals
▶ Address Spaces, Translation, Paged Memory
▶ mmap(), Sharing Pages
Date 12/06 Mon
12/08 Wed
Event
Virtual Mem 1/2
Virtual Mem 2/2 Lab 14 VirtMem HW 14 Linking P5 Release
ELF Files/Linking 1/2 Obj Code/Linking 2/2
Last Lecture, Review Last Lab, Review
P5 Due
Final Exam 1:30pm
12/10 Fri 12/13 Mon
12/15 Wed 12/18 Sat
2
Exercise: The View of Memory Addresses so Far
▶ Every process (running program) has some memory, divided
into roughly 4 areas (which are…?)
▶ Reference different data/variables through their addresses
▶ If only a single program could run at time, no trouble: load program into memory and go
▶ Running multiple programs gets interesting particularly if they both reference the same memory location, e.g. address 1024
PROGRAM 1
…
## load global from #1024
movq 1024, %rax
…
PROGRAM 2
…
## add to global at #1024
addl %esi, 1024
…
▶ What conflict exists between these programs?
▶ What are possible solutions to this conflict?
3
Answers: The View of Memory Addresses so Far
▶ 4 areas of memory are roughly: (1) Stack (2) Heap (3)
Globals (4) Text/Instructions
▶ Both programs use physical address #1024, behavior depends on order that instructions are interleaved between them
ORDER A: Program 1 loads first
———————————
ORDER B: Program 2 adds first
———————————–
PROGRAM 1
movq 1024, %rax
…
PROGRAM 2
…
addl %esi, 1024
PROGRAM 1
…
movq 1024, %rax
PROGRAM 2
addl %esi, 1024
…
▶ Solution 1: Never let Programs 1 and 2 run together (bleck!)
▶ Solution 2: Translate every memory address in every program on loading it, run with physical addresses
▶ Tough/impossible as not all addresses are known at compile/load time…
▶ Solution 3: Translate every memory address/access in every program while it runs (!!!)
4
Paged Memory
▶ Physical memory is divided into hunks called pages
▶ Common page size supported by many OS’s (Linux) and
hardware is 4KB = 4096 bytes
▶ Memory is usually byte addressable so need offset into page
▶ 12 bits for offset into page
▶ A − 12 bits for page number where A is the address size in bits
▶ Usually A is NOT 64-bits > cat /proc/cpuinfo
vendor_id
cpu family
model
model name
…
address sizes : 46 bits physical, 48 bits virtual
: GenuineIntel
: 6
: 79
: Intel(R) Xeon(R) CPU E5-1620 v4 @ 3.50GHz
▶ Leaves 48 − 12 = 36 bits for Page Number
▶ Means a page table may have up to 236 entries (!)
5
Translation happens at the Page Level
▶ Within a page, addresses are sequential
▶ Between pages, may be non-sequential
Page Table: |——————+——+———————–| | Virtual Page | Size | Physical Page | |——————+——+———————–| | 00007ffa0997a000 | 4K | RAM: 0000564955aa1000 | | 00007ffa0997b000 | 4K | RAM: 0000321e46937000 | |… ||… | |——————+——+———————–|
Address Space From Page Table:
|——————+————-+——————|
| Virtual Address | Page Offset | Physical Address |
|——————+————-+——————|
| 00007ffa0997a000 |
| 00007ffa0997a001 |
| 00007ffa0997a002 |
| … |
| 00007ffa0997afff |
|——————+————-+——————|
| 00007ffa0997b000 |
| 00007ffa0997b001 |
| … |
|——————+————-+——————|
0 | 0000564955aa1000 |
1 | 0000564955aa1001 |
2 | 0000564955aa1002 |
| … |
4095 | 0000564955aa1fff |
0 | 0000321e46937000 |
1 | 0000321e46937001 |
| … |
6
Addresses Translation Hardware
▶ Translation must be FAST so usually involves hardware
▶ MMU (Memory Manager Unit) is a hardware element specifically designed for address translation
▶ Usually contains a special cache, TLB (Translation Lookaside Buffer), which stores recently translated addresses
▶ OS Kernel interacts with MMU
▶ Provides location of the Page Table, data structure relating Virtual/Physical Addresses
▶ Page Fault : MMU couldn’t map Virtual to Physical page, runs a Kernel routine to handle the fault
7
Exercise: Translating Virtual Addresses
Nearby diagram illustrates relation of Virtual Pages to Physical Pages
1. How many page tables are there?
2. Where can a page table entry refer to?
3. Count the number of Virtual pages, compare to the number of physical pages – which his larger?
4. What happens if PID #123 accesses its Virtual Page #2
5. What happens if PID #456 accesses its Virtual Page #2
8
Translating Virtual Addresses 1/2
▶ On using a Virtual Memory address, MMU will search TLB for physical DRAM address,
▶ If found in TLB, Hit, use physical DRAM address
▶ If not found, MMU will search Page Table, if found and in DRAM, cache in TLB
▶ Else Miss = Page fault, OS decides..
1. Page is swapped to Disk, move to DRAM, potentially evicting another page
2. Page not in page table = Segmentation Fault
9
Translating Virtual Addresses 2/2
▶ Each process has its own page table, OS maintains mapping of Virtual to Physical addresses
▶ Processes “compete” for RAM
▶ OS gives each process impression it
owns all of RAM
▶ OS may not have enough memory to back up all or even 1 process
▶ Disk used to supplement ram as Swap Space
▶ Thrashing may occur when too many processes want too much RAM, “constantly swapping”
10
Trade-offs of Address Translation
Wins of Virtual Memory
1. Avoids processes each referencing the same address, conflicting
2. Allows each Process (running program) to believe it has entire memory to itself
3. Gives OS tons of flexibility and control over memory layout
▶ Present a continuous Virtual chunk which is spread out in Physical memory
▶ Use Disk Space as memory
▶ Check for out of bounds
memory references
Losses of Virtual Memory
1. Address translation is not constant O(1), has an impact on performance of real algorithms*
2. Requires special hardware to make translation fast enough: MMU/TLB
3. Not needed if only a single program is running on a machine
Wins often outweigh Losses so Virtual Memory is used in most modern computing systems, a “great idea” in CS
*See On a Model of Virtual Address Translation (2015)
11
The Many Other Advantages of Virtual Memory
1. Caching: Seen that VirtMem can treat main memory as a cache for larger memory
2. Security: Translation allows OS to check memory addresses for validity, segfault on out-of bounds access
3. Debugging: Valgrind checks addresses for validity
4. Sharing Data: Processes can share data with one another; request OS to map virtual addresses to same physical addresses
5. Sharing Libraries: Can share same program text between programs by mapping address space to same shared library
6. Convenient I/O: Map internal OS data structures for files to virtual addresses to make working with files free of read()/write()
Will start with last of these and the hand mmap() function
12
Virtual Memory and mmap()
▶ Normally programs interact indirectly with Virtual Memory system
▶ Stack/Heap/Globals/Text are mapped automatically to regions in Virtual Memory System
▶ Maps are adjusted as Stack/Heap Grow/Shrink
▶ mmap() / munmap() function allows direct manipulation of the page table
▶ mmap() creates new entries in page table, munmap() deletes entries
▶ Can map arbitrary or specific addresses into memory
▶ mmap() is used to initially set up the Stack/Heap/Globals/Text when a program is loaded by the program loader
▶ Can also use mmap() as a convenient way to interact with files via Memory Mapped Files
13
Exercise: Printing Contents of file
1. Examine print_file.c: reads contents of a file and prints it to the screen. Identify the key parts of this program and its memory requirements.
2. Examine mmap_print_file.c: does it contain all of these key features? Which ones are missing?
14
Exercise: Printing Contents of file
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16 }
FILE *fin = fopen(argv[1], “r”); char inchar; 4
// print_file.c
int main(int argc, char *argv[]){
1 // mmap_print_file.c
2 int main(int argc, char *argv[]){
3 int fd = open(argv[1], O_RDONLY);
5 struct stat stat_buf;
6 fstat(fd, &stat_buf);
7 int size = stat_buf.st_size;
9 char *file_chars =
10 mmap(NULL, size,
11 PROT_READ, MAP_SHARED,
12 fd, 0);
13
14 for(int i=0; i
0x5575555a71e9 :
0x5575555aa0c0 :
0x557555b482a0 :
0x600000000000 :
0x600000001000 :
0x7f2244dc4000 :
0x7ffff0133b70 :
my pid is 496605
press any key to
main()
global_arr
heap_arr
mmap’d block1
mmap’d block2
mmap’d file
stack_arr
continue
> pmap 496605
496605: ./memory_parts
▶ Determine process id of running program
▶ pmap reports its virtual address space
▶ More details of pmap output in this article from
▶ His diagram is awesome
00007f2244d8e000
00007f2244d91000
00007f2244dc4000
00007f2244dc5000
00007f2244dc7000 132K r-x– ld-2.32.so
00007f2244de8000 36K r—- ld-2.32.so
00007f2244df2000 8K rw— ld-2.32.so
00007ffff0114000 132K rw— [ stack ] STACK
00007ffff014d000 12K r—- [ anon ]
total 2352K
00005575555a6000
00005575555a7000
00005575555a8000
00005575555a9000
00005575555aa000
00005575555ab000
0000557555b48000
0000600000000000
00007f2244bca000
00007f2244bcc000 152K r—- libc-2.32.so
00007f2244bf2000 1332K r-x– libc-2.32.so
00007f2244d3f000 304K r—- libc-2.32.so
4K r—-
4K r-x–
4K r—-
4K r—-
4K rw—
4K rw—
memory_parts
memory_parts TEXT
memory_parts
memory_parts
memory_parts GLOBALS
132K rw—
8K rw—
8K rw—
[ anon ]
[ anon ] HEAP
[ anon ]
[ anon ]
12K rw— libc-2.32.so
24K rw— [ anon ]
4K r—- gettysburg.txt
8K r—- ld-2.32.so
32
Memory Protection
▶ Output of pmap indicates another feature of virtual memory: protection
▶ OS marks pages of memory with Read/Write/Execute/Share permissions like files
▶ Attempt to violate these and get segmentation violations (segfault)
▶ Ex: Executable page (instructions) usually marked as r-x: no write permission.
▶ Ensures program don’t accidentally write over their instructions and change them
▶ Ex: By default, pages are not shared (no ‘s’ permission) but can make it so with the right calls
33
Exercise: Quick Review
1. While running a program, memory address #1024 always refers to a physical location in DRAM (True/False: why?)
2. Two programs which both use the address #1024 cannot be simultaneously run (True/False: why?)
3. What do MMU and TLB stand for and what do they do?
4. What is a memory page? How big is it usually?
5. What is a Page Table and what is it good for?
34
Answers: Quick Review
1. While running a program, memory address #1024 always refers to a physical location in DRAM (True/False: why?)
▶ False: #1024 is usually a virtual address which is translated by the OS/Hardware to a physical location which may be in DRAM but may instead be paged out to disk
2. Two programs which both use the address #1024 cannot be simultaneously run (True/False: why?)
▶ False: The OS/Hardware will likely translate these identical virtual addresses to different physical locations so that the programs doe not clobber each other’s data
3. What do MMU and TLB stand for and what do they do?
▶ Memory Management Unit: a piece of hardware involved in
translating Virtual Addresses to Physical Addresses/Locations
▶ Translation Lookaside Buffer: a special cache used by the
MMU to make address translation fast
4. What is a memory page? How big is it usually?
▶ A discrete hunk of memory usually 4Kb (4096 bytes) big 5. What is a Page Table and what is it good for?
▶ A table maintained by the operating system that is used to map Virtual Addresses to Physical addresses for each page
35
Additional Review Questions
▶ What OS data structure facilitates the Virtual Memory system? What kind of data structure is it?
▶ What does pmap do?
▶ What does the mmap() system call do that enables easier
I/O? How does this look in a C program?
▶ Describe at least 3 benefits a Virtual Memory system provides to a computing system
36