經典併發問題
使用 Golang 解決經典併發問題
造成死鎖的條件
- 禁止搶佔(No Preemption): 系統資源不能被強制從thread中移出,如果系統資源不是主動release而是被preempt則會發生不可預期事件
- 持有和等待(Hold and Wait): 一個thread在等待時持有concurrency resource,持有concurrency resource的thread還在等待其他resource
- 互斥(Mutual Exclusion): 資源在同一時刻只能被分配到一個thread,無法實現多thread共享並且resource具有排他性
- 循環等待(Circular Waiting): 一系列thread相互持有其他thread所需的resource,thread之間必須有一個循環依賴關係
- 上述四個條件同時滿足才會發生死鎖,只要破壞掉其中一個就可以avoid deadlock
哲學家就餐問題
- 定義筷子和哲學家
- 筷子是併發資源,具有排他性,因此具備鎖實現互斥並且禁止搶佔(不持有這根筷子的哲學家不能unlock)
- 每位哲學家都需要左手邊的筷子和右手邊的筷子
- status代表哲學家的狀態(冥想,餓了,吃飯)
- 還有另一種狀態就是持有一根筷子並請求另一根
問題描述
package main
import (
"fmt"
"math/rand"
"sync"
"time"
)
type Chopstick struct {
sync.Mutex
}
type Philosopher struct {
name string
leftChopstick *Chopstick
rightChopstick *Chopstick
status string
}
func (p *Philosopher) dine() {
for {
mark(p, "冥想")
randomPause(10)
mark(p, "餓了")
p.leftChopstick.Lock()
mark(p, "拿左邊快子")
randomPause(100)
p.rightChopstick.Lock()
mark(p, "吃飯")
randomPause(10)
p.rightChopstick.Unlock()
p.leftChopstick.Unlock()
}
}
func randomPause(max int) {
time.Sleep(time.Duration(rand.Intn(max)) * time.Millisecond)
}
func mark(p *Philosopher, action string) {
fmt.Printf("%s start %s\n", p.name, action)
p.status = fmt.Sprintf("%s start%s", p.status, action)
}
func main() {
count := 5
chopstick := make([]*Chopstick, count)
for i := 0; i < count; i++ {
chopstick[i] = new(Chopstick)
}
names := []string{"哲學家1", "哲學家2", "哲學家3", "哲學家4", "哲學家5"}
philosophers := make([]*Philosopher, count)
for i := 0; i < count; i++ {
philosophers[i] = &Philosopher{
name: names[i],
leftChopstick: chopstick[i],
rightChopstick: chopstick[(i+1)%count],
}
go philosophers[i].dine()
}
select {}
}
解決方式1
- 限制就餐人數
- 從發生死鎖的條件中發現
if i >= 1 {
go philosophers[i-1].dine()
}
解決方式2
- 使用奇偶性解決
func (p *Philosopher) dine() {
for {
mark(p, "冥想")
randomPause(10)
mark(p, "餓了")
if p.id%2 == 0 {
p.leftChopstick.Lock()
mark(p, "拿左邊快子")
p.rightChopstick.Lock()
mark(p, "吃飯")
randomPause(10)
p.rightChopstick.Unlock()
p.leftChopstick.Unlock()
} else {
p.rightChopstick.Lock()
mark(p, "拿右邊快子")
p.leftChopstick.Lock()
mark(p, "吃飯")
randomPause(10)
p.leftChopstick.Unlock()
p.rightChopstick.Unlock()
}
}
}
解決方式3
- 資源分級
func (p *Philosopher) dine() {
for {
mark(p, "冥想")
randomPause(10)
mark(p, "餓了")
if p.id == 5 {
p.rightChopstick.Lock()
mark(p, "拿起右邊的筷子")
p.leftChopstick.Lock()
mark(p, "吃飯")
randomPause(10)
p.leftChopstick.Unlock()
p.rightChopstick.Unlock()
} else {
p.leftChopstick.Lock()
mark(p, "拿起左邊的筷子")
p.rightChopstick.Lock()
mark(p, "吃飯")
randomPause(10)
p.rightChopstick.Unlock()
p.leftChopstick.Unlock()
}
}
}
解決方法4
- 引入服務生
func (p *Philosopher) dine() {
for {
mark(p, "冥想")
randomPause(10)
mark(p, "餓了")
p.mu.Lock()
p.leftChopstick.Lock()
mark(p, "拿起左邊的筷子")
p.rightChopstick.Lock()
p.mu.Unlock()
mark(p, "吃飯")
randomPause(10)
p.rightChopstick.Unlock()
p.leftChopstick.Unlock()
}
}