CSC 716–Advanced Operating System

Fall 2007 Exam 2

Answer all the questions. The maximum credit for each question is as shown.

  1. (12) Multiple Choice(3 points for each):

1)Assume the cost of context switching is 0, which of the following algorithm is optimal for aperiodicreal-time tasks: __B______

  1. Rate-monotonic scheduling algorithm
  2. Earliest-Deadline-First scheduling algorithm
  3. Deadline-monotonic scheduling algorithm
  4. All of the above
  5. None of the above

2)Semaphores can be inspected or manipulated by the operations of: ___D______

  1. Initializing
  2. Wait
  3. Signal
  4. All of the above
  5. None of the above

3)Assume we use rate-monotonic algorithm to schedule the following two real-time tasks, which of the following statement is right? ____B______

Ti / si / di / pi / ei
T1 / 0 / 50 / 50 / 25
T2 / 0 / 80 / 80 / 35
  1. Before time point 100, P1 missed the deadline.
  2. Before time point 100, P2 missed the deadline.
  3. Before time point 100, both P1 and P2 missed the deadline.
  4. Before time point 100, both P1 and P2 meet the deadline.
  5. None of the above statements is true.

4)A solution to the critical-section problem must satisfy:___E______

  1. Mutual exclusion must be enforced: Only one process at a time is allowed into its critical section
  2. A process waiting to enter its critical section cannot be delayed infinitely
  3. When no process is in a critical section, any process that requests entry to its critical section must be permitted to enter without delay.
  4. No assumption are made about the relative process speeds or the number of processors
  5. All of the above
  1. (20) Construct the schedule for the following set of jobs if multi-level feedback queue is used. Assume we use 3 levels in the multi-level feedback queue and that the time quantum for level 1 and level 2 is 1.5 time units.

Jobs / Arrival Time / Service Time
A / 0 / 4
B / 1 / 2
C / 2 / 5
D / 4 / 3
E / 5 / 4
F / 6 / 5

Answer:

  1. (13) The following is one attempt to solve the Critical Section problem. Can mutual exclusion be guaranteed? Can mutual blocking be avoided? Why?

Global variable flag[0] and flag[1], initially flag[0] and flag[1] are both false

P0:

Prefix0

flag[0]=true

While (flag[1]) do {}

CS0

flag[0]=false

suffix0

P1:

Prefix1

flag[1]=true

While (flag[0]) do {}

CS1

flag[1]= false

suffix1

Answer:

Mutual Exclusion can be guaranteed as if one process is in critical section, second process cannot enter.

Mutual Blocking can occur if both processes execute at the same time with same speed alternatively. That is, after P0 set flag[0] to be true, P1 set flag[1] to be true, then P0 cannot proceed and P1 cannot proceed, so both processes are blocked.

  1. (15) Give a solution to the Producer-Consumer problem using the Wait(s) and Signal(s) instructions. The producer and Consumer will be sharing a common buffer BUF[0..N-1]. The Producer will be putting items in the array and the Consumer will be taking items from the array. We need to synchronize the two processes so that the Producer will not be overwriting a full buffer and the Consumer will not be taking items from an empty buffer.

Answer:

Global Variable

  1. B[0..N-1] – an array of size N (Buffer)
  2. P – a semaphore, initialized to N
  3. C – a semaphore, initialized to 0

Local Variable

  1. In – a ptr(integer) used by the producer, in=0 initially
  2. Out – a ptr(integer) used by the consumer, out=0 initially

Producer Process

producer: produce(w)

wait(p)

B[in]=w

in=(in+1)mod N

signal(c)

goto producer

Consumer Process

consumer: wait(c)

w=B[out]

out=(out+1)mod N

signal(p)

consume(w)

goto consumer

  1. (20) Define the Test-and-Set instruction and show how it can be used to solve the Mutual Exclusion problem. Use Test-and-Set to solve the ticket reservation: Ticket agent i(process i) will check the #-of-seats. If it is greater than 0, he will grab a seat and decrement #-of-seats by 1. Use global variable NumOfSeat to represent the number of total available seats.

Answer:

(a) Definition of Test-and-Set:

Boolean TS(i)= true if i=0; it will also set i to 1

false if i=1

(b) The solution to the Mutual Exclusion:

Global Variable – lock, Initially, lock=0

Pi

Prefixi

while(¬ TS(lock)) do {}

CSi

lock=0

suffixi

(c) Use Test-and-Set to solve the ticket reservation:

Global Variable – lock, initially, lock=0

NumOfSeats, initially, NumOfSeats=200

Pi

Prefixi

while(¬ TS(lock)) do {}

if(NumOfSeats>0)

NumOfSeats--;

lock=0

suffixi

  1. (20) Shown below are two sets of real-time, periodic tasks. For (a), will the schedule produced by the Earliest Deadline First algorithm meet all the deadlines? For (b), will the scheduled produced by the Deadline Monotonic algorithm meet all the deadlines?

Ti / si / di / pi / ei
T1 / 0 / 2 / 3 / 1
T2 / 2 / 3 / 4 / 1
T3 / 1 / 5 / 6 / 1

(a)

Ti / si / di / pi / ei
T1 / 0 / 3 / 3 / 1
T2 / 2 / 6 / 7 / 1.5
T3 / 3 / 5 / 6 / 2.0

(b)

Answer:

(a) Sufficient condition:

Necessary condition:

Necessary condition holds, but sufficient condition does not hold, so we need to schedule to decide if there is a feasible schedule that will meet all the deadlines by using EDF alg.

We need to give a schedule from time 0 to T=max{r1,r2,r3}+2LCM{p1, p2,p3}=2+24=26

We can have feasible schedule in the time interval [0, 26], so this instance can be schedule by EDF alg.

(b) Sort the jobs by priority(relative deadline), then we have {J1=T1, J2=T3, J3=T2}.

Then we use the sufficient condition:

Note: You can always give the schedule to claim that there is feasible schedule by EDF alg or other scheduling alg.