The Drinking Philosophers Problem

The Drinking Philosophers Problem is a generalization of the classic Dining Philosophers Problem, proposed by K. M. Chandy and J. Misra in 1984. Unlike the dining version where philosophers share forks with immediate neighbors in a circle, drinking philosophers share bottles with arbitrary neighbors based on a conflict graph. This makes it much more realistic for modeling real-world resource allocation.

The Scenario

The drinking party has:

  • N philosophers who alternately think and drink
  • B bottles shared among them
  • An arbitrary conflict graph showing who shares bottles
  • Some philosophers may need multiple bottles simultaneously

The rules:

  1. Philosophers share bottles based on an arbitrary graph (not just a circle)
  2. A philosopher may need 1 or more bottles to drink
  3. Each bottle is shared by exactly 2 philosophers
  4. Bottles have priorities (clean vs dirty)
  5. Must avoid deadlock without central coordinator

Example conflict graph:

      P0 --- B01 --- P1
      |              |
     B02            B12
      |              |
      P2 --- B23 --- P3
             |
            B24
             |
            P4

Philosopher 2 needs bottles B02, B23, and B24 to drink!

The Challenge: Arbitrary Resource Graphs

The dining philosophers problem is a special case - a simple ring. The drinking philosophers problem handles:

  • Arbitrary topology: Not limited to circles
  • Multiple resources per task: Some philosophers need many bottles
  • Asymmetric sharing: Not all philosophers share the same number of bottles
  • Graph-based conflicts: Models real resource contention

Why this matters:

  • Real systems rarely have simple ring topologies
  • Processes often need multiple resources simultaneously
  • Resource graphs in practice are complex and irregular

Real-World Applications

This pattern appears in many systems:

  • Database locking: Transactions need multiple locks across arbitrary tables
  • Distributed systems: Nodes need resources from arbitrary other nodes
  • Operating systems: Processes need multiple resources in complex dependency graphs
  • Manufacturing: Assembly stations need parts from various suppliers
  • Network routing: Routers need bandwidth on multiple links
  • Microservices: Services depend on arbitrary sets of other services

Conflict Graph Visualization

graph TD P0((P0)) P1((P1)) P2((P2)) P3((P3)) P4((P4)) P0 ---|B01| P1 P0 ---|B02| P2 P1 ---|B12| P2 P2 ---|B23| P3 P2 ---|B24| P4 style P0 fill:#e1f5ff style P1 fill:#e1f5ff style P2 fill:#ffe1e1 style P3 fill:#e1f5ff style P4 fill:#e1f5ff note0[P2 needs 3 bottles:
B02, B23, B24] style note0 fill:#fff9c4

State Diagram

stateDiagram-v2 [*] --> Thinking Thinking --> Requesting: Thirsty Requesting --> Acquiring: Request bottles Acquiring --> Drinking: Got all bottles Drinking --> Releasing: Done drinking Releasing --> Thinking: Release bottles note right of Requesting Send requests to all
neighbors for needed bottles end note note right of Acquiring Wait until all bottles
are clean (owned by us) end note note right of Releasing Mark bottles dirty,
grant to waiting neighbors end note

Implementation in Go

package main

import (
	"fmt"
	"math/rand"
	"sync"
	"time"
)

// Bottle represents a shared resource between two philosophers
type Bottle struct {
	id       int
	owner    int  // Current owner (philosopher ID)
	clean    bool // Clean = held by owner, Dirty = should pass to requester
	mu       sync.Mutex
	requests chan int // Requests for this bottle
}

func NewBottle(id, initialOwner int) *Bottle {
	return &Bottle{
		id:       id,
		owner:    initialOwner,
		clean:    true,
		requests: make(chan int, 10),
	}
}

// Philosopher represents a drinking philosopher
type Philosopher struct {
	id           int
	bottles      []*Bottle     // Bottles this philosopher needs
	neighbors    []int         // IDs of neighboring philosophers
	bottleOwned  map[int]bool  // Which bottles we currently own
	pendingReqs  map[int]bool  // Pending requests for bottles
	mu           sync.Mutex
	condition    *sync.Cond
	drinkCount   int
	thinkTime    time.Duration
	drinkTime    time.Duration
}

func NewPhilosopher(id int, bottles []*Bottle, thinkTime, drinkTime time.Duration) *Philosopher {
	p := &Philosopher{
		id:          id,
		bottles:     bottles,
		neighbors:   make([]int, 0),
		bottleOwned: make(map[int]bool),
		pendingReqs: make(map[int]bool),
		thinkTime:   thinkTime,
		drinkTime:   drinkTime,
	}
	p.condition = sync.NewCond(&p.mu)

	// Determine which bottles we initially own
	for _, bottle := range bottles {
		bottle.mu.Lock()
		if bottle.owner == id {
			p.bottleOwned[bottle.id] = true
		}
		bottle.mu.Unlock()
	}

	return p
}

