Week 8: Virtual Memory

Question 1

What is the basic principle behind virtual memory?

Answer 1

At any given time, only the code and data needed for the current instruction must be in physical memory.

Question 2

How does the operating system handle references to virtual memory and not to physical memory?

Answer 2

By recognizing them and fetching the required data into memory.

Question 3

What is logical address space?

Answer 3

The address space that a program assumes is available, mapped to physical memory during execution.

Question 4

How large is the logical address space for a 32-bit processor?

Answer 4

4GB (2³² bytes).

Question 5

What are pages and page frames?

Answer 5

Pages are blocks of memory in logical address space, and page frames are their counterparts in physical memory.

Question 6

Why are pages and page frames the same size?

Answer 6

To simplify mapping between logical and physical memory.

Question 7

What role does the memory management unit (MMU) play in address translation?

Answer 7

It intercepts logical addresses and maps them to physical addresses using a page table.

Question 8

What is a page table?

Answer 8

A data structure that stores the mapping between page numbers and page frame numbers.

Question 9

Why are multilevel page tables used?

Answer 9

To reduce the size of page tables for systems with large address spaces.

Question 10

How does multilevel indexing work?

Answer 10

It splits the page table into layers, reducing the memory needed for storing the entire table.

Question 11

What is a page fault?

Answer 11

An interrupt generated when a process accesses a page not currently in physical memory.

Question 12

What is demand paging?

Answer 12

Loading a page into memory only when it is needed.

Question 13

What is the goal of page replacement algorithms?

Answer 13

To decide which page to remove from memory to make space for a new page.

Question 14

How does the optimal page replacement algorithm work?

Answer 14

It replaces the page that will not be used for the longest time in the future.

Question 15

Why is the optimal algorithm impractical?

Answer 15

A: It requires knowledge of future memory references.

Question 16

How does the Not-Recently-Used (NRU) replacement algorithm work?

Answer 16

It records if a page is referenced or modified and saves it in the page table. The reference flag is reset at regular intervals (e.g., system clock interrupt). When a page fault occurs the pages are examined:
- Class 0: not referenced, not modified,
- Class 1: not referenced, modified,
- Class 2: referenced, not modified,
- Class 3: referenced, modified
A random page of the lowest available class is chosen

Question 17

How does the FIFO algorithm work?

Answer 17

It removes the oldest page in memory, based on insertion order.

Question 18

What is the disadvantage of FIFO?

Answer 18

It may remove frequently used pages.

Question 19

How does the second chance algorithm improve FIFO?

Answer 19

It checks if the oldest page has been recently referenced and gives it another chance if it has.

Question 20

What is the clock algorithm?

Answer 20

A circular implementation of second chance that uses a pointer to track pages.

Question 21

How does LRU approximate the optimal algorithm?

Answer 21

By replacing the page that has not been used for the longest time.

Question 22

What are the challenges of implementing LRU?

Answer 22

It requires keeping track of the last usage time for every page.

Question 23

What factors influence the design of virtual memory systems?

Answer 23

Page size, prepaging strategies, and maintaining free pages.

Question 24

What is a paging demon?

Answer 24

A process that periodically frees old pages to maintain a pool of free pages.