Review V: Principles of virtual memory

Problem V1.1

a.	Explain how a CPU supporting virtual memory would translate a virtual memory address into the actual memory address, assuming that the requested page is in memory.
b.	Explain what the CPU does when the requested page is not in memory.

Problem V1.2

When a program accesses a virtual memory address, each of the following could possibly occur. For each, write “CPU” if it would be performed by the CPU while executing the instruction, and write “OS” if it would be performed by the operating system's interrupt handler for page faults.

a. Translating the virtual memory address to a DRAM address.

b. Marking a page as recently referenced.

c. For a page that isn't in DRAM, determining which existing page in DRAM should be removed to make room for it.

d. Loading a page off of disk into DRAM.

e. Updating the page table to reflect that the loaded page is now in DRAM.

f. If the program's instruction is a store, marking its page table entry to reflect that the page is dirty.

Problem V1.3

Describe at least three elements of a typical page table entry.

Problem V1.4

Describe the purpose of the dirty bit found in each page table entry in most virtual memory systems. How does the use of the dirty bit help the system's performance?

Problem V2.1

Recall that most computing systems use some variant of the Clock page replacement algorithm for virtual memory, and that the Clock algorithm is meant to approximate the LRU (Least Recently Used) algorithm.

a. Describe the memory usage patterns of real-world processes that lead LRU to be a good page replacement algorithm.

b. Explain why computing systems rarely use LRU for virtual memory.

Problem V2.2

Suppose we were using a virtual memory system with three page frames, using the Clock algorithm as our page replacement policy. For the sequence of page accesses 1-2-3-4-2-5-6, identify the contents of the three page frames after each memory access.

page	frame
ref	1	2	3
1	1
2	1	2
3	1	2	3

Problem V2.3

Suppose we were using a virtual memory system with three page frames, and our program accesses the pages in the order 1–2–3–1–4–2–5–3. For each of the algorithms FIFO, LRU, and CLOCK, identify the contents of the three page frames after each memory access.

FIFO		LRU		CLOCK
page frame ref 1 2 3 1 1 2 1 2 3 1 2 3		page frame ref 1 2 3 1 1 2 1 2 3 1 2 3		page frame ref 1 2 3 1 1 2 1 2 3 1 2 3

Problem V2.4

Suppose we were using a virtual memory system with three page frames, using the Clock algorithm as our page replacement policy. For the sequence of page accesses 1-2-3-4-2-5-2-6-3, identify the contents of the three page frames after each memory access.

page	frame
ref	1	2	3
1	1
2	1	2
3	1	2	3

Problem V2.5

Suppose our virtual memory system has four page frames and uses the Clock algorithm as its page replacement policy. For the sequence of page accesses 1–2–3–4–1–5–3–6–7–6–8, identify the contents of the four page frames after each memory access.

page	frame
ref	1	2	3	4
1	1
2	1	2
3	1	2	3
4	1	2	3	4

Problem V2.6

Suppose our virtual memory system has four page frames and uses the Clock algorithm as its page replacement policy. For the sequence of page accesses 1–2–3–4–2–5–3–1–6–7 identify the contents of the four page frames after each memory access.

page	frame
ref	1	2	3	4
1	1
2	1	2
3	1	2	3
4	1	2	3	4

Problem V3.1

Explain what a translation lookaside buffer (TLB) is, and explain why it is important for reducing the amount of time for accessing memory.

Problem V3.2

Suppose we have a system with a TLB and a single level of cache for regular data. The TLB miss rate is 1%, while the cache miss rate is 5%. (Assume that these probabilities are independent of one another.) Accessing the TLB or cache takes one clock cycle, whereas accessing DRAM takes 30 clock cycles.

a. What will be the average time to access a memory value addressed using virtual memory?

b. If there were no TLB at all, what would be the average time to access memory?

Problem V3.3

Explain the concept and purpose of page directories.

Problem V4.1

Describe at least two advantages of a virtual memory system over using the actual DRAM addresses.

Problem V4.2

Recall that Linux's fork system call involves creating a new process whose memory is a complete copy of the process initiating the system call. However, copying many megabytes of memory from one location in RAM to another can take quite a bit of time; this cost is particularly wasteful when a program (like a shell) promptly uses execvp after fork to replace all of the duplicated memory with a program loaded from disk. Explain how this cost can be alleviated (or at least deferred) using virtual memory.