Why I receive an intermittent deadlock error?

Hello,

I am trying the Dining Philosophers problem to learn about concurrency, but I am receiving a fatal error: all goroutines are asleep - deadlock!

package main

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

type Chops struct{ sync.Mutex }

type Philo struct {
	leftChopStick, rightChopStick *Chops
	count                         int
}

var wq sync.WaitGroup

func (p Philo) eat(num int) {
	for i := 0; i < 3; i++ {
		if p.count > 3 {
			continue
		} else {
			p.leftChopStick.Lock()
			p.rightChopStick.Lock()
			p.count++
			fmt.Printf("starting to eat %d, %d time(s)\n", num+1, p.count)

			p.leftChopStick.Unlock()
			p.rightChopStick.Unlock()
			fmt.Printf("finishing eating %d\n", num+1)
		}
	}
	wq.Done()

}

func main() {
	ChopSticks := make([]*Chops, 5)
	for i := 0; i < 5; i++ {
		ChopSticks[i] = new(Chops)
	}

	philos := make([]*Philo, 5)
	rand.Seed(time.Now().UnixNano())

	for i := 0; i < 5; i++ {
		var randElem1 int
		var randElem2 int
		for {
			if randElem1 != randElem2 {
				break
			} else {
				randElem1 = rand.Intn(len(ChopSticks) - 1)
				randElem2 = rand.Intn(len(ChopSticks) - 1)
			}
		}
		philos[i] = &Philo{ChopSticks[randElem1], ChopSticks[randElem2], 0}
	}

	for i := 0; i < 5; i++ {
		wq.Add(1)
		go philos[i].eat(i)
	}
	wq.Wait()
}
2 Likes

I try on the go playground It has no any problems.

This is test share link
https://play.golang.org/p/OyEKA55xhe9

2 Likes

Tested on my local machine. The crash happens occasionally. @meibou, did you plan out your goroutines? If yes, can you share the plan out?

EDIT: or can you share the dining philosophers problem?

1 Like

@hollowaykeanho sorry I am new to go, what do you mean if I plan out my goroutines?

the problem is this one:

  • There should be 5 philosophers sharing chopsticks, with one chopstick between each adjacent pair of philosophers.

  • Each philosopher should eat only 3 times

  • The philosophers pick up the chopsticks in any order, not lowest-numbered first

In order to eat, a philosopher must get permission from a host which executes in its own goroutine.

The host allows no more than 2 philosophers to eat concurrently.

  • Each philosopher is numbered, 1 through 5.

  • When a philosopher starts eating (after it has obtained necessary locks) it prints “starting to eat on a line by itself, where is the number of the philosopher.

  • When a philosopher finishes eating (before it has released its locks) it prints “finishing eating on a line by itself, where is the number of the philosopher.

2 Likes

yes so basically I dont receive the deadlock error every time

2 Likes

The dining philosopher are supposed to be in circle. See https://medium.com/@maheshkariya/operating-system-dining-philosopher-problem-using-semaphores-4caf0b22516f.

This means that philosopher i has chopsticks i and (i + 1) mod 5 next to him. See the pseudo code in referenced article.

To avoid deadlocks, the chopsticks must be locked together. If you lock one, then lock the second, it is possible to get into a deadlock.

Randomizing the left/right chopstick lock order will not avoid deadlocks. It increases the probability of deadlock. If every philosopher take the right chopstick and lock it, none will be able to get its left chopstick. That’s how you get a deadlock!

In your implementation, you randomized the chopstick assignment. This means that you don’t have one big circle of philosopher, but likely tow or more smaller circles. This increase the probability of deadlock.

You can’t use a mutex for the chopstick. A philosopher must eat when it holds both chopsticks, but must not keep a stick in hand (locked) while waiting for the second.

It is easy to implement with a global lock mutex. But I guess this is not want you want to implement.

Another way to do this is for a philosopher to lock on the first chopstick and try lock on the second. If it succeed, he eats, and release both locks. Otherwise, he release the first locked chopstick and think for a random time before retrying to lock both chopsticks.

The problem is that go doesn’t have a try lock method. It can be implemented with atomic operations though.

With the try lock approach, the order of locking is important. It must be always lock the right chopstick first and try lock the left chopstick, or the reverse. Otherwise you will get deadlocks.

If you have a method to lock both or none in one atomic step, the order is not relevant.

3 Likes

The firs thing to change in your code is the random assignment of chopsticks. The dining philosopher are in one big circle with one chopstick between each one of them.

Ideally we should try lock both chopstick at once, but this can be made in sequence, as long as we unlock the first chopstick if we fail to also lock the second chopstick. In this case, the lock order is not relevant and can’t lead to a deadlock.

What you could do is assign chopsticks in sequence to philosophers and then randomly swap right and left chopstick of each philosopher to ensure they don’t pick them in same order.

