CS111 - Lecture 15

Stephanie Dang, Mitchell Squires, Byron Wong
2012-05-24

Table of Contents

Process Virtual Space

The page table could take up too much room (recall: 4MB / process)

Figure1

There is a large gap in virtual space

The page table contains a lot of unused space

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

It doesn't actually allocate all of this memory, only uses empty indirect blocks

We can apply this concept to page tables:

Multi-Level Page Table

Figure2

x86: 2 level page table

Virtual Address: 10 bit high part, 10 bit low part, 12 bit offset

+------------------------+------------------------+----------------------+
 |   high part (10)   |    low part (10)   |     offset (12)    |
+------------------------+------------------------+----------------------+
 |                Virtual page #               |                       |

size_t pmap(int vpn)
{
      // vpn is virtual page #
      // "pmap" really built into hardware
      int hi = vpn >> 10;
      int lo = vpn & ((1 << 10) - 1);
      int *lopage = PAGE_TABLE[hi];
      if(!lopage)
           return FAULT;
      return lopage[lo];
}

Page Faulting Process

(unusual case in memory references)

/** Send SIGSEGV to the process **/

int volatile i;

// In process: reference a[i], where i is too big
// Go into signal handler
void sighandler(int sig)
{
      set (global variable) i to something else
           If i is global, the program may use a version of i cached in a register, if used in many places
           This won't work ... unless i is volatile
}

Bourne shell (/bin/sh)

Figure3
// Has internal stack:
int *stack;
int stacksize;

Start with small stack:
stacksize = 8196;
stack = malloc_special(stacksize);
// (For malloc_special, memory after stack guaranteed to be inaccessable page fault if access stack+stacksize or later)

// To grow stack:
stack[stacksize++] = x;

// Assume that this is the only bug that will cause SIGSEGV
void fixstack(int sig)
{
      "realloc"(stack, stacksize *= 2);
      // not really library realloc function
}

Low-level memory allocation

mmap(lots of parameters) system call:

When try to access this, page fault, file is brought to this location

Can do I/O without reads or writes

Most common file to mmap is /dev/zero (reads all zeroes, writes ignored)

Can create new memory, initialized to zero

Bad design if there is an actual segfault (ok for Steve Bourne (maybe), not for the rest of us)

Page Faults

The kernel must deal with page faults

Figure4
/** Bring a page in from secondary storage **/
void pfault(int va, int access_type, proc_t cp)
{
// va is virtual address
// access_type is read, write, or execute (rwx)
// cp is current process

      if(swapmap(cp, va) == FAIL)
      // check to see if cp actually has rights to this address
           kill(cp);
      else
      {
           // want to bring page into RAM
           (vp, vva) = removal_policy();
           // vp is victim process
           // vva is victim's virtual process

           physaddr = vp->pmap(vva);
           // write page at physaddr to disk at swapmap(vp, vva)

           // modify victim process' page table
           vp->pmap(vva) = FAULT;

           // read page from disk at swapmap(cp, va), to physaddr
           // modify current process' page table
           cp->pmap(va) = physaddr;
      }
}

Page faults require read from and write to secondary storage (20-30 ms on hard disk)

We want to avoid page faults as much as possible

Page Removal

Q: What if page that holds pfault gets paged out?
A: Don't do that!

The removal policy is tricky, need to be careful which page to remove...

Figure5

What is the best way to do I/O to disk?

B seems more simple, why not do it?

Policy: which page will be the victim?

If pages are accessed at random (the 'R' in "RAM" does stand for Random), then choose a page at random! However, the principle of locality of reference applies and we want to exploit this.

Page Replacement Policies

Assume 5 virtual pages (0-4), 3 physical pages (A-C)

Reference string is a sequence of virtual page #'s (VPNs)

0 1 2 3 0 1 4 0 1 2 3 4

empty entries are garbage

yellow highlighted entries are page faults

FIFO policy
0 1 2 3 0 1 4 0 1 2 3 4
A 0 0 0 3 3 3 4 4 4 4 4 4
B 1 1 1 0 0 0 0 0 2 2 2
C 2 2 2 1 1 1 1 1 3 3
9 faults

What if we get another page of physical memory?

FIFO policy with another page of physical memory
0 1 2 3 0 1 4 0 1 2 3 4
A 0 0 0 0 0 0 4 4 4 4 3 3
B 1 1 1 1 1 1 0 0 0 0 4
C 2 2 2 2 2 2 1 1 1 1
D 3 3 3 3 3 3 2 2 2
10 faults!

Belady's Anomaly: adding RAM can hurt performance (it usually doesn't)


LRU (Least Recently Used)
0 1 2 3 0 1 4 0 1 2 3 4
A 0 0 0 3 3 3 4 4 4 2 2 2
B 1 1 1 0 0 0 0 0 0 3 3
C 2 2 2 1 1 1 1 1 1 4
10 faults!

Note: In practice (not for this contrived example), LRU is better than FIFO

Optimal policy: consult an oracle and find the page least needed in the future
0 1 2 3 0 1 4 0 1 2 3 4
A 0 0 0 0 0 0 0 0 0 2 3 3
B 1 1 1 1 1 1 1 1 1 1 1
C 2 3 3 3 4 4 4 4 4 4
7 faults

You can run the program, get reference string, and use this for the next execution.

More generally, get statistics from previous reference strings to approximate oracle.

Use Virtual Memory to Shrink Wait Time for Running a Program

  1. Copy program into RAM
  2. ip = start of file (running)

Step 1 takes a long time, so instead:

Demand Paging:

  1. mmap from file to virtual memory
    we have not read/written into memory - just set up the page table
  2. ip = start (virtual address)
    automatic page fault, and get the file through the first page fault

Faster to copy one page than entire program

  1. + start up faster
  2. - total cost of loading increases (bring in one page at a time)

Optimizations

Dirty Bit

The dirty bit records for each page whether it has been modified since it was read in. If dirty bit is clear, no need to write out to disk. Some hardware does this for you. Otherwise, can do this in software.

When you bring a page in: