CS 111 Fall 2010 Lecture 15 Notes

Notes by Charles Graves and Max Vujovic on Professor Paul R. Eggert's 15th lecture of fall 2010 presented on November 18, 2010.

Virtual Memory Policy

Locality of reference

• 
• How do we pick a victim page to swap out? First, we need to consider locality of reference. There are two types of locality of reference.

Temporal Locality

• If you access a page p at time t, it is likely that you will access page p at time (t + delta), where delta is small. That is, after accessing a page, you will probably visit it again soon.

Spatial Locality

• If you access a page p at time t, it is likely that you will access page (p + delta) at time t, where delta is small. That is, after accessing a page, you will probably visit it again or a page close by soon.

Reference Strings

• How do we see whether a policy works well? Trace the pages that were touched by the executing program.
• A reference string is a sequence of virtual page numbers representing pages that were accessed during an execution of a program.
• e.g. Pages: 0 1 2 3 0 4 0 1 2 3

FIFO Page Replacement Policy

• In FIFO, we swap out the page that has been in memory for the longest time.
• Using FIFO, we have the following execution history given the sequence of pages accesses defined by the reference string.
• Reference string: {0 1 2 3 0 4 0 1 2 3}
• 
• Our biggest cost is the cost of getting something off of the disk. Thus, page faults are our biggest cost.
• Let's evaluate FIFO's performance by counting the number of page faults.
• In this example, cost = 9 page faults.

Belody's Anomaly

• We could make the argument that we were thrashing in the previous example. That is, we simply did not have enough physical pages regardless of the algorithm that we used.
• Suppose we buy more RAM.
• With 3 physical pages, we get 9 page faults.
• With 4 physical pages, we get 10 page faults.
• 
• With 5 physical pages, we get 5 page faults. This is the minimum amount because we must fault at least 5 times to get each desired page into RAM. Since we only have 5 virtual pages, they all stay in RAM.
• Look at the transition between 3 and 4 physical pages. We added more RAM, but our system got slower! This is called Belody's Anomoly.

Optimal Page Replacement Policy

• To perform the optimal page replacement policy, we need an "oracle" subroutine. It can look into the future (i.e. the tail of the replacement string) and find the page that will not be needed for the longest amount of time from the current point in execution.
• 
• Cost = 7 faults.
• However, programs do not have "crystal balls". Though sometimes the same program is run over and over frequently, like a nightly payroll program. However, often times, the program's behavior is unpredicatble like a user interacting with a web browser.

Least Recently Used

• Least recently used relies on temporal locality.
• 
• Cost = 10 page faults. This is worse than FIFO in this case, but LRU usually performs better than FIFO. This example was not a common case; it was chosen to exhibit Belody's Anomoly.
• How do we implement LRU?
• Let's start with one-level page tables.
• 
• What happens when the page fault counter overflows? We can renormalize all of the numbers.
• We need to update the timestamp efficiently. If we do it in hardware, we will make loads and stores slower, which is unacceptable.
• How many bits do we give to the timestamp? Since we do not want the page tables to get any bigger, use a small 5-bit number to approximate the timestamp.
• Besides LRU, we can use a more complex heuristic like temporal locality combined with spatial locality, as long as we can compute it cheaply.

Demand Paging

• In demand paging, we should not load a page of application code until the program actually needs it.
• In ordinary paging, we read the entire program into RAM, and then execute it.
• For example, suppose:
• There are N pages in the program.
• U pages are used, and less than N pages can be used, so 0 < U <= N.
• The cost of reading a page is C.
• The cost of page faulting is F.
• In ordinary paging, the total cost = NC and the latency = NC.
• In demand paging, the total cost = UC + (U-1)F and the latency = C. That is, we had to fault in all but one page.
• If U is much less than than N, demand paging yields a better total cost. Otherwise, ordinary paging yields a better total cost.
• Demand paging is better for a faster initial response of the program. With demand paging, the user does not have to wait and can work in parallel with the program.

Dirty Bit

• 
• Suppose a victim page that we are swapping out has not been modified while it has been in a phyiscal page. This is a huge win for us because we do not have to write it out again while swapping.
• Let's define a dirty bit with the following settings:
• 0 if the page is clean (has not been modified).
• 1 if the page is dirty (has been modified).
• How can we implement the dirty bit?
• Option A: Require that store instructions must be paired with a "set dirty bit" instruction. This will not work because we have to change large amounts of application code.
• Option B: Add hardware support for setting the dirty bit when a page changes. Note that we do not have to set the dirty bit again after it has already been set. This is actually feasible in hardware and many processors support this.
• Option C: Mark all pages read-only at first. Update their permissions to read-write on the first page fault, setting the implicit, figurative dirty bit. There is no need for an actual dirty bit in this case since if a page is read-write, we will consider it as if it had a dirty bit set. Also, the software contains its page permission table elsewhere.

