CS 414 Fall 1997: Homework 1 (due Sept

CS 414 Fall 1997: Homework 2 (due Sept. 23)

Recall the code for the producer in the bounded-buffer problem. That code looked like the following:

Produce(x: obj): (1)

{ (2)

(* Code to put x into the buffer *) (3)

WAIT(nfree); (4)

WAIT(mutex); (5)

Buffer[pptr] := x; (6)

pptr := (pptr+1) mod B; (7)

SIGNAL(mutex); (8)

SIGNAL(ninuse); (9)

} (10)

Consume(): obj (11)

{ (12)

(* Code to extract one item from the buffer *)(13)

WAIT(ninuse); (14)

WAIT(mutex); (15)

consume := Buffer[cptr]; (16)

cptr := (cptr+1) mod B; (17)

SIGNAL(mutex); (18)

SIGNAL(nfree); (19)

}

1) Suppose that the SIGNAL(inuse) was moved inside the WAIT(mutex)…SIGNAL(mutex) by swapping lines (8) and (9), and the SIGNAL(nfree) was similarly moved inside the mutex by swapping lines (17) and (18). Would this change the execution of the code in an important way? Explain.

This change would have no effect at all. To get past lines (5) and (15), a process must first do a WAIT() on both semaphores – nfree and mutex, or inuse and mutex. SIGNAL never blocks the caller, so the order of doing the SIGNAL() operations is unimportant.

2) Suppose that the WAIT(mutex)…. SIGNAL(mutex) were moved to the outside of the whole block of code, e.g. lines (4) and (14) would now both be WAIT(mutex) and lines (9) and (19) would be SIGNAL(mutex). Would this change the execution of the code in an important way? Explain.

This would cause the code to hang (it wouldn’t be live). Now you could have some process that does a WAIT(mutex) and gets the mutex, but then waits by doing a WAIT(inuse) or a WAIT(nfree) when those semaphores are 0. No other process could get into the critical section, even to do the SIGNAL() operation, thus leaving the modified solution “stuck” forever.

3) Suppose that we broke up the producer’s critical section by adding an extra SIGNAL(mutex); WAIT(mutex) in between lines (6) and (7) (but that we leave the consumer unchanged). So the new producer would have this code in it:

WAIT(mutex); (5)

Buffer[pptr] := x; (6)

SIGNAL(mutex); (xx – new line)

WAIT(mutex); (xx – new line)

pptr := (pptr+1) mod B; (7)

SIGNAL(mutex); (8)

Assume that objects are “characters”, that the buffer is initially all zeros, and that there are initially 6 producer threads which produce characters ‘a’, … ‘f’ respectively. Assume that these threads begin execution concurrently and hence can invoke produce in an arbitrary order. Now, assume that there is a single consumer thread and it prints the characters it obtains from the buffer. For each of the following, explain why the output shown cannot occur, or give a sequence of events that would cause it to be printed. Also tell us if the output could also occur with the original, correct code, or can only occur with the new, buggy code.

(a) The output is ‘abcdef’

This can occur with the original code and can still occur with the new code. It happens if the producers enter one by one in the order shown, or enter concurrently but happen to get the mutex in the order shown.

(b) The output is ‘fedcba’

This can occur as a result of the code change – it is a form of bug that the change introduces. Suppose that all six producers enter concurrently and all six execute line (6) before any of them gets to line 7. The characters all get stored at location 0 of the buffer, and the last one stored is the only one you’ll end up seeing (‘a’ in this case). Now all six will SIGNAL(ninuse) the consumer will try and consume six characters. It sees the last value written in buffer(0) and five 0’s, because the initial value was 0 (I assume that 0 prints as \000, which is what happens in most computer systems these days).

(d) The output is ‘\000\000\000\000\000a’

This output cannot occur. Even with the change to the code, the first buffer element would have had one of the legal character values in it.

(e) The output is ‘abacad’

This cannot occur. If ‘a’ is only produced once, and the consumer moves `cptr’ one step at a time through the buffer, the consumer will only see one ‘a’ in the buffer and hence will only print ‘a’ once, if at all.

(f) The output is ‘d’ (just one character, not six as for the examples above)

This can’t occur either. If the producers all produce a value, a scheduler must eventually let them in, and eventually they will call SIGNAL(inuse) 6 times, and eventually the consumer will manage to consume six values.

4) Suppose that each process models a student living in a co-ed dorm with a single shared shower room (with lots of shower stalls in it). A process looks like this:

Pi: while(true)

{

non-critical code

Enter the shower room

Use the shower room

Leave the shower room

}

Assume that processes 0…M-1 are male and that processes M…M+N-1 are female, and that M and N are both non-zero. Use fair general semaphores to implement a unisex shower room policy.

The following code is a modified readers/writers solution.

var nm, nw, wm, wf: Integer := {0,0,0,0}

var mwait, wwait, mutex: Semaphore := {0,0,1};

MEnter:

P(mutex);

if(nw > 0 or ww > 0) { wm := wm+1; V(mutex); P(mwait); }

else { nm :=nm+1; V(mutex); }

MLeave:

P(mutex);

nm := nm-1;

if(nm = 0 and ww > 0) {

while(ww>0) { ww := ww-1; nw := nw+1; V(wwait); }

}

V(mutex);

WEnter:

P(mutex);

if(nm > 0 or wm > 0) { ww := ww+1; V(mutex); P(wwait); }

else { nw :=nw+1; V(mutex); }

WLeave:

P(mutex);

nw := nw-1;

if(nw = 0 and wm > 0) {

while(wm>0) { wm := wm-1; nm := nm+1; V(mwait); }

}

V(mutex);

5) In the Dining Philosopher’s problem, assume that we know that there are 5 philosophers and we also know that philosopher 3 is never hungry while philosopher 4 is hungry (or eating). Thus one or the other might be hungry or eating, but both would never be doing this at the same time. Would deadlock be an issue in this case? Explain.

Deadlock cannot arise in the Dining Philosopher’s problem if we have some way to be sure that the philosophers won’t all try to eat at the same time. With this knowledge, we can rule out any possibility of a cyclic wait – and we know that a cycle is a necessary condition for deadlock.