LEC9 - Virtual Memory

[2022] Consider 2 programs: one program that accesses random location of a large sparse matrix in the memory and the other program that sequentially searches a large array for a pattern match. Which program(s) would benefit from pre-paging? Why?

The program that sequentially searches a large sparse array for a pattern match. Because pre-paging relies on programs with predictable access patterns. 

NOTE: Pre-paging is like doing mise-en-place when cooking. It loads the pages into RAM before they become requested. It follows the spatial locality principle.

[2022] LRU (Least-Recently Used) and LFU (Least-Frequently Used) are two representative page replacement algorithms. Now consider the memory footprint of a process (shown below). Which one page replacement policy will be a better choice for the memory workload? Why?

By observation of the diagram, most of the page accesses are concentrated in a few specific pages (indicated by red and orange lines). Other pages (in blue) are accessed infrequently. This leads to LFU being the better choice since the program clearly has a certain group of pages that it accesses frequently. The frequently used pages should be stored in the RAM, ready to be accessed.

[2022] There are two ways to duplicate files: 

1. Mapping the source and destination files using mmap() and then using memcpy() to copy data over.

2. Opening the 2 files using fopen() and then using fread()/fwrite() to copy data.

Now you are duplicating large files on a fast storage device (ex. NVMe SSD). Which one of the above will be faster? Give 2 major reasons why.

Option 1. Because mmap() maps the source and destination files and memcpy() will perform mem-to-mem copying. This reduces system calls and memory usage. In contrast, fread() reads the data into a buffer (costing system resources) and fwrite() copies from the buffer to destination.

[2023] Consider the following sub-operations of demand paging. Which one(s) are conducted by hardware (MMU), and which one(s) are carried out by software (OS)? Why?

1. Looking up the TLB

2. Looking up the page table

3. Updating a page table entry

4. Allocating the memory space for a page table

5. Finding a victim page for page replacement

1. MMU. 

2. MMU. “Looking-up” jobs are usually the MMU’s responsibility.

3. OS. 

4. OS. 

5. OS. OS is the manager here.
   

NOTES:

• MMU is responsible for translating logical (virtual) addresses into physical ones. It operates quickly.

• OS is responsible for managing system resources.

[2023] The following figure shows that format of a page table entry (PTE) of Intel 386+ processors. Explain the purpose of the following bits: 

1. D: Dirty

2. A: Accessed, as known as referenced

3. U/S: user/supervisor

4. R/Q: read/write

5. P: present, as known as valid

1. Flag that says if the page has been modified (dirtied) since it was loaded from disk or created.

2. Flag that says if the page has been accessed by some process recently. 

3. Flag that indicates the privilege required to access the page. 0 = supervisor.

4. Flag that says if the page is flagged as “read-only”. 

5. Flag that says if the entry is currently loaded into the RAM.

[2023] LRU (Least-Recently Used) and LFU (Least-Frequently Used) are two typical page replacement algorithms. Which one better suits the following workloads? Why?

1. Intensive reference to a small page set interleaved by sequential scan of a large page set.

2. Migrating among a few sets of popular pages.

1. LFU. Since the workload involves referencing the same group of pages over and over again, minimizing page faults. 

2. LRU. Since the workload is migrating new set of popular pages, LRU will evict the least recently used one in favor of the recently used ones.

[2023] See the figure below that depicts the total number of page faults vs. the total number of free frames. Which curves (A or B) best describe the performance trend of a typical program? Why?

Curve B. The total number of page faults starts high since you just started the program. Things are being loaded. The number of page faults decreases as some pages are requested again. However, curve A is not accurate since it fails to reflect the sharp reduction in page faults when the number of free frames increases by a small amount.