Chapter 10: Virtual Memory

Question 1

What is a primary benefit of introducing virtual memory (also known as logical memory)?

Answer 1

It makes memory management easier.

Question 2

Initially, how was the size of a process’s virtual memory constrained in relation to physical memory?

Answer 2

It was limited to the size of physical memory.

Question 3

What does virtual memory allow regarding a process’s size compared to physical memory?

Answer 3

It allows the size of a process to be greater than the size of physical memory.

Question 4

The technique that allows a process’s size to be greater than physical memory is known as _____.

Answer 4

demand paging

Question 5

What is the first method mentioned for loading a program into physical memory at execution time?

Answer 5

Load the entire program in physical memory.

Question 6

What is a potential inefficiency of loading an entire program into memory when it starts?

Answer 6

The entire program may not be needed in memory initially.

Question 7

In a program with selectable options, what is the consequence of loading the entire program at once?

Answer 7

It loads the executable code for all options, regardless of whether an option is selected.

Question 8

What is the second method for loading a program, which involves loading pages only as needed?

Answer 8

Demand paging.

Question 9

With demand-paged virtual memory, pages are loaded only when they are _____ during program execution.

Answer 9

demanded

Question 10

Under demand paging, what portion of a program is initially loaded into physical memory?

Answer 10

Only part of the program.

Question 11

During execution with demand paging, where can a process’s pages be located?

Answer 11

Some pages will be in memory, and some will be in secondary storage.

Question 12

What is needed to distinguish between pages in memory and pages on disk in a demand-paged system?

Answer 12

Some form of hardware support.

Question 13

What can be added to a page table to implement demand paging?

Answer 13

A valid-invalid bit.

Question 14

If a page’s valid-invalid bit is set to ‘valid’, where is the corresponding page located?

Answer 14

The corresponding page is in memory.

Question 15

If a page’s valid-invalid bit is set to ‘invalid’, where is the corresponding page located?

Answer 15

The page is currently in secondary storage.

Question 16

What event is triggered when a process tries to access a page that is not in memory?

Answer 16

A page fault, which results in a trap to the OS.

Question 17

What is the first step the hardware takes when handling a memory access?

Answer 17

Extract the address from the current instruction.

Question 18

What is the second step in the page fault procedure, after extracting the address?

Answer 18

Use the page table to check if the page is loaded; an ‘invalid’ bit generates a trap.

Question 19

What is the third step the OS performs after a page fault trap is generated?

Answer 19

Find a free frame in physical memory.

Question 20

What is the fourth step in handling a page fault, after a free frame is found?

Answer 20

Move the desired page into the newly allocated frame.

Question 21

What is the fifth step in handling a page fault, after the needed page is moved into memory?

Answer 21

Modify the page table to indicate that the page is now in memory.

Question 22

What is the final step in the procedure for handling a page fault?

Answer 22

Restart the instruction that was interrupted by the trap.

Question 23

After a page fault is successfully handled, how does the process access the page?

Answer 23

As if it had always been in memory.

Question 24

What aspect of a computer system can be significantly affected by demand paging?

Answer 24

The performance of the system.

Question 25

In a demand-paged system with no page faults, the effective access time is equal to the _____.

Answer 25

memory access time

Question 26

When a page fault occurs, what must happen before the desired instruction or data can be accessed?

Answer 26

The relevant page must be moved from secondary storage to physical memory.

Question 27

In the formula for effective access time, what does the variable 'p' represent?

Answer 27

The probability of a page fault, where $0 \le p \le 1$.

Question 28

For good performance, the probability of a page fault, 'p', is expected to be close to what value?

Answer 28

Zero.

Question 29

What is the formula for effective access time, given page fault probability 'p' and memory access time 'ma'?

Answer 29

effective access time = $(1-p) \times ma + p \times$ page fault time

Question 30

In the example calculation, what value is assumed for the average page-fault service time?

Answer 30

8 milliseconds (ms).

Question 31

In the example calculation, what value is assumed for the memory-access time?

Answer 31

200 nanoseconds (ns).

Question 32

How is 8 milliseconds represented in nanoseconds for the effective access time calculation?

Answer 32

8,000,000 nanoseconds.

Question 33

What is the simplified formula for effective access time in nanoseconds, based on the provided example?

Answer 33

$(200 + 7,999,800 \times p)$ ns

Question 34

What variable is the primary determinant of overall memory access performance in a demand-paged system?

Answer 34

The page fault probability (p).

Question 35

When a page fault occurs, what does the operating system typically need to find to load the desired page?

Answer 35

A free frame in physical memory.

Question 36

What is the situation called when a free frame is requested by the OS, but none exists?

Answer 36

Physical memory is full.

Question 37

When a page fault occurs and there is no free frame, what must the OS use?

Answer 37

One of the page replacement algorithms.

Question 38

What is the first step of a page replacement algorithm?

