These are three problems with synchronizing multithreaded programs (concurrent programming). Each is the form of a parable and demonstrates complications sharing resources across threads, even with the use of locks. More than my solutions, I think, these examples are valuable because the representation itself sheds light on different techniques in synchronization. The first two are from the 1960s, The Dining Philosophers and The Sleeping Barber attributed to Edsger Dijkstra. The third is from the 1970s and originates from Suhas Patil.

This code is written in Go. To see my representations and solutions in full, visit this repository.

Dining Philosophers

N philosophers eat around a table together, with N chopsticks, one between each pair of philosophers. The philosophers pick up one chopstick, another, eat, and then put the chopsticks down and think. Eventually, each philosopher picks up the chopstick to their left and deadlocks, waiting for their right chopstick. Unable to eat, they starve.

Sleeping Barber

A barber checks on the waiting room and then either cuts hair or goes to sleep (if there is no one in the waiting room). Concurrently, the customer checks on the barber and if the barber is sleeping, the barber wakes up.

If the customer checks on the barber when the barber is checking on an empty waiting room, the barber would go back to sleep and the customer would go wait, possibly forever.

Cigarette Smokers

There are three smokers around a table, each with unlimited supply of either paper, tobacco, or paper. A fourth party, with an unlimited supply of everything, chooses at random a smoker, and put on the table the supplies needed for a cigarrette. The chosen smoker smokes, and the process should repeat indefinitely.

Dining Philosophers

Problem

N philosophers eat around a table together, with N chopsticks, one between each pair of philosophers. The Philosophers pick up one chopstick, another, eat, and then put the chopsticks down and think. Eventually, each philosopher picks up the chopstick to their left and deadlocks, waiting for their right chopstick. Unable to eat, they starve.

Butler Left: e2c0 Right: e2c8 // Representing Chopsticks
bhooks Left: e2c8 Right: e2d0 // by their reference in memory
Simone Left: e2d0 Right: e2d8
Bingen Left: e2d8 Right: e2e0
Arendt Left: e2e0 Right: e2c0

Synchronization in Concurrent Programming

Chopsticks are sync.Mutex locks, Mutex locks limit access to a single resource for multliple threads. So when a program is performing N operations, which need shared resources, the lock ensures that the resources aren’t being used by another thread – or rather, that the chopstick isn’t being used by another philosopher.

This script represents the philosopher struct and eat() method:

type Philosopher struct {
    name  string
    left  *sync.Mutex                  // a chopstick
    right *sync.Mutex                  // a chopstick
    food  int
}

func (p *Philosopher) eat() {
    p.left.Lock()                      // Pick up chopsticks
    p.right.Lock()
    p.food += 1                        // Eat food
    time.Sleep(time.Millisecond * 100)
    p.left.Unlock()                    // Put down chopsticks
    p.right.Unlock()
                                       // Think
}

When the philosopher eats() in a loop, they’ll all reach for the left:

fatal error: all goroutines are asleep - deadlock!

Solution

Resource Hierarchy assigns a hierarchy, or partial order, to the philosophers’ chopstick preference: each will reach for the left most chopstick first, except for the last philosopher, who will reach for the right most first. Partial order ranks the chopsticks and only one philosopher will have access to the highest fork._

        // left index is i and right is i+1
        // swapping the values for the last philosophers
        // and only one philosopher will have access to the
        // "highest" chopstick
        if i == n-1 {
            philosphers[i].left = chopsticks[left]
            philosphers[i].right = chopsticks[right]
        } else { // partial order
            philosphers[i].right = chopsticks[left]
            philosphers[i].left = chopsticks[right]
        }

Output:


    Bingen picks up left: 0xc42000e2e0
    Bingen picks up right: 0xc42000e2d8
    Bingen eats 200/200
Bingen is finished
Philosphers are full

Example Failure:

Output:

