Virtual memory and demand paging

Why it exists

A program rarely needs all of its code and data at once: error-handling routines almost never run, a large array is used a part at a time, and a program may be bigger than the physical memory. Virtual memory separates the memory the programmer sees (a large, uniform virtual address space) from the memory the machine has. Only the parts in use are kept in RAM, the rest waits on disk. This lets programs be larger than memory, lets more programs run at once (each uses less RAM), and makes starting a program faster. The cost appears when a needed part is not in RAM: a page fault. GATE asks what a page fault does, how to compute the effective access time with page faults, and how large a fault rate a system can tolerate.

Prerequisites

You need the page table, the valid bit and the translation of addresses from paging.

Precise definitions

Virtual memory. A technique that lets a process run although only part of it is in physical memory. The virtual address space (size fixed by the address width) can be much larger than physical memory. The disk area that holds the pages not in memory is the backing store or swap space.

Demand paging. Pages are brought into memory only when they are needed (when a reference to them is made), like a swapper that never loads a page that will not be used (a lazy swapper, or pager). In pure demand paging a process starts with no pages in memory at all and faults on its first instruction.

Valid-invalid bit. Each page-table entry has a bit. With virtual memory it means:

• valid (1): the page is legal and is in memory (the entry holds its frame);
• invalid (0): either the page is illegal (not part of the process's address space) or it is legal but not currently in memory. The operating system keeps, for such a page, its disk address.

Page fault. The trap that occurs when a process references a page whose valid bit is 0. Handling it:

1. The hardware traps to the operating system (saving the state of the process).
2. The operating system checks an internal table to see whether the reference was legal. If it was illegal, the process is terminated.
3. If it was legal but the page is not in memory, the OS finds a free frame. If there is none it chooses a victim page with a page-replacement algorithm (page replacement); if the victim was modified (its dirty/modified bit is 1) it is first written back to disk.
4. The OS schedules a disk read of the needed page into the frame. Meanwhile the process is blocked and the CPU may run another process.
5. When the read completes (a disk interrupt), the OS updates the page table (frame number, valid bit 1) and the frame table.
6. The OS makes the process ready; when it runs again, the instruction that faulted is restarted from the beginning, and now succeeds.

The hardware must be able to restart an instruction after a fault; some instructions that change several locations (block moves) need special care.

Effective access time (EAT) with page faults. If the page-fault rate (probability that a reference faults) is $p$, the memory access time is $ma$ and the time to service a fault is $T_f$,

$\text{EAT} = (1 - p)\,ma + p\,T_f.$

$T_f$ is dominated by the disk: a disk access takes milliseconds while a memory access takes nanoseconds, a ratio of about $10^5$ to $10^6$. If the victim is modified, the page must be written out as well as read in, so $T_f$ is about doubled: with a probability $q$ that the victim is dirty, $T_f \approx T_{read}(1 + q)$.

Locality of reference. Programs tend to use the same pages again and again in a short period (temporal locality), and to use pages near those just used (spatial locality). Demand paging works only because the fault rate is tiny in practice: the set of pages in active use (the working set, thrashing) fits in memory.

Copy-on-write (COW). When a process is forked, parent and child share the same physical pages, all marked read-only. Only when one of them writes to a page does the OS make a private copy of that page for the writer. A fork of a process of 100 pages in which the child writes to 5 pages copies 5 pages, not 100; if the child calls exec at once nothing is copied.

Memory-mapped files. A file is mapped into the virtual address space; reading and writing memory reads and writes the file, with the file's disk blocks acting as the backing store and pages loaded on demand.

How it works

The animation shows demand paging for a process of 8 pages in a memory of only 3 frames. The page table (left) starts empty: every valid bit is 0. Seven references are made. A reference to a page that is already in memory (reference 3, to page 2) just translates. Otherwise there is a fault: the page is loaded into a free frame, or into the frame of the least recently used page when memory is full, the table changes, and the reference is restarted and succeeds. Watch the valid bits and frame numbers change in the table from step to step.

Worked examples

#include <stdio.h>
 
int main(void) {
    /* effective access time with page faults: ma = 200 ns, fault service time 8 ms */
    double ma = 200, service = 8e6;
    double ps[3] = {0, 1e-3, 1e-6};
    for (int i = 0; i < 3; i++) {
        double p = ps[i];
        printf("page fault rate %.0e: effective access time %.1f ns (slowdown %.1f%%)\n", p, (1 - p) * ma + p * service, 100 * ((1 - p) * ma + p * service - ma) / ma);
    }
    /* the largest fault rate that keeps the slowdown below 10 percent */
    double pmax = 0.10 * ma / (service - ma);
    printf("for at most 10%% slowdown: p < %.4g, i.e. fewer than one fault per %.0f references\n", pmax, 1 / pmax);
    /* demand paging with 3 frames and LRU on the page references of the animation */
    int refs[7] = {2, 5, 2, 7, 0, 5, 3};
    int page[3] = {-1, -1, -1}, last[3] = {0, 0, 0}, faults = 0;
    for (int t = 0; t < 7; t++) {
        int slot = -1;
        for (int i = 0; i < 3; i++) if (page[i] == refs[t]) slot = i;
        if (slot < 0) {
            faults++;
            for (int i = 0; i < 3; i++) if (page[i] < 0) { slot = i; break; }
            if (slot < 0) { slot = 0; for (int i = 1; i < 3; i++) if (last[i] < last[slot]) slot = i; }
            page[slot] = refs[t];
        }
        last[slot] = t + 1;
    }
    printf("page faults for 7 references with 3 frames (LRU): %d\n", faults);
    return 0;
}

page fault rate 0e+00: effective access time 200.0 ns (slowdown 0.0%)
page fault rate 1e-03: effective access time 8199.8 ns (slowdown 3999.9%)
page fault rate 1e-06: effective access time 208.0 ns (slowdown 4.0%)
for at most 10% slowdown: p < 2.5e-06, i.e. fewer than one fault per 399990 references
page faults for 7 references with 3 frames (LRU): 6

Cheat box

Traps and GATE patterns

Connections

Demand paging is paging with the valid bit used to mean "on disk". Choosing a victim is the subject of page replacement; keeping the fault rate low enough needs each process to have its working set in memory (thrashing and the working set); the cost of the extra translation accesses is reduced by the TLB. A process that waits for the disk is in the Waiting state of the process life cycle, and copy-on-write is what makes fork cheap.

PYQs

Consider a system that has a cache memory unit and
a memory management unit (MMU). The address
input to the cache memory is a physical address. The
MMU has a Translation Lookaside Buffer (TLB).
Assume that when a page is evicted from main
memory, the corresponding blocks in the cache are
marked invalid.

For a given memory reference, which of the following
sequences of events can NEVER happen?

Which
of
the
following
tasks
is/are
the
responsibility/responsibilities
of
the
memory
management unit (MMU) in a system with paging-
based memory management?

Consider the following two-dimensional array D in
the C programming language, which is stored in
row-major order:

int D[128][128];

Demand paging is used for allocating memory and
each physical page frame holds 512 elements of the
array D. The Least Recently Used (LRU) page-
replacement policy is used by the operating system.
A total of 30 physical page frames are allocated to
a process that executes the following code snippet:

for (int i = 0; i < 128; i++)

for (int j = 0; j < 128; j++)

D[j][i] *= 10;

The number of page faults generated during the
execution of this code snippet is

Consider a paging system that uses a 1-level page
table residing in main memory and a TLB for
address translation. Each main memory access
takes 100 ns and TLB lookup takes 20 ns. Each
page transfer to/from the disk takes 5000 ns.
Assume that the TLB hit ratio is 95%, page fault
rate is 10%. Assume that for 20% of the total page
faults, a dirty page has to be written back to disk
before the required page is read in from disk. TLB
update time is negligible. The average memory
access time in ns (round off to 1 decimal place) is
______.

Consider a process executing on an operating system
that uses demand paging. The average time for a
memory access in the system is M units if the
corresponding memory page is available in memory
and D units if the memory access causes a page fault.
It has been experimentally measured that the average
time taken for a memory access in the process is X
units.

Which one of the following is the correct expression
for the page fault rate experienced by the process?

Let the page fault service time to 10 ms in a
computer with average memory access time being
20 ns. If one page fault is generated for every 106
memory accesses, what is the effective access time
for the memory?

A computer system supports 32-bit virtual addresses
as well as 32-bit physical addresses. Since the virtual
address space is of the same size as the physical
address space, the operating system designers decide
to get rid of the virtual memory entirely. Which one
of the following is true?

Increasing the RAM of a computer typically improves
performance because:

What is the swap space in the disk used for?

Self-check

Revision card

References