Assignment 8, due Mar. 30

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday). The only exceptions to this rule will be by advance arrangement unless there is what insurance companies call "an act of God" - something outside your control. Homework must be turned in on paper and in class! Late work may be turned in to the teaching assistant's mailbox, but see the late work policy. Never push late work under someone's door!

1. Background: Consider the specifications for MP3. These are brief, because most of the behavior of the cache is defined by the behavior of the system calls that the cache mimics. For example, the behavior of cache_open() is defined by the behavior of open(). There are, however, edge cases that are not covered by the specification. An edge case arises when some use of a piece of software approaches the edge of the specified behavior. Most uses will not visit the edges, but errors in the use of the package could easily cause trouble. The classic edge case is an off by one error at the termination of a loop -- most iterations work correctly, just one is in error.

   Question: Identify several two or more of the edge cases that are not covered by the specification. For each, suggest an appropriate change to the specification that identifies a feasible behavior in that case. (1.0 points)

2. Background: The clock algorithm and other page-replacement policies are usually described in terms of two data structures, the page table and the frame table. In fact, it is possible to omit either one of these data structures and use only the other.

   a) If the frame table is omitted, what computation on the page table can be used to find the page, if any, associated with a particular frame? When would this need to be done? Based on the above, what is the expected impact of the elimination of the frame table on the performance of a demand-paged virtual memory system? (0.5 points)

   b) If the page table is omitted, what computation on the frame table can be used to find the frame, if any, associated with a particular page? When would this need to be done? Based on the above, what is the expected impact of the elimination of the page table on the performance of a demand-paged virtual memory system? (0.5 points)

3. Background: Consider a massive list-processing application running on a machine with virtual memory. As the application runs, the performance gets worse and worse with access times to data structures growing longer and longer until it seems that the program is running at disk speed instead of at main memory speed.

   a) Describe the likely cause of this performance problem. (0.5 points)

   b) This performance problem can be solved by adding a bit of code that makes a periodic pass through the list data structures. What should this code do? (0.5 points)