Unit 9 Self-Check Quiz

Question

Question 1

Given a 4 KB page size and a 32-bit virtual address, how many bits are used for the page number and how many for the offset? How large is a single-level page table if each entry is 4 bytes?

Answer 1

4 KB = 2¹², so the offset is 12 bits. The page number is the remaining 20 bits. The page table has 2²⁰ = 1,048,576 entries. At 4 bytes each, that is 4 MB per process. This is why single-level page tables are impractical for 32-bit and larger address spaces; multi-level tables allocate only the parts that are used.

Answer 2

4 KB page size: offset = low 12 bits. 0x3A7C = 0011 1010 0111 1100. Page number = 0x3 = 3; offset = 0xA7C = 2684. Page 3 maps to frame 5. Physical address = (5 << 12) | 0xA7C = 0x5000 | 0xA7C = 0x5A7C.

Answer 3

A multi-level page table splits the page number into several indices and uses a tree of tables, one per level. The top-level table points to second-level tables, which point to third-level tables, and so on, until the leaf table contains the frame number. The design solves the size problem of the single-level table: if the process uses only a small fraction of its virtual address space, most of the lower-level tables are not allocated. On x86-64, four levels are used (PML4, PDPT, PD, PT), each indexed by 9 bits of the 48-bit address. A process that uses only a few pages needs only a few lower-level tables, and its page-table overhead is a few kilobytes instead of the hundreds of megabytes a full table would require.

Answer 4

The TLB (translation lookaside buffer) is a small, fast cache of recent page-table entries. On a TLB hit, the translation is available in one cycle; on a miss, the MMU must walk the page table (potentially several memory accesses) and then cache the result. Because almost every instruction accesses memory, and every memory access requires a translation, the TLB is on the critical path of the CPU. Programs with good spatial and temporal locality have very high TLB hit rates, so the effective cost of translation is near zero. Programs that jump randomly across a large working set (pointer chasing through a large graph) have poor TLB behaviour and pay the full page-table-walk cost on most accesses.

Answer 5

A single TLB entry for a 4 KB page covers 4 KB of address space; a single entry for a 2 MB huge page covers 2 MB — 512 times more. For a workload whose working set is much larger than the TLB's coverage (a database, a virtual machine, a large in-memory array), huge pages allow the TLB to cover the working set with far fewer entries, so the hit rate rises dramatically. The trade-off is internal fragmentation (a process that needs only 100 KB but is given a 2 MB huge page wastes ~1.9 MB) and the fact that huge pages must be pre-allocated and are harder to swap. Transparent Huge Pages (THP) in Linux attempt to use huge pages automatically when the access pattern suggests they would help.

Answer 6

Demand paging loads a page into memory only when it is first referenced. The page table entry for an unreferenced page has its valid bit cleared; an access raises a page fault, and the kernel loads the page. The alternative is prepaging, in which the kernel loads pages before they are referenced, either by reading ahead sequentially or by loading the entire program at startup. Demand paging minimises the memory used at any instant and the I/O performed, at the cost of a page fault on every first access. Prepaging reduces the number of faults (a single read can bring in several pages at once) but may load pages that are never used. Modern systems use demand paging with read-ahead for file-backed pages, which is essentially a form of prepaging driven by observed access patterns.

Answer 7

The MMU detects that the page table entry for the accessed address is invalid and raises a page-fault trap.
The kernel saves the faulting instruction's state (program counter, registers) so that the instruction can be restarted.
The kernel checks whether the reference is legal. If the address is not in the process's address space, or the access violates the page's protection, the kernel delivers SIGSEGV and the process terminates.
If the page is legal, the kernel locates the page on backing store (or in the page cache).
If no free frame is available, the kernel selects a victim page via the replacement algorithm and writes it back to backing store if it is dirty.
The kernel reads the required page into the free frame. For a minor fault (the page is already in memory but not mapped), it simply maps the existing physical page into the process's page table.
The kernel updates the page table entry with the frame number and the valid bit.
The kernel returns from the trap, and the CPU restarts the faulting instruction. This time, the translation succeeds.

