CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 6 of 7 · 4 min read

The backing store

Where the missing page comes from

Think of it this way. A library lends only some of its books at a time, but it knows where every book belongs on a shelf. In the same way, every page that may be absent from memory needs a home to be fetched from. The analogy stops in one place: a library has one shelf for each book, while a page may be copied in memory and also kept on disk, and the two copies may differ.

The home depends on the kind of region:

  • Anonymous memory, such as the heap and the stack, has no file. The first touch of a page gives a frame of zeros. If memory later runs short, the kernel may write the page to swap space, a region of the disk set aside for this, and read it back at the next fault.
  • File-backed memory, such as the program's code and files mapped with mmap, is read from the file. A page of the program code is never written back, because the file already holds it. A changed page of a mapped file is written back to the file.
  • Copy-on-write pages (page 6) start as shared pages of another process, and a write gives the writer its own copy.

In plain words: This is why the fork-then-exec pattern of Level 1 is cheap: the new program is not read at all at the start. Its code pages fault in one at a time, from the file cache or from disk, as the program runs.

The kernel can also help the program. Reading a file in order often leads to prefetching: after a fault, the kernel reads several following pages at the same time, because the next page is probably wanted soon. The 516 faults for 16,384 pages in section 3 are a result of this, and of the mapping of many cached pages at each fault.

Backing store

The backing store of a page is the place the kernel can read the page from when it is absent from memory: swap space for anonymous pages, and the file itself for file-backed pages.

Example: a page of a shared library is backed by the library file, while a page of the heap is backed by swap space once it has been written out.

Check yourself: 1. What is the backing store of a stack page, and of a page of program code? 2. Why is a code page never written to swap space? 3. How does prefetching reduce the number of faults?

Words you will meet

Word Meaning
Demand paging A page is brought in at its first use
Pure demand paging A process starts with no pages in memory
Present bit A page table bit that says whether the page is in memory
Page fault The exception raised on an access to an absent page
Restartable instruction An instruction that can run again from its start after a fault
Minor fault A fault fixed without a storage read
Major fault A fault that waits for a storage read
Page-fault rate The share of accesses that fault
Backing store The place an absent page is read from
Swap space Disk space that holds pages of anonymous memory
Prefetching Reading pages before they are asked for

Quick notes

  • Demand paging is the scheme in which a page is brought into memory only when a process first uses it, and the page table marks pages that are absent with a present bit set to zero.
  • A page fault is an exception raised by the hardware when an access uses a page whose page table entry does not allow it, usually because the present bit is.
  • A major page fault is a page fault whose handling must wait for a read from storage, while a minor page fault is one that the kernel fixes with no.
  • The page-fault rate is the share of a process's memory accesses that cause a page fault, and it enters the effective access time as the weight of the fault service time.
  • The backing store of a page is the place the kernel can read the page from when it is absent from memory: swap space for anonymous pages, and the file itself for file-backed pages.