​

Virtual Memory

CS-446/646

C. Papachristos

Robotic Workers (RoboWork) Lab

University of Nevada, Reno

Virtual Memory

Virtual Memory (VM)

​

Early computers

• Programs use Physical Memory Addresses directly
• OS loads Job, runs it, unloads it

​

• Multiprogramming paradigm changed everything
• Want to have multiple Processes in Memory simultaneously

​

• Consider Multiprogramming directly on Physical Memory
• What happens if OS (Pintos) needs to expand?
• What if vim needs more Memory than is on the Machine?
• What if OS (Pintos) tries to erroneously write to Memory Address 0x7100?
• When does gcc have to know it will run at 0x4000?
• What if vim isn’t using most of its Memory?

CS446/646 C. Papachristos

Virtual Memory

Virtual Memory (VM)

​

Issues of sharing Physical Memory

• Protection
• A bug in one Process can corrupt Memory in another
• Must somehow prevent Process A from clobbering Process B’s Memory
• Also prevent Process A from even being able to observing Process B’s Memory

​

• Abstraction
• A Process shouldn’t require specific Physical Memory locations
• Processes often require large amounts of Contiguous Memory (Program Stack, large Data Structures, etc.)

​

• Resource Exhaustion
• Developer typically assumes Machine has “enough” Memory
• Sum of sizes of all Processes often greater than Physical Memory

CS446/646 C. Papachristos

Virtual Memory

Virtual Memory (VM) Goals

​

​

​

​

​

​

• Give each Program its own Virtual Address Space
• At Runtime the Hardware, i.e. the Memory Management Unit (MMU) translates each load/store
• Application doesn’t ever see Physical Memory Addresses

​

• Enforce Protection
• Prevent one Process from messing with another’s Memory

​

Allow Programs to “see” more Memory than exists

• Ability to “Page(/Swap)-Out” some Memory sections to Disk

CS446/646 C. Papachristos

Kernel-Space

Memory

User-Space

Memory

MMU

Physical

Memory

0x30408

0x1A408

load

MMU

0x30408

load

• Address Legal

✗ Address Illegal

to Fault Handler

Virtual Memory

Virtual Memory (VM) Advantages

​

Can re-locate Program while running

• Run partially in Memory, partially “evict”/“Page(/Swap)-Out” to Disk

​

Most of a Process’s Memory may be idle (“80/20 Rule” – more later)

• Can write idle parts to Disk until they become needed
• Let other Processes use Memory of idle part
• Like CPU Virtualization: When a Process is not using CPU, switch-over to executing a different Process�When a Memory region is unused, “switch” it over to a different Process

​

Challenge:

• Virtual Memory introduces an additional layer to Memory accessing
• Can impact Performance

CS446/646 C. Papachristos

Virtual Memory

Core Concept 1: Load-Time Dynamic Linking & Code Sharing

​

• Compiler makes distinguishable in the Symbol Table:
• Global Definitions which are routines/variables exported by the file being Compiled
• External Refs corresponding to external routines/variables

​

• Linker has to somehow “patch” at Loading-Time the Addresses of Symbols

i.e. Load-Time Dynamic Linking happens when Process executed (not at Compile-Time or at Link-Time)

• Why? Loading rules for Dynamic Libraries (location? order?)�cannot be too concrete: need them to be Relocatable
• Need Position-Independent Code (PIC) support
• Note: Compile Shared Libraries with gcc -fPIC
• First determine where Process will reside in Memory; Platform-specific
• Note: Can even have Position Independent Executables (PIEs) to provide Protection
• e.g. techniques like Address Space Layout Randomization (ASLR) guarding against Buffer Overflow attacks

Problems?

• “Patching” of every symbol required for each run,�can be time-consuming

CS446/646 C. Papachristos

Virtual Memory

Core Concept 1: Load-Time Dynamic Linking & Code Sharing

​

• Compiler makes distinguishable in the Symbol Table:
• Global Definitions which are routines/variables exported by the file being Compiled
• External Refs corresponding to external routines/variables

​

• Linker has to somehow “patch” at Loading-Time the Addresses of Symbols

i.e. Load-Time Dynamic Linking happens when Process executed (not at Compile-Time or at Link-Time)

• Add one level of Memory indirection:
• Global Offset Table (GOT)/Procedure Linkage Table (PLT)�in Executable and Linkable Format (ELF) binary
• Used to resolve the Loaded Address of Symbols (Variables/�Functions) when they are accessed
• Emitted code for a single access:
• At Loading Time, populate GOT

More Problems?

• How to move an entire Process that is already in Memory?
• What if no Contiguous free region can fit the Program?

mov 0x200271(%rip),%rax # the %rip: 200828 <_DYNAMIC+0x1a0>

mov (%rax),%eax # use that address’ contents

(Note: PLT populated lazily

during first function call)

0x200828 inside the .got Section of the ELF binary

value stored in 0x200828 will be populated with Dynamic Address to actually use (by dereferencing)

