Demand Paging

Time: 95 min.

Optional readings for this topic from Operating Systems: Principles and Practice: Chapter 9.

So far we have separated the programmer's view of memory from the system's view using a mapping mechanism. Each sees a different organization. This makes it easier for the OS to shuffle processes around and simplifies memory sharing between processes.

However, until now a user process had to be completely loaded into memory before it could run. This could be wasteful since a process doesn't use all of its memory at any given time (locality). Demand paging permits a process to run with only some of its virtual address space loaded into physical memory.

Overall goal: allow programs to run without all of their information in memory

  • Keep in memory the information that is being used.
  • Keep unused information on disk in paging file (also called backing store, or swap space)
  • Move information back and forth as needed.
  • Locality: most programs spend most of their time using a small fraction of their code and data.
  • Disk cost is ~100x less than DRAM
  • DRAM is 100,000x faster than disk
  • Ideally: paging produces a memory system with the performance of main memory and the cost/capacity of disk!
  • Like Hermione Granger's purse

When a program is running, each page can be either:

  • In memory (physical page frame)
  • On disk (backing store)

Page Faults

What happens when a process references a page that is in the backing store?

  • Start off with the high-level idea
  • For pages in the backing store, the present bit is cleared in the page map entries.
  • If present is not set, then a reference to the page causes a trap to the operating system.
  • These traps are called page faults.
  • To handle a page fault, the operating system
    • Finds a free page frame in memory
    • Reads the page in from backing store to the page frame
    • Updates the page map entry, setting present
    • Resumes execution of the thread

How does the OS figure out which page generated the fault?

  • x86: hardware saves the virtual address that caused the fault (CR2 register)
  • Skip this??
     On earlier machines OS got only address of faulting instruction, must simulate the instruction and try every address to find the one that generated the fault

Restarting process execution after a page fault is tricky, since the fault may have occurred in the middle of an instruction.

  • If instructions are idempotent, just restart the faulting instruction (hardware saves instruction address during page fault).
  • Non-idempotent instructions are more difficult to restart:
    pushl %eax
    Ask what would happen if the auto decrement occurred after the memory reference.
  • Without hardware support it may be impossible to resume a process safely after a page fault.
    • Hardware must keep track of side effects while executing an instruction
    • Undo all side effects during a page fault
  • Many early architectures did not consider restartability and hence had troubles with demand paging:
    • First versions of Motorola 68000 chips were not restartable; Apollo workstations had two processors, one just for handling page faults.
    • IBM System/370: executed long instructions twice.

Page Fetching

Once the basic page fault mechanism is working, the OS has two policy decisions to make:

  • Page fetching: when to bring pages into memory.
  • Page replacement: which pages to throw out of memory.

Most modern OSes use demand fetching:

  • Draw figure with memory in middle, executable file on left, paging file on right, show various page movements. Show source of zeroes on left.
  • Start process with no pages loaded, don't load a page into memory until it is referenced.
  • The pages for a process divide into three groups:
    • Read-only code pages: read from the executable file when needed.
    • Initialized data pages: on first access, read from executable file. Once loaded, save to the paging file since contents may have changed.
    • Uninitialized data pages (stack, malloc): on first access, just clear memory to all zeros. When paging out, save to the paging file.

Prefetching: try to predict when pages will be needed and load them ahead of time to avoid page faults.

  • Requires predicting the future, so hard to do.
  • One approach: when taking a page fault, read many pages instead of just one (wins if program accesses memory sequentially).
    • Cost to read first 4KB page: 5-10ms
    • Cost for each additional page: .04ms!
    • Read 100 extra pages: adds 4ms.

Page Replacement

Once all of memory is in use, will need to throw out one page each time there is a page fault.

Random: pick any page at random (works surprisingly well!)

FIFO: throw out the page that has been in memory longest. Be fair: give all pages equal residency.

MIN: The optimal algorithm requires us to predict the future. Replace the page whose next access is farthest in the future (put off page faults as long as possible). Not practical because it requires a prophet, but good for comparison.

Least Recently Used (LRU): use the past to predict the future. Replace the page whose most recent access is farthest in the past. If there is locality, then past behavior will predict future behavior, so LRU should perform almost as well as MIN.

Show slide comparing replacement algorithms.

Implementing LRU: need hardware support to keep track of which pages have been used recently.

  • Perfect LRU?
    • Keep a hardware register for each page, store system clock into that register on each memory reference.
    • To choose page for placement, scan through all pages to find the one with the oldest clock.
    • Hardware costs prohibitive in the early days of paging; also, expensive to scan all pages during replacement.
    • No machines have actually implemented this.
  • Current computers settle for an approximation that is efficient. Just find an old page, not necessarily the oldest.

Two extra bits in each page map entry:

  • Referenced: set by hardware whenever a page is read or written.
  • Dirty: set by hardware whenever the page is modified.

Clock algorithm (also called second chance algorithm). To choose page for placement:

  • Cycle through pages in order (circularly).
  • If the current page has been referenced, then don't replace it; just clear the reference bit and continue to the next page. "Second chance."
  • If the page has not been referenced since the last time we checked it, then replace that page.
  • Draw diagram with clock, show analogy.
  • What does it mean if the clock hand is sweeping very slowly (plenty of memory, not many page faults: good)?
  • What does it mean if the clock hand is sweeping very quickly (not enough memory, too many page faults: bad)?
  • Optionally: if the dirty bit is set, don't replace this page now, but clear the dirty bit and start writing the page to disk.

How to implement page replacement when there are multiple processes running in the system?

  • Global replacement:
    • All pages from all processes lumped into a single replacement pool.
    • Each process competes with all the other processes for page frames. One "pig" process can slow the entire system down. Mention performance isolation?
  • Per-process replacement:
    • Each process has a separate pool of pages.
    • A page fault in one process can only replace one of its own frames.
    • Eliminates interference from other processes.
    • Dilemma: how many page frames to allocate to each process? Poor choice can result in inefficient memory usage.
  • Most systems use global replacement.

What happens if memory gets overcommitted?

  • Suppose the pages being actively used by the current threads don't all fit in physical memory.
  • Each page fault causes one of the active pages to be moved to disk, so another page fault will occur soon.
  • Just run another thread?
  • The system will spend all its time reading and writing pages, and won't get much work done.
  • Compute how bad this is (let class try to figure this out?):
    • Assume that memory references normally occur every 100 ns.
    • Disk access 10ms.
    • Suppose 1 in every 100 memory references generates a page fault (i.e. memory is 1% too small).
    • Instead of 107 memory references/second, we get 100*100 (104) memory references/sec: system is 1000x slower!!
    • Progress of the program will make it look like the access time of memory is as slow as a disk, rather than disks being as fast as memory.
  • This situation is called thrashing; it was a serious problem in early timesharing machines with dozens or hundreds of users:
    • Why should I stop my processes just so you can make progress?
    • System had to handle thrashing automatically: stop running some processes for a while.
  • With personal computers, users can notice thrashing and kill some processes, so that others can make progress.
  • Memory is cheap enough that there's no point in operating a machine in a range where memory is even slightly overcommitted; better to just buy more memory.