Assignment 8, solutions

Part of the homework for 22C:112, Spring 2009
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

  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)

    • What happens if you use cache_open() to open the same file two or more times?
    • What happens if you use cache_open() to open a file that is not a disk file, such as /dev/mouse?
    • What happens if you use cache_read() on a descriptor that was not opened with cache_open()?

  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)

    Search the page table for an entry where page_table[i] holds the desired frame number. In this case, i is the page number. This search would need to be done for each frame considered as a candidate for replacement in the page fault service routine.

    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)

    Search the frame table for an entry where frame_table[i] holds the desired page number. This search would need to be done once for each virtual address translated by the memory management unit.

  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)

    The list data structures were probably originally allocated so that sequential list elements were stored sequentially in (virtual) memory, giving the structures a reasonable degree of locality. As the program manipulated its lists, editing, linking and relinking the data elements, the locality was gradually destroyed, until there was an effectively random relationship between the logical position of an item in the list data structures and the memory address used to store that item.

    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)

    If the code periodically "straightened out" all the lists so that consecutive list elements were stored in consecutive memory locations, performance would be significantly improved.