# The Sushi Bar Problem

Posted on March 10, 2017 by Brian Jaress

I’ve been not-so-diligently working my way through Allen Downey’s book on concurrency [1] and came up with a solution to the Sushi Bar Problem that isn’t in that book or any place I can find online. It also seems correct to me, even after coding it up and stress testing it. That’s no guarantee, but it’s enough for me to publish it here and see if anyone else can spot a flaw.

## Problem

Downey adapts the problem from Kenneth Reek [2] and explains it this way:

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.

In other words, whenever five customers are eating at once, new customers cannot start eating until all five existing customers finish. That’s not how sushi bars work in real life, but it seems common in the study of concurrency to make up word problems that are realistic except for a few strange rules.

## Solution

My solution is similar to the second solution from Reek via Downey, but a little simpler. For stress testing, I’ve written it in Haskell (another thing I’m learning not-so-diligently) but I’ve put a wrapper around the standard library semaphores so my code resembles Downey’s Python.

### Variables

type Eat customer = customer -> IO ()

sushiBar :: Int -> Eat customer -> IO (customer -> IO ())
sushiBar seats eat = do

-- track the number currently eating
eating <- var 0

-- controls entry to the sushi bar
door <- semaphore 1

-- used to track whether the 'door' has been locked because 'eating'
-- hasn't yet been zero since it was at maximum
locked <- var False

-- used to protect 'eating' and 'locked'
mutex <- semaphore 1

-- construct a function to be called per visit to the sushi bar
return $visitSushiBar saneSeats eat eating door mutex locked where -- force at least one seat at the sushi bar saneSeats = max seats 1 There are two semaphores: The mutex just protects the shared eating and locked variables, but the door semaphore is used with the locked variable to enforce the grouping rule. ### Interactions The visitSushiBar function is what happens when a customer tries to visit the sushi bar. The analogy is that groups lock the door when they form and unlock it when they are ready to leave. visitSushiBar seats eat eating door mutex locked customer = do wait door wait mutex increment eating full <- check eating (== seats) if full then set locked True else signal door signal mutex eat customer wait mutex decrement eating empty <- check eating (== 0) is_locked <- get locked when (empty && is_locked)$ do
set locked False
signal door

signal mutex

## Thoughts

Subjectively, this solution seems simpler to me than either of Reek’s. Objectively, it uses fewer variables because it doesn’t track how many customers are waiting to enter the sushi bar.

But is it correct?

I’ve thrown one million threads at it, and I’ve fuzzed the numbers of seats and threads, but that’s still no guarantee. Maybe the next book I read on concurrency will be about proofs of correctness.

[1] Downey, A.B. 2016. The little book of semaphores. (2016).

[2] Reek, K.A. 2004. Design patterns for semaphores. ACM SIGCSE (2004).