# load into %rax an address offseted w.r.t.

# by dereferencing %rax and

# loading %eax with its value

C. Papachristos

(in _DYNAMIC section + an offset _0x1a0)

Virtual Memory

CS446/646 C. Papachristos

Base

Bound

Virtual Memory

Core Concept 3: Virtual Address Space (VAS)

​

• Program (Assembly) Code does load/store/jump to Virtual Addresses

​

• Actual Memory Access uses Physical Addresses

​

​

​

The Virtual-to-Physical Memory-managing Hardware is the Memory Management Unit (MMU)

• Usually part of CPU
• Can be configured through Privileged Instructions (e.g. setting of Base/Bound Regs)
• Translates from Virtual-to-Physical Addresses
• Gives a per-Process view of the Memory, called the “(Virtual) Address Space”

CS446/646 C. Papachristos

MMU

Physical

Memory

CPU

Physical

Addresses

Virtual

Addresses

Virtual Memory

VAS through Base & Bound Registers: Trade-offs

​

Advantages

• Cheap in terms of Hardware (just 2 Registers)
• Cheap in terms of CPU cycles
• Perform adding Logical Address and Base (to determine Virtual-to-Physical mapping),�and compare (to ensure Bound within limits) in parallel inside the MMU

​

Disadvantages

• If we rely on using just this extra layer:
• Growing a Process’ Virtual Address Space is expensive or impossible
• No systematic way to Share code or data among different Processes

CS446/646 C. Papachristos

Virtual Memory

Core Concept 4: Segmentation

​

• Let Processes have multiple Base & Bound Regs
• Virtual Address Space built from many Segments
• Can share/protect Memory at Segment–level granularity

​

How?

• Each Virtual Address has to somehow indicate the specific�Segment that it corresponds to
• Has to contain this as part of its information

CS446/646 C. Papachristos

Physical

Memory

Code Segment

Data�Segment

Stack Segment

P0

Extra Segment

Example Illustration:

8086 Segmentation Model

ES

SS

DS

CS

Corresponding�CPU� Register

Virtual Memory

Core Concept 4: Segmentation

​

​

​

​

​

​

Segmentation Mechanics

• Each Process has its own associated “Segment Table”, set up and maintained by the OS
• Each Virtual Address indicates (is made up by) a Segment and Offset
• Top bits of Virtual Address select Segment, low bits select Offset
• Note: x86 stores each Segment’s Physical Address in Registers (CS, DS, SS, ES, FS, GS)
• Instruction Fetch uses CS; Memory Addressing defaults to DS / SS; Some (string) Instructions use ES,�FS & GS are special-purpose (e.g. Linux uses GS for Thread-local storage)

Virtual Address

Segment #

Offset

0x5 (DS)

0x128

Physical

Memory

0x1000

0x128 (Offset)

Physical

Address

<

+

MMU

C. Papachristos

CS

DS

SS

Segment Table

0x1512

Virtual Memory

Core Concept 4: Segmentation

​

Segmentation Example

​

​

​

​

​

​

CS446/646 C. Papachristos

• 4-bit Segment # (1st HEX digit: 0x0 – 0xF)
• 12-bit Offset (last 3 HEX digits: 0x000 – 0xFFF)

A Process’ Segment Table

0x0: CS

0x1: SS

0x2: DS

…

16-bit Virtual Address (0x0000 – 0xFFFF)

0x4FF

0xFFF

0x6FF

Virtual Memory

CS446/646 C. Papachristos

Virtual Memory

CS446/646 C. Papachristos

Allocated

?

External Fragmentation

Unused –

Internal Fragmentation

Virtual Memory

Core Concept 5: Paging for Virtual Memory Management

​

• Divide Memory up into fixed-size Pages
• Eliminates External Fragmentation

​

• Mapping of Virtual Pages –to– Physical Pages
• A higher level of Virtual Memory Mapping
• Each Process has a separate such Mapping

​

• Allow OS to gain control on certain operations
• Read-only Pages trigger Trap to OS on-Write
• Invalid Pages trigger Trap to OS on-Read or on-Write
• OS can change Mapping and resume Application

CS446/646 C. Papachristos

Virtual Memory

Physical Memory

Virtual Memory

Paging Trade-offs

​

​

​

​

​

​

​

• Eliminates External Fragmentation

​

• Simplifies Allocation, Freeing, and Memory Backing with storage (“Swap”)

​

• Average Internal Fragmentation of .5 Pages per Segment

CS446/646 C. Papachristos

P0 - CS

P1 - SS

Internal Fragmentation

Virtual Memory

Simplified Allocation

​

​

​

​

​

​

​

​

• Allocate any Physical Page to any Process

​

• Can store idle Virtual Pages on Disk (“Paging-Out”)

CS446/646 C. Papachristos

Disk

P0

P1

Virtual Memory

CS446/646 C. Papachristos

Virtual Memory

CS446/646 C. Papachristos

Virtual Address

VPN

Offset

0x5

