Operating Systems - Chapter 7

Virtual memory (VM)

A collection of one or more logical address spaces, each of which may exceed the size of physical memory.

Virtual address

A logical address in virtual memory.

Demand paging

The principle of loading a page into memory only when it's needed, rather than at the start of execution.

Present bit

A binary flag in each page table entry indicating whether the corresponding page is currently resident in memory.

Page fault

An interrupt that occurs when a program references a non-resident page, triggering the OS to load it from disk.

Page replacement

The act of overwriting a page in memory with a different page loaded from disk.

Modified bit (m-bit)

A binary flag in each page table entry indicating whether the page has been modified during execution (set automatically on a write).

Reference string

The sequence of page numbers referenced by an executing program during a time interval.

Optimal page replacement algorithm

Selects the page that will not be referenced for the longest time in the future; unrealizable in practice but gives a lower bound on page faults.

FIFO page replacement algorithm

Selects the page that has been resident in memory for the longest time.

Least-recently-used (LRU) algorithm

Selects the page that has not been referenced for the longest time; implemented via a queue sorted from least- to most-recently used.

Referenced bit (r-bit)

A bit set automatically by hardware whenever a page is referenced.

Aging register

A register associated with a page that is shifted right periodically; used to approximate LRU by tracking recent access history.

Aging page replacement algorithm

Groups pages by recency using aging registers; replaces the page with the smallest register value.

Second-chance (clock) algorithm

A coarse LRU approximation using the r-bit and a circular pointer; gives a page a "second chance" if r = 1.

Third-chance (not-recently-used/NRU) algorithm

Refines second-chance by also using the m-bit, giving modified pages extra chances since replacing them is costlier.

Optimal working set

The set of resident pages that will still be needed in the immediate future (determined via a forward-looking window of size d).

Working set (WS)

The set of pages referenced during the past d memory operations preceding time t (trailing window).

Working set page replacement algorithm

Keeps resident only pages visible in a trailing sliding window of size d.

Page-fault-frequency (PFF) replacement algorithm

Adjusts the resident set size based on the frequency of page faults, using a threshold d.

Page fault rate (P)

P = f/t, the fraction of memory references that result in a page fault (0 ≤ P ≤ 1).

Effective access time (E)

The average memory access time accounting for page fault overhead.

Load control

Determining how many processes should run concurrently to maximize system performance.

Thrashing

A state where most time is spent moving pages between memory and disk, with little real progress made (CPU nearly idle).

L = S criterion

Load control heuristic: CPU utilization is near-optimal when mean time between page faults (L) equals the time to service a page fault (S).