COMP 322 Chapter 7: Virtual Memory

Question 1

Virtual Memory

Answer 1

A collection of one or more logical address spaces.

It may exceed the size of the physical memory

Question 2

Demand paging

Answer 2

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

Question 3

A present bit

Answer 3

A binary flag/bit in a page table, it indicates whether the corresponding page is currently resident in memory.

If the page is resident, the entry points to the frame that holds the page.

Question 4

A page fault

Answer 4

An interrupt that occurs when the program attempts to reference a non-resident page.

if a page fault occurs it sets 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

The modified-bit (m-bit)

Answer 6

A binary bit 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 OS.

Question 7

Potential size of the Virtual Memory (VM)

Answer 7

2^(64)

Question 8

Potential size of segment and page tables

Answer 8

2^(26)

Question 9

A reference string

Answer 9

The sequence of page numbers referenced by an executing program.

Question 10

The optimal page replacement algorithm

Answer 10

An algorithm that searches the most distant resident page and replaces it with the page that causes a page fault.

Question 11

FIFO page replacement algorithm

Answer 11

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

It takes advantage of the principle of locality.

Question 12

Least-recently-used page replacement algorithm (LRU)

Answer 12

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

Requires a queue of length n (The number of memory frames).

When a page fault occurs, the page at the head of the queue is removed and and a new page is inserted at the end.

Question 13

Requirement for the LRU

Answer 13

The LRU requires the queue of the pages to be modified at each memory reference.

Question 14

The referenced bit (r-bit)

Answer 14

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

Question 15

Aging register

Answer 15

it is associated with a page and is shifted periodically to the right by 1 bit.

Question 16

The aging page replacement algorithm

Answer 16

Does not maintain the pages sorted in the exact LRU order.

It groups together pages referenced during a period of consecutive references.

Each period is represented by 1 bit when shifting the aging register.

Question 17

Second-chance page replacement algorithm

Answer 17

Is a coarse grain approximation of LRU.

It uses the r-bit to divide all pages into two categories:
recently referenced and non-recently referenced.

A page is then selected from the not-recently referenced category.

Question 18

The third-chance page replacement algorithm

Answer 18

aka the not-recently used page replacement algorithm (NRU).

It is a coarse grain approximation of the LRU.
It divides the pages into 4 categories which is based on the 4 possible combinations of the r-bit and the m-bit:

The possible combinations are:
(for the modified page)
11 -> 01
01 -> 00

10 -> 00 unmodified page

Question 19

The optimal working set

Answer 19

a set of resident pages that will be needed in the immediate future and should remain resident.

Question 20

The working set (WS)

Answer 20

At time t, It is the set of pages referenced during the past d memory operations preceding t.

Question 21

The working set page replacement algorithm

Answer 21

An algorithm that determines which pages must be resident but not in which frames.

Question 22

Page fault frequency replacement algorithm

Answer 22

An algorithm takes a direct approach to controlling page fault rate by adjusting the current resident set based on how frequently consecutive page faults occur.

Question 23

Page fault rate

Answer 23

its the number of page faults f occurring during a number of memory references t.

Question 24

Effective access time

Answer 24

The average time to access memory in the presence of page faults in the presence of page faults.

Question 25

Equation of effective access time

Answer 25

E = (1 - P) * m + P * S

Question 26

Load control

Answer 26

The activity of determining how many processes should be running concurrently at any given time.

Question 27

Thrashing

Answer 27

An execution state during which most of the time is spent on moving pages between the memory.

It occurs when there are too many processes are sharing memory concurrently.