0x128

MMU

(2 << 12) | 0x128

0x2000 (=2 x 4KiB)

0x128 (Offset)

4 KiB

Page Table

Page

Table

Entries

Virtual Memory

Page Table Entries

• Page Table Entries control Mapping

​

• The Physical Page Number (PPN) determines the Physical Page

​

• The Valid (or Present/Absent) bit indicates whether the Page exists in Memory
• Checked each time the Virtual Address is tries to use this PTE
• Page Fault when Absent
• The Protection bits say what operations are allowed on this Page
• Read, Write, Execute
• Protection Fault on unallowed operation
• The Reference (or Access) bit says whether the Page has been accessed
• It is set when a Read or Write to the Page occurs
• The Modified (or Dirty) bit says whether the Page has been written to
• It is set when a Write to the Page occurs
• The Caching bit enables/disables Caching of the Page
• Related to Translation Lookaside Buffer (TLB) – more soon

​

CS446/646 C. Papachristos

Physical Page Number

V

P

R

C

D

20-bit

32-bit

Virtual Memory

CS446/646 C. Papachristos

Virtual Memory

Paging Advantages

​

• Easy to Allocate Memory
• Memory comes from a “Freelist” of fixed-size chunks (Pages)
• Allocating a Page is just removing it from the “Freelist” (more in Dynamic Allocation)
• External Fragmentation not a problem

​

• Easy to “Page-Out” chunks of a Program (or “Swap-Out” the entire thing)
• All chunks (Pages) are the same size
• Use Valid bit to detect references to “Paged-Out” Pages
• Pages are a convenient multiple of the Disk Block Size (more in Disks & Filesystems)

CS446/646 C. Papachristos

Next Lecture Reading Preparation

Operating Systems – Three Easy Pieces (https://pages.cs.wisc.edu/~remzi/OSTEP/)

​

Virtualization

• 19. Paging: Faster Translations (TLBs)
• Beginning of Chapter
• 19.1 TLB Basic Algorithm
• 19.2 Example: Accessing An Array
• 19.3 Who Handles The TLB Miss?
• 19.5 TLB Issue: Context Switches
• 19.6 Issue: Replacement Policy
• 19.7 A Real TLB Entry
• 20. Paging: Smaller Tables
• Beginning of Chapter
• 20.1 Simple Solution: Bigger Pages
• 20.2 Hybrid Approach: Paging and Segments
• 20.3 Multi-level Page Tables
• 20.5 Swapping the Page Tables to Disk

CS446/646 C. Papachristos

• 23. Complete Virtual Memory Systems
• Beginning of Chapter
• 23.2 The Linux Virtual Memory System

Virtual Memory

CS446/646 C. Papachristos

Virtual Memory

CS446/646 C. Papachristos

32-bit Virtual Address

Secondary VPN

1024 entries (PTEs)

Offset

Master VPN

1024 entries (PDEs)

10-bit long

10-bit long

12-bit long

Remaining 10 bits for

Secondary VPN

Virtual Memory

x86 Page Translation

​

​

CS446/646 C. Papachristos

Physical

Address

Physical Address

Physical Address

Note:

For every Page Directory, we need two 4KiB arrays:

• One with the Physical Addresses of its Page Tables (the one loaded on CR3 and used by the MMU)
• One with the Virtual Address locations of its Page Tables, in order to be able to read from/write to the�Page Tables themselves�(Remember: Code does load/�store on Virtual Addresses)

Virtual Memory

Two-Level Page Tables

​

Evolution

​

CS446/646 C. Papachristos

Page Tables

Two-Level Page Tables

4 MiB

4 KiB

4 KiB

Virtual Memory

CS446/646 C. Papachristos

Two-Level Page Tables

4 KiB

4 KiB

Virtual Memory

Two-Level Page Tables

​

How to access (Secondary) Page Tables themselves?

• I.e. to read/modify them (their Page Table Entries)

​

• Page Directory must hold Physical Addresses (of Page Tables), not Virtual Addresses
• But to read/write to Memory, we need to use Virtual Addresses (!)

​

Solution 1) Have 1 Page Table in the Page Directory reserved to point back to Page Directory

• Now to the MMU, all Page Tables (their Physical Addresses contained in Page Directory) appear as if they were (Physical Addresses of) Pages, and we can access (read/write) all their Page Table Entries as if we were accessing (reading/writing) just normal integers (using native int-sized Offset-ting)
• Downside: Complex to conceptualize, and waste of Total Addressable VAS

​

Solution 2) Keep 2 arrays for every Page Directory

• One contains Physical Addresses of its Page Tables (for MMU usual Address Translation), the other contains Virtual Addresses of its Page Tables, so we can access (read/write) their contents
• Downside: Additional 4KiB per Page Directory (reasonable)

​

CS446/646 C. Papachristos

Virtual Memory

CS446/646 C. Papachristos

Virtual Memory

x86 Paging and Segmentation

​