start:  0 Butler:, Left: 0xc42000e2c0 Right: 0xc42000e2c8
start:  1 bhooks:, Left: 0xc42000e2c8 Right: 0xc42000e2d0
start:  2 Simone:, Left: 0xc42000e2d0 Right: 0xc42000e2d8
start:  3 Bingen:, Left: 0xc42000e2d8 Right: 0xc42000e2e0
start:  4 Arendt:, Left: 0xc42000e2e0 Right: 0xc42000e2c0
    Bingen picks up left: 0xc42000e2d8
    Butler picks up left: 0xc42000e2c0
    Bingen picks up right: 0xc42000e2e0
    Butler picks up right: 0xc42000e2c8
    Simone picks up left: 0xc42000e2d0
    Bingen eats 1/200
    Butler eats 1/200
    Bingen picks up left: 0xc42000e2d8
    Bingen picks up right: 0xc42000e2e0
    Butler picks up left: 0xc42000e2c0
    Butler picks up right: 0xc42000e2c8
    Butler eats 2/200
    Bingen eats 2/200
    Butler picks up left: 0xc42000e2c0
    Simone picks up right: 0xc42000e2d8
    Butler picks up right: 0xc42000e2c8
    Arendt picks up left: 0xc42000e2e0
    Butler eats 3/200
    Arendt picks up right: 0xc42000e2c0
    bhooks picks up left: 0xc42000e2c8
    bhooks picks up right: 0xc42000e2d0
    Simone eats 1/200
    Bingen picks up left: 0xc42000e2d8
    bhooks eats 1/200
    bhooks picks up left: 0xc42000e2c8
    Arendt eats 1/200
    Bingen picks up right: 0xc42000e2e0
    Butler picks up left: 0xc42000e2c0
    Simone picks up left: 0xc42000e2d0
    Bingen eats 3/200
    Bingen picks up left: 0xc42000e2d8
    Bingen picks up right: 0xc42000e2e0
    Bingen eats 4/200
    Simone picks up right: 0xc42000e2d8
    Arendt picks up left: 0xc42000e2e0
    Simone eats 2/200
    bhooks picks up right: 0xc42000e2d0
    Bingen picks up left: 0xc42000e2d8
    bhooks eats 2/200
    bhooks picks up left: 0xc42000e2c8
    bhooks picks up right: 0xc42000e2d0
    bhooks eats 3/200
    bhooks picks up left: 0xc42000e2c8
    bhooks picks up right: 0xc42000e2d0
    bhooks eats 4/200
    bhooks picks up left: 0xc42000e2c8
    bhooks picks up right: 0xc42000e2d0
    bhooks eats 5/200
    bhooks picks up left: 0xc42000e2c8
    bhooks picks up right: 0xc42000e2d0
    bhooks eats 6/200
    bhooks picks up left: 0xc42000e2c8
    bhooks picks up right: 0xc42000e2d0
    bhooks eats 7/200
    Simone picks up left: 0xc42000e2d0
    bhooks picks up left: 0xc42000e2c8
fatal error: all goroutines are asleep - deadlock!

Sleeping Barber

Problem

A barber checks on the waiting room and then either cuts hair or goes to sleep (if there is no one in the waiting room). Concurrently, the customer checks on the barber and if the barber is sleeping, the barber wakes up.

If the customer checks on the barber when the >barber is checking on an empty waiting room, the barber would go back to sleep and the customer would go wait, possibly forever.

Solution

The solution relies on a Mutex lock for assuring only one thread can change state at a time – so that way the barber is never checking for the customers when a customer is checking for the barber (which would cause a deadlock). As long as the barber or the customer is checking, the mutex should block the other from doing so.

type Barber struct {
    sync.Mutex         // for controlling access to state
    state    int       // sleeping/checking/cutting
    customer *Customer // customer currently being served
}

Using channels to handle state

In addition to sync.Mutex, my solution handles the waiting room resource by passing customers into channels, chan *Customer, like queues with built in mutexes. Channels are safe ways for passing messages between concurrent threads. The customer enters and checks the barber’s state, and then passes (itself) into a buffered channel, the waiting room. The customer switches on the barber’s state, and then selects on a channel: waking the barber up make(chan *Customer, 1) or going to the waiting room make(chan *Customer, 10). If the channels are full, the customer leaves.


func customer(c *Customer, b *Barber, wr chan<- *Customer, wakers chan<- *Customer) {
    b.Lock()                   // Arrive and Check on Barber
    switch b.state {
    case sleeping:
        select {
        case wakers <- c:      // Go wake up barber if asleep
        default:               // if there is someone already
            select {           // on their way to "waking" the Barber
            case wr <- c:      // go to waiting roomn
            default:           // if full, leave
            }
        }
    case cutting:
        select {
        case wr <- c:         // Go to waiting room if Barber is cutting
        default:              // if full waiting, leave shop
        }
    case checking:            // BOTH goroutines checking at once could result in deadlock
        panic("Customer shouldn't check for the Barber when the barber is checking the waiting room")
    }
    b.Unlock()
}

The barber thread, when sleeping, blocks on the wakers channel. The barber gets to sleep by having an empty waiting room, when wr isn’t sending a *Customer, the default case is selected.

func barber(b *Barber, wr chan *Customer, wakers chan *Customer) {
    for {
        b.Lock()
        defer b.Unlock()
        b.state = checking     // barber goes to check the waiting room
        b.customer = nil       // current served customer
        time.Sleep(time.Millisecond * 100)
        select {
        case c := <-wr:        // cuts hair of first person in queue
            HairCut(c, b)      // unlocks during cut
            b.Unlock()         // barber is cutting
        default:               // if waiting room is empty
            b.state = sleeping
            b.customer = nil
            b.Unlock()         // go to sleep on chair Zzzz
            c := <-wakers      // block, wait for waker to arrive
            b.Lock()
            HairCut(c, b)
            b.Unlock()
        }
    }
}

