Final Exam: Comp. Sys. Org. II

Tuesday, May 4, 2004

Part I: Multiple choice

For each of the following give the single correct answer. (5 points each)

Problem 1:

Suppose that there are three processes P, Q, and R, and two semaphors s and t. Initially s=1 and t=2. The following operations occur:
P executes DOWN(s)
Q executes DOWN(t)
Q executes DOWN(s)
R executes DOWN(t)
R executes DOWN(s)
P executes UP(s)
P executes DOWN(t)
Which of the following is a possible state of the system after these operations?

Answer: C. When P executes UP(s), either process Q or process R may be unblocked. If the semaphor uses a FIFO queue, then Q would unblock; but a semaphor is not required to use FIFO queue.

Problem 2:

To switch from reading one track to reading another track on the same cylinder in a hard disk requires:

Answer: C.

Problem 3:

Consider a UNIX operating system that implements files using i-nodes. Suppose that there is a hard link from filename /Y/G to filename /X/F. Then:

Answer: E

Problem 4:

One common security hole is exploited by calling a systems routine with an extremely long argument (e.g. a file name with thousands of characters). The effect of this is that

Answer: D.

Problem 5:

In the TCP/IP protocol for Internet communication, which of the following is true:

Answer: A.

Part II: Long questions

15 points each.

NOTE: In any of the following problems, if you are asked to "explain" something or another, I am looking for a concise, specific answer. Do not give long explanations.

Problem 6:

An OS designer is trying to decide between using a round-robin scheduler with a 50 msec quantum and a first-come-first-served (FCFS) scheduler in his operating system. He tries out the two scheduling algorithms with three separate collections of 20 jobs, C1, C2, and C3. All jobs enter the system simultaneously at t=0. In each experiment he measures two quantities: The average time to completion and the total time to completion (i.e. the time at which the last job completes.) Note: None of the problems below requires that you actually calculate the specific values of these numbers.
  • A. In collection C1, all the jobs are CPU-bound and consist of a single, 1 minute long, CPU-burst. Which scheduling algorithm has the lower average time to completion? Which has the lower total time to completion?

    Answer: FCFS will have a much lower average time to completion. In FCFS the first job will complete after 1 minute, the second job after 2 minutes and so on, for an average completion time of 10.5 minutes. In round-robin all the jobs will finish within 1 second of one another after 20 minutes, for an average completion time of slightly less than 20 minutes. The total completion time for FCFS will be very slightly less than for round-robin, because there much less time required for context-switching.

  • B. In collection C2, all the jobs consists of 1000 cycles in which a CPU burst of 5 msec is followed by a 100 msec delay waiting for I/O. Which scheduling algorithm has the lower average time to completion? Which has the lower total time to completion?

    Answer: In this situation no job every exhausts its quantum. Hence FCFS executes jobs in exactly the same order as round robin, so the two are equal in both measurements.

  • C. In collection C3, all the jobs are CPU-bound. One job requires 20 minutes of CPU time; the other 19 each require 10 seconds of CPU time. The experimenter finds that Explain these observations.