Lecture 15: Virtual Memory and Processes and Distributed Systems

By: Sijia Lu, Devin Abbott, Yuta Kai

Table Of Contents

• Process Virtual Space
• Page Table
• 2 Level Page Table
• x86 2 Level Page Table Virtual Address
• Page Faulting Process
• Bourne Shell
• FIFO policy
• Belady's Anomaly
• LRU (Least Recently Used)
• LNF (Least Needed in Future)
• Demand Paging

Process Virtual Space

Page Table (to scale)

Similar to sparse files in a Unix file system,

open("foo", O_RDWR|O_CREAT|O_TRUNC, 0600);
lseek(fd,100000000000000000000, SEEK_CGR);
write(fd, "x", 1);

creates a sparse file via indirect blocks.

2 level Page Table

x86 2 level Page Table virtual address

size_t pmap(int vpn) {
    int hi = vpn >> 10;
    int lo = vpn & ((1<<10) - 1);
    int* lopage = PAGE_TABLE[hi];
    if(!lopage)
        return FAULT;
    return lopage[lo];
}

written in C but done in hardware

Page faulting process (unusual case in memory references)

• trap
• kernel gets control
• RETI
  • something useful must happen here, possibilities:
    • terminate the process(big exit status)
    • send a signal to the process SIGSEGV
    • we need to bring a page in from disk

void sighandler(int sig) {
    ~~~~~~~ i = 27; // won't work since value of 'i' might be cached
}

solution: int volatile i

Bourne shell /bin/sh

int* stack;
int stacksize;
stacksize = 8196;
stack = malloc_special(stacksize); // guarantee page fault if you pass end of array
signal(SIG_SEGV, fixstack);

Page Table does the following:

Bourne Shell does: stack[stacksize++] = x;

void fixstack(int sig) {
    realloc(stack, stacksize *= 2); // not exactly realloc
}

mmap:

• lots of arguments
• alters page table in a controlled way
• e.g. "I'd like 0x100000 to 0x1800000 to correspond to contents of this fd + flags (e.g. rwx)

Most common file to mmap is /dev/zero.

The kernel must deal with page faults

// va = virtual address, accessType has flags rwx, cp = current process
void pfault(int va, int accessType, proc_t cp) {
    if(swapmap(cp,va) == FAIL)
        kill(cp);
    else { // choose a victim
        (vp, vva) = removal_policy(); // vp = victim process, vva = victim virtual address
        physaddr = vp->pmap(vva);
        /*write page at physaddr to disk at swapmap(vp,vva)*/
        vp->pmap(vva) = FAULT;
        /*read page at physaddr from disk at swapmap(cp,va)*/
        cp->pmap(va = physaddr);
    }
}

What if this code gets paged out? Don't page out this code!

For swapmap(cp,va) inside kernel memory: disk address for process + size

What's the best way to do I/O to disk?
A. open, (read|write)*, computation, close
B. open, mmap, computation (your Virtual Memory subsystem must be smart), close

Policy: Whose page will be the victim?
If pages are accessed at random ("RAM") then any victim will do
but: we want to exploit LOCALITY OF REFERENCE

FIFO policy example

reference string (sequence of virtual page numbers)
assume 5 virtual pages and 3 physical pages

9 faults

Belady's Anomaly example

Even though we have more RAM, we have 10 faults.

LRU (Least Recently Used) example

10 faults

LNF (Least Needed in Future) example

This is the Optimal Policy with 7 faults.
Instead of using an oracle, the kernel can get statistics from previous reference strings.

Demand Paging

Use virtual memory to shrink wait time for running a program.

1. copy file into RAM (takes a long time)
2. instruction pointer = start of file (running)

Alternate Method(costs one page fault)

1. mmap from file to virtual memory
2. instruction pointer = start of virtual address

With demand paging, we start up faster, but the total cost of loading increases.

Optimizations

• The dirty bit (some hardware has this built in)
  • records for each page whether it has been modified since it was read in

If hardware does not implement the dirty bit, you can do it in software.
When you bring a page in, tell the hardware that it's read only.
The first access causes a trap, and the kernel sets the dirty bit.