Lecture 15: Virtual Memory & Paging

By: Aditya Kajla & Jay Topiwala

A Process's virtual space:

• Mapping of virtual addresses (process) to physical memory:
  
• Mapping from virtual to physical addresses is handled via a page table
• Problem with the page table - The area between the stack and the heap is unused
• Similar to a problem in file systems - sparse files in Unix:

• fd = open("foo", O_RDWR | O_CREAT | O_TRUNC, 0600);
  lseek(fd, 10000000000000, SEEK_CUR);
  write(fd, "x", 1); //creates a sparse file

• Allocating the entire file upon creation when even the data is unavailable is inefficient
• Basic premise: create the data structure that represents the file and simply allocate the indirect blocks without necessarily allocating data blocks
• Similarly, we can have multi-level page tables (ex. 2 levels):
  • A top level page table points to indirect page tables which point to actual pages (memory)
  
• This is supported in x86
  • Addresses (32-bits) in which 10 bits represent index in page directory (1st table), 10 bits for index in indirect page table and 12 bits for offset within actual page
  • Sample code to look up an address using a vpn: (this is carried out within hardware)

    size_t pmap(int vpn) {
    

    int hi = vpn >> 10;
    int lo = vpn & ((1 << 10) - 1);
    int *topage = PAGETABLE[hi]; // register cr3
    if (!topage)
    return FAULT;

    }

Page Faults:

• Since physical memory is usually limited, accessing certain page mappings might result in a request for a page that is not currently in physical memory - this is known as a page fault
  • the page must be loaded from disk to memory in order for the process to continue running
• Page faults are hardware traps (similar to interrupt)
• Kernel gets control --> can return to app using RETI
• BUT: kernel can't simply return using RETI - it must do something useful to resolve the page fault otherwise page fault will occur again
• What can we do when a page fault occurs?
  • Mark the process as terminated
  • Give it a big exit status (100+)
  • Send the process a signal, giving it an opportunity to clean-up, or even repair the situation
  • SIGSEGV, then RETI to resume process
• Ex: Try to reference a[i] where i is too big
  • can be a problem - i might be cached in a register
  • So our signal handler might not be able to properly change the value of i
  • must use "volatile" keyword with i to ensure it is never cached in a register
  • these are the types of cases we need to worry about when dealing with page faults
• Real-life case - Bourne Shell:
  • Utilizes code that doesn't error check for indexes in order to grow the stack
  • An index error triggers a signal handler that reallocates more memory for the stack
    • Assumes that error indicates allocation failure - no other bugs are responsible
    • BIG assumption - generally not a good idea
• Instead, we can use mmap
  • mmap maps addresses to file/memory location
  • alters page table in a controlled way
  • Note: can't completely change page table due to security issues
  • Example: "I'd like 0x1000000 - 0x1800000 to correspond to contents of fd"
    • allows I/O without explicitly using the read system call
    • However, this takes a lot of virtual memory so it's better to still utilize the system call for reading
  • flags passed to mmap set read, write, executable bits
• Sample code for a page fault function:
  
  
• The swap space is the area where the process resides
  • RAM is a physical cache of swap space
• The above function can take between 20 - 30 ms to execute
• Therefore, it is important to avoid page faults as much as possible
• Where does this code run?
  • within memory
  • NOTE: code for this function must never be overwritten/paged out (part of removal_policy)
• Overview
  • virtual addresses - visible to both the app and the kernel
  • physical addresses - visible only to the kernel
  • disk addresses:
    • file offset - visible to both the app and the kernel
    • swap space - visible to the kernel
      • contiguous region of disk

Page Replacement Policies:

• How do we decide who will be the victim?
• If pages are accessed at random (RAM), any victim will do
• But, keep in mind locality of reference
  • In practice, accesses to pages are not random
  • we should exploit this fact
• We can compare different replacement policies using a reference string
  • defines a sequence of pages accessed by a process
  • Sample reference string: 0,1,2,3,0,1,4,0,1,2,3,4 (5 virtual pages)
  • 3 physical pages: A,B,C
• FIFO (First In - First Out)
  • Pick victims that have been around for the longest time
  • 9 total page faults (highlighted in red)
  
  
  
• FIFO with more RAM
  
  • 10 total page faults despite more physical memory
  • Belady's anomaly: adding RAM can sometimes hurt performance
• LRU (Least Recently Used)
  
  • 10 page faults
• LNF (Least Needed First -- optimal solution)
  
  • "Consult an Oracle"
  • Kernel can try to get statistics from previous reference strings (runs of an app) and use those to approximate "consulting an oracle"
  • overall less page faults - 7 page faults

More Optimizations:

• Demand Paging
  • Load a process's first page into memory and begin running the process
  • Additional pages loaded into memory on demand when required
  • Improves start-up time for programs
  • However, the total cost of loading increases (might need other parts of the file which requires multiple loads)
• Dirty Bit
  • Keep a record (single bit) for each page indicating whether it has changed since it was last read into memory
    • built into some hardware
  • If a page hasn't been modified, it does not need to be written back to disk, saving time
  • Can also be implemented within software (kernel) if not supported by hardware
    • on a page fault, the kernel interrupts and flips a bit
  • Advantages/Disadvantages of software vs. hardware approach?
    • depends on situation - saving hardware frees it up for other uses but doing this in software might cause more kernel overhead