We then need a function to try lock both chopsticks. This can be achieved by using atomic operation CompareAndSwapUint32. Each chopstick would be a Uint32 initialized to 0 which would stand for unused chopstick.

You then call atomic.atomic.CompareAndSwapUint32(&rightChopstick, 0, 1) returning a bool. It will return true if the rightChopstick was 0 (unused), and will set it to 1. If it succeed, it will do the same with the leftChopstick. If both chopsticks could have beed locked, they are released with atomic.StoreUint32(&rightChopstick,0) and atomic.StoreUint32(&lefttChopstick,0), and the philosopher has eaten.

If the first chopstick can’t be locked, the philosopher should get back thinking again for a random time and retry later. If the second chopstick can’t locked, the first must be released, and the philosopher must also get back thinking again.

That is the general algorithm of the synchronization I would use for the dining philosopher problem. The right/left order is not relevant as long as both a try locks which we implement here with atomic operation.

3 Likes

The main reason I can see is the missing concurrency planning.

The reason the codes got deadlock is because your timing of locking for each sticks is unclear. Topping up the fact that you randomizes the sticks and assign to 5 philosophers, there is a chance where a stick is getting locked multiple rounds at the same time, repeatedly. That’s why you occasionally get deadlock.

The way you’re currently doing is like picking 1 stick from a pair chopstick and combine with another stick from another pair and tell the philosopher to use that pair of chopstick to eat.


Aside from @Christophe_Meessen mentioning about not understanding the problem clearly, you always need to plan out your concurrency. This is important because you’re dealing with multiple processes. If one process is giving you problem(s), it will be magnified. Concurrency planning also helps you prioritizes what to control and simplify the processes to the minimum viable codes. Only then, you can have full power to ensure all processes will not get into deadlock and race conditions problems.

Planning Example

Here is an example of the planning (I refactored the plan 2 times before testing it on code) based on your listed requirements.

Plan 1


If you notice, in Plan 1, it serves as an overview of the program, testing whether I’m understanding the problem correctly or otherwise. It is cleared that we have at least 2 main process structures (main as “host”, p as philosopher process). The arrows (with some errors) indicate data exchanges between main and any p processes.

However, it is still unclear how would I approach the synchronization, so we need to improve the plan.

Plan 2


In Plan 2, a more improved version, we can now clearly see that host is actually controlling who can eat, offers a request function to either return nil to deny eating or a chopstick to allow eating.

Also, p will check his/her fullness and inform back to host that he/she will no longer eats. However, we did not take that into account in both Plan 1 and Plan 2, so we need to improve it again.

Plan 3


In Plan 3, it is very clear now with roles and synchronization. The table is synchronized using mutex locking in order to offer request function. It has clarity on when to lock and unlock during checking.

Also, main setup a channel approach (c1) after table for synchronizing with all philosophers regarding of their fullness before serving them. Hence, we understood that step 6 in main is a for...select mechanism for their waiting. Hence, at step 5, we are clear that each philosopher will take in c1 as a parameter in order to inform host of his/her fullness.

On p side, it is clear that philosopher knows whether he/she can eat by checking the return value of the request function. Without chopstick, repeat the request again. Since we’re using c1 channel, it made it easy to infrom the host before completing the process.

With Plan 3, you can now know how-to and what-to code. If you notice:

  1. we do not need to manage chopsticks down to sticks level.
  2. chopsticks ownership is not needed.

However, we are still unclear with

  1. contact switching between main, table, and p. (WHO is doing WHAT at WHEN)
  2. After eating, who is freeing the chopsticks.

Hence, we refactor the plan again.

Plan 4


This time, it has very clear contact switching, and explanation on WHO is doing WHAT at WHEN.

We can now clearly see that table is responsible to setup and managing chopsticks, offering contacting switching functions like Request and Return to p. The mutex locking happens only at table.

p only needs to setup his/her fullness limit, use Request to get a chopstick from table, start eating, stop eating etc and Return to free the chopstick back to table and check for its fullness. If full, then he/she informs host by sending his/her name to the fullness c1 channel.

main (host) only needs to know the headcount, setup table, the fullness channel c1, serve the philosophers (p1, p2, …), then process the waiting (for..select) by checking the fullness report is the same has headcount.

At any point, any time, you can use this map to explain WHO is doing WHAT at WHEN. This is the best indicator that you’re ready to code. You can continue to refactor your plan. However, Plan 4 is good enough for coding.


The codes differs from individual to individuals. However, all of them should agree to your concurrency plan. Please try it out yourself.

I’m hiding my tested source codes just in case. Please be self-disciplined. Welcome to Golang-Bridge by the way. :rocket::fireworks:

One coding Example
package main

import (
	"fmt"
	"sync"
)

const (
	maxEating = 2
	fullnessLimit = 2
)

// Chopsticks is an object structure that serves as a tool to eat
type Chopsticks struct {
	mutex  sync.RWMutex
	ID     int
	isUsed bool
}

