Classical concurrency problem: the dining problem of philosophers

The dining problem of philosophers is a very classic problem , It is also a very general problem to study deadlock in concurrent programming .

Why should we study classical concurrency problems ？ These classical problems are abstractions of computer programming in reality , It represents a very general computer concurrency problem , Computer scientists have conducted in-depth research on this , Also summed up a lot of effective solutions . We learn these classic problems , We can compare the concurrency problems we encounter , See if it's a similar problem , How is the same problem , Solutions summarized by predecessors can be used to solve . At the same time, contact and solve these problems , It can also enable us to learn and master concurrency primitives and problem-solving skills , Draw inferences from one instance to solve more concurrency problems .

stay 1971 year , Ezig, a famous computer scientist · Dikosche (Edsger Dijkstra) A synchronization problem is proposed , Let's say that five computers are trying to access five shared tape drives . later , This is a question Tony · Holzer (Tony Hoare) Restated as the dining problem of philosophers . This problem can be used to explain deadlock and resource exhaustion .

In China , The dining problem of philosophers can be expressed in this way , Suppose because of the new crown , Five philosophers were quarantined in a room . These five philosophers are Confucius 、 Chuang tzu 、 mozi 、 Grandson and Lao Tzu , They sat around a round table , There are endless delicious meals on the table , Unfortunately , For environmental reasons , There are only five chopsticks , Each chopstick lies between two philosophers . Philosophers eat , You must pick up two chopsticks on your left and right sides to eat , Put chopsticks back after eating , So that other philosophers can pick up chopsticks .

Although the days of isolation are lonely , But these philosophers still have something to do , They constantly meditate or eat . Try to pick up chopsticks when you are hungry , Eat random meals , Then put down your chopsticks and meditate . I'm hungry after meditating for a while , Start eating again . So they are always in meditation - I'm hungry - having dinner - In such a state of meditation .

This philosopher well simulated the concurrency problem of a certain number of resources and a certain number of holders in computer concurrent programming , A big problem of this kind is deadlock .

If five philosophers are hungry at the same time , At the same time, pick up the chopsticks on the left , You will find that when they want to get the chopsticks on the right , There is no way to pick up the chopsticks on the right , Because the chopsticks on the right were taken away by the philosopher next to them , All philosophers are in a state of waiting and have no way to continue . For the program , It's the program hang dead , There is no way to continue processing .

If these five philosophers find at the same time that there is no chopsticks available on the right , They put down their left chopsticks at the same time , meditation 5 Minutes and then eat at the same time , You will find that the program seems to be in progress , But philosophers still have no way to eat , This phenomenon is called deadlock . In the distributed consistency algorithm, there will be a similar phenomenon when selecting the master , Some implementations sleep randomly for a certain time , Avoid all nodes requesting to choose the master at the same time to avoid .

If there is only one thread in the system , Of course, there will be no deadlock . If each thread requires only one concurrent resource , And there's no deadlock . But this is only the ideal state , In reality, it can be met but not sought . If you search Go In the official project issue, You can see hundreds of deadlocks issue, Enough to show that deadlocks are common and not easy to handle bug.

The four conditions of deadlock are ：

• No preemption （no preemption）： System resources cannot be forced to exit from a thread . If philosophers can rob , Then everyone grabs others' chopsticks , It will also break the deadlock , But there are risks , Because maybe Confucius was robbed by Lao Tzu before he had a meal . If computer resources are not actively released but robbed, unexpected phenomena may occur .

• Hold and wait （hold and wait）： A thread holds concurrent resources while waiting . Hold concurrent resources and wait for other resources , That is, eating in the bowl and looking at the pot .

• Mutually exclusive （mutual exclusion）： Resources can only be allocated to one thread at the same time , Cannot be shared by multiple threads . Resources are exclusive , No matter how good the relationship between Confucius and Lao Tzu is , They are not allowed to eat with one chopstick together .

• Loop waiting for （circular waiting）： A series of threads hold resources needed by other processes . There must be a circular dependency relationship .

