Problems (30 + 30 + 60 pts)

1. In lab3, you are asked to devise your own page replacement policy, MYPOLICY. Describe the motivation and thinking underlying your design, along with the algorithm. Discuss why you would expect it to perform better than FIFO. The discussion should incorporate your assumptions on the target workload for which the algorithm is best suited. The overall goal is not to create a page replacement scheme that is only useful for "unusual" reference strings that are unlikely to occur in practice.

   LIMIT: 2 paragraphs

2. [A] Describe two qualitatively different application types that lead to different levels of locality of reference — strong and weak — in their memory referencing behavior. To the extent possible, your two application types should be grounded in real-world applications. Avoid the case where locality of reference is so strong such that page faults rarely occur ("strong" means stronger relative to "weak").

   [B] Can you make one of the two application types behave in both ways (i.e., either strong or weak locality of reference) by varying one or more program variables and/or data? If not, find a third application type that does.

   [C] From your case studies, generalize by identifying key features of programs and data that tend to induce strong or weak locality of reference.

   LIMIT: 1 paragraph for each part

3. [A] Benchmark your application types in Problem 2 under MYPOLICY in Xinu and show that your claims are supported by objective quantitative measurements. Use FIFO as a reference point. Log and plot page fault rate at per second granularity as a time series (i.e., the x-axis indicates 1 second time windows and the y-axis shows the number of page faults that have occurred during the time window). Show the average rate as a dotted line.

   [B] Devise and implement a method for quantifying the overhead introduced by page faults with respect to consuming CPU cycles that the application process is, therefore, unable to use. Show your metric also as a per-second granularity time series. Show the average value as a dotted line.

   LIMIT: 1 paragraph + plots for each part

   ( Note: When plotting time series make sure that the y-axis starts from 0. Oftentimes plotting tools, including gnuplot, will zoom to a y-axis range where both maximum and minimum y-axis values are contained. For systems work, first and foremost, it is important to get an overall sense of how large the values and their variations are. Further details are more meaningful after the coarse structure has been gleaned. )

Write your answers in a file named HW3.pdf. Please place this file in the sys/ directory and turn it in, along with the lab programming assignment.