CS 111 Lecture 14 Scribe Notes: Virtual Memory

Contents

• File System Robustness
  • Variations
• Virtual Memory
  • Simple Approach
  • Segmented Memory
  • Virtual Memory and Paging

File System Robustness (continuation from previous lecture)

We would like our file systems to support atomic updates in the presence of power failure. We used two big ideas:

1. Commit records
2. Journaling

A general process for an atomic action implementation:

• BEGIN
  • Pre-commit phase:
    • Save just enough of the details so if things crash, we remember what you were about to do. It is safe to back out of this phase.
  • COMMIT or ABORT
  • Post-commit phase
    • Clean up and do performance optimizations. Can't back out.
• END

To the user, all of this will appear as one step.

Variations

Main memory database

We can modify the journals we observed in the previous lecture by keeping the cell data in RAM (caching it) instead of on disk. Changes will be logged to the disk.

Pros:

• Access to cells is very fast (RAM speed)
• No seeks when writing (appending to the same log over and over again).

Cons:

• Access to cells is very fast (RAM speed)
• No seeks when writing (appending to the same log over and over again).

Logging Protocols

We have been discussing "write-ahead" logs. Alternatively, we can use "write-behind" logs. Both work, but they differ in their recovery procedures.

Write-ahead

• Steps:
  1. Log planned writes
  2. Commit
  3. Install new values
• Recovery:
  • Scan forwards through the log looking for actions that have been committed but not yet installed. Finish up these actions.
• Advantages:
  • More likely to save the last action and doesn't need to know the old values.

Write-behind

• Steps:
  1. Log old cell values
  2. Install new values
  3. Commit
• Recovery:
  • Scan backwards through the log looking for actions marked as begun but not committed. Restore old, uncommitted values.
• Advantages:
  • Old data is typically cached anyway (counterargument to write-ahead argument)
  • More conservative/cautious
  • More recovery is possible
  • Recovery tends to be faster because you know where the log ends. We scan from right to left until the most recent end point and then stop scanning (write-ahead requires scanning back and forth).

Cascading Aborts and Compensating Actions

We have two processes, P1 and P2. P1 is scheduled to perform its atomic action before P2.

• Cascading Aborts
  • As P1 is performing its atomic action, we can tell P2 the file size. We then later tell P2 that an error occurred in P1 and P2 will abort its transaction. Multiple processes can be nested and aborts in inner processes will abort outer processes, thus the aborts cascade.
  • In a write-ahead log, an abort would look like:
    • log planned writes
    • commit abort record
    • install new value
• Compensating Actions
  • As P1 is performing its atomic action, we can tell P2 the file size. We then later tell P2 that an error has occurred in P1. P2 must now perform compensating actions to make sure it tells the correct story after it made assumptions from P1.

Cascading aborts are more automatable, but compensating actions are more flexible.

Virtual Memory

We've examined how to protect our data from problems with the hardware such as power outages. Now we'll examine a different form of unreliability that can cause problems: unreliable programs that make bad memory references.

Here are some possible solution:

• Hire better programmers!
• Get help from the hardware and/or emulator
  • faster
  • can do pointer checking in parallel
  • popular for performance reasons
• Get help from compiler and/or runtime
  • turn nullptr checking on
  • slows down programs, but detects problems and makes them more debuggable

A Simple Approach

When P1 runs, two registers will store the base and bounds of P1's memory. Any memory address M that is accessed by P1 will be checked: P1_base <= M < P1_bounds.

Downsides to this approach:

• Requires contiguous RAM for each process
• Hard to share data between programs
• Can't have identical programs
• All instructions must be relative. This is called position-independent code and is a bit slower because it gives the compiler less options to optimize. We can use virtual addresses to allow for absolute jmps and calls. Memory access would then look like: P1_base <= P1_base  + M < P1_bounds

New Approach: Segmented Memory

Each process has 8 base-bound pairs for each segment of memory. Examples of the segments are text, data, stack, etc. 32-bit addresses can be split so that the first 3 bits represent the segment number and the rest of the 29 bits represent the offset within the segment.

Pros:

• No longer requires contiguous RAM for each process

Cons:

• Still has external fragmentation
• Segment sizes are limited

Virtual Memory and Paging

Each process is given its own address space of 32 bits, or 4 GB

We split the address space into fixed sizes called pages.

We will split the virtual address number into two sections forming a virtual page number (VPN) and an offset (PO). The first 20 bits will be the virtual page number and the rest of the 12 bits will be the page offset.

12 offset bits means that each page is 2¹² bytes long, or 4 KB. The number of pages is then memory_size/page_size = 2³²/2¹² = 2²⁰

The OS takes first 20 bits of the virtual address space and put it into a function that maps the virtual page number to a physical page number (PPN). The physical page number and the page offset combined gives the physical address of where the data is actually stored. This mapping is done using a page table. The page table lives in RAM and the %cr3 register points to the page table.

Each process has its own page table.

The process table has an entry for each virtual page number (2²⁰).

Each entry in the page table is made of 32 bits (4 bytes). Let's assume that we need 20 bits for the physical page number. Then the first 20 bits of the page table entry are for the physical page number. The rest of the 12 bits can be used for flags (such as read/write permissions).

The page table has an entry for each page 2²⁰. The page table size is number_of_entries * entry_size = 2²⁰ * 4 bytes = 2²² bytes = 4 MiB. That's per process!

Having hundreds of processes means that we quickly use up a lot of space for page tables. To reduce memory usage, we can create another level of indirection by using a multilevel page table.

Click here to see a diagram of two-level page table.

With virtualization and paging, programs can use more than physical memory! However, potential problems that can occur include thrashing. Performance can be really bad if the locality of references are not practical and cause to thrash.

Page Faults

Page faults occur when a process cannot access a page (it doesn't have access privileges, the page is not in RAM, etc.). When a page fault occurs, a trap is generated and the kernel decides how to deal with it. Here is some pseudo-code to give an idea of how page faulting works:

int swapmap(virtual_address, current_process) {
    if invalid address in swap space
        return 0
    else
        return address in swap space
}

void pfault(void * virtual_address, struct proc *current_process, int access_type) {
    if(swapmap(virtual_address, current_process) == 0)
        kill (current_process, SIGSGSV);
    else {
        pick a victim physical page (details in later lecture)
        (vppn, vva) = removal_policy();
        write out vppn to disk
        read in desired page to same physical location
        page_table[vva] = 0;
        page_table[va] = vppn;
        return; // re-execute the instruction that failed
}

External references

Wikipedia - Virtual Memory

Wikipedia - Page Table

Wikipedia - Page Faults