Solving the Philosophers’ Dining Problem with Channels and Concurrency in Go

INTRO

The Philosophers’ Dining Problem is a classic synchronization problem in computer science that illustrates the challenges of avoiding deadlock and starvation in concurrent systems. It involves a group of philosophers sitting around a circular table, with a fork placed between each pair of adjacent philosophers. Each philosopher must alternately think and eat, but to eat, they need to acquire two forks — one from their left and one from their right. The problem arises when multiple philosophers try to acquire forks simultaneously, leading to potential deadlocks or starvation scenarios.

In this blog post, we’ll explore a solution to the Philosophers’ Dining Problem using Go’s built-in concurrency primitives, specifically goroutines and channels. We’ll dive into the details of the problem, discuss the challenges involved, and present a complete solution that ensures fairness, avoids deadlocks, and prevents starvation.

The problem consists of the following components:

1. Philosophers: A group of philosophers, each representing a concurrent process or thread.
2. Forks: A limited number of forks, equal to the number of philosophers, placed between each pair of adjacent philosophers.
3. Thinking and Eating: Each philosopher alternates between thinking and eating. To eat, a philosopher must acquire two forks — one from their left and one from their right.

The constraints of the problem are:

1. A philosopher can only pick up one fork at a time.
2. A philosopher cannot pick up a fork if it is already held by another philosopher.
3. A philosopher cannot start eating until they have acquired both forks.
4. After eating, a philosopher must put down both forks, allowing other philosophers to acquire them.

SOLUTION

The key components of our solution are:

1. Philosopher goroutines: Each philosopher will be represented by a goroutine that continuously alternates between thinking and eating.
2. Fork channels: We’ll create a channel for each fork, representing its availability. Philosophers will send and receive values on these channels to acquire and release forks.
3. Pickup and putdown functions: These functions will handle the logic for acquiring and releasing forks, ensuring fairness and preventing deadlocks and starvation.
4. Synchronization mechanisms: We’ll employ techniques like channel operations and select statements to synchronize the philosophers’ actions and ensure proper coordination.

We can define a Philosopher struct like so

type philosopher struct {
   id                  int
   leftFork, rightFork chan struct{}
}

We can actually go ahead and implement some of the actions that a Philosopher can perform like thinking and eating

func (p *philosopher) think() {
 fmt.Printf("Philosopher %d is thinking\n", p.id)
 time.Sleep(time.Duration(rand.Intn(int(maxThinkingTime/time.Millisecond))) * time.Millisecond)
}

func (p *philosopher) eat(wg *sync.WaitGroup) {
 defer wg.Done()

 for {
  if pickUpForks(p.leftFork, p.rightFork) {
   fmt.Printf("Philosopher %d is eating\n", p.id)
   time.Sleep(time.Duration(rand.Intn(int(maxEatingTime/time.Millisecond))) * time.Millisecond)
   putDownForks(p.leftFork, p.rightFork)
   p.think()
   return
  }
 }
}

The last parts of the implemention would entail the PutDownFork function as well as the PickUpFork function, which basically just releases the resources.

func pickUpForks(leftFork, rightFork chan struct{}) bool {
   select {
   case leftFork <- struct{}{}:
    select {
    case rightFork <- struct{}{}:
     return true
    default:
     <-leftFork
     return false
    }
   default:
    return false
   }
}

func putDownForks(leftFork, rightFork chan struct{}) {
   <-leftFork
   <-rightFork
}

Bringing it all together, we can then define a main method like below

func Main() {
 rand.New(rand.NewSource(time.Now().UnixNano()))

 forks := make([]chan struct{}, numPhilosophers)
 for i := range forks {
  forks[i] = make(chan struct{}, 1)
 }

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

 var wg sync.WaitGroup
 wg.Add(numPhilosophers)

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

 wg.Wait()
 fmt.Println("All philosophers have finished eating.")
}

and thats it!

When you run the above solution with the following constants

const (
 numPhilosophers = 5
 maxThinkingTime = 3 * time.Second
 maxEatingTime   = 1 * time.Second
)

you will get an output similar to the one below

$ go run main.go
Philosopher 4 is eating
Philosopher 1 is eating
Philosopher 3 is eating
Philosopher 4 is thinking
Philosopher 1 is thinking
Philosopher 0 is eating
Philosopher 0 is thinking
Philosopher 3 is thinking
Philosopher 2 is eating
Philosopher 2 is thinking
All philosophers have finished eating.

SUMMARY

The solution models the philosophers and forks using goroutines and channels, respectively. Each philosopher is represented by a goroutine that continuously alternates between thinking, picking up forks, eating, and putting down forks.

The forks are represented by channels, with each fork having a channel of buffer size 1. A value in the channel indicates that the fork is available, while an empty channel means the fork is taken.

The pickUpForks() method handles the logic for acquiring forks. It uses a select statement to attempt to acquire the left and right forks in a fair manner, ensuring that no philosopher is indefinitely denied access to the forks (preventing starvation).

The solution employs techniques like channel operations and select statements to synchronize the philosophers’ actions and ensure proper coordination, avoiding deadlocks and starvation scenarios.

The solution demonstrates how Go’s concurrency primitives, goroutines and channels, can be used to elegantly solve a classic synchronization problem like the Philosophers’ Dining Problem, ensuring fairness, avoiding deadlocks, and preventing starvation.