CSE 121 Spring 2003 Homework 3
Due Midnight, 23 May 2003 

Please turn in a tar file that contains your program and your solution for Problem 2. Your solution for Problem 2 can be jsut a simple text file with no formatting.


Problem 1

In the system described in Implementing Global Memory Management in a Workstation Cluster, the when a page is faulted from disk, the LRU oldest page in the cluster is discarded.
  1. Explain how it is possible for two pages to both be the LRU oldest page in the cluster.
  2. Suppose that there are two LRU oldest pages in the cluster: one is a local page and one is a global page. Does it matter which page is chosen to be discarded? Explain.

Problem 2

  1. In Figure 1 of Implementation and Performance of Integrated Application-Controlled File Caching, Prefetching, and Disk Scheduling, an example is given in which prefetching hurts performance. Does this example violate the controlled-agressive policy? Explain.
  2. The LRU-SP allocation policy has the following rule (page 320, paragraph following point 2): if block C is replaced while block A is at the end of the "LRU" list, then after A is put in C's position on the list, any placeholder pointing to C is changed to point to A. Explain why this rule is needed. Do so by showing how omitting this rule (but leaving the others in place) how one of the critera at the beginning of Section 3.2 would be violated.

Problem 3

  1. Why is it important, when using CLOCK, to start running the clock algorithm before the number of free page frames becomes too low?
  2. Modern computers have large enough physical memories that long periods of times might elapse without any page faults. What does this do to CLOCK's ability to approximate LRU? Explain.

Problem 4

Write a C program that creates a named pipe using the mkfifo system call (described in the 3c man pages) and then waits for a process to open the file for reading. When opened, your program should increment a counter and write the ASCII value of the counter to the pipe. It should then close the pipe and wait to do it again. Hence, your program will implement what appears to be a file that contains the number of times it is read. For example, if your program is called count and takes as a parameter the name of the pipe to create, then a run of your program could look like the following:
> count foo &
> cat foo
1
> cat foo
2
This program should be short; my version has only about 30 lines of code.

Give a brief explanation of the logic of your program, especially any part that are not immediately obvious.

last edited by Keith Marzullo on 17 May 2003