CS 414 Fall 1997: Homework 1 (due Sept

CS 414 Fall 1999 Homework 2 (due Sept. 21

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)

P(nfree); (4)

P(mutex); (5)

Buffer[tail] := x; (6)

tail := (tail+1) mod N; (7)

V(mutex); (8)

V(ninuse); (9)

}

Consume(): obj (10)

{ (12)

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

P(ninuse); (14)

P(mutex); (15)

consume := Buffer[head]; (16)

head := (head+1) mod N; (17)

V(mutex); (18)

V(nfree); (19)

}

1) Suppose that the V(inuse) was moved inside the P(mutex)…V(mutex) by swapping lines (8) and (9), and the V(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.

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

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

P(mutex); (5)

Buffer[tail] := x; (6)

V(mutex); (xx – new line)

P(mutex); (xx – new line)

tail := (tail+1) mod N; (7)

V(mutex); (8)

Assume that objects are “characters”, that the buffer is initially all zeros, and that there are initially 6 producer threads which call “produce” one time each, giving characters ‘a’, … ‘e’ respectively as arguments. 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’

(b) The output is ‘fedcba’

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

(e) The output is ‘abacad’

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

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 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 policy should have the following properties:

(a) Any number of male students can use the showers at the same time

(b) Any number of female students can use the showers at the same time

(d) While female students are using the showers, male students wait.

(e) If any female student is waiting and a male student is using the showers, no additional male student can enter until all that female and any others who are waiting have gotten in

(f) If any male student is waiting and a female student is using the showers, no additional female students can enter until that male and any others who are waiting have gotten in.

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.