Comp111 - Operating Systems
Final Exam Review Sheet #2 Answers
Dec 17, 2009
Open Books and Notes

Please write all answers on the exam. Please feel free to use the back of each sheet if appropriate. Please show all of your work for full credit.

    Name: ______Answers_________ Login:_____couch_______

  1. There are 200 people typing on a time-sharing system, where each one types at an average rate λ=1 character/second. The observed average response time is 1 second between typing a character and seeing the result. There is no assumption that the inter-arrival time distribution or service distribution is exponential.
    1. (15 points) What is the average number of characters "in system", either queued or being processed?
      Answer: By Little's law, the number of objects in system times the processing rate equals the arrival rate. There are 200 people * 1 character/second = 200 characters/second arriving, and each one takes an average of 1 second to process, so there are an average of 200 characters/second * 1 second = 200 characters in system at any time.
    2. (15 points) Suppose that the clock rate of the machine is C, and that we replace the machine with another one with clock rate 2C. Suppose that the time in system for the current machine is T1 and the time in system for the new machine is T2. Is T2 equal to T1/2, greater than T1/2, or less than T1/2? Why? List all reasons that apply.
      Answer: T2 > T1/2. The main reason for this is that there are architectural limits other than CPU, including I/o speed, speed with which memory is read into cache, etc. T2 would equal T1/2 only if all of these speeds were doubled.
  2. A real-time scheduler attempts to wake up processes on demand in response to time-critical I/O events. It runs at the same time as a round-robin scheduler. When a selected I/O event occurs, a real-time scheduler disables any scheduler that might in use otherwise, processes the event, and then returns control to the regular scheduler.
    1. (10 points) Exhibit the result of a real-time scheduling event as a process schedule diagram, with processes on the y-axis and time on the x-axis. Show context switches.
      Answer: Suppose we have three processes P1, P2, P3 and one real-time process R1. Then the schedule would look something like this:

      where diagonal lines represent context switches.
    2. (10 points) It is typical for the real-time scheduler to invoke only a small [size] producer for a non-real-time consumer. Why is this design desirable?
      Answer: The main reason is to keep processing of real-time interrupts short, in order to maximize the fairness of the existing round-robin scheme, even in the presence of real-time scheduling. The shortness of the code means that it fits into perhaps one page, which plays a part in the next answer.
    3. (10 points) What limits must be imposed upon the "real-time" process for the process to respond as fast as possible. Why?
      Answer: The main limit is that it must be resident, i.e., not able to swap out. This is easily accomplished. There seems to have been some confusion between "resident in memory" and "resident in cache". The OS can't control what is in cache; cache updates are automatic.
  3. A translucent filesystem makes a read-only device act as if it is read-write, by associating two filesystems to one another: a read-only filesystem (e.g., a DVD) and a writeable filesystem (e.g., a disk). If a file is written into the translucent filesystem, it is actually written onto the writeable drive, but other read-only files surround it. To open a file for reading, the OS first queries the writeable device, and then the read-only device, for a match. The first match is opened.
    1. (20 points) As a matter of filesystem design, should the translucent filesystem driver interact directly with the raw disk devices? Why or why not?
      Answer: No, because the other drivers already know how to do this. One should layer on top so that one's code is simpler and easier to write and understand.
    2. (20 points) Based upon just the description above, can one delete a file from the read-only part of a translucent filesystem? Why or why not?
      Answer: No, because there is no provision for deleting anything that is on the read-only media. One can delete something from the read-write part but that does not remove its analogue from the read-only media.

      One way that deletions are done in a translucent filesystem is to include a pseudo-directory ".whiteout" in each writeable directory, that lists the files to consider deleted in the read-only analogue. People who knew about this were not penalized.