EEL 602 -
Operating Systems
Spring 2007
Indian Institute of
Technology Delhi, New Delhi
Solutions Minor # 2
1. The goal of this exercise is for you to create a monitor with methods Hydrogen() and Oxygen(), which wait until a water molecule can be formed and then return. Don’t worry about actually creating the water molecule; instead only need to wait until two hydrogen threads and one oxygen thread can be grouped together. For example, if two threads call Hydrogen, and then a third thread calls Oxygen, the third thread should wake up the first two threads and they should then all return.
Observe that there is only one condition any thread will wait for (i.e., a water molecule being formed). However, it will be necessary to signal hydrogen and oxygen threads independently, so we choose to use two condition variables, waitingH and waitingO.
State variable description
Variable name
Initial value
Number of waiting hydrogen threads
wH
0
Number of waiting oxygen threads
wO
0
Number of active hydrogen threads
aH
0
Number of active oxygen threads
aO
0
You start with the following code:
Hydrogen() {
wH++;
lock.acquire();
while (aH == 0) {
if (wH >= 2 && wO >= 1) {
wH-=2; aH+=2;
wO-=1; aO+=1;
waitingH.signal();
waitingO.signal();
} else {
lock.release();
waitingH.wait();
lock.acquire();
}
}
lock.release();
aH--;
}
Oxygen() {
wO++;
while (aO == 0) {
if (wH >= 2 && wO >= 1) {
wH-=2; aH+=2;
wO-=1; aO+=1;
waitingH.signal();
waitingH.signal();
} else {
waitingO.wait();
}
}
aO--;
}
For each method, say whether it either (i) works, (ii) doesn’t work, or (iii) is dangerous – that is, sometimes works and sometimes doesn’t. If the implementation does not work or is dangerous, explain why (there maybe several errors) and show how to fix it so it does work.
i. Hydrogen()
The routine is (iii) dangerous
1. Starvation and Deadlocks are possible - The lock should not be acquired acquire()d and release()d around the wait() call - the condition variable does that for you.
You will loose marks for any additional bugs, since there were no others (except for a complete rewrite of the implementation – which is not what I am looking for).
ii. Oxygen()
The routine is (i) works
Marking Scheme ® (i) Hydrogen - 1 {Clear Solution} + 2 {Explanation}; (i) Oxygen - 1 {Clear Solution} + 2 {Explanation}
2. One EEL 602 student proposed an alternative solution to the mutual exclusion problem for two processes. This solution is reproduced in the following program. Please verify the correctness of this solution. [4]
boolean blocked[2]
int turn;
void P (int id)
{
while (true)
{
blocked[id] = true;
while (turn != id)
{
while (blocked[1-id])
/* do nothing*/
turn = id;
}
/* critical section*/
blocked[id] = false;
/* remainder */
}
}
void main()
{
blocked[0] = false;
blocked[1] = false;
turn = 0;
parbegin (P(0), P(1));
}
In above solution, it is possible for both processes to simultaneously enter ‘critical section’. Consider the case in which turn equals 0 and P(1) sets blocked[1] to true and then finds blocked[0] set to false. The process P(0) may again renter its critical section and then set blocked[0] to true, find turn = 0, and enter its critical section. P(1) will then assign 1 to turn and will also enter its critical section.
3. Five batch jobs A through E, arrive at a computer center at almost the same time. They have estimated running times of A:10, B:6, C:2, D:4, and E:8 minutes. Their (externally determined) priorities are A:3, B:5, C:2, D:1, and E:4, respectively, with 5 being the highest priority. For each of the following scheduling algorithms, determine the mean process turnaround time (average response time). Ignore context switching overhead. (a) Round-Robin (the timeslice size is not important, so assume a timeslice of 1 millisecond), (b) Priority scheduling, (c) First-come, First-served (run in order 10, 6, 2, 4, 8), (d) Shortest Job First. [4]
i) Round-Robin
During the first 10 minutes, each job gets 1/5 of the CPU. At the end of 10 minutes, C finishes. During the next 8 minutes, each job gets 1/4 of the CPU,
after which time D finishes. Then each of the three remaining jobs gets 1/3 of the CPU for 6 minutes, until B finishes, and so on. The finishing times for the
five jobs are 10, 18, 24, 28, and 30, for an average of 22 minutes.
There are varieties of incorrect answers for this one. The most common mistake is to compute the TurnAroundTime for round-robin with a time slice of
1 minute, instead of 1 millisecond. This results in 3 incorrect finishing times, so no credits!
ii) Priority scheduling - B is run first. After 6 minutes, it is finished. The other jobs finish at 14, 24, 26, and 30, for an average of 20 minutes.
iii) First-come, First-served (run in order 10, 6, 2, 4, 8) - If the jobs run in the order A through E, they finish at 10, 16, 18, 22, and 30, for an average of 19.2 minutes.
iv) Shortest Job First - Finish times are 2, 6, 12, 20, and 30, for an average of 14 minutes.
4. Why do Solaris, Linux, and Windows 2000 use spinlocks as a synchronization mechanism only on multiprocessor systems and not on single-processor systems? [1]
Solaris, Linux, and Windows 2000 use spinlocks as a synchronization mechanism only on multiprocessor systems. Spinlocks are not appropriate for single-processor systems because the condition that would break a process/thread out of spinlock could be obtained only by executing a different process. If the process is not relinquishing the processor, other processes do not get the opportunity to set the program condition required for the first process/thread to make progress. In a multiprocessor system, other processes execute on other processors and thereby modify the program state in order to release the first process/thread from the spinlock.
Those answers detailed about the advantages of spinlocks (single processor or multiprocessor case) did not receive any credits.
{Updated 25/04/2007}