CSE 121 Spring 2003 Homework 3
Solutions

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.

    There is true concurrency in a cluster. Two processors could both reference a page at the same time. If neither processor subsequently references it page, then they will both become 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.

    Consider two LRU oldest pages, one local and the other global. Suppose the system discards the local page and then later faults on the local page. The overhead needed to correct for this poor choice is the page fault time. If, instead, the system mistakenly discarded the global page, then the overhead is the page fault time minus the time to fault in a page from global. That is, the overhead for making a poor choice is lower when the global page is discarded, and so the global page should be preferentially discarded.


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.

    No, it doesn't. The reference string is A; B; C; A. C is prefetched when the reference to B starts, and A is prefetched when the reference to C starts. This algorithm satisfies optimal prefetching, since the next missing block is prefetched. It satisfies optimal replacement in that when A is discarded (over B), it is because B is referenced before A. It does not violate do no harm for the same reason, and it is prefetching as early as possible thereby satisfying first opportunity.

  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.

    It can result in a foolish process causing another process to suffer. Suppose the three pages at the bottom of the stack are D; C; B; A where A is the oldest.C belongs to process q and the other three belong to p. At the first decision to discard, process p decides that D should be discarded instead of A. So, D is discarded, a placeholder for D is created that points to A, and the stack becomes A; C; B. At the second decision to discard, process p chooses to discard A instead of B. The stack becomes B; C. The rule under discussion determines which placeholders point to B: with the rule, both A and
    D point to B, while without the rule only D points to B. What now if p references page A? With the rule, p will discard B which is reasonable: p discarded A while B was cached, but it subsequently  referenced A without referencing B (which would have moved it up the stack out of harm's way). Without the rule, process q has the LRU oldest page and so has to discard a page even though p made the poor prediction.

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?

    Because of the burstiness of page requests. If the number of free page frames is too low, then page faulting speed is limited by the time it takes to write dirty pages out to backing store.

  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.

    It makes CLOCK behaves less like LRU. Consider the situation in which the the number of free page frames is so large that there is no page faulting for a long time. The clock hand will stop moving, and the likelihood of a page being reference before being revisited by CLOCK is high. In this scenario, when a fault does finally occur and the page frame pool needs to replenished, the clock hand will need to make a complete cycle to find a page marked unreferenced. Thus, at this point, CLOCK is behaving much closer to FIFO than LRU.

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.

Here's my program. The only unusual part of it is the sleep call, which I've marked in red. If it is not included, then unless there is a context switch soon thereafter, this process will try to open the file again. There will still be a process waiting for the file to be opened, and so the process will write another number to the file. In this way, a single cat request to the file can result in hundreds of numbers.
#include <sys/types.h>
#include <sys/stat.h>
#include <stdlib.h>
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>

int main (int argc, char **argv) {
  int count = 0;
  char string_count[10];

  if (argc != 2) {
    printf("Need name of fifo!\n");
    exit(1);
  }

  if (mkfifo(argv[1], 0600) == -1) {
    printf("Could not create fifo %s.\n", argv[1]);
    exit(1);
  }

  while (1) {
    int f = open(argv[1], O_WRONLY);
    sprintf(string_count, "%8d\n", ++count);
    write(f, string_count, 11);
    close(f);
    sleep(1);
  }



last edited by Keith Marzullo on 11 June 2003