Mid-Term Exam

March 9, 2004

Problem 1: (15 points)

Suppose that a system is running a round-robin scheduler. At some particular time, the running process P is preempted and Q is chosen to run instead. Which of the following events occurs, and in what order?

Answer: A, H, B, G, F, I occur in that order. (The order of G and F could be reversed.) C, D, and E do not occur.

Problem 2: (25 points)

Suppose that there are three processes, P, Q, and R, with the following characteristics:
P will run for 60 msec, block for 70 msec, run for 10 msec, and terminate.
Q will run for 20 msec, block for 40 msec, run for 30 msec, and terminate.
R will run for 110 msec and terminate.
P enters the system at time 0, Q enters at time 15, and R enters at time 40.

Trace what happens (A) with a first-come first-served scheduler; (B) with a round-robin scheduler using a 50 msec quantum.

Answer:

First-come first-served scheduler
Time Running process Ready queue Event at end
0-15 P empty Q enters.
15-40 P {Q} R enters.
40-60 P {Q,R} P blocks until 130
60-80 Q {R} Q blocks until 120
80-120 R empty Q unblocks
120-130 R {Q} P unblocks
130-190 R {Q,P} R terminates
190-220 Q {P} Q terminates
220-230 P empty P terminates

Round robin scheduler.
Time Running process Ready queue Event at end
0-15 P empty Q enters.
15-40 P {Q} R enters.
40-50 P {Q,R} P is preempted for Q.
50-70 Q {R,P} Q blocks until 110.
70-110 R {P} Q unblocks
110-120 R {P,Q} R is preempted for P
120-130 P {Q,R} P blocks until 200.
130-160 Q {R} Q terminates.
160-200 R empty P unblocks.
200-210 R {P} R is preempted for P.
210-220 P {R} P terminates
220-230 R empty R terminates

Problem 3: (10 points)

Consider a system with two semaphors, X and Y, and three processes, P, Q and R. The processes execute the following code:
    Process P              Process Q             Process R.
      DOWN(X)                Q.1                   DOWN(X)
       P.1                  DOWN(Y)                 R.1
      DOWN(Y)                Q.2                   UP(X)
       P.2                  DOWN(X)             
      UP(X)                  Q.3
       P.3                  UP(X)
      UP(Y)                 UP(Y)
Initially X=Y=1.

Problem 4: (10 points)

A programmer is trying to convert single-threaded code into multiple-threaded code in an open-source OS with no built-in support for threads. He has the choice of implementing his threads at the user level or at the kernel level. Mark each of the following considerations true or false.

Problem 5: (10 points)

In order for a deadlock of processes on resources to occur, four conditions, known as Coffman's conditions, must be met. Which of the following are among Coffman's conditions (the list below does not necessarily include all of Coffman's conditions:)

Answer: B, D, and F are among Coffman's conditions.

Problem 6: (10 points)

A paging system uses pages of size 1KByte. At some particular time, the page table begins as follows: [3, *, 0, 4, 2, * ...]. (* means that the page is not in memory.) The (very small) TLB is
Page number Frame number
2 0
3 4
For each of the following virtual addresses, state whether the memory translation involves a TLB hit, a page table lookup, or a page fault, and what, if anything, is the corresponding physical address. (Note: 2*1024-2048. 3*1024=3072. 4*1024=4096. 5*1025=5120.)

Problem 7: (5 points)

(Multiple choice: one correct answer)
The advantage to using a multi-level page table as opposed to a single level page table is that Answer: B.

Problem 8: (15 points)

Suppose an operating system uses paging. At some particular time, pages 0-4 of a given process P are in memory and are clean. The following events then occur: