Deadlock problems in software often occur when two processes are trying to write into one resource at the same time, causing both to fail. This can be likened to two buyers trying to purchase the last product at the same time, both failing because they try to update the product data simultaneously.

One of the best ways to explain deadlocks is through the Five Philosophers Problem.

The Five Philosophers Problem

Imagine five philosophers seated around a circular table. Each has a plate of noodles and a chopstick on both sides of their plate. The complication arises when they all try to eat at once, each needing both chopsticks to eat.

Scenario Explanation

• Setup: Five philosophers sitting at a round table, each with a chopstick on either side.
• Eating Process: To eat, a philosopher must pick up both the left and right chopsticks.

Consider the following image for clarity:

Five philosophers sitting at a round table with a chopstick on each side of their plate. If each philosopher picks up their left chopstick, they all hold one chopstick and wait indefinitely for the right one, resulting in deadlock.

Deadlock happened since everyone picked up a chopstick and waited for each other.

Implementing the Solution in Go

Basic Eating Simulation

First, let's write a simple program to simulate the philosophers eating.

package main

import "fmt"

type philosophers []string

func main() {
    philosophers := philosophers{"Aristotle", "Plato", "Socrates", "Descartes", "Kant"}

    for _, p := range philosophers {
        fmt.Printf("%s is eating\n", p)
    }

    fmt.Println("All philosophers are done eating")
}

*Output:*

```console
Aristotle is eating
Plato is eating
Socrates is eating
Descartes is eating
Kant is eating

Introducing Chopsticks

Now, we introduce chopsticks, so each philosopher picks up the chopsticks before eating.

type chopstick []int

func main() {
    chops := chopstick{0, 1, 2, 3, 4}
    philosophers := philosophers{"Aristotle", "Plato", "Socrates", "Descartes", "Kant"}

    for i, p := range philosophers {
        leftChop, rightChop := chops[i], chops[(i%4)+1]
        fmt.Printf("%s picked up chop %d \n", p, chops[leftChop])
        fmt.Printf("%s picked up chop %d \n", p, chops[rightChop])
        fmt.Printf("%s is eating \n", p)
    }

    fmt.Println("All philosophers are done eating")
}

Output:

Aristotle picked up chop 0 
Aristotle picked up chop 1 
Aristotle is eating 
Plato picked up chop 1 
Plato picked up chop 2 
...

Preventing Deadlock with Mutex

Next, we need to introduce a locking mechanism to prevent a chopstick from being used by two philosophers at the same time.

The red connections to the chopsticks mean that the chopstick is locked and the therapist needs to wait for it to be available.

To prevent deadlock, we use a locking mechanism. Each chopstick will be protected by a Mutex. I explained how mutex work in this article posted on my blog.

package main

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

type Chop struct {
    sync.Mutex
}

type Philosopher struct {
    name     string
    eatCount int
}

func (p *Philosopher) Eat(leftChop, rightChop *Chop) {
    leftChop.Lock()
    rightChop.Lock()
    fmt.Println(p.name, "is eating")
    time.Sleep(time.Second)
    leftChop.Unlock()
    rightChop.Unlock()
}

func main() {
    var wg sync.WaitGroup
    chops := make([]*Chop, 5)
    for i := 0; i < 5; i++ {
        chops[i] = new(Chop)
    }

    philosophers := []Philosopher{
        {"Aristotle", 0},
        {"Plato", 0},
        {"Socrates", 0},
        {"Descartes", 0},
        {"Kant", 0},
    }

    for i := 0; i < 5; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            philosophers[i].Eat(chops[i], chops[(i+1)%5])
        }(i)
    }

    wg.Wait()
    fmt.Println("All philosophers are done eating")
}

In the code above, we execute 5 goroutines for each philosopher to eat, and each of them waits for the other chopstick to be free in order to eat.

But since we go in order 1…5, there won’t be a deadlock because they are just waiting until it’s their turn.

Output:

Kant is eating
Plato is eating
Aristotle is eating
Descartes is eating
Socrates is eating
All philosophers are done eating

Running Goroutines Indefinitely

In the following code, we will add an infinite loop that will just run goroutines in order, and each loop will wait until the previous 5 goroutines are done.

func main() {
    var wg sync.WaitGroup
    chops := make([]*Chop, 5)
    for i := 0; i < 5; i++ {
        chops[i] = new(Chop)
    }

    philosophers := []Philosopher{
        {"Aristotle", 0},
        {"Plato", 0},
        {"Socrates", 0},
        {"Descartes", 0},
        {"Kant", 0},
    }

    for {
        for i := 0; i < 5; i++ {
            wg.Add(1)
            go func(i int) {
                defer wg.Done()
                philosophers[i].Eat(chops[i], chops[(i+1)%5])
            }(i)
        }
        wg.Wait()
    }
}

Output:

...
Kant is eating
Plato is eating
Descartes is eating
Aristotle is eating
Socrates is eating
Plato is eating
Aristotle is eating
Kant is eating
Descartes is eating
...

This will give you a simple visualization of how the philosophers are going to eat and how they won't be able to eat if the adjacent one is eating.

Conclusion

While this solution reduces the likelihood of deadlocks, it is not entirely foolproof.

Go's concurrency model and goroutine scheduling help manage execution order, making deadlocks less common. Avoiding deadlocks in Go is easier thanks to its built-in tools and mechanisms.

Deadlocks are a frequent problem in software, especially when working with microservices and multiple storage instances for data read/write operations. As you scale your project horizontally—running multiple instances—the chances of encountering deadlocks increase.

Understanding and implementing proper concurrency control is crucial to mitigating these risks.