Breaking the Deadlock

In the previous article, we saw how the naive implementation of the Dining Philosophers problem inevitably leads to deadlock. Now we’ll implement the Waiter Solution - a centralized coordinator that prevents deadlock by controlling resource access.

The Waiter Solution Concept

The Idea: Add a waiter who controls access to the forks. No philosopher can pick up forks without the waiter’s permission. The waiter ensures that at most 4 philosophers can attempt to pick up forks simultaneously.

Why it works: With only 4 philosophers competing for 5 forks, at least one philosopher is guaranteed to get both forks. This breaks the circular wait condition.

Real-World Applications

This pattern appears in many production systems:

  • Semaphores limiting concurrent access to resources
  • Connection pools with max connection limits
  • Rate limiters controlling API request rates
  • Resource managers in operating systems
  • Job schedulers limiting concurrent tasks

Implementation with Semaphore

Go doesn’t have a built-in semaphore type, but we can implement one using channels. A buffered channel naturally provides semaphore semantics!

package main

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

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

// Waiter controls access to the dining table using a semaphore
type Waiter struct {
	semaphore chan struct{}
}

// NewWaiter creates a waiter that allows up to maxSeated philosophers
func NewWaiter(maxSeated int) *Waiter {
	return &Waiter{
		semaphore: make(chan struct{}, maxSeated),
	}
}

// RequestPermission asks the waiter for permission to pick up forks
func (w *Waiter) RequestPermission(philosopherID int) {
	fmt.Printf("Philosopher %d is requesting permission from waiter\n", philosopherID)
	w.semaphore <- struct{}{} // Acquire semaphore
	fmt.Printf("Philosopher %d got permission from waiter\n", philosopherID)
}

// ReleasePermission returns permission to the waiter
func (w *Waiter) ReleasePermission(philosopherID int) {
	<-w.semaphore // Release semaphore
	fmt.Printf("Philosopher %d returned permission to waiter\n", philosopherID)
}

// Philosopher represents a dining philosopher
type Philosopher struct {
	id                  int
	leftFork, rightFork *Fork
	waiter              *Waiter
	eatenCount          int
	thinkTime           time.Duration
	eatTime             time.Duration
}

// dine simulates a philosopher's behavior with waiter coordination
func (p *Philosopher) dine(wg *sync.WaitGroup) {
	defer wg.Done()

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

		// Ask waiter for permission
		p.waiter.RequestPermission(p.id)

		// Now safe to pick up forks
		p.pickUpForks()

		// Eat
		p.eat()

		// Put down forks
		p.putDownForks()

		// Return permission to waiter
		p.waiter.ReleasePermission(p.id)
	}
}

func (p *Philosopher) think() {
	fmt.Printf("Philosopher %d is thinking...\n", p.id)
	time.Sleep(p.thinkTime)
}

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

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

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

func (p *Philosopher) putDownForks() {
	p.rightFork.Unlock()
	p.leftFork.Unlock()
	fmt.Printf("Philosopher %d put down both forks\n", p.id)
}

func main() {
	fmt.Println("=== Dining Philosophers: Waiter Solution ===")
	fmt.Println("Using a semaphore to prevent deadlock")
	fmt.Println()

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

	// Create waiter that allows 4 philosophers at a time
	// This is key: 4 philosophers competing for 5 forks = no deadlock!
	waiter := NewWaiter(4)

	// 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],
			waiter:    waiter,
			thinkTime: time.Duration(100+i*20) * time.Millisecond,
			eatTime:   time.Duration(150+i*10) * time.Millisecond,
		}
	}

	// Start dining
	var wg sync.WaitGroup
	startTime := time.Now()

	fmt.Println("Starting philosophers...")
	for i := 0; i < 5; i++ {
		wg.Add(1)
		go philosophers[i].dine(&wg)
	}

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

	select {
	case <-done:
		elapsed := time.Since(startTime)
		fmt.Println("\n✓ All philosophers finished dining!")
		fmt.Printf("Total time: %v\n\n", elapsed)
		fmt.Println("Meal counts:")
		totalMeals := 0
		for i, p := range philosophers {
			fmt.Printf("  Philosopher %d: %d meals\n", i, p.eatenCount)
			totalMeals += p.eatenCount
		}
		fmt.Printf("  Total: %d meals\n", totalMeals)
		fmt.Println("\n✓ No deadlock! The waiter solution works!")

	case <-time.After(10 * time.Second):
		fmt.Println("\n✗ Timeout! Something went wrong.")
	}
}

How the Semaphore Works

Buffered Channel as Semaphore

semaphore: make(chan struct{}, maxSeated)

