18. Page Replacement

Question 1

On certain architectures, the MMU will search the page table itself to locate virtual-to-physical address translations missing from the TLB. What are the pros and cons of this?

Answer 1

The pro is that hardware is way faster.

The con is that the OS must set up the page tables in a fixed way that the hardware understands.

With a hardware-managed TLB, the kernel sees TLB faults. They are handled in hardware.

Question 2

What is a TLB fault?

Answer 2

A required virtual to physical address translation is not in the TLB

Question 3

What is a page fault?

Answer 3

The contents of a virtual page are either not initialized or not in memory.

Note: Every page fault is preceded by a TLB fault

Question 4

Why is every page fault preceded by a TLB fault?

Answer 4

If the contents of the virtual page are not in memory, a translation cannot exist for it.

Question 5

Why is it that not every TLB fault generates a page fault?

Answer 5

If a page is in memory and the translation is the page table, the TLB fault can be handled without generating a page fault

Question 6

When must we swap in a page?

Answer 6

When the virtual address is used by the process

Question 7

What do we need to do first to swap out a page?

Answer 7

We need to choose which page to move to disk

Question 8

When swapping in a page, what might we need to do first?

Answer 8

We might need to choose which page to swap out

Question 9

What is the cost of swapping a page out (page eviction)?

Answer 9

Mainly the time and disk bandwidth required to move a page to and from the disk

Question 10

What is the benefit of swapping a page out (page eviction)?

Answer 10

The use of 4K (or a page) of memory (as long as the page on disk remains unused)

Question 11

What are three methods of improving performance of page translations?

Answer 11

1. OS uses methods to minimize the cost of a page swap
2. Algorithms can be designed to maximize the benefits of a page while it’s in memory
3. Minimize the page fault rate

Question 12

What is thrashing?

Answer 12

When a computer’s virtual memory subsystem is in a constant stage of paging, rapidly exchanging data in memory for data on disk.

This causes the performance of the computer to degrade or collapse.

Question 13

How do we maximize the benefit of page eviction?

Answer 13

Pick the page to evict that will remain unused the longest

Question 14

What is the absolute best page to evict, the one that page replacement algorithms dream about?

Answer 14

A page that will never be used again.

Question 15

What would we like to know about a page when choosing one to evict?

Answer 15

How long it will be before this page will be used again.

It’ll allow us to choose the one that won’t be used for the longest

Question 16

When we can’t predict the future, how do we choose the optimal page to swap out?

Answer 16

Use the past!

Question 17

What are the three things required to do intelligent page replacement?

Answer 17

1. Determine what [relevant] information to track
2. Figure out how to collect that information
3. Store that information

Question 18

In a hardware assisted translation system, what information does the OS not have access to?

Answer 18

The OS won’t know how many times an address is used, so it won’t know how useful a given page is or isn’t.

The OS won’t know this information because it isn’t involved in the translation.

Question 19

What are the CONS of collecting usage statistics for pages?

Answer 19

1. Collecting statistics may be computationally expensive, slowing down the process of translating virtual addresses
2. Storing statistics may be expensive, occupying kernel memory that could be better used for other things.

Question 20

What is the simplest possible page replacement algorithm?

Answer 20

Random replacement

Question 21

What are the PROS of a random page replacement algorithm?

Answer 21

It’s extremely simple and a good performance baseline for algorithms that try to be smarter than random

Question 22

What are the CONS of a random page replacement algorithm?

Answer 22

It’s way too simple. We can definitely do better than this.

Think, do we want to risk randomly swapping out (evicting) a page used by a high-priority process?

Question 23

What is an algorithm that uses a page’s past to predict its future?

Answer 23

Least Recently Used (LRU).

LRU chooses the page that has not been used for the longest period of time and hopes that this page will not be used again for a while

Question 24

What are the PROS of the Least Recently Used (LRU) algorithm for page eviction?

Answer 24

It might be as good as we can do without actually predicting the future

Question 25

What are the CONS of the Least Recently Used (LRU) algorithm for page eviction?

Answer 25

We need to know AND store data on how long it has been since a page has been accessed

Question 26

When storing statistics for running a Least Recently Used algorithm for page eviction, how much access time information can we store?

Answer 26

32 bits = 2^32 “ticks”. This literally doubles the page table entry size.

8 bits = 256 bits. This is better.

Question 27

Assuming we have the appropriate statistics, how do we find the least recently used page?

Answer 27

We need some kind of efficient data structure which holds all physical pages on the system that is searched on every page eviction

Question 28

What are the three steps required to locate a page to evict in Clock LRU?

Answer 28

1. Cycle through all pages in memory in a fixed order
2. If a page accessed bit is clear, evict that page
3. If a page accessed bit is set, clear the bit

Note: There is a record of where on the data structure the last cleared page was, that way the next time we need to evict a page we pick up one position past the last position (so as to not unfairly evict unused pages early in the “clock”)

Question 29

What is the “Clock” LRU?

Answer 29

It is a simple and efficient LRU-like algorithm.

There is one bit of accessed information, set when loading a virtual address into the TLB.

Note: This tracks only if a page has been accessed AT ALL. It doesn’t track how many times after the first time it has been accessed.

Question 30

What does it mean when the clock hand is turning slowly in Clock LRU?

Answer 30

Either there is little memory pressure (demand from processes) or we are making good decisions about which pages to evict

Question 31

What does it mean when the clock hand is turning quickly in Clock LRU?

Answer 31

Either there is a lot of memory pressure (demand from processes) or we are making bad decisions about what to evict

Question 32

What is the goal of the “copy-on-write” memory management technique?

Answer 32

Don’t allocate ANY additional memory during fork, but preserve private address spaces.

Question 33

What are the 4 steps to implement the “copy-on-write” memory management technique?

Answer 33

1. During fork, point all of the child’s PTEs to the same physical memory as the parent
2. As long as the child and parent are both just reading from any shared page, we are OK (large parts of the address space may be read-only anyway)
3. As soon as either the child or the parent modifies the contents of any shared virtual page, we have to make a private copy.
4. How do we trap writes? Mark the page as read only in the TLB [?]