Terminating the program

This could go on forever, but instead one can add() to a sync.WaitGroup struct for every customer, and wg.Done() after the customer leaves.

Example output

The Customer is printed as the last four characters of their memory address (pointer).

=== RUN   TestChecking
Checking waiting room: 0
Sleeping Barber ZzzzZzz - <nil>
Customer 12140 checks sleeping barber | room: 0, w 0 - customer: <nil>
Woken by 12140
Cutting  12140's hair
Customer 12150 checks  cutting barber | room: 0, w 0 - customer: 12140
Checking waiting room: 1
Cutting  12150's hair
Checking waiting room: 0
Sleeping Barber ZzzzZzz - <nil>
Customer 121d0 checks sleeping barber | room: 0, w 0 - customer: <nil>
Customer 74e30 checks sleeping barber | room: 0, w 0 - customer: <nil>
Customer 74e40 checks sleeping barber | room: 0, w 1 - customer: <nil>
Woken by 121d0
Cutting  121d0's hair
Checking waiting room: 1
Cutting  74e40's hair
Customer 74e50 checks  cutting barber | room: 0, w 1 - customer: 74e40
Checking waiting room: 1
Cutting  74e50's hair
Customer c8150 checks  cutting barber | room: 0, w 1 - customer: 74e50
Checking waiting room: 1
Cutting  c8150's hair
Customer 12270 checks  cutting barber | room: 0, w 1 - customer: c8150
Checking waiting room: 1
Cutting  12270's hair
Checking waiting room: 0
Sleeping Barber ZzzzZzz - <nil>
Woken by 74e30
Cutting  74e30's hair
Checking waiting room: 0

No more customers for the day

Cigarette Smokers

Problem

There are three smokers around a table, each with unlimited supply of either paper, tobacco, or paper. A fourth party, with an unlimited supply of everything, chooses at random a smoker, and put on the table the supplies needed for a cigarrette. The chosen smoker smokes, and the process should repeat indefinitely.

Solution

This solution sends a signal to all smokers, telling whose turn it is to smoke, and then places the necessary inputs into the Table by the table’s three channels. The smokers don’t reach for anything until the signal channel stops blocking, and then only the chosen smoker will access the table.

func arbitrator(t *Table, smokers [3]chan int) {
    for {
        time.Sleep(time.Millisecond * 500)
        next := rand.Intn(3)              // choose next smoker
        switch next {
        case paper:
            t.grass <- 1                  // put the proper
            t.match <- 1                  // ingredients
        case grass:                       // on the table
            t.paper <- 1
            t.match <- 1
        case match:
            t.grass <- 1
            t.paper <- 1
        }
        for _, smoker := range smokers {
            smoker <- next               // send the signal
        }
        wg.Add(1)                        // wait for them to light up
        wg.Wait()
    }
}

func smoker(t *Table, name string, smokes int, signal chan int) {
    var chosen = -1
    for {
        chosen = <-signal         // blocks
        if smokes != chosen {     // skip if not chosen
            continue
        }
        select {                  // consume first item
        case <-t.paper:           // blocks
        case <-t.grass:
        case <-t.match:
        }
        select {                  // consume second item
        case <-t.paper:
        case <-t.grass:
        case <-t.match:
        }
        time.Sleep(time.Millisecond * 100)
        wg.Done()                 // aribitrator can move on
    }
}

Example Output

Sandy, Apple, Daisy, sit with
paper, grass, match

Table chooses match: Daisy
Table: 1 grass: 1 match: 0
Table: 1 grass: 0 match: 0
Table: 0 grass: 0 match: 0
Daisy smokes a cigarette
Table chooses paper: Sandy
Table: 0 grass: 1 match: 1
Table: 0 grass: 0 match: 1
Table: 0 grass: 0 match: 0
Sandy smokes a cigarette
Table chooses match: Daisy
Table: 1 grass: 1 match: 0
Table: 1 grass: 0 match: 0
Table: 0 grass: 0 match: 0
Daisy smokes a cigarette
Table chooses match: Daisy
Table: 1 grass: 1 match: 0
Table: 1 grass: 0 match: 0
Table: 0 grass: 0 match: 0
Daisy smokes a cigarette
Table chooses grass: Apple
Table: 1 grass: 0 match: 1
Table: 1 grass: 0 match: 0
Table: 0 grass: 0 match: 0
Apple smokes a cigarette
Table chooses paper: Sandy
Table: 0 grass: 1 match: 1
Table: 0 grass: 1 match: 0
Table: 0 grass: 0 match: 0
Sandy smokes a cigarette