// NewChopsticks creates a Chopsticks object with the given id label.
func NewChopsticks(id int) *Chopsticks {
	return &Chopsticks{
		mutex:  sync.RWMutex{},
		ID:     id,
		isUsed: false,
	}
}

// Use is to set the Chopsticks status to "In-Use"
func (c *Chopsticks) Use() {
	c.mutex.Lock()
	defer c.mutex.Unlock()
	c.isUsed = true
}

// Free is to set the Chopsticks status to "Free"
func (c *Chopsticks) Free() {
	c.mutex.Lock()
	defer c.mutex.Unlock()
	c.isUsed = false
}

// IsInUse is to check the Chopsticks status, currently "In-Use" or "Free".
func (c *Chopsticks) IsInUse() bool {
	c.mutex.Lock()
	defer c.mutex.Unlock()
	return c.isUsed
}

// Table is the structure serving foods and chopsticks
type Table struct {
	mutex      sync.RWMutex
	isEating   uint
	chopsticks []*Chopsticks
}

// NewTable creates the table object with person quantity.
func NewTable(quantity uint) *Table {
	t := &Table{
		mutex:      sync.RWMutex{},
		isEating:   0,
		chopsticks: []*Chopsticks{},
	}
	for i := 0; i < int(quantity); i++ {
		t.chopsticks = append(t.chopsticks, NewChopsticks(i))
	}

	return t
}

// RequestChopsticks is to allows a customer to eat using an available
// Chopsticks.
func (t *Table) RequestChopsticks() *Chopsticks {
	t.mutex.Lock()
	defer t.mutex.Unlock()

	// table is full
	if t.isEating >= maxEating {
		return nil
	}

	// permit to eat. Scan for available chopsticks
	c := t.seekChopsticks()
	c.Use()
	t.isEating++
	return c
}

func (t *Table) seekChopsticks() *Chopsticks {
	// NOTE: here, you can use random. I will use FIFO instead.
	for _, c := range t.chopsticks {
		if !c.IsInUse() {
			return c
		}
	}
	return nil
}

// ReturnChopsticks is to allow a customer to place back chopsticks when
// he/she is done eating
func (t *Table) ReturnChopsticks(c *Chopsticks) {
	t.mutex.Lock()
	defer t.mutex.Unlock()
	t.isEating--
	c.Free()
}

func philosopher(id int, fullness chan int, table *Table) {
	eatCount := fullnessLimit

	for {
		chopsticks := table.RequestChopsticks()
		if chopsticks == nil {
			continue
		}

		// start eating
		fmt.Printf("P%d: START eating with chopstick %d.\n",
			id,
			chopsticks.ID)

		// eating
		eatCount--

		// stop eating
		fmt.Printf("P%d: FINISH eating with chopstick %d.\n",
			id,
			chopsticks.ID)
		table.ReturnChopsticks(chopsticks)

		// check fullness
		if eatCount == 0 {
			fullness <- id
			return
		}

	}
}

func main() {
	headcount := 5

	t := NewTable(uint(headcount))
	c1 := make(chan int)
	fullness := 0

	for i := 0; i < headcount; i++ {
		go philosopher(i, c1, t)
	}

	// Wait for fullness
	for {
		select {
		case person := <-c1:
			fullness++
			fmt.Printf("Philosopher %d is full\n", person)
			if fullness == headcount {
				fmt.Printf("All are full.\n[ ENDED ]\n")
				return
			}
		}
	}
}

// Output:
// P4: START eating with chopstick 0.
// P4: FINISH eating with chopstick 0.
// P4: START eating with chopstick 0.
// P4: FINISH eating with chopstick 0.
// Philosopher 4 is full
// P0: START eating with chopstick 0.
// P0: FINISH eating with chopstick 0.
// P0: START eating with chopstick 0.
// P0: FINISH eating with chopstick 0.
// Philosopher 0 is full
// P3: START eating with chopstick 0.
// P2: START eating with chopstick 1.
// P2: FINISH eating with chopstick 1.
// P3: FINISH eating with chopstick 0.
// P3: START eating with chopstick 0.
// P3: FINISH eating with chopstick 0.
// Philosopher 3 is full
// P2: START eating with chopstick 1.
// P2: FINISH eating with chopstick 1.
// Philosopher 2 is full
// P1: START eating with chopstick 0.
// P1: FINISH eating with chopstick 0.
// P1: START eating with chopstick 0.
// P1: FINISH eating with chopstick 0.
// Philosopher 1 is full
// All are full.
// [ ENDED ]

3 Likes

oh wow :smiley: thank you so so much :pray: @hollowaykeanho I am going to study this and try it myself.

@Christophe_Meessen thank you :pray: I will try the atomic operation as well

2 Likes

You’re welcome. Feel free to “mark as solved” when you got your answer.

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.