• ia-32 (x86-32 bit) Architecture supports combined Paging and Segmentation
• A Virtual Address Space consists of multiple Segments, and each Segment is formed�by multiple Pages

Step 1) Segment Base + Pointer Val = Linear Address (also, Segment Bound checking)

Step 2) Linear Addresses translated to Physical Address via usual Page Translation

​

• Two levels of Protection and Translation checking
• Segmentation model: Architecture supports four Privilege Levels (CPL 0-3)
• Paging model: Architecture supports only two, so 0-2 = Kernel-level, 3 = User-level

​

• Why do we want both Paging and Segmentation ?

CS446/646 C. Papachristos

Virtual Memory

x86 Paging and Segmentation

​

• Why do we want both Paging and Segmentation ?

​

• Short answer: We don’t – just adds overhead
• Most OSes simulate “Flat Memory Model”
• IA-32 (x84-32) cannot turn off Segmentation, so OS sets Base = 0x0, Bound = 0xFFFFFFFF in all Segment Registers, then forgets about it (i.e. does not actively leverage Segmentation support)
• x86-64 Architecture removes much Segmentation support

​

• Long answer: Has some fringe/incidental uses
• Already mentioned in previous slide, can be used as follows:

1) Segments for logically related units

2) Pages to partition Segments into fixed-size chunks� • Tends to be complex

• VMware runs Guest OS in Privilege Level CPL 1 to Trap Stack Faults

CS446/646 C. Papachristos

Virtual Memory

Where does the OS live?

​

• Where does the OS live?
• In its own separate Virtual Address Space?
• Can’t do this on most Hardware (e.g. syscall Instruction won’t switch Address Spaces)
• Also would make it harder to parse any System Call arguments passed as Pointers

​

• Common approach: “Sharing” the same Virtual Address Space as the Process
• I.e. there exist some “shared” (same) Page Table Mappings
• Remember: Each Process has its own separate Page Table Mappings
• Can use Protection bits to prohibit User code from accessing Memory belonging to the Kernel-owned part of the (common) Virtual Address Space

​

Note1: Kernel Sharing the total Addressable VAS limits User-Space (on 32-bit Linux, Kernel: 1GB, User: 3GB)

​

Note2: Recent Spectre and Meltdown CPU vulnerabilities force OSes to reconsider things

• https://lwn.net/Articles/743265/

​

CS446/646 C. Papachristos

Virtual Memory

Where does the OS live?

​

• Typically all Kernel Text, most Data remain at�same Virtual Addresses for every Address Space

​

• I.e. for every per-Process Page Table Mapping
• On x86, must manually set up Page Tables for this
• Usually just map Kernel into contiguous Virtual Memory�at the phase when Bootloader puts Kernel into�contiguous Physical Memory
• e.g. in Pintos, Kernel Virtual Memory is mapped one-�to-one to Physical Memory, starting at PHYS_BASE,�and a User Process can only access its own User Virtual�Memory. An attempt to access Kernel Virtual Memory�causes a Page Fault, handled by page_fault().
• In some cases Hardware can also place Pseudo-Physical�Memory (Kernel-only) somewhere in Virtual Address Space

CS446/646 C. Papachristos

Pintos Virtual Memory model

User VM

Kernel VM

User Stack

Heap

Uninitialized Data (BSS)

Initialized Data Segment

Code Segment

Kernel Pseudo-Physical �& Virtual Memory

0xFFFFFFFF

0xC0000000

0x00000000

0x08048000

PHYS_BASE

Invalid Virtual Addresses (for this Process)

Grows Downward

Grows Upward

“Identity Mapping”

Virtual Address Space�of a Process:

Virtual Memory

Where does the OS live?

​

• The Kernel Virtual Memory Mappings are the same across all Processes

​

Implications:

• When we Context Switch to another Process, although it involves changing the Page Tables, the Kernel Virtual Memory Addresses are still valid after the Context Switch

​

• All objects created in Kernel functions remain accessible across all Processes
• e.g. static struct list all_list; threadX->wait_status;
• For example, allows to implement int wait (pid_t pid) where you want to create a variable in struct thread to store some information of the new Child Process (wait_status), and it is necessary to be able to read/write this variable from the Parent Process

​

• Memory for User Processes will be free()d when it exits, but Memory objects allocated within the Kernel code using malloc() should be explicitly free()d

CS446/646 C. Papachristos

Virtual Memory

Where does the OS live?

​

• The Kernel Virtual Memory Mappings are the same across all Processes

​

How ?

• e.g. Pintos

CS446/646 C. Papachristos

struct thread {

tid_t tid; // Thread identifier

enum thread_status status; // Thread state

char name[16]; // Name (for debugging purposes)

uint8_t *stack; // Saved stack pointer

int priority; // Priority

struct list_elem allelem; // List element for

// all threads list

struct list_elem elem; // List element

​

#ifdef USERPROG

/* Owned by userprog/process.c. */

uint32_t *pagedir; // Page directory

#endif

​

/* Owned by thread.c. */

unsigned magic; // Detects stack overflow

};

