Chapter 7: Virtual Memory

Question 1

Virtual Memory (VM)

Answer 1

a collection of one or more logical address spaces, each of which may exceed the size of physical memory. A logical address is then referred to as a virtual address. A paged VM creates a single large contiguous address space per process. A paged VM with segmentation creates multiple large address spaces per process, each of which is paged.

Question 2

Demanding Page

Answer 2

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

Question 3

Present Bit

Answer 3

A binary flag in each page table entry that indicates whether the corresponding page is currently resident in memory. If a page is resident, then the entry points to the frame that holds the page.

Question 4

Page Fault

Answer 4

An interrupt that occurs when a program attempts to reference a non-resident page. The interrupt triggers the operating system to find the page on disk, copy the page into a frame, and set the present bit to 1.

Question 5

Page Replacement

Answer 5

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

Question 6

Modified-Bit (m-bit)

Answer 6

A binary flag in each page table entry that indicates whether the corresponding page has been modified during execution. The modified bit is set to 1 automatically by any instruction that stores data into the page and is used by the operating system to minimize the movement of data to disk.

Question 7

reference string

Answer 7

the sequence of page numbers referenced by an executing program during a given time interval. Reference strings are used to compare different page replacement algorithms by counting the number of page faults generated.

Question 8

optimal page replacement algorithm

Answer 8

selects the page that will not be referenced for the longest time in the future

Question 9

FIFO page replacement algorithm

Answer 9

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

Question 10

least-recently-used page replacement algorithm (LRU)

Answer 10

Selects the page that has not been referenced for the longest time.

Implementation:

• Whenever a resident page p is referenced, p is moved to the end of the queue. Thus the queue is always sorted from most recently used page to least recently used page.
• When a non-resident page p is referenced, p is moved to the end of the queue and the least recently referenced page q at the head of the queue is removed. Page p then replaces q in memory.

Question 11

referenced bit (r-bit)

Answer 11

A bit associated with a page that is set automatically by the hardware whenever the page is referenced by any instruction.

Question 12

aging register

Answer 12

Associated with a page and is shifted periodically to the right by 1 bit. Unless the most significant bit is 1, the page is aging in the sense that the associated register value is steadily decreasing.

Question 13

aging page replacement algorithm

Answer 13

does not maintain exact LRU order, but groups together pages referenced during a period of d consecutive references.

1. Shift all aging registers to the right by 1, discarding the least significant bit.
2. Copy the r-bits into the most significant bits of the aging registers.
3. Reset all r-bits to 0.

when a page fault occurs:

• Select the page with the smallest aging register value for replacement.
• If multiple pages have the same smallest value then select one at random.

Question 14

second-chance page replacement algorithm

Answer 14

a coarse-grain approximation of LRU. The algorithm uses the r-bit to divide all pages into only two categories: recently referenced and not recently referenced. A page is selected from the not-recently referenced category.

At a page fault, the algorithm repeats the following steps until a page is selected for replacement:

1. If the pointer is at a page p with r = 0 then select p and advance the pointer to the next page.
2. Otherwise, reset r to 0, advance the pointer to the next page, and continue the search.

Question 15

third-chance page replacement algorithm
or
not-recently-used page replacement algorithm (NRU)

Answer 15

a coarse-grain approximation of LRU, which divides pages into 4 categories based on the 4 possible combination of the r-bit and the m-bit

1. If the pointer is at a page p with r = 0 and m = 0 then select p and advance the pointer to the next page.
2. Otherwise, reset the bits according to the following table, advance the pointer to the next page, and continue the search.

11 01 |
01 00 | modified page
———-|—————–
10 00 | unmodified page