The Classic Dining Philosophers Problem

The Dining Philosophers problem is one of the most famous concurrency problems, introduced by Edsger Dijkstra in 1965. It beautifully illustrates the challenges of resource sharing and deadlock in concurrent systems.

The Setup: Five philosophers sit around a circular table. Between each pair of philosophers is a single fork (5 forks total). Each philosopher needs two forks to eat - one from their left and one from their right.

The Challenge: How do we coordinate the philosophers so they can all eat without:

Deadlock: Everyone waiting forever
Starvation: Someone never getting to eat
Race conditions: Two philosophers grabbing the same fork

In this first implementation, we’ll explore the naive solution that leads to deadlock.

Why This Problem Matters

This isn’t just a theoretical exercise. The same pattern appears in real-world systems:

Database transactions needing multiple locks
Resource pools where tasks need multiple resources
Distributed systems coordinating shared resources
Network protocols managing connections

Understanding this problem teaches you to recognize and avoid deadlock in production code.

The Deadlock Implementation

Let’s start with the naive implementation that will deadlock. This helps us understand what goes wrong before we fix it.

package main

import (
	"fmt"
	"sync"
	"time"
)

// Fork represents a dining fork as a mutex
type Fork struct {
	id int
	sync.Mutex
}

// Philosopher represents a dining philosopher
type Philosopher struct {
	id                  int
	leftFork, rightFork *Fork
	eatenCount          int
}

// dine simulates a philosopher's behavior
// This implementation WILL DEADLOCK!
func (p *Philosopher) dine(wg *sync.WaitGroup) {
	defer wg.Done()

	for i := 0; i < 3; i++ {
		// Think for a bit
		p.think()

		// Pick up left fork first
		p.leftFork.Lock()
		fmt.Printf("Philosopher %d picked up left fork %d\n", p.id, p.leftFork.id)

		// Small delay to increase chance of deadlock
		time.Sleep(50 * time.Millisecond)

		// Pick up right fork
		p.rightFork.Lock()
		fmt.Printf("Philosopher %d picked up right fork %d\n", p.id, p.rightFork.id)

		// Eat
		p.eat()

		// Put down forks
		p.rightFork.Unlock()
		p.leftFork.Unlock()
		fmt.Printf("Philosopher %d put down both forks\n", p.id)
	}
}

func (p *Philosopher) think() {
	fmt.Printf("Philosopher %d is thinking...\n", p.id)
	time.Sleep(time.Duration(100+p.id*10) * time.Millisecond)
}

func (p *Philosopher) eat() {
	fmt.Printf("Philosopher %d is eating (meal %d)\n", p.id, p.eatenCount+1)
	p.eatenCount++
	time.Sleep(200 * time.Millisecond)
}

func main() {
	fmt.Println("=== Dining Philosophers: Deadlock Example ===")
	fmt.Println("This implementation will likely deadlock!")
	fmt.Println()

	// Create 5 forks
	forks := make([]*Fork, 5)
	for i := 0; i < 5; i++ {
		forks[i] = &Fork{id: i}
	}

	// Create 5 philosophers
	philosophers := make([]*Philosopher, 5)
	for i := 0; i < 5; i++ {
		philosophers[i] = &Philosopher{
			id:        i,
			leftFork:  forks[i],
			rightFork: forks[(i+1)%5], // Circular arrangement
		}
	}

	// Start dining with a timeout to detect deadlock
	var wg sync.WaitGroup
	wg.Add(5)

	// Start all philosophers
	for i := 0; i < 5; i++ {
		go philosophers[i].dine(&wg)
	}

	// Wait with timeout
	done := make(chan struct{})
	go func() {
		wg.Wait()
		close(done)
	}()

	select {
	case <-done:
		fmt.Println("\n✓ All philosophers finished dining!")
		for i, p := range philosophers {
			fmt.Printf("  Philosopher %d ate %d times\n", i, p.eatenCount)
		}
	case <-time.After(5 * time.Second):
		fmt.Println("\n✗ DEADLOCK DETECTED!")
		fmt.Println("All philosophers are waiting for forks.")
		fmt.Println("This is the classic deadlock scenario.")
	}
}

Understanding the Deadlock

The Circular Wait Condition