// Think simulates thinking
func (p *Philosopher) Think() {
	fmt.Printf("[Phil %d] 🤔 Thinking...\n", p.id)
	time.Sleep(p.thinkTime + time.Duration(rand.Intn(100))*time.Millisecond)
}

// RequestBottles requests all needed bottles
func (p *Philosopher) RequestBottles() {
	p.mu.Lock()
	defer p.mu.Unlock()

	fmt.Printf("[Phil %d] 🙋 Requesting bottles: ", p.id)
	neededBottles := make([]int, 0)

	for _, bottle := range p.bottles {
		if !p.bottleOwned[bottle.id] {
			neededBottles = append(neededBottles, bottle.id)
			p.pendingReqs[bottle.id] = true
		}
	}

	fmt.Printf("%v\n", neededBottles)

	// Send requests for bottles we don't own
	for _, bottle := range p.bottles {
		if !p.bottleOwned[bottle.id] {
			go func(b *Bottle) {
				b.requests <- p.id
			}(bottle)
		}
	}
}

// WaitForBottles waits until all needed bottles are acquired
func (p *Philosopher) WaitForBottles() {
	p.mu.Lock()
	defer p.mu.Unlock()

	for !p.hasAllBottles() {
		p.condition.Wait()
	}

	fmt.Printf("[Phil %d] ✅ Acquired all bottles\n", p.id)
}

// hasAllBottles checks if philosopher owns all needed bottles
func (p *Philosopher) hasAllBottles() bool {
	for _, bottle := range p.bottles {
		if !p.bottleOwned[bottle.id] {
			return false
		}
	}
	return true
}

// Drink simulates drinking
func (p *Philosopher) Drink() {
	p.mu.Lock()
	p.drinkCount++
	count := p.drinkCount
	p.mu.Unlock()

	fmt.Printf("[Phil %d] 🍺 Drinking (session #%d)...\n", p.id, count)
	time.Sleep(p.drinkTime)
	fmt.Printf("[Phil %d] ✓ Done drinking\n", p.id)
}

// ReleaseBottles releases all bottles and handles pending requests
func (p *Philosopher) ReleaseBottles() {
	p.mu.Lock()
	defer p.mu.Unlock()

	fmt.Printf("[Phil %d] 🔄 Releasing bottles\n", p.id)

	for _, bottle := range p.bottles {
		bottle.mu.Lock()
		bottle.clean = false // Mark dirty after use
		bottle.mu.Unlock()
	}
}

// HandleRequests processes incoming bottle requests
func (p *Philosopher) HandleRequests(done chan bool) {
	for {
		select {
		case <-done:
			return

		default:
			// Check each bottle for requests
			for _, bottle := range p.bottles {
				select {
				case requester := <-bottle.requests:
					p.handleBottleRequest(bottle, requester)
				default:
					// No request, continue
				}
			}
			time.Sleep(10 * time.Millisecond)
		}
	}
}

func (p *Philosopher) handleBottleRequest(bottle *Bottle, requester int) {
	p.mu.Lock()
	defer p.mu.Unlock()

	bottle.mu.Lock()
	defer bottle.mu.Unlock()

	// If bottle is dirty and we own it, pass it to requester
	if bottle.owner == p.id && !bottle.clean {
		fmt.Printf("[Phil %d] 📤 Passing bottle %d to Phil %d\n", p.id, bottle.id, requester)

		bottle.owner = requester
		bottle.clean = true
		p.bottleOwned[bottle.id] = false
		delete(p.pendingReqs, bottle.id)

		// Signal that bottle ownership changed
		p.condition.Broadcast()
	} else if bottle.owner == requester {
		// Requester now owns it
		p.bottleOwned[bottle.id] = true
		delete(p.pendingReqs, bottle.id)
		p.condition.Broadcast()
	}
}

// Run executes the philosopher's lifecycle
func (p *Philosopher) Run(iterations int, done chan bool, wg *sync.WaitGroup) {
	defer wg.Done()

	// Start request handler
	go p.HandleRequests(done)

	for i := 0; i < iterations; i++ {
		p.Think()
		p.RequestBottles()
		p.WaitForBottles()
		p.Drink()
		p.ReleaseBottles()
	}

	fmt.Printf("[Phil %d] 🏁 Finished %d drinking sessions\n", p.id, iterations)
}