Answer 8

A minor fault occurs when the page is already in physical memory (for example, in the page cache or as a copy-on-write page from fork) but the page-table entry for this process is not yet established. The handler simply updates the page table; no I/O is required. A major fault occurs when the page must be read from backing store (disk or swap). The handler must issue I/O, block the faulting process, and resume it when the I/O completes. A major fault costs thousands of times more than a minor fault. The ratio of minor to major faults is a useful indicator of the memory pressure on the system: a sudden increase in major faults often signals that a working set no longer fits in memory.

Answer 9

A page is dirty if it has been modified since it was loaded into memory. The MMU sets a dirty bit in the page-table entry on the first write to the page. The kernel tracks dirty pages because a dirty page must be written back to backing store before its frame can be reused; a clean page (one that has not been modified) can be discarded immediately, since the backing store already has an up-to-date copy. Deferring write-back until eviction is efficient because it amortises I/O: many pages are modified several times before eviction, and each modification need not be written individually. The kernel periodically flushes dirty pages to disk to bound the amount of data that could be lost in a crash.

Answer 10

FIFO with 3 frames:

1: F  [1]
2: F  [1 2]
3: F  [1 2 3]
4: F  evict 1 → [4 2 3]
1: F  evict 2 → [4 1 3]
2: F  evict 3 → [4 1 2]
5: F  evict 4 → [5 1 2]
1: H  [5 1 2]
2: H  [5 1 2]
3: F  evict 5 → [3 1 2]
4: F  evict 1 → [3 4 2]
5: F  evict 2 → [3 4 5]

Faults: 9. FIFO with 4 frames:

1: F  [1]
2: F  [1 2]
3: F  [1 2 3]
4: F  [1 2 3 4]
1: H  [1 2 3 4]
2: H  [1 2 3 4]
5: F  evict 1 → [5 2 3 4]
1: F  evict 2 → [5 1 3 4]
2: F  evict 3 → [5 1 2 4]
3: F  evict 4 → [5 1 2 3]
4: F  evict 5 → [4 1 2 3]
5: F  evict 1 → [4 5 2 3]

Faults: 10. More frames produced more faults. This is Belady's anomaly, a counter-intuitive property of FIFO. It arises because FIFO does not satisfy the stack property: the set of pages retained with n+1 frames is not always a superset of the set retained with n frames.

Answer 11

The Optimal (OPT, or MIN) algorithm evicts the page whose next use is farthest in the future. It produces the minimum possible number of page faults for a given reference string and number of frames. It is not implementable because it requires knowing the future reference string in advance — which is exactly what a real system cannot know. It is useful as a benchmark: measuring how close LRU or Clock comes to OPT on realistic workloads tells us how much room for improvement there is. On most workloads, LRU and Clock are within a few percent of OPT, which is why they are considered excellent approximations.

Answer 12

Exact LRU requires, on every memory access, updating a data structure that records the recency of the accessed page. A naive implementation (a timestamp per page) would make every access a write to memory, and the bookkeeping would double or triple the cost of memory access. A doubly-linked list (move the accessed page to the head on every access) has the same problem: every access requires updating the list, and the list manipulation must be atomic on multicore systems. The overhead is unacceptable. Real systems use approximations: the Clock (second-chance) algorithm, which uses a single reference bit per page and a circular pointer; and variants such as enhanced second-chance, which uses a dirty bit as well. The reference bit is set by the hardware on every access and cleared periodically by the kernel, so the kernel only needs to scan the clock hand occasionally rather than update state on every access.

Answer 13

Clock arranges the physical frames in a circular buffer and maintains a clock hand that points to the next candidate. Each frame has a reference bit set by hardware on every access. When a frame is needed:

The hand checks the reference bit of the current frame.
If the bit is 0, the frame is evicted; the hand moves to the next frame.
If the bit is 1, the algorithm clears it (giving the page a "second chance") and advances the hand.

This repeats until a frame with a cleared reference bit is found. The algorithm approximates LRU: pages that have been accessed recently have their reference bit set and get a second chance; pages that have not been accessed have their bit cleared and are evicted. It requires only one bit per frame and a single pointer, making it cheap to implement; Linux uses a variant that also considers the dirty bit (enhanced second-chance) so that clean pages are preferred as victims.

Answer 14

Thrashing is a state in which the sum of the working sets of the running processes exceeds physical memory, so every process faults constantly, the CPU spends most of its time on page-fault handling and I/O, and useful throughput collapses. Symptoms: very high page-fault rate, high disk I/O (especially swap), low CPU utilisation despite many runnable processes, and a system that feels unresponsive even though the CPU is busy. The counter-intuitive aspect is that reducing the degree of multiprogramming (suspending some processes) usually increases throughput, because it allows the remaining processes' working sets to fit in memory.

Answer 15

The working-set model tracks the set of pages referenced by a process in the last Δ time units (or last Δ references). The size of this set is the process's working-set size. The kernel admits a process to the ready set only if the sum of the working-set sizes of the admitted processes does not exceed the number of available frames. The choice of Δ is critical: too small and the working set misses pages the process is actively using; too large and it includes pages the process has already finished with. The page-fault-frequency (PFF) policy monitors the actual fault rate of each process and adjusts its frame allocation: if the rate exceeds an upper threshold, the process is suspended or its frames are reduced; if the rate falls below a lower threshold, more frames are granted. PFF reacts to actual behaviour rather than to a model of it, and it avoids choosing Δ, but it is reactive rather than preventive.

Answer 16

EAT = (1 − p) × memory_access + p × page_fault_time = (1 − 0.0001) × 200 ns + 0.0001 × 8 ms = 0.9999 × 200 ns + 0.0001 × 8,000,000 ns = 199.98 ns + 800 ns = 999.98 ns ≈ 1 μs. The 0.01% fault rate has slowed the system by a factor of 5. This illustrates why even a small fault rate has a large effect: the fault-service time (8 ms) is 40,000 times the memory access time (200 ns). To keep the overhead below 10%, the fault rate must be below 1 in 400,000 — a stringent requirement that only good locality and a large page cache can meet.

Answer 17

7: F  [7]
0: F  [7 0]
1: F  [7 0 1]
2: F  [7 0 1 2]
0: H  [0 7 1 2]
3: F  evict 7 (LRU) → [3 0 1 2]
0: H  [0 3 1 2]
4: F  evict 1 (LRU) → [4 0 3 2]
2: H  [2 4 0 3]
3: H  [3 2 4 0]
0: H  [0 3 2 4]
3: H  [3 0 2 4]
2: H  [2 3 0 4]

Faults: 6. (The first four references are cold misses; the next two are the only replacements, and the remaining references all hit.)

Answer 18

The working set W(t, Δ) is the set of pages that a process has referenced in the time interval (t − Δ, t). It represents the pages the process is actively using, plus a margin for pages it has just finished using but may return to. Its size is a measure of how much memory the process needs to run efficiently. Thrashing occurs precisely when the sum of the working sets exceeds physical memory: each process's working set does not fit, pages are evicted before they are reused, and faults become frequent. By tracking the working set, the kernel can decide how many processes to admit — the ones that fit, and only the ones that fit. The working-set model thus turns a vague notion ("too many processes") into a quantitative criterion.

Answer 19

A copy-on-write (COW) page is a page that is shared between two processes (typically a parent and a child after fork) and marked read-only in both page tables. As long as both processes only read the page, they share the same physical frame — no copy is made. When either process writes to the page, the MMU raises a protection fault, and the kernel allocates a new frame, copies the page's content, and updates the writer's page table so that the write can proceed. The other process continues to share the original frame. COW reduces the cost of fork because the parent's entire address space is not duplicated at fork time; only pages that are subsequently written are copied. Since many children immediately call exec (which discards the copied address space), the copy is often never made at all.