bool load (const char *file_name, void (**eip) (void), void **esp) {

struct thread *t = thread_current ();

...

​

/* Allocate and activate page directory. */

t->pagedir = pagedir_create ();

​

if (t->pagedir == NULL)

goto done;

​

process_activate ();

​

/* Open executable file. */

file = filesys_open (file_name);

...

}

uint32_t * pagedir_create (void) {

uint32_t *pd = palloc_get_page (0);

if (pd != NULL)

memcpy (pd, init_page_dir , PGSIZE);

return pd;

}

init_page_dir: Initialized in paging_init() in thread.c

Virtual Memory

Where does the OS live?

​

• The Kernel Virtual Memory Mappings are the same across all Processes

​

How ?

• e.g. Pintos

CS446/646 C. Papachristos

bool load (const char *file_name,

void (**eip) (void),

void **esp) {

struct thread *t = thread_current ();

...

​

/* Allocate and activate page directory. */

t->pagedir = pagedir_create ();

​

if (t->pagedir == NULL)

goto done;

​

process_activate ();

​

/* Open executable file. */

file = filesys_open (file_name);

...

}

void process_activate (void) {

struct thread *t = thread_current ();

​

pagedir_activate (t->pagedir);

​

/* Set thread's kernel stack for use in processing interrupts. */

tss_update ();

}

void pagedir_activate (uint32_t *pd) {

if (pd == NULL)

pd = init_page_dir;

​

/* Store the physical address of the page directory

into CR3 aka PDBR (Page Directory Base Register).

This activates our new page tables immediately.

See [IA32-v2a] "MOV—Move to/from Control Registers“

and [IA32-v3a] 3.7.5 "Base Address of the Page Directory". */

asm volatile ("movl %0, %%cr3" : : "r" (vtop (pd)) : "memory");

}

After this point Virtual Memory mappings have changed

Virtual Memory

Addressing Page Tables

​

Where do we store the (Secondary) Page Tables (which Address Space)?

​

• Possibility #1: Reserve Physical Memory
• Consistent to address, no Translation required
• But, allocated (Secondary) Page Tables consume Memory for lifetime of each Virtual Address Space

​

• Possibility #2: General Virtual Memory (in Kernel Virtual Address Space)
• “Cold” (unused, more on that later) Pages can be “Paged-Out” to Disk as we’ve seen so far
• So, entire (Secondary) Page Tables (each being the same size as a single Page) can also be “Paged-Out”
• But! Have to keep Page Directories (/Master Page Tables) from being “Paged-Out”
• called “Wiring”
• avoid circular Page Faults

​

If we’re “Paging-Out” (Secondary) Page Tables, could as well have OS Address Space “Swapped-Out”

• Possible, but some special code and data (Fault, Interrupt Handlers) need to remain “Wired”

​

CS446/646 C. Papachristos

Virtual Memory

Addressing Page Tables

​

• Kernel Address Space is also Page-Mapped

​

• First, “Identity Mapping”:
• Virtual Addresses and Physical Addresses are the same (almost, they differ by constant PAGE_OFFSET)
• Generally up to 4 MiB

​

• After Identity Mapping the Kernel is Page-Mapped to some other Virtual Addresses
• e.g. Linux, Windows

​

• A Process’ PCB contains the Physical Address (remember: “Wired”) of its Page Directory
• This Physical Address is loaded on the %CR3 Register
• The MMU calculates the Addresses of the inner Page Tables and Pages using this
• Remember: Each Process has its own Page Directory, therefore while Task Context Switching the�%CR3 is updated with the Physical Address of the Page Directory of the next Process in the list
• i.e. the inner (Secondary) Page Tables are not even part of the Process’ PCB data structure,�they are just setup and maintained by the OS

CS446/646 C. Papachristos

Virtual Memory

Efficient Translations

​

The single Page Table approach already carries 2x the cost of Memory access

• One indirection into the Page Table, another indirection to the actual Physical Address

​

Now the Two-Level Page Tables 3x the cost!

• 2 indirections into the Page Directory & the (Secondary) Page Table, 1 more to the actual Physical Address
• Worse, 64-bit Architectures (e.g. x86-64) support 4-Level Page Tables
• And this assumes that the target Page Table is already in Memory (i.e. not previously “Paged-Out”)

​

How can we use Paging but also reduce Lookup cost?

• Cache Translations in Hardware

​

• The Translation Lookaside Buffer (TLB)
• TLB managed by Memory Management Unit (MMU)

CS446/646 C. Papachristos

Virtual Memory

Translation Lookaside Buffer (TLB)

​

• Translates a Virtual Page Number into a Page Table Entry (Remember: PTE is PPN + Protection bits)
• An entire PTE, not just the PPN (and not to a Physical Address, this is done by the MMU)
• Translation can be done in a single machine cycle

​

