CS414 Fall 2000 Prelim 1 Solutions

Q1)

BinarySemaphore {

Bit b;

}

P(S) {

Bit temp = 1;

While (temp) XCHNG(temp, S.b);

}

V(S) {

S.b = 0;

}

Q2a)

ii) This new code would perform the same task as the old code.

In this case, the process executing the signal continues to run until it exits the monitor or waits on a condition.

Q2b)

iv) This new code would cause a violation of critical section mutual exclusion requirements.

In this case, the process executing the signal is preempted while another process begins execution. Thus the statement after signal is not executed until much later possibly causing violation of consistency.

Q3a)

Yes, the algorithm is subject to starvation because repeated arrivals of short jobs would potentially make long jobs wait forever. One way to avoid this is to use feedback queuing techniques (A process waiting for a long time goes to a lower number queue).

Q3b)

Yes, the algorithm is subject to convoy effect because when a job from a high numbered queue is executing, all short jobs must wait for a long time until it finishes. One way to avoid this is to preempt the currently executing job from a higher numbered queue whenever a new ready process is added to queue 0.

Q3c)

The total number of context switches per each CPU burst can be expressed as élog₂(n + 1)ù - 1. This is because if i is the index of the queue in which the process was at the time of completion of the CPU burst, then 1 + 2 + 4 + … + 2ⁱ = 2^{i + 1} – 1 £ n. Thus, the total number of context switches can be expressed as k(élog₂(n + 1)ù) – 1. Note here that the IO bursts essentially mean than the process is blocked for m milliseconds performing IO.

Q4a)

i. enable/disable interrupts

ii. tset/xchng primitives

iii. baker’s algorithm

Q4b)

i. tset/xchng primitives

ii. Peterson’s algorithm

iii. Spin locks

Q5a)

i. mutual exclusion

ii. hold and wait

iii. no preemption

iv. circular wait

Q5bi)

Either P1 and P3 or P2 and P3 could get into a deadlock.

Q5bii)

If only processes P1 and P2 existed, then there can be no deadlocks because both the processes invoke the P operation on the semaphores in the same order. This is an example of deadlock prevention by ordering.

Q6)

Here is a solution for this problem.

Semaphore: mutexM = 1; /* allows only one man to be paired */

Semaphore: mutexW = 1; /* allows only one woman to be paired */

Semaphore: waitM = 0; /* allows woman to wait for man */

Semaphore: waitW = 0;/* allows man to wait for woman */

String: nameM, nameW;/* shared variables to share names */

Man (name) {

String temp;

P(mutexM);

nameM = name;

V(waitM);

P(waitW);

temp = nameW;

V(mutexW);

return temp;

}

Woman (name) {

String temp;

P(mutexW);

nameW = name;

V(waitW);

P(waitM);

temp = nameM;

V(mutexM);

return temp;

}