Comp111 Final Exam Review
Fall 2017
Open Books and Notes
Final exam: Thu Dec 14, 7-9 PM, Lane 100.

Final exam coverage

Covered topics

Everything after the midterm, including: and it is difficult not to mention:

Be aware that I can ask you...

Some example problems:
  1. In class we have studied the Least-Recently-Used (LRU) paging strategy for process pages. Another commonly utilized strategy is Least-Frequently-Accessed (LFA). In this strategy, a counter is maintained of the number of times each logical page has been accessed since the beginning of time. Then, the pages with the lowest counts are swapped out first when physical pages are needed.
    1. Under what conditions is LFA superior to LRU? Give an example of a set of processes, and an environment, where the completion time for the whole set of processes is longer under LRU than under LFA.
    2. Under what conditions is LFA inferior to LRU? Give an example of a set of processes, and an environment, where the completion time for the whole set of processes is longer under LFA than under LRU.
    3. Give an example in which LFA and LRU have identical behavior.
    4. One compromise between LFA and LRU is to keep track of the total count of accesses Ctotal, and the total elapsed time Tlifetime for which each logical page has existed. Divide Ctotal by Tlifetime to get the frequency F of accesses per unit time, and choose the page with the lowest such frequency. How does this strategy compare with LRU and LFA for your examples?
  2. You are running a server whose purpose is to enable 100 students to complete Comp11 assignments. All students are logged in at the same time. Each student runs a shell that randomly accesses 10 pages of text memory and 1 page of data memory. Each student alternates between editing a file, compiling it, and running it, leaving the shell and editor running while compiling and running the assignment. Compiling and running never occur together. The editor occupies 20 pages of text memory but primarily runs in a main edit loop on (logical) page 10, and the program to be edited takes up two pages of data memory. The compiler takes up 10 pages of text memory and utilizes four pages of data memory per compilation. Each compiled assignment occupies one page of (read-only) text and accesses two pages of data memory.
    1. At any one time, on average, what is the minimum number of physical pages one needs in order to avoid thrashing? Justify your answer.
    2. Suppose each student's typing is exponential with rate λ=2 (characters per second). Suppose everyone is editing (all 100 students), and that the response time for typing a character (at any terminal) is observed as an average of 1/4 second per character. What is the service rate μ for responding to typed characters? Please show your work. Hint: model as an M/M/1 queue, as there is only one processor on the machine.
  3. You are running a web service with an average response rate (= arrival rate) of 100 requests/second and the average time to process a request is 1/2 second. How big should the queue be inside the server to store pending requests? Hint: use Little's law.
  4. In a short essay, explain why the transaction queue in a disk needs to be in the middle, rather than on either side of the platter.

Exam design

I am designing the final exam to take one hour and be roughly at the same level as the midterm. There will be at least:

I am designing the exam to take one hour. I will pick and choose which topics!

Some tips on taking my exams

Some tips on answering my essay questions