Debugging Grimoire

Dining Philosophers Problem in Go

// Philosopher's problem, exploring concurrency in Go

package main

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

const (
	numPhilosophers = 5
	numForks        = 5
	numMeals        = 3
)

type Philosopher struct {
	id        int
	leftFork  *sync.Mutex
	rightFork *sync.Mutex
	ladle     *sync.Mutex
}

func (p *Philosopher) eat(wg *sync.WaitGroup) {
	defer wg.Done()
	for i := 0; i < numMeals; i++ {
		// think
		think := rand.Intn(5) + 1
		fmt.Printf("Philosopher %d is thinking for %d seconds\n", p.id, think)
		time.Sleep(time.Duration(think) * time.Second)

		// pick up ladle
		p.ladle.Lock()
		fmt.Printf("Philosopher %d used the ladle\n", p.id)

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

		// eat after picking up two forks
		eat := rand.Intn(5) + 1
		fmt.Printf("Philosopher %d is eating for %d seconds\n", p.id, eat)
		time.Sleep(time.Duration(eat) * time.Second)

		// put down forks
		p.leftFork.Unlock()
		fmt.Printf("Philosopher %d put down the left fork\n", p.id)
		p.rightFork.Unlock()
		fmt.Printf("Philosopher %d put down the right fork\n", p.id)

		// Put down ladle
		p.ladle.Unlock()
		fmt.Printf("Philosopher %d put down the ladle\n", p.id)
	}
}

func main() {
	forks := make([]*sync.Mutex, numForks)
	for i := range forks {
		forks[i] = &sync.Mutex{}
	}

	ladle := &sync.Mutex{}

	philosophers := make([]*Philosopher, numPhilosophers)
	for i := range philosophers {
		leftFork := forks[i]
		rightFork := forks[(i+1)%numForks]
		philosophers[i] = &Philosopher{id: i + 1, leftFork: leftFork, rightFork: rightFork, ladle: ladle}
	}

	var wg sync.WaitGroup
	wg.Add(numPhilosophers)
	for _, p := range philosophers {
		go p.eat(&wg)
	}
	wg.Wait()
}

Key Concepts in Go

1. Concurrency with Goroutines

   • Go’s goroutines are lightweight threads managed by the Go runtime, making concurrent programming simple and efficient.
   • Each philosopher runs as a separate goroutine, simulating independent actors that can execute and be scheduled concurrently.

2. Mutual Exclusion with Mutexes

   • Uses sync.Mutex to represent forks and a ladle (shared resource), ensuring that only one philosopher can access each at a time.
   • Prevents race conditions and ensures data consistency.

3. Deadlock Avoidance

   • The classic dining philosophers problem risks deadlocks if every philosopher picks up one fork and waits for another.
   • This implementation introduces a ladle (a single mutex all philosophers must acquire before picking up forks), serializing entry to the critical section and eliminating deadlock risk.

4. WaitGroup Synchronization

   • sync.WaitGroup is used to wait for all philosopher goroutines to finish their meals before the main program exits.

Overview of the Program

• Problem: Five philosophers sit at a table with five forks. Each needs two forks to eat. This classic concurrency problem explores synchronization and deadlock.
• Go Solution:
  • Each philosopher is modeled as a goroutine.
  • Forks and the ladle are mutexes.
  • Philosophers repeatedly “think,” then attempt to eat by acquiring the ladle and both adjacent forks.
  • After eating, they release all resources and think again.

Real-World Applications of Concurrency

• Resource Scheduling: This pattern is useful for modeling systems where many agents need exclusive access to a limited set of resources (e.g., database locks, printer queues).
• Professional Use: Concurrency is fundamental in backend services, networking, simulations, and distributed systems.
• Go in Production: Go’s model is widely used in cloud infrastructure, microservices, high-performance servers, and real-time applications.

Code Explanation

• Philosopher Struct:

  type Philosopher struct {
      id        int
      leftFork  *sync.Mutex
      rightFork *sync.Mutex
      ladle     *sync.Mutex
  }
  

  • Each philosopher keeps track of their forks and the shared ladle.

• Eating Logic:

  func (p *Philosopher) eat(wg *sync.WaitGroup) {
      defer wg.Done()
      for i := 0; i < numMeals; i++ {
          // Think (simulate with sleep)
          // Lock ladle (serialize access)
          // Lock left then right fork (mutexes)
          // Eat (simulate with sleep)
          // Unlock all in reverse order
      }
  }
  

  • The philosopher must acquire the ladle before forks, then eat, then release all.

• Launching Goroutines:

  for _, p := range philosophers {
      go p.eat(&wg)
  }
  wg.Wait()
  

How to Run

1. Save the file as philosopher.go.
2. Run the program:

   go run philosopher.go
   

3. Example output:

   Philosopher 1 is thinking for 3 seconds
   Philosopher 2 is thinking for 5 seconds
   ...
   Philosopher 1 used the ladle
   Philosopher 1 picked up left fork
   Philosopher 1 picked up right fork
   Philosopher 1 is eating for 2 seconds
   ...
   

Extensions and Professional Tips

• Alternative Deadlock Solutions: Explore solutions such as ordering resource acquisition or using semaphores.
• Performance Tuning: In high-concurrency systems, analyze lock contention and consider lock-free or channel-based designs.
• Production Use: Always test concurrent code with race detection (go run -race); concurrency bugs can be subtle.

Would you like to document another concurrency example or go deeper into Go’s concurrency patterns?