// DrinkingPhilosophers manages the entire system
type DrinkingPhilosophers struct {
	philosophers []*Philosopher
	bottles      []*Bottle
}

func NewDrinkingPhilosophers() *DrinkingPhilosophers {
	return &DrinkingPhilosophers{
		philosophers: make([]*Philosopher, 0),
		bottles:      make([]*Bottle, 0),
	}
}

func (dp *DrinkingPhilosophers) AddBottle(id, initialOwner int) *Bottle {
	bottle := NewBottle(id, initialOwner)
	dp.bottles = append(dp.bottles, bottle)
	return bottle
}

func (dp *DrinkingPhilosophers) AddPhilosopher(id int, bottles []*Bottle, thinkTime, drinkTime time.Duration) {
	philosopher := NewPhilosopher(id, bottles, thinkTime, drinkTime)
	dp.philosophers = append(dp.philosophers, philosopher)
}

func (dp *DrinkingPhilosophers) Run(iterations int) {
	fmt.Printf("\n🍺 Starting %d philosophers with %d bottles\n\n",
		len(dp.philosophers), len(dp.bottles))

	done := make(chan bool)
	var wg sync.WaitGroup

	for _, philosopher := range dp.philosophers {
		wg.Add(1)
		go philosopher.Run(iterations, done, &wg)
	}

	wg.Wait()
	close(done)

	// Print statistics
	fmt.Println("\n📊 Session Statistics:")
	for _, p := range dp.philosophers {
		fmt.Printf("   Philosopher %d: %d drinks\n", p.id, p.drinkCount)
	}
}

func main() {
	fmt.Println("=== Drinking Philosophers Problem ===")
	fmt.Println("Arbitrary conflict graph with generalized resource sharing")

	dp := NewDrinkingPhilosophers()

	// Create bottles (shared between specific philosopher pairs)
	b01 := dp.AddBottle(0, 0) // Shared by P0 and P1, initially owned by P0
	b02 := dp.AddBottle(1, 0) // Shared by P0 and P2, initially owned by P0
	b12 := dp.AddBottle(2, 1) // Shared by P1 and P2, initially owned by P1
	b23 := dp.AddBottle(3, 2) // Shared by P2 and P3, initially owned by P2
	b24 := dp.AddBottle(4, 2) // Shared by P2 and P4, initially owned by P2

	// Create philosophers with their required bottles
	dp.AddPhilosopher(0, []*Bottle{b01, b02}, 200*time.Millisecond, 300*time.Millisecond)
	dp.AddPhilosopher(1, []*Bottle{b01, b12}, 200*time.Millisecond, 300*time.Millisecond)
	dp.AddPhilosopher(2, []*Bottle{b02, b12, b23, b24}, 200*time.Millisecond, 400*time.Millisecond) // Needs 4 bottles!
	dp.AddPhilosopher(3, []*Bottle{b23}, 200*time.Millisecond, 200*time.Millisecond)
	dp.AddPhilosopher(4, []*Bottle{b24}, 200*time.Millisecond, 200*time.Millisecond)

	fmt.Println("\nConflict Graph:")
	fmt.Println("  P0 --- B0 --- P1")
	fmt.Println("  |             |")
	fmt.Println("  B1           B2")
	fmt.Println("  |             |")
	fmt.Println("  P2 --- B3 --- P3")
	fmt.Println("        |")
	fmt.Println("        B4")
	fmt.Println("        |")
	fmt.Println("       P4")
	fmt.Println("\n  Note: P2 needs 4 bottles (B1, B2, B3, B4)!")

	// Run simulation
	dp.Run(3) // Each philosopher drinks 3 times

	fmt.Println("\n✓ All philosophers satisfied!")
}

How It Works

1. Bottle Ownership with Clean/Dirty Flags

type Bottle struct {
    owner  int   // Current owner
    clean  bool  // Clean = keep it, Dirty = pass to requester
}

The clean/dirty mechanism is key:

  • Clean bottle: Owner needs it, won’t pass it
  • Dirty bottle: Owner finished using it, can pass to requester

2. Request-Based Protocol

// Philosopher requests bottles it doesn't own
for _, bottle := range p.bottles {
    if !p.bottleOwned[bottle.id] {
        bottle.requests <- p.id  // Send request
    }
}

Asynchronous requests via channels - no blocking!

3. Opportunistic Passing