• TLBs implemented in Hardware
• Typically 4-Way to Fully-Associative Memory (i.e. all entries Looked-up in parallel)
• Non-sequential search, Extremely fast, but Expensive
• Cache Keys/Tags are Virtual Page Numbers (VPNs)
• Cache Values are Page Table Entries (PTEs)
• With PTE + Offset, the MMU can directly calculate Physical Address

​

• Intuition: TLBs exploit Locality
• Processes only use a handful of Pages at a time
• 32 - 128 Page Table Entries out of all of the Process’ Pages (128 KiB – 512 KiB of Virtual Memory)
• Only need Page Table Entries for those Pages to be present and “mapped” in the TLB Cache
• Hit rates are very important for performance

CS446/646 C. Papachristos

Virtual Memory

Translation Lookaside Buffer (TLB)

​

CS446/646 C. Papachristos

Virtual Memory

TLB Management

​

• Address Translations for most Instructions are handled using the TLB
• >99% of Translations, but misses do happen (“TLB Miss”)

​

On a “TLB Miss”, who loads Translations into the TLB?

1. Hardware-managed (Memory Management Unit) [e.g. x86, ARM, RISC] (Modern Architectures)

• Knows where Page Tables are in Main Memory
• OS responsible for maintaining Page Tables, and Hardware (re-)loads them directly
• Page Tables have to be in Hardware-defined format
• Inflexible

2. Software-managed TLB (OS) [MIPS, Alpha, Sparc, PowerPC] (Legacy Architectures)

• TLB Faults to the OS, OS finds appropriate Page Table Entry, (re-)loads it into the TLB
• Must be fast (but still 20-200 cycles)
• CPU Instruction Set Architecture (ISA) offers Instructions for manipulating TLB
• Page Tables can be in format convenient for OS
• Flexible

CS446/646 C. Papachristos

Virtual Memory

TLB Management

​

• OS responsible to ensure that TLB and Page Tables are consistent
• e.g. when it changes the Protection bits of a PTE, it needs to Invalidate any corresponding TLB entry

​

• On Process Context Switch the TLB needs to be Reloaded
• Invalidate (possibly all) TLB entries of a VPN (otherwise MMU would continue using the old Translations)
• e.g. invlpg (CPU determines VPN of a given Address and flushes all TLB entries for that Page including the Global TLB mappings –and optionally for current Process Context IDentifier (PCID) or for all PCIDs)
• But we might want to flush TLB entries of a VPN for specific (and non-current) PCIDs
• e.g. invpcid (Control through INVPCID Type over invalidating: 0 – individual Address for specific PCID & not Global, 1 – All Addresses of specific PCIDs & not Global, 2 - All & Global, 3 – All & not Global)

​

When the TLB “Misses” a new Page Table Entry has to be loaded:

• A Cached Page Table Entry must be “evicted”
• Choosing which Page Table Entry to “evict” is called the “TLB Replacement Policy”
• Implemented in Hardware, often simple algorithmically
• e.g. Least-Recently-Used (more later on Eviction Policies)

CS446/646 C. Papachristos

Note: “Global mappings” means they have the same Translation inde-pendently of the current Process Address Space (e.g. Kernel mappings)

Virtual Memory

“Paged”(/“Swapped”) Virtual Memory

​

• Pages can be moved between Memory and Disk
• Use Disk to simulate larger Virtual Memory than physically available
• This process is called “Paging-In” / “Paging-Out”

CS446/646 C. Papachristos

Disk

P0

P1

Swap-Out

Swap-In

Virtual Memory

“Paged”(/“Swapped”) Virtual Memory

​

• Pages can be moved between Memory and Disk
• Use Disk to simulate larger Virtual Memory than physically available
• This process is called “Paging-In” / “Paging-Out”

​

• 1) Gradually Swapping a Process over time
• Initially, Pages are allocated from Memory
• When Memory fills up, allocating a Page requires some other Page to be evicted
• Evicted Pages go to Disk – “Swap” file / backing storage
• Done by the OS, and “invisible” to the Application

​

• 2) Extreme design case: “Demand Paging”
• “Paging-In” a Page from Disk into Memory only if an access attempt is made
• Main Memory essentially acts as a “Cache” for the Disk

CS446/646 C. Papachristos

Virtual Memory

Page Faults

​

What happens when a Process accesses a Page that has been evicted?

• 1. When the OS evicts a Page, it sets the PTE as Invalid (modifies Valid bit) and modifies the location of the Page to point to the Swap file (location where it was “Paged-Out”)
• 2. When a Process accesses that Page, the Invalid PTE access causes a Trap
• “Page Fault”
• 3. The Trap is handled by the OS Page Fault Handler
• 4. Handler uses the Invalid PTE to locate missing Page in Swap file
• 5. Reads Page into a Physical Memory frame, updates PTE to point to that and as Valid
• 6. Restart Process’ Instruction that caused the Fault

​

• But where does it put it? Have to evict something else…
• OS usually keeps a Pool of Free Pages around so that allocations do not immediately cause evictions

CS446/646 C. Papachristos