Answer 38

Find a victim frame.

Question 39

After finding a victim frame, what is the second step in page replacement?

Answer 39

Move the victim frame to secondary storage.

Question 40

What is the final step of a page replacement algorithm after freeing a frame?

Answer 40

Move the page that caused the page fault into the freed frame.

Question 41

When page replacement is necessary, how many page transfers are required?

Answer 41

Two page transfers are required (one page-out and one page-in).

Question 42

How does the need for page replacement affect the page-fault service time?

Answer 42

It effectively doubles the page-fault service time.

Question 43

What is the ideal characteristic of a page-replacement algorithm that we should adopt?

Answer 43

The algorithm with the lowest page-fault probability.

Question 44

How can one evaluate a page-replacement algorithm's performance?

Answer 44

By running it with a particular series of memory references and computing the number of page faults.

Question 45

A series of memory references used to evaluate page-replacement algorithms is called a _____.

Answer 45

reference string

Question 46

What are two methods for obtaining a reference string for evaluation purposes?

Answer 46

Generating it artificially or tracing a given system to record actual memory references.

Question 47

When using a reference string, do we need to consider the detailed addresses or just the page numbers?

Answer 47

We only need to consider the page number.

Question 48

If a reference to page 'p' is immediately followed by another reference to page 'p', will a page fault occur?

Answer 48

No, it will not cause a page fault.

Question 49

Why does an immediate, repeated reference to the same page not cause a page fault?

Answer 49

Because the page will already be in memory after the first reference.

Question 50

In addition to a reference string, what other information is needed to determine the number of page faults?

Answer 50

The total number of frames in physical memory.

Question 51

What is the general relationship between the number of frames and the number of page faults?

Answer 51

As the total number of frames increases, the number of page faults decreases.

Question 52

As the number of available frames increases, the number of page faults drops to some _____.

Answer 52

minimal level

Question 53

What is considered the simplest page-replacement algorithm?

Answer 53

The first-in, first-out (FIFO) algorithm.

Question 54

The FIFO replacement algorithm associates each page with the _____ when that page was brought into memory.

Answer 54

time

Question 55

According to the FIFO page-replacement algorithm, which page is chosen for replacement?

Answer 55

The oldest page is chosen.

Question 56

In the FIFO example, the next reference (2) replaces page 7 for what reason?

Answer 56

Because page 7 was brought in first.

Question 57

The Optimal (OPT) page replacement algorithm replaces the page that will not be _____ for the longest period of time.

Answer 57

used

Question 58

What does the use of the Optimal (OPT) page-replacement algorithm guarantee?

Answer 58

The lowest possible page-fault probability for a fixed number of frames.

Question 59

In the provided example, the Optimal (OPT) algorithm resulted in how many page faults?

Answer 59

Nine page faults.

Question 60

In the provided example, the FIFO algorithm resulted in how many page faults?

Answer 60

Fifteen page faults.

Question 61

Why is the optimal page-replacement algorithm difficult to implement?

Answer 61

Because it requires knowledge about future memory accesses.

Question 62

What is the primary use of the optimal algorithm in practice?

Answer 62

It is used mainly for comparison purposes to evaluate other algorithms.

Question 63

What is the key difference in the time metric used by the FIFO and OPT algorithms?

Answer 63

FIFO uses the time a page was brought into memory, whereas OPT uses the time a page will be used in the future.

Question 64

What does the acronym LRU stand for in the context of page replacement?

Answer 64

Least Recently Used.

Question 65

The LRU replacement algorithm associates each page with the time of that page's _____.

Answer 65

last use

Question 66

When a page must be replaced, which page does the LRU algorithm choose?

Answer 66

It chooses the page that has not been used for the longest period of time.

Question 67

In the provided example, the LRU algorithm resulted in how many page faults?

Answer 67

Twelve page faults.

Question 68

What key question about resource management arises in a system with multiple programs?

Answer 68

How many frames should be allocated to each program initially?

Question 69

Describe the 'Equal Allocation' strategy for 'm' frames and 'n' processes.

Answer 69

Give everyone an equal share, m/n frames.

Question 70

In an equal allocation scheme with 93 frames and 5 processes, how are the 3 leftover frames utilized?

Answer 70

They can be used as a free-frame buffer pool.

Question 71

The Proportional Allocation strategy allocates available memory to each process according to its _____.

Answer 71

size

Question 72

In the formula for Proportional Allocation, what does $s_i$ represent?

Answer 72

The size of the virtual memory for process $p_i$.

Question 73

In the formula for Proportional Allocation, what does $S$ represent?

Answer 73

The sum of the sizes of all processes, $S=\sum s_i$.

Question 74

What is the formula to determine the number of frames ($a_i$) for process $p_i$ using Proportional Allocation?

Answer 74

$a_i \approx (s_i / S) \times m$, where m is the total number of available frames.