Deadlock occurs only when four conditions are met at the same time , Deadlock prevention must break at least one of them .

Simulating the dining problem of philosophers

First, we simulate the dining problem of philosophers through programs , See if the program running will cause deadlock problems .

First, we define chopsticks and philosophers . Chopsticks are concurrent resources , Be exclusive , So it contains a lock , Used to realize mutual exclusion , And no preemption ( Other philosophers who do not hold this chopstick cannot call Unlock, Only philosophers who hold this chopstick can call Unlock).

Every philosopher needs left-hand chopsticks and right-hand chopsticks ,status Represents the state of philosophers ( meditation 、 I'm hungry 、 At dinner ), He has a state of holding one chopstick and asking for another .

1 2 3 4 5 6 7 8 9 10 11

// Chopstick Represents chopsticks . type Chopstick struct{ sync.Mutex } // Philosopher For philosophers . type Philosopher struct { // The name of the philosopher name string // One left hand and one right hand chopsticks leftChopstick, rightChopstick *Chopstick status string }

Philosophers in isolated rooms are constantly meditating 、 dining 、 meditation 、 dining ...... Forever .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

// Endless meals and meditation . // Eat and sleep ( meditation 、 Sit in meditation ), Eat after sleeping . // You can adjust the time of eating and sleeping to increase or reduce the chance of grabbing forks . func (p *Philosopher) dine() { for { mark(p, " meditation ") randomPause (10) mark(p, " I'm hungry ") p.leftChopstick.Lock() // First try to pick up the chopsticks on your left mark(p, " Pick up the left chopsticks ") p.rightChopstick.Lock() // Try picking up the chopsticks on your right mark(p, " Eat ") randomPause (10) p.rightChopstick.Unlock() // First try to put down the chopsticks on your right p.leftChopstick.Unlock() // Then try to pick up the chopsticks on your left } } // Pause randomly for a period func randomPause(max int) { time.Sleep(time.Millisecond * time.Duration(rand.Intn(max))) } // Show the status of this philosopher func mark(p *Philosopher, action string) { fmt.Printf( "%s Start %s\n", p.name, action) p.status = fmt.Sprintf( "%s Start %s\n", p.name, action) }

there mark Used to output the status of this philosopher on the console , It's easy for us to observe .

The last step is to realize main function , Distribute 5 Root chopsticks and five philosophers , Let the program run :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

func main() { go http.ListenAndServe( "localhost:8972", nil) // The number of philosophers count := 5 // establish 5 Chopsticks chopsticks := make([]*Chopstick, count) for i := 0; i < count; i++ { chopsticks[i] = new(Chopstick) } // names := [] string{color.RedString( " Confucius "), color.MagentaString( " Chuang tzu "), color.CyanString( " mozi "), color.GreenString( " Grandson "), color.WhiteString( " Lao tze ")} // Create philosophers , Give them the forks at their left and right hands , Lead them to the round table . philosophers := make([]*Philosopher, count) for i := 0; i < count; i++ { philosophers[i] = &Philosopher{ name: names[i], leftChopstick: chopsticks[i], rightChopstick: chopsticks[(i +1)%count], } go philosophers[i].dine() } sigs := make( chan os.Signal, 1) signal.Notify(sigs, syscall.SIGINT, syscall.SIGTERM) <-sigs fmt.Println( " Exiting ... The state of every philosopher :") for _, p := range philosophers { fmt.Print(p.status) } }

Run this program and you will soon find that this program will hang live , Every philosopher is in a state of holding his left chopsticks and waiting for his right chopsticks .

In our practical application , Deadlock problem is not so easy to find , Probably in some very specific scenarios ( Also known as corner case) Will be triggered and found .

Solution 1 ： Limit the number of people eating

We know , To solve the problem of deadlock is to destroy one of the four conditions for deadlock formation . Generally speaking , Prohibition of preemption and mutual exclusion is a necessary condition , So the other two conditions are our key breakthrough .

For the dining problem of philosophers , If we limit the number of philosophers allowed to eat at the same time , You can avoid the condition of circular dependency , Because according to the drawer principle , There will always be a philosopher who can get two chopsticks , So the program can run .

For limiting a specific number of resources , The best concurrency primitive to use is semaphore (Semaphore).Go An extension library is officially provided , Provides a Semaphore The implementation of the ：semaphore/Weighted.

We set the initial value of this semaphore to 4, It means that at most 4 Dining for philosophers . Send this semaphore to the philosopher object , Philosophers ask for this semaphore when they want to eat , If you can get a permit , You can eat , After eating, release the permission back to the semaphore .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

type Philosopher struct { // The name of the philosopher name string // One left hand and one right hand chopsticks leftChopstick, rightChopstick *Chopstick status string // Semaphore sema *semaphore.Weighted } // Endless meals and meditation . // Eat and sleep ( meditation 、 Sit in meditation ), Eat after sleeping . // You can adjust the time of eating and sleeping to increase or reduce the chance of grabbing forks . func (p *Philosopher) dine() { for { mark(p, " meditation ") randomPause (10) mark(p, " I'm hungry ") p.sema.Acquire(context.Background(), 1) // Ask for permission p.leftChopstick.Lock() // First try to pick up the chopsticks on your left mark(p, " Pick up the left chopsticks ") p.rightChopstick.Lock() // Try picking up the chopsticks on your right mark(p, " Eat ") randomPause (10) p.rightChopstick.Unlock() // First try to put down the chopsticks on your right p.leftChopstick.Unlock() // Then try to pick up the chopsticks on your left p.sema.Release (1) // Release permission to semaphore } } func main() { ...... // At most four philosophers are allowed to eat sema := semaphore.NewWeighted (4) // names := [] string{color.RedString( " Confucius "), color.MagentaString( " Chuang tzu "), color.CyanString( " mozi "), color.GreenString( " Grandson "), color.WhiteString( " Lao tze ")} // Create philosophers , Give them the forks at their left and right hands , Lead them to the round table . philosophers := make([]*Philosopher, count) for i := 0; i < count; i++ { philosophers[i] = &Philosopher{ name: names[i], leftChopstick: chopsticks[i], rightChopstick: chopsticks[(i +1)%count], sema: sema, } go philosophers[i].dine() } ...... }

You can run this program , See if the program will be hang live .

Solution 2 ： Parity resources

We number every philosopher , from 1 To 5, If we stipulate that philosophers with odd numbers first take the chopsticks on their left , Then take the chopsticks at your right hand , Philosophers with even numbers first take the chopsticks at their right hand , Then take the chopsticks on the left , Release chopsticks in reverse order , This can also avoid circular dependency .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

// Endless meals and meditation . // Eat and sleep ( meditation 、 Sit in meditation ), Eat after sleeping . // You can adjust the time of eating and sleeping to increase or reduce the chance of grabbing forks . func (p *Philosopher) dine() { for { mark(p, " meditation ") randomPause (10) mark(p, " I'm hungry ") if p.ID %2 == 1 { // Odd number p.leftChopstick.Lock() // First try to pick up the chopsticks on your left mark(p, " Pick up the left chopsticks ") p.rightChopstick.Lock() // Try picking up the chopsticks on your right mark(p, " Eat ") randomPause (10) p.rightChopstick.Unlock() // First try to put down the chopsticks on your right p.leftChopstick.Unlock() // Then try to pick up the chopsticks on your left } else { p.rightChopstick.Lock() // First try to pick up the chopsticks on your left mark(p, " Pick up your right chopsticks ") p.leftChopstick.Lock() // Try picking up the chopsticks on your right mark(p, " Eat ") randomPause (10) p.leftChopstick.Unlock() // First try to put down the chopsticks on your right p.rightChopstick.Unlock() // Then try to pick up the chopsticks on your left } } } func main() { ...... // Create philosophers , Give them the forks at their left and right hands , Lead them to the round table . philosophers := make([]*Philosopher, count) for i := 0; i < count; i++ { philosophers[i] = &Philosopher{ ID: i + 1, name: names[i], leftChopstick: chopsticks[i], rightChopstick: chopsticks[(i +1)%count], } go philosophers[i].dine() } ...... }

Run this program , You will also find that the program can run smoothly , There will be no deadlock .

Solution 3 ： Resource classification

Another simple solution is for resources （ Here are chopsticks ） Assign a partial order or hierarchical relationship , And agree that all resources are obtained in this order , Release in reverse order , And it is guaranteed that there will not be two unrelated resources needed by the same work at the same time . In the dining problem of philosophers , Chopsticks are numbered 1 to 5, Every unit of work （ philosopher ） Always pick up the chopsticks with lower numbers on the left and right first , Take the one with higher number . After using chopsticks , He always puts down the chopsticks with higher number first , Then put down the lower number . under these circumstances , When the four philosophers picked up the lower numbered chopsticks at the same time , Only the highest numbered chopsticks remain on the table , So the fifth philosopher can't use any chopsticks . and , Only one philosopher can use the highest numbered chopsticks , So he can eat with two chopsticks . When he finished eating , He will put down the chopsticks with the highest number first , Then put down the chopsticks with lower number , So that another philosopher picked up the one behind and began to eat .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

// Endless meals and meditation . // Eat and sleep ( meditation 、 Sit in meditation ), Eat after sleeping . // You can adjust the time of eating and sleeping to increase or reduce the chance of grabbing forks . func (p *Philosopher) dine() { for { mark(p, " meditation ") randomPause (10) mark(p, " I'm hungry ") if p.ID == 5 { // p.rightChopstick.Lock() // Try to pick up the first 1 Chopsticks mark(p, " Pick up the left chopsticks ") p.leftChopstick.Lock() // Try again to pick up the 5 Chopsticks mark(p, " Eat ") randomPause (10) p.leftChopstick.Unlock() // Try to put down the first 5 Only chopsticks p.rightChopstick.Unlock() // Try to put down the first 1 Only chopsticks } else { p.leftChopstick.Lock() // First try to pick up the chopsticks on your left ( The first n only ) mark(p, " Pick up your right chopsticks ") p.rightChopstick.Lock() // Try picking up the chopsticks on your right ( The first n+1 only ) mark(p, " Eat ") randomPause (10) p.rightChopstick.Unlock() // First try to put down the chopsticks on your right p.leftChopstick.Unlock() // Then try to pick up the chopsticks on your left } } }

Method four ： Introduce waiters

If we introduce a waiter , For example, Han Feizi , Han Feizi is responsible for distributing chopsticks , In this way, we can regard holding left-hand chopsticks and right-hand chopsticks as an atomic operation , Or get chopsticks , Or wait , The second condition of deadlock can be broken ( Hold and wait ).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

type Philosopher struct { // The name of the philosopher name string // One left hand and one right hand chopsticks leftChopstick, rightChopstick *Chopstick status string mu *sync.Mutex } // Endless meals and meditation . // Eat and sleep ( meditation 、 Sit in meditation ), Eat after sleeping . // You can adjust the time of eating and sleeping to increase or reduce the chance of grabbing forks . func (p *Philosopher) dine() { for { mark(p, " meditation ") randomPause (10) mark(p, " I'm hungry ") p.mu.Lock() // Waiter control p.leftChopstick.Lock() // First try to pick up the chopsticks on your left mark(p, " Pick up the left chopsticks ") p.rightChopstick.Lock() // Try picking up the chopsticks on your right p.mu.Unlock() mark(p, " Eat ") randomPause (10) p.rightChopstick.Unlock() // First try to put down the chopsticks on your right p.leftChopstick.Unlock() // Then try to pick up the chopsticks on your left } }

The complete code can be referred to [dive-to-gosync-workshop(https://github.com/smallnest/dive-to-gosync-workshop/tree/master/11.classical_problems)

In the next article, we will talk about another classic concurrency problem ： The formation of hydrogen monoxide .