Virtual Memory

Page Faults

​

​

CS446/646 C. Papachristos

Virtual Memory

All together – the “Normal Operation” case

​

A simple situation: Process is executing on the CPU, and it issues a read to an Address

​

The read goes to the TLB in the MMU

• 1. TLB performs a Lookup using the Virtual Page Number of the Address
• 2. Common case is that the Virtual Page Number finds a TLB match, and returns a�Page Table Entry for the mapping for this Address
• 3. TLB validates that Protection bits of Page Table Entry allow reads (for this particular example)
• If it would fail, “Protection Fault”
• 4. Page Table Entry specifies which Physical Frame holds the Page
• 5. MMU combines the Physical Frame + Offset into a Physical Address
• 6. MMU then reads from that Physical Address, returns value to CPU

​

Note: This is all done by the Hardware

CS446/646 C. Papachristos

Virtual Memory

TLB Misses and Protection Faults

​

Two other things can also happen:

​

• (At step 1.) TLB Miss :
• TLB does not contain a Cached Page Table Entry mapping this Virtual Address

​

• (At step 3.) Protection Fault :
• PTE in TLB, but Memory access violates PTE Protection bits

CS446/646 C. Papachristos

Virtual Memory

TLB Misses and Protection Faults

​

Reloading the TLB

​

If the TLB does not contain the Mapping, two possibilities:

​

1. MMU Hardware loads Page Table Entry from Page Table in Memory

• Hardware-managed TLB (Modern Architectures), OS not involved in this step
• OS has already set up the Page Tables, so that the Hardware can (re-)load it directly

​

2. Trap to the OS – Software-managed TLB (Legacy Architectures)

• OS intervenes & performs Lookup in Page Table, loads the Page Table Entry into TLB
• Remember: Page Directory first, then Page Table, but Page Table might have been “Paged-Out” previously, so it needs to be brought back in (yet another Trap); this process can indeed become quite complicated…
• OS returns from Fault (TLB Miss) Handler, TLB continues

​

• An Architecture will only support one method or the other

CS446/646 C. Papachristos

Virtual Memory

TLB Misses and Protection Faults

​

(Re-)loading the TLB

​

A Page Table Lookup (by Hardware or OS) can cause a recursive Fault if Page Table has been “Paged-Out”

• Assuming Page Tables themselves are in OS part that is Page-Mapped to Kernel Virtual Address Space
• Would not be a problem if all Page Tables remained “Wired” to Physical Memory (like Page Directories)

​

When TLB has Page Table Entry it restarts Translation

• Common case: Page Table Entry refers to a Valid (/Present) Page in Memory
• These Faults are handled quickly, just read Page Table Entry (from the Page Table which is in Memory) and load it into TLB
• Less common case: TLB Faults again on Page Table Entry because of its Protection bits
• e.g. Page is Invalid (/Not Present in Memory) or has mismatching Protection access
• becomes a Page Fault or Protection Fault

CS446/646 C. Papachristos

Virtual Memory

TLB Misses and Protection Faults

​

Protection Faults

​

Page Table Entry can indicate a Protection Fault

• Read/Write/Execute bits – Operation not permitted on Page
• Invalid bit – Page not allocated (for Process), or Page not present in Physical Memory (“Paged-Out”)

​

TLB Traps to the OS (Software takes over)

• R/W/E – “Protection Fault” : OS usually will “forward” the Fault back up to Process
• or might be part of “trick” implementations (e.g. Copy-on-Write, Mapped Files, more later)
• Invalid – “Page Fault”:
• Virtual Page not allocated at all in Address Space of Process
• OS “forwards” the Fault back up to Process (e.g. Segmentation Fault)
• Page not currently present in Physical Memory (i.e. “Paged-Out”)
• OS allocates Physical Frame, reads from Disk, maps Page Table Entry to allocated Physical Frame

CS446/646 C. Papachristos

Virtual Memory

TLB Misses and Protection Faults

​

​

CS446/646 C. Papachristos

“Walk”

Page Table

Protection

Check

Page

Fault

Protection Check

Yes

Protection Fault

Segmentation

Fault

CPU Cache

No

“Page Replacement” Policies

Is P in memory

(Now have PTE & frame)

(Now have PTE & frame)

Virtual Memory

Advanced Functionalities through Virtual Memory “Tricks”

​

1. Copy-on-Write

​

2. Memory-Mapped Files

​

3. Shared Memory

​

CS446/646 C. Papachristos

Virtual Memory

CS446/646 C. Papachristos

Virtual Memory

1. Copy-on-Write

​

CS446/646 C. Papachristos

Before fork()

After fork()

Virtual Memory

1. Copy-on-Write

​

CS446/646 C. Papachristos

After first write

Virtual Memory

2. Memory-Mapped Files

​

• Memory-Mapped Files enable Processes to do File I/O using loads and stores
• Instead of performing System Calls, e.g. open(), read(), write(), fseek()

​

