Sushi Bar Problem

Implement the Sushi Bar problem in explained with pseudo codes below (Alternative 1 and Alternative 2).

• You can implement either alternative solution below (Alternative 1 or Alternative 2
• Create n threads where n is provided by the user.
• Each thread should print the following messages when appropriate:
  • Thread i: j seats are empty so I sit.
  • Thread i: j seat(s) are empty but I wait. There are other k people waiting.
  • Thread i: I sit on the last seat. We are dining together now.
  • Thread i: I leave so j seats are empty now.
• "// eat sushi" in the pseudo code should be usleep(d) where d is a random integer between 100 and 1000. It is different for each thread. Reference: http://linux.die.net/man/3/usleep
• Do not implement the solution attempt at the end of the file.

ABOUT SUSHI BAR PROBLEM

Imagine a sushi bar with 5 seats. If you arrive while there is an empty seat, you can take a seat immediately. But if you arrive when all 5 seats are full, that means that all of them are dining together, and you will have to wait for the entire party to leave before you sit down.

Design a program for simulating customers entering and leaving this sushi bar.

Variables Used in the Solution

1 eating = waiting = 0 // keep track of the number of threads
2 mutex = Semaphore (1) // mutex protects both counters
3 block = Semaphore (0) // incoming customers' queue (regular meaning)
4 must_wait = False // indicates that the bar is full

Alternative 1

The reason a waiting customer reacquires mutex is to update eating/waiting state. Make the departing customer, who already has the mutex, do the updating.

1 mutex.wait ( )
2 if must_wait:
3 waiting += 1
4 mutex.signal ( )
5 block.wait ( )
6 else:
7 eating += 1
8 must_wait = (eating == 5)
9 mutex.signal ( )
10
11 //eat sushi
12
13 mutex.wait ( )
14 eating -= 1
15 if eating == 0:
16 n = min (5, waiting)
17 waiting -= n
18 eating += n
19 must_wait = (eating == 5)
20 block.signal (n)
21 mutex.signal ( )

Alternative 2

If there are fewer than 5 customers at the bar and no one waiting, an entering customer just increments eating and releases the mutex. The _fth customer sets must_wait.

If there are 5 customers at the bar, entering customers block until the last customer at the bar clears must_wait and signals block.

The signaling thread gives up the mutex and the waiting thread receives it.

This process continues, with each thread passing the mutex to the next until there are no more chairs or no more waiting threads.

1 mutex.wait ( )
2 if must_wait:
3 waiting += 1
4 mutex.signal ( )
5 block.wait ( ) // when we resume , we have the mutex
6 waiting -= 1
7
8 eating += 1
9 must_wait = (eating == 5)
10 if waiting and not must_wait:
11 block.signal ( ) // and pass the mutex
12 else:
13 mutex.signal ( )
14
15 // eat sushi
16
17 mutex.wait ( )
18 eating -= 1
19 if eating == 0: must_wait = False
20
21 if waiting and not must_wait:
22 block.signal ( ) // and pass the mutex
23 else:
24 mutex.signal ( )