Problem 1

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

> count foo &
> cat foo
1
> cat foo
2

#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);
  }
}