• “Bind” a File to a Virtual Memory Region
• mmap(void *addr, size_t len, int prot, int flags, int fd, off_t offset) in Unix
• Page Table Entries Map Virtual Addresses to Physical Frames holding File’s data
• Virtual Address : [addr + x] refers to [offset + x] into File fd

​

• Initially, all Pages Mapped to a File are Invalid
• OS reads a Page from the File when Invalid Page is accessed (Page Fault handling)
• OS only writes a Page to the File when it is Evicted, or region Unmapped (munmap())
• If Page is not Modified/Dirty (not written-to), no write to File is needed at all
• Yet another clever use for the Dirty bit in Page Table Entries

CS446/646 C. Papachristos

Virtual Memory

2. Memory-Mapped Files

​

CS446/646 C. Papachristos

File-backed Virtual Memory

Virtual Memory

2. Memory-Mapped Files

​

• File essentially also acts as backing store for that region of the Virtual Address Space (similar concepts to using the Swap File)
• Virtual Address Space not backed by “real” Files also called “Anonymous” Virtual Memory

​

Advantages

• Uniform access for Files and Memory (can just use Pointers as the interface)
• Less copying (write-to-File only on Page Eviction, Unmapping)
• Similar motivation as with Copy-on-Write

​

Drawbacks

• Process has less control over data movement (what would happen in a system “crash”?)
• OS handles Faults in a way that is “invisible” to Process
• Does not generalize to streamed I/O (Pipes, Sockets, etc.)

CS446/646 C. Papachristos

Virtual Memory

2. Memory-Mapped Files

​

• File essentially also acts as backing store for that region of the Virtual Address Space (similar concepts to using the Swap File)
• Virtual Address Space not backed by “real” Files also called “Anonymous” Virtual Memory

​

Also very importantly:

• Facilitate Memory Sharing with Persistence
• Several Processes can Memory-Map the same File
• The individual Virtual Address Spaces are mapped to the same Physical Addresses
• Memory Persistence
• Processes can Share Memory that persists independently of their lifetimes
• msync() System Call can be used to trigger a forced flush to Backing Store (File)

CS446/646 C. Papachristos

Virtual Memory

3. Shared Memory

​

• Private Virtual Address Spaces protect Applications from each other
• Usually exactly what we want to accomplish

​

• But data sharing might also be desired
• Parents and Children Processes in a fork()ing Web server or proxy will want to�Share the same in-Memory cache

​

• We can use Shared Memory to allow Processes to share data using direct Memory references
• Both Processes will be able to see updates to the Shared Memory Segment
• Process B can immediately read an update by Process A
• Remember: Requires Synchronization through Shared objects performing some Synchronization Mechanisms

CS446/646 C. Papachristos

Virtual Memory

3. Shared Memory

​

CS446/646 C. Papachristos

Isolation: No Sharing

Sharing Pages

Virtual Memory

3. Shared Memory

​

Implement Inter-Process Communication (IPC) Memory Sharing using Page Tables :

• In both Processes, have Page Table Entries map to the same Physical Frame
• Each Page Table Entry can have different values for its Protection bits
• Must take care to update both Page Table Entries whenever Page becomes Invalid

​

Can map Shared Memory at same or different Virtual Addresses in each Process’ Address Space

• Different: Flexible (no Address Space conflicts),�but the values of Pointers inside the Shared�Memory Segment are (most probably) invalid (Why?)
• Same: Non-portable, but values of Pointers�inside Shared Memory are valid

​

• Also Caution: Pointer in Shared Memory Segment�referencing Address outside the Shared Memory Segment

CS446/646 C. Papachristos

typedef struct {

int * arr_p;

int arr[256];

} data_t;

​

inst shmid = shmget(KEY, sizeof(data_t),

IPC_CREAT | 0666);

data_p = (data_t *)shmat(shmid);

​

data_p->arr_p = data_p->arr; // Possible

// Problem!

Next Lecture Reading Preparation

Operating Systems – Three Easy Pieces (https://pages.cs.wisc.edu/~remzi/OSTEP/)

​

Virtualization

• 21. Beyond Physical Memory: Mechanisms
• Beginning of Chapter
• 21.1 Swap Space
• 21.2 The Present Bit
• 21.3 The Page Fault
• 21.4 What If Memory Is Full?
• 21.5 Page Fault Control Flow
• 21.6 When Replacements Really Occur

CS446/646 C. Papachristos

• 22. Beyond Physical Memory: Policies
• Beginning of Chapter
• 22.1 Cache Management
• 22.2 The Optimal Replacement Policy
• 22.3 A Simple Policy: FIFO
• 22.4 Another Simple Policy: Random
• 22.5 Using History: LRU
• 22.6 Workload Examples
• 22.7 Implementing Historical Algorithms
• 22.8 Approximating LRU
• 22.9 Considering Dirty Pages
• 22.10 Other VM Policies
• 22.11 Thrashing

Time for Questions !

CS-446/646

CS446/646 C. Papachristos