Classic Virtual Memory Trick: Using the SIGSEGV Signal to Grow the Heap

• 
• There is a system call called sbrk, which grows the heap toward the stack. That is, it moves the break between the heap and the forbidden zone.
• For example, sbrk(4096) adds 4096 bytes to the break.
• Accessing memory after the break raises a SIGSEGV signal.
• The trick: Call sbrk inside the SIGSEGV signal handler to grow the heap when we access memory beyond the current heap size.
• Advantage: Avoids some sbrk overhead.
• Disadvantage: Disables segmentation faults, the useful memory address checking feature provided by SIGSEGV signal.

Classic Virtual Memory Trick: Using vfork instead of fork.

• vfork behaves like fork except that the parent and child share the same memory, and the parent is frozen until the child exists or calls exec.
• The most common forking patten in Unix is a fork followed by exec in the child process. Instead, we can use vfork followed by exec, so we do not clone the memory which will just be blown away by exec anyway. This is a performance improvement at the expense of the parent being frozen.
• Some clean design proponents dislike vfork because its completely non-orthogonal.
• Can we instead make regular fork run faster? Yes, we can instead do a lazy fork. After the lazy fork, the child and the parent have read-only access to shared pages. Pages are only cloned when the parent or child writes to them and they can no longer share an identical copy. However, we still have to clone the page tables with this method, which is why the lazy fork cannot entirely replace vfork.

Virtual Machine Efficiency and File System Efficiency

• We Need disk scheduling algorithms because there are always pending access requests to blocks on disk.
• In order to understand, we use a simple model by pretending that the disk is linear(instead of cylindrical).
• We want to use disk scheduling algorithms to improve performance.
• We assume under the simple model that the cost = seek time on the disk
• The time to seek from block i to block j is: cost = |i-j|

FCFS Disk Scheduling Policy

• 
• FCFS is the easiest policy to implement because it is simple.
• It executes requests in the order they are received.
• However, there can be problems if different processes are switching back and forth.
• This causes the disk arm to have to move a lot around the disk which is inefficient.
• If we assume random access to the disk, with the head in the middle, the seek time is 1/4
• If the head is either end of the disk the average seek time is 1/2
• We can calculate the average cost by using the following integral:
• 
• This integral takes into account the average costs of having the head in the last half of the disk and in the first half
• Under this policy, the average wait time is the time it takes the disk head to traverse 1/3 of the disk

Shortest Seek Time First (SSTF) Scheduling Policy

• Under this policy, the disk head moves to the request that is closest to its current position.
• This policy minimizes the amount of latency in between requests because it always goes to the closest one.
• The policy also maximizes the throughput of requests it does not move the disk head around.
• A negative of SSTF is that it can cause starvation of some requests that are located too far away from the disk head.

The Elevator Algorithm

• 
• The elevator algorithm works like an elevator by giving the disk head a direction.
• The disk head looks for the shortest seek time first in its current direction of travel.
• When the disk head, reaches the end or the beginning of the disk, it changes its directions.
• This algorithm makes sure there is no starvation of requests but it reduces the latency and the throughput
• Though Requests at the ends will not starve, they must wait longer on average so this policy is not quite fair.

The Circular Elevator Algorithm

• This algorithm functions the same as the elevator algorithm but when the disk head finds the end, it immediately jumps to the beginning of the disk.
• This solves the fairness problem because requests at the ends have the same wait time as requests in the middle of the disk.
• The algorithm has worse latency and throughput than the elevator algorithm, but is fair to all disk requests.

Anticipatory Scheduling

• The other methods all work well when they are able to stay in a zone of high requests.
• If there are two processes making requests on opposite sides of the disk, however, the efficiency of all the policies reduces drastically.
• Anticipatory scheduling dallies in the area of the last request for a certain length of time to see if another request comes nearby that it can handle.
• In order to do this, we need to find out how long we should dally
• We can attempt to find a good number by using heuristics on past reference strings and the known properties of the seek time.

Robustness Constraints for File Systems

• A problem can arise when we must update multiple blocks to implement functions like 'rename'
• Maintaining block order is important in certain situations and all of the disk scheduling algorithms(except FCFS) reorder block requests.
• We must implement dependencies into requests, and disk scheduling algorithms must respect the dependencies.
• This is the approach used in modern BSD file systems.