The deadlock occurs due to circular wait:

Philosopher 0 holds Fork 0, waits for Fork 1
Philosopher 1 holds Fork 1, waits for Fork 2
Philosopher 2 holds Fork 2, waits for Fork 3
Philosopher 3 holds Fork 3, waits for Fork 4
Philosopher 4 holds Fork 4, waits for Fork 0

Each philosopher is waiting for a resource held by the next philosopher in the circle. No one can proceed!

The Four Conditions for Deadlock

This implementation demonstrates all four Coffman conditions that must hold for deadlock:

Mutual Exclusion: Forks can only be used by one philosopher at a time (mutex)
Hold and Wait: Philosophers hold one fork while waiting for another
No Preemption: Forks can’t be forcibly taken away
Circular Wait: The circular dependency shown above

Break ANY of these conditions and you prevent deadlock.

Visualizing the Problem

Here’s what happens when deadlock occurs:

Time 0: All philosophers thinking
Time 1: All pick up left fork simultaneously
        P0 has F0, wants F1
        P1 has F1, wants F2
        P2 has F2, wants F3
        P3 has F3, wants F4
        P4 has F4, wants F0
Time 2: All wait forever... DEADLOCK!

Running the Example

Save this code and run it:

go run dining_philosophers_deadlock.go

You’ll likely see output like:

=== Dining Philosophers: Deadlock Example ===
This implementation will likely deadlock!

Philosopher 0 is thinking...
Philosopher 1 is thinking...
Philosopher 2 is thinking...
Philosopher 3 is thinking...
Philosopher 4 is thinking...
Philosopher 0 picked up left fork 0
Philosopher 1 picked up left fork 1
Philosopher 2 picked up left fork 2
Philosopher 3 picked up left fork 3
Philosopher 4 picked up left fork 4

✗ DEADLOCK DETECTED!
All philosophers are waiting for forks.
This is the classic deadlock scenario.

Key Go Concurrency Concepts

1. sync.Mutex for Resource Protection

type Fork struct {
    id int
    sync.Mutex
}

The sync.Mutex provides mutual exclusion - only one goroutine can hold the lock at a time.

2. Goroutines for Concurrent Execution

for i := 0; i < 5; i++ {
    go philosophers[i].dine(&wg)
}

Each philosopher runs in their own goroutine, simulating concurrent execution.

3. WaitGroup for Synchronization

var wg sync.WaitGroup
wg.Add(5)
// ... start goroutines ...
wg.Wait()

The WaitGroup lets us wait for all philosophers to finish (or detect when they don’t!).

4. Timeout Pattern with Select

select {
case <-done:
    fmt.Println("Success!")
case <-time.After(5 * time.Second):
    fmt.Println("Deadlock!")
}

This is a critical pattern for detecting deadlocks in production systems. Always use timeouts!

What We Learned

Deadlock is easy to create - The naive implementation naturally deadlocks
Circular wait is dangerous - When everyone grabs resources in the same order
You need deadlock detection - Use timeouts to detect stuck systems
Go makes it visible - Goroutines and mutexes make the problem explicit

Next Steps

In the next articles, we’ll explore two solutions:

The Waiter Solution - Using a centralized coordinator
The Asymmetric Solution - Breaking the circular wait

Both prevent deadlock while allowing philosophers to eat. Stay tuned!

Try It Yourself

Experiment with the code:

Reduce the delay in dine() - Does deadlock happen less often?
Add more philosophers - Does it deadlock faster?
Add logging - Track which fork each philosopher holds
Measure timing - How long until deadlock occurs?

Understanding deadlock through experimentation is the best way to recognize it in production code!

This is part 1 of the Dining Philosophers series in “Golang Experiments: Classic Concurrency Problems”

The Classic Dining Philosophers Problem#

Why This Problem Matters#

The Deadlock Implementation#

Understanding the Deadlock#

The Circular Wait Condition#

The Four Conditions for Deadlock#

Visualizing the Problem#

Running the Example#

Key Go Concurrency Concepts#

1. sync.Mutex for Resource Protection#

2. Goroutines for Concurrent Execution#

3. WaitGroup for Synchronization#

4. Timeout Pattern with Select#

What We Learned#

Next Steps#

Try It Yourself#