Grant Novota
About Projects Peaks Blog Links Resume

Virtual Memory

18 Jul 2019

On-Demand Paging

Page tables might be large and cosume a lot of RAM.

A key observation: Not all pages in a logical address space need to be kept in memory.

In the simplest case, we could just keep the current page where the PC is executing and all other pages could be on disk. Then, when another page is needed, we would retrieve the page from disk and place it in memory before executing. This would be costly and slow, because it would happen every time that a page different from the current one is needed.

Instead of just keeping one page, we could keep a subset of a process’s pages in memory. We would load just what we need, not the entire address space and use memory as a cache of frequently or most recently used pages. This would rely on a program’s behavior to exhibit locality of reference. If an instruction or data reference in a page was previously invoked, then that page is likely to be referenced again in the near future.

Most programs exhibit some form of locality.

  • Looping locally through the same set of instructions.
  • Branching through the same code.
  • Executing linearly, the next instruction is typically the next one immediately after the previous instruction, rather than some random jump. Thus process execution revisits pages already stored in memory. So we don’t have to go to disk each time the program counter jumps to a different page.

On-demand paging is used to page in new pages from disk to RAM. Only when a page is needed is it then loaded into memory from disk.

We can page in an entire process on demand starting with “zero” pages. The reference to the first instruction causes the first page of the process to be loaded on demand into RAM. Subsequent pages are loaded on demand into RAM as the process executes.

Advantages of Virtual Memory

  1. Virtual address space can now exceed physical RAM
    • Only a subset (most demanded) of pages are kept in RAM
    • We have decoupled virtual memory from physical memory.
  2. We can fit many more processes in memory.
  3. Swap time is decreased.
    • There is less to swap.
  4. We can have large sparse address spaces.
    • Most of the address space is unused.
    • Does not take up physical RAM.
    • A large heap and stack that is mostly unused/empty won’t take up any actual RAM until needed.

Virtual Memory

Page-fault steps to load a page into RAM:

  1. MMU detects a page is not in memory (invalid bit set) which causes a page-fault trap to OS.
  2. OS saves registers and process state. Determines that the fault was due to demand paging and jumps to page fault handler.
  3. Page fault handler
    • If reference to page not in logical A.S. then seg fault.
    • Else if reference to page in logical A.S., but not in RAM, then load page.
    • OS finds a free frame.
    • OS schedules a disk read. Other processes may run in meantime.
  4. Disk returns with interrupt when done reading desired page. OS writes desired page into free frame.
  5. OS updates page table, sets valid bit of page and its physical location.
  6. Restart interrupted instruction that caused the page fault.

OS can retrieve the desired page either from the disk’s file system or to its swap space/backing store, which is faster because it avoids the overhead of file system lookup.

Pages can be in swap space because:

  • The entire executable file was copied into swap space when the program was first started.
    • Avoids file system, but also allows the copied executable to be laid out contiguously on disk’s swap space, for faster access to pages (no seek time).
  • As pages have to be replaced in RAM, they are written to swap space instead of the file system’s portion of disk.
    • The next time they’re needed, they’re retrieved quickly from swap space, avoiding a file system lookup.

Performance of On-Demand Paging

We want to limit the number/frequency of page faults, which cause a read from disk and slow performance.

  • Disk read is about 10 ms
  • Memory read is about 10 ns

What is the average memory access time?

  • Average access time = p*10 ms + (1-p)*10 ns, where p is the probability of a page fault.
  • If p = .001, then average access time = 10 us » 10 ns (1000 x greater)
  • To keep average access time within 10% of 10 ns, we would need a page fault rate lower than p < 10^-7.
  • Reducing page fault frequency improves performance in a big way.
Top