func handleBottleRequest(bottle *Bottle, requester int) {
    if bottle.owner == me && !bottle.clean {
        // Bottle is dirty, pass it to requester
        bottle.owner = requester
        bottle.clean = true
    }
}

Bottles automatically flow to those who need them.

4. Waiting with Condition Variables

// Wait until we own all needed bottles
for !p.hasAllBottles() {
    p.condition.Wait()
}

Efficient waiting - no busy polling!

Advanced: Priority-Based Resource Allocation

package main

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

type PriorityBottle struct {
	*Bottle
	requestQueue []BottleRequest
	mu           sync.Mutex
}

type BottleRequest struct {
	philosopherID int
	timestamp     time.Time
	priority      int
}

func NewPriorityBottle(id, initialOwner int) *PriorityBottle {
	return &PriorityBottle{
		Bottle:       NewBottle(id, initialOwner),
		requestQueue: make([]BottleRequest, 0),
	}
}

func (pb *PriorityBottle) AddRequest(philosopherID, priority int) {
	pb.mu.Lock()
	defer pb.mu.Unlock()

	req := BottleRequest{
		philosopherID: philosopherID,
		timestamp:     time.Now(),
		priority:      priority,
	}

	// Insert in priority order (higher priority first, then FIFO)
	inserted := false
	for i, existing := range pb.requestQueue {
		if req.priority > existing.priority ||
			(req.priority == existing.priority && req.timestamp.Before(existing.timestamp)) {
			// Insert here
			pb.requestQueue = append(pb.requestQueue[:i], append([]BottleRequest{req}, pb.requestQueue[i:]...)...)
			inserted = true
			break
		}
	}

	if !inserted {
		pb.requestQueue = append(pb.requestQueue, req)
	}

	fmt.Printf("[Bottle %d] 📋 Request queue: ", pb.id)
	for _, r := range pb.requestQueue {
		fmt.Printf("P%d(pri:%d) ", r.philosopherID, r.priority)
	}
	fmt.Println()
}

func (pb *PriorityBottle) GetNextRequest() (int, bool) {
	pb.mu.Lock()
	defer pb.mu.Unlock()

	if len(pb.requestQueue) == 0 {
		return -1, false
	}

	next := pb.requestQueue[0]
	pb.requestQueue = pb.requestQueue[1:]

	return next.philosopherID, true
}

// Priority-aware philosopher
type PriorityPhilosopher struct {
	*Philosopher
	priority int
}

func (pp *PriorityPhilosopher) RequestBottlesWithPriority() {
	pp.mu.Lock()
	defer pp.mu.Unlock()

	fmt.Printf("[Phil %d] 🎯 Requesting bottles (priority %d)\n", pp.id, pp.priority)

	for _, bottle := range pp.bottles {
		if !pp.bottleOwned[bottle.id] {
			if pb, ok := bottle.(*PriorityBottle); ok {
				pb.AddRequest(pp.id, pp.priority)
			}
		}
	}
}

func RunPriorityExample() {
	fmt.Println("\n=== Priority-Based Resource Allocation ===\n")

	// High-priority philosophers get resources first
	// Useful for real-time systems, VIP users, etc.

	fmt.Println("Philosopher priorities:")
	fmt.Println("  P0: Priority 1 (normal)")
	fmt.Println("  P1: Priority 5 (high)")
	fmt.Println("  P2: Priority 3 (medium)")
	fmt.Println("\nP1 should drink first despite arriving later!\n")

	// Implementation would use PriorityBottle and PriorityPhilosopher
	// with request queue management based on priorities

	fmt.Println("✓ Priority example complete!")
}

func main() {
	RunPriorityExample()
}

Advanced: Deadlock Detection

package main

import (
	"fmt"
	"sync"
)

type DeadlockDetector struct {
	waitGraph map[int][]int // Who is waiting for whom
	mu        sync.Mutex
}

func NewDeadlockDetector() *DeadlockDetector {
	return &DeadlockDetector{
		waitGraph: make(map[int][]int),
	}
}

// AddEdge adds a wait relationship: from philosopher waits for to philosopher
func (dd *DeadlockDetector) AddEdge(from, to int) {
	dd.mu.Lock()
	defer dd.mu.Unlock()

	dd.waitGraph[from] = append(dd.waitGraph[from], to)
}

// RemoveEdge removes a wait relationship
func (dd *DeadlockDetector) RemoveEdge(from, to int) {
	dd.mu.Lock()
	defer dd.mu.Unlock()

	edges := dd.waitGraph[from]
	for i, edge := range edges {
		if edge == to {
			dd.waitGraph[from] = append(edges[:i], edges[i+1:]...)
			break
		}
	}
}