A buffered channel with capacity N acts as a semaphore:

  • Sending to the channel acquires a resource
  • Receiving from the channel releases a resource
  • When full (N sends), further sends block until someone receives

Acquiring Permission

w.semaphore <- struct{}{} // Blocks if 4 philosophers already seated

If 4 philosophers already have permission, the 5th philosopher blocks here until one of them finishes.

Releasing Permission

<-w.semaphore // Unblocks one waiting philosopher

This allows another philosopher to acquire permission.

Why This Prevents Deadlock

Breaking Circular Wait

The waiter solution breaks the circular wait condition:

With 4 philosophers competing for 5 forks:

  • At least one philosopher can get both their forks
  • That philosopher eats and releases their forks
  • This unblocks others

The key insight: N-1 processes competing for N resources guarantees progress.

The Math

With 5 forks and at most 4 philosophers:

  • Worst case: 4 philosophers each hold 1 fork
  • Forks in use: 4
  • Free forks: 1
  • At least one philosopher has access to both their forks!

Performance Characteristics

Advantages

✓ No deadlock - Mathematically guaranteed ✓ Simple to understand - Centralized control ✓ Fair - FIFO channel ordering ✓ Prevents starvation - Everyone eventually gets permission

Disadvantages

✗ Limited concurrency - Only 4 of 5 philosophers can compete ✗ Centralized bottleneck - The waiter is a single point of coordination ✗ Not optimal throughput - Could potentially allow more concurrency

Running the Example

go run dining_philosophers_waiter.go

You’ll see output like:

=== Dining Philosophers: Waiter Solution ===
Using a semaphore to prevent deadlock

Starting philosophers...
Philosopher 0 is thinking...
Philosopher 0 is requesting permission from waiter
Philosopher 0 got permission from waiter
Philosopher 0 picked up left fork 0
Philosopher 0 picked up right fork 1
Philosopher 0 is eating (meal 1)
...

✓ All philosophers finished dining!
Total time: 2.5s

Meal counts:
  Philosopher 0: 3 meals
  Philosopher 1: 3 meals
  Philosopher 2: 3 meals
  Philosopher 3: 3 meals
  Philosopher 4: 3 meals
  Total: 15 meals

✓ No deadlock! The waiter solution works!

Key Go Patterns Used

1. Buffered Channel as Semaphore

type Waiter struct {
    semaphore chan struct{}
}

This is a common Go idiom for limiting concurrency. The empty struct struct{} uses zero bytes!

2. Struct Embedding for Clean Design

type Fork struct {
    id int
    sync.Mutex
}

Embedding sync.Mutex makes Fork itself lockable: fork.Lock().

3. Method Receivers for Clean API

func (w *Waiter) RequestPermission(philosopherID int) {
    w.semaphore <- struct{}{}
}

Methods on structs provide a clean, object-oriented style API.

4. Defer for Cleanup

func (p *Philosopher) dine(wg *sync.WaitGroup) {
    defer wg.Done()
    // ... rest of function
}

defer ensures Done() is called even if panic occurs.

Variations to Try

1. Different Semaphore Limits

waiter := NewWaiter(3) // Only 3 can dine at once
waiter := NewWaiter(2) // Only 2 can dine at once

Still no deadlock! As long as limit < numPhilosophers, it works.

2. Weighted Semaphore

Some philosophers might need more forks:

func (w *Waiter) RequestPermission(weight int) {
    for i := 0; i < weight; i++ {
        w.semaphore <- struct{}{}
    }
}

3. Timeout-Based Permission

Add timeouts to permission requests:

func (w *Waiter) RequestPermissionWithTimeout(id int, timeout time.Duration) bool {
    select {
    case w.semaphore <- struct{}{}:
        return true
    case <-time.After(timeout):
        return false
    }
}

When to Use This Pattern

✓ Use when:

  • You need guaranteed deadlock prevention
  • Simplicity is more important than maximum throughput
  • You can afford to limit concurrency
  • You need fair resource allocation

✗ Avoid when:

  • You need maximum parallelism
  • Centralized coordination is a bottleneck
  • You can use a lock-free design
  • Resources can be ordered (see asymmetric solution)

Next Up: The Asymmetric Solution

The waiter solution sacrifices some concurrency for safety. In the next article, we’ll explore the Asymmetric Solution, which allows all 5 philosophers to dine simultaneously while still preventing deadlock!

Try It Yourself

Experiment with the code:

  1. Change the semaphore limit - Try 3, 2, or even 1
  2. Add metrics - Track wait times for permission
  3. Add priority - Give some philosophers higher priority
  4. Stress test - Run with 100 philosophers and 100 forks
  5. Add timeouts - What happens if permission times out?

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