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

Like Downey, I’ll start with the 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).