Spring 2009 Mid Term Exam solutions

1. (25 points)

Consider 5 jobs A, B, C, D and E.

All throughput = 85/5 utilization = 100%

Turnaround time:

FCFS: (30+50+65+75+85)/5

SJF: (10+20+35+55+85)/5

RR: (50+50+65+75+85)/5 // hard to see why

2. (25 points)

Suppose we have two identical processes.

a) 50%

b) 50%

c) Obviously between 5 and 10 – but a better answer would be 5 plus the duration of the first CPU burst.

3 (25 points)

The following is an extension of the Peterson's algorithm for software mutual exclusion.

Fails mutual exclusion

figure out why – --

hint process j sets turn to k and k goes in and then process i sets turn to j and j goes in)

4 (25 points)

Barrier synchronization

Solution 1

//initialize semaphore to -1

// can be fixed if negative init is not allowed – use more semaphores.

barrier()

{ V(s2); V(s3);

P(s1); P(s1); }

Solution 2

Global count set to 0

barrier() {

int i; /* one local variable */

P(mutex));

if (count == N-1) {

V(mutex);

for (i=0; i<N-1;i++) V(waiting);

} else {

count++;

V(mutex);

P(waiting);

}

}