Problem 2: H2O Building Problem

Problem 2: H2O Building Problem

There are two kinds of threads, oxygen and hydrogen. In order to assemble these threads into water molecules, we have to create a barrier that makes each thread wait until a complete molecule is ready to proceed.As each thread passes the barrier, it should invoke bond. You must guarantee that all the threads from one molecule invoke bond before any of the threads from the next molecule do.

In other words:

• If an oxygen thread arrives at the barrier when no hydrogen threads are present, it has to wait for two hydrogen threads.

• If a hydrogen thread arrives at the barrier when no other threads are present, it has to wait for an oxygen thread and another hydrogen thread.

We don’t have to worry about matching the threads up explicitly; that is, the threads do not necessarily know which other threads they are paired up with. The key is just that threads pass the barrier in complete sets; thus, if we examine the sequence of threads that invoke bond and divide them into groups of three, each group should contain one oxygen and two hydrogen threads.

Puzzle: Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.

Problem 3:Dining Savages Problem

A tribe of savages eats communal dinners from a large pot that can hold M servings of stewed missionary. When a savage wants to eat, he helps himself from the pot, unless it is empty. If the port is empty, the savage wakes up the cook and then waits until the cook has refilled the pot.

Any number of savage threads run the following code:

Unsynchronized savage code

while true:
getServingFromPot()
eat()

And one cook thread runs this code:

Unsynchronized cook code

while true:
putServingsInPot(M)

The synchronization constraints are:

Savages cannot invoke getServingFromPot if the pot is empty.
The cook can invoke putServingsInPot only if the pot is empty.

Please add code for the savages and the cook that satisfies the synchronization constraints.

Solution1 for the barbershop problem:

customers = 0

mutex = Semaphore(1)

customer = Semaphore(0)

barber = Semaphore(0)

<Customer>

1 mutex.wait()

2 if customers == n+1:

3 mutex.signal()

4 leave()

5 customers += 1

6 mutex.signal()

8 customer.signal()

9 barber.wait()

10 getHairCut()

12 mutex.wait()

13 customers -= 1

14 mutex.signal()

1 customer.wait()

2 barber.signal()

3 cutHair()

Solution2 for the barbershop problem:

Semaphore Customers = 0

Semaphore Barber = 0

Semaphore accessSeats (mutex) = 1

intNumberOfFreeSeats = N //total number of seats

while(true) { //runs in an infinite loop

SemWait(accessSeats) //tries to get access to the chairs

if ( NumberOfFreeSeats > 0 ) { //if there are any free seats

NumberOfFreeSeats-- //sitting down on a chair

SemSignal(Customers) //notify the barber, who's waiting that there is a customer

SemSignal(accessSeats) //don't need to lock the chairs anymore

SemWait(Barber) //now it's this customer's turn, but wait if the barber is busy

//here the customer is having his hair cut

} else { //there are no free seats

//tough luck

SemSignal(accessSeats) //but don't forget to release the lock on the seats

//customer leaves without a haircut

}

while(true) { //runs in an infinite loop

//tries to acquire a customer - if none is available he goes to sleep

SemWait(Customers)

//at this time he has been awakened - want to modify the number of available seats

SemWait(accessSeats)

NumberOfFreeSeats++ //one chair gets free

SemSignal(Barber) //the barber is ready to cut

SemSignal(accessSeats) //we don't need the lock on the chairs anymore

//here the barber is cutting hair

}

Solution for Building H2O Problem:

mutex = Semaphore(1)

oxygen = 0

hydrogen = 0

oxyQueue = Semaphore(0)

hydroQueue = Semaphore(0)

1 mutex.wait()

2 oxygen += 1

3 if hydrogen >= 2:

4 hydroQueue.signal()

5 hydroQueue.signal()

6 hydrogen -= 2

7 oxyQueue.signal()

8 oxygen -= 1

9 else

10 mutex.signal()

12 oxyQueue.wait()

13 bond()

14 mutex.signal()

1 mutex.wait()

2 hydrogen += 1

3 if hydrogen >= 2 and oxygen >= 1:

4 hydroQueue.signal()

5 hydroQueue.signal()

6 hydrogen -= 2

7 oxyQueue.signal()

8 oxygen -= 1

9 else

10 mutex.signal()

12 hydroQueue.wait()

13 bond()

Solution for the dining savages problem:

servings = 0

mutex = Semaphore(1)

emptyPot = Semaphore(0)

fullPot = Semaphore(0)

<Cook>

1 while true:

2 emptyPot.wait()

3 putServingsInPot(M)

4 fullPot.signal()

1 while true:

2 mutex.wait()

3 if servings == 0:

4 emptyPot.signal()

5 fullPot.wait()

6 servings = M

7 servings -= 1

8 getServingFromPot()

9 mutex.signal()

11 eat()