Answer 20

The resident set is the set of pages that are currently in physical memory for a process — that is, the pages whose page-table entries are valid. The working set is the set of pages the process has referenced in the last Δ time units, regardless of whether they are currently resident. The two overlap but are not identical: a page in the working set may have been evicted (it is not resident), and a page may be resident but not in the working set (it has not been used recently and is a candidate for eviction). The kernel's goal is to keep the resident set close to the working set — large enough that few faults occur, small enough that the total resident sets of all processes fit in memory.

Answer 21

Global replacement allows a process to evict frames belonging to any process — the victim is chosen from all frames in the system. Local replacement restricts a process to evicting only its own frames. Global replacement is more efficient on average: a process with a low fault rate is not penalised while a process with a high fault rate is free to grow. But it makes each process's resident set unpredictable — a process's frames may be taken by another — and it can cause a process to thrash even though its working set is small. Local replacement gives each process a stable allocation and predictable performance, but it can waste memory if a process's working set shrinks. Most general-purpose systems use global replacement, with the working-set or PFF policy correcting allocations periodically.

Answer 22

A page fault is raised when the accessed page is legal but not resident — the page-table entry is invalid because the page has not been loaded (or has been evicted). The kernel loads or maps the page and restarts the instruction. A protection fault is raised when the access violates the permissions of the page — a write to a read-only page, an execute of a non-executable page, or an access by an unprivileged process to a supervisor page. The kernel typically delivers SIGSEGV and terminates the process. The two faults are distinguished by the page-table entry's state and by the hardware's error code: a present-but-protected page raises a protection fault, while a not-present page raises a page fault. (Copy-on-write pages blur the distinction: they are present but read-only, so a write raises a protection fault that the kernel handles by copying rather than by killing the process.)

Answer 23

The effective access time (EAT) is the average time to service a memory access. A fraction (1 − p) of accesses hit in memory and take the memory access time; a fraction p fault and take the much larger page-fault service time. The formula is EAT = (1 − p) × mem + p × fault. The fault rate p matters because the fault time is so much larger than the memory time: in a typical system, the fault time is 10⁴ to 10⁵ times larger. A fault rate of 0.01% (1 in 10,000) can multiply the EAT by 5 or more. Keeping p small is therefore the dominant goal of the memory-management subsystem, and it is achieved through good replacement (to keep hot pages resident), read-ahead (to anticipate demand), and adequate physical memory.

Answer 24

/proc/<pid>/smaps reports, for each memory region of a process, the region's size, the resident set size (RSS), the proportional set size (PSS), the shared/private clean and dirty page counts, and the kernel's accounting of swapped pages. It is useful for understanding memory behaviour because it distinguishes:

Resident pages (in physical memory) from virtual pages (mapped but not necessarily resident).
Shared pages (mapped into several processes) from private pages.
Clean pages (backed by a file, can be discarded) from dirty pages (modified, must be written back).
Anonymous pages (heap, stack, mmap without a file) from file-backed pages (executable, libraries, mapped files).

Together these fields reveal where a process's memory is going and which pages would be lost if the process were killed — the shared, file-backed, clean pages would not be lost because the file is on disk; the private, dirty, anonymous pages would be lost because they exist only in memory (or in swap).

Answer 25

Virtual memory works because programs exhibit locality: at any moment, a program accesses only a small fraction of its address space, and that fraction changes slowly, so the fault rate can be kept very low even when the program's total address space is far larger than physical memory. The rare fault is expensive, but it happens so rarely that its cost, averaged over all accesses, is small — and the benefit, in terms of running programs far larger than memory and sharing memory between processes, is enormous.

Unit 9 Self-Check Quiz

Multiple choice and short answer

Ready for the graded quiz?