// DetectCycle checks for cycles in the wait graph (deadlock)
func (dd *DeadlockDetector) DetectCycle() (bool, []int) {
	dd.mu.Lock()
	defer dd.mu.Unlock()

	visited := make(map[int]bool)
	recStack := make(map[int]bool)
	path := make([]int, 0)

	for node := range dd.waitGraph {
		if dd.hasCycle(node, visited, recStack, &path) {
			return true, path
		}
	}

	return false, nil
}

func (dd *DeadlockDetector) hasCycle(node int, visited, recStack map[int]bool, path *[]int) bool {
	visited[node] = true
	recStack[node] = true
	*path = append(*path, node)

	for _, neighbor := range dd.waitGraph[node] {
		if !visited[neighbor] {
			if dd.hasCycle(neighbor, visited, recStack, path) {
				return true
			}
		} else if recStack[neighbor] {
			*path = append(*path, neighbor)
			return true
		}
	}

	recStack[node] = false
	*path = (*path)[:len(*path)-1]
	return false
}

func (dd *DeadlockDetector) MonitorDeadlocks(interval time.Duration, done chan bool) {
	ticker := time.NewTicker(interval)
	defer ticker.Stop()

	for {
		select {
		case <-done:
			return
		case <-ticker.C:
			if hasCycle, cycle := dd.DetectCycle(); hasCycle {
				fmt.Printf("⚠️  DEADLOCK DETECTED! Cycle: %v\n", cycle)
				// Could trigger recovery mechanism here
			}
		}
	}
}

Key Go Patterns

1. Graph-Based Resource Modeling

type Philosopher struct {
    bottles []*Bottle  // Arbitrary set of needed resources
}

// Not limited to left/right neighbors!

Much more flexible than ring topologies.

2. Channel-Based Request Queue

type Bottle struct {
    requests chan int  // Buffered channel for requests
}

// Non-blocking requests
bottle.requests <- philosopherID

3. Condition Variables for Complex Conditions

// Wait for multiple resources
for !hasAll(resources) {
    condition.Wait()
}

// Any change might satisfy condition
condition.Broadcast()

4. State Flags for Protocol

clean bool  // Bottle state determines behavior

if !bottle.clean && hasRequest {
    passBottle()
}

Performance Considerations

Message Complexity

  • Dining: O(1) per philosopher (2 forks)
  • Drinking: O(degree) where degree = number of bottles needed

Fairness

The clean/dirty protocol provides eventual fairness:

  • Bottles flow toward those who need them
  • No philosopher can hoard dirty bottles
  • Starvation is prevented

Scalability

  • Scales with graph density
  • More bottles = more messages
  • High-degree nodes (like P2 with 4 bottles) are bottlenecks

Advantages of This Pattern

✓ Generalized topology - Works with any conflict graph ✓ Decentralized - No central coordinator needed ✓ Deadlock-free - Clean/dirty protocol prevents cycles ✓ Fair - Eventual fairness guaranteed ✓ Realistic - Models real resource contention

When to Use

✓ Use when:

  • Resource dependencies form arbitrary graphs
  • Processes need multiple resources
  • Decentralized coordination required
  • Fairness is important

✗ Avoid when:

  • Simple topology (use dining philosophers)
  • Central coordinator available
  • Resources are uniform
  • Performance is critical (protocol has overhead)

Variations

1. Asymmetric Resource Needs

// Some philosophers need 1 bottle, others need 5
p1.bottles = []*Bottle{b1}
p2.bottles = []*Bottle{b2, b3, b4, b5, b6}

2. Dynamic Graph Changes

// Add/remove bottles at runtime
func (p *Philosopher) AddBottle(bottle *Bottle) {
    p.mu.Lock()
    defer p.mu.Unlock()
    p.bottles = append(p.bottles, bottle)
}

3. Hierarchical Resources

// Bottles have types: Beer, Wine, Whiskey
// Philosopher may need specific types
type Bottle struct {
    id       int
    category string
}

Try It Yourself

  1. Create different graphs - Try star, mesh, tree topologies
  2. Vary resource needs - Some philosophers need many bottles
  3. Add priorities - High-priority philosophers get resources first
  4. Implement timeouts - Give up if can’t acquire resources
  5. Add deadlock detection - Monitor wait-for graph
  6. Measure fairness - Track drink counts over time

Further Reading

  • Chandy-Misra solution
  • Graph-based synchronization protocols
  • Distributed deadlock detection
  • Resource allocation in distributed systems

This is part 23 of “Golang Experiments: Classic Concurrency Problems”