死鎖

定義

死鎖指的是所有的並發協程彼從等待的程式，當死鎖產生時，除非外界的干預，否則程式將永遠無法恢復運行。

解決方案

要先了解deadlock只會發生在下列三種情況都成立的時候:

• 具有多個shared resource，例如上述的spoon以及fork。
• 執行緒鎖定一個shared resource時，還沒解除鎖定就想去鎖定另外一個shared resource。
• 取得shared resource的順序不固定，例如先拿spoon再拿fork以及先拿fork再拿spoon。

因此我們反向思考，只要能打破死鎖的其中一個條件，就能避免deadlock。

Go語言的Deadlock

直接讀取空 Channel

package main

import (
  "fmt"
)

func main() {
  ch := make(chan int, 3)
  <-ch
}

輸出結果：

fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan receive]:
main.main()
  /home/work/code/golang/src/interview/go/deadlock/test.go:9 +0x56

Process finished with exit code 2

解決方式

使用select case default ，給定阻塞時的預設處理方式

package main

import (
  "fmt"
)

func main() {
  ch := make(chan int, 3)

  select {
  case v := <-ch:
    fmt.Println(v)
  default:
    fmt.Println("chan no data")
  }
}

阻塞 Channel

package main

import "fmt"

func main() {
  ch := make(chan int)

  ch <- 1 // 無緩衝的 Channel，寫入 Channel 卻沒有相應的讀取 Channel 之動作 

  fmt.Println(<-ch)
}

輸出結果

fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan send]:
main.main()
  /home/work/code/golang/src/interview/go/deadlock/test02.go:8 +0x59

Process finished with exit code 2

解決方式

1. 採用子協程，保證讀寫 Channel 有成對的相應動作存在。

package main

import "fmt"

func main() {
  ch := make(chan int)

  go func() {
    ch <- 1 // 開啟子協程寫入資料
  }()

  fmt.Println(<-ch) // 阻塞到ch有資料為止

}
2. 採用有緩存的 Channel

package main

import "fmt"

func main() {
  ch := make(chan int, 1)

  ch <- 1

  fmt.Println(<-ch)
}

超過 Channel 緩存容量

package main

import (
  "fmt"
)

func main() {
  ch := make(chan int, 3)
  ch <- 1
  ch <- 2
  ch <- 3
  ch <- 4 //超過緩存容量，阻塞main函數，產生deadlock

  for v := range ch {
    fmt.Println(v)
  }
}

解決方式

1. 增加緩存容量，保證能滿足寫入所有資料；
2. 採用 select case default 阻塞預設處理方式

for range 產生死鎖

package main

import (
  "fmt"
)

func main() {
  ch := make(chan int, 3)

  ch <- 1
  ch <- 2
  ch <- 3

  // range 一直讀取直到chan關閉，否則產生阻塞死鎖
  for v := range ch {
    fmt.Println(v)
  }
}

輸出結果

1
2
3
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan receive]:
main.main()
  /home/work/code/golang/src/interview/go/deadlock/test04.go:15 +0x115

Process finished with exit code 2

解決方式

1. 顯式關閉 channel
2. 開啟子協程，主協程 sleep 等待時間後退出；

package main

import (
  "fmt"
  "time"
)

func main() {
  ch := make(chan int, 3)

  ch <- 1
  ch <- 2
  ch <- 3

  close(ch) // 解決方式1：關閉chan

  // range 一直讀取直到chan關閉，否則產生阻塞死鎖
  // 解決方式2：開啟子協程，主協程sleep等待
  go func() {
    for v := range ch {
      fmt.Println(v)
    }
  }()

  time.Sleep(1e9)
}

活鎖 - 哲學家就餐問題

起源

在1971年，著名的電腦科學家艾茲格·迪科斯徹提出了一個同步問題，即假設有五台電腦都試圖存取五份共用的磁帶驅動器。稍後，這個問題被托尼·霍爾重新表述為哲學家就餐問題。這個問題可以用來解釋死結和資源耗盡。

問題描述

這個問題說的是五個哲學家坐在一張圓桌上，每個人有五碗意大利面，每個碗之間有一把叉子(即圓桌上總共有五把叉子)。每個哲學家都需要左右叉來吃這碗意大利面，但他們的狀態只能是思考或用餐其中之一，思考時就不能用餐，用餐時就不能思考。當哲學家吃完之後，他才能放下叉子，這樣其他哲學家就可以拿起叉子了。

在這裏，每個哲學家都可以被看作是一個協程，而叉子則是每個協程完成任務所需的資源。最大的挑戰是避免協程之間的死鎖。如果每個哲學家都擁有一個叉子，那麽哲學家們就沒有其他的叉子可以選擇和完成他們的任務了。

如果我們讓哲學家在等待超過一定時間後就先放下手上的叉子，是否可以解決這個用餐問題呢？很顯然不行，因為我們會出現另一個可能的情境-哲學家們同時舉起叉子等待超過一段時間後放下，並且重複以上無止境的循環。

解法

服務生解法

一個簡單的解法是引入一個餐廳服務生，哲學家必須經過他的允許才能拿起餐叉。因為服務生知道哪只餐叉正在使用，所以他能夠作出判斷避免死結。

為了演示這種解法，假設哲學家依次標號為A至E。如果A和C在吃東西，則有四隻餐叉在使用中。B坐在A和C之間，所以兩隻餐叉都無法使用，而D和E之間有一隻空餘的餐叉。假設這時D想要吃東西。如果他拿起了第五隻餐叉，就有可能發生死結。相反，如果他徵求服務生同意，服務生會讓他等待。這樣，我們就能保證下次當兩把餐叉空餘出來時，一定有一位哲學家可以成功的得到一對餐叉，從而避免了死結。

資源分級解法

另一個簡單的解法是為資源（這裡是餐叉）分配一個偏序或者分級的關係，並約定所有資源都按照這種順序取得，按相反順序釋放，而且保證不會有兩個無關資源同時被同一項工作所需要。在哲學家就餐問題中，資源（餐叉）按照某種規則編號為1至5，每一個工作單元（哲學家）總是先拿起左右兩邊編號較低的餐叉，再拿編號較高的。用完餐叉後，他總是先放下編號較高的餐叉，再放下編號較低的。在這種情況下，當四位哲學家同時拿起他們手邊編號較低的餐叉時，只有編號最高的餐叉留在桌上，從而第五位哲學家就不能使用任何一隻餐叉了。而且，只有一位哲學家能使用最高編號的餐叉，所以他能使用兩隻餐叉用餐。當他吃完後，他會先放下編號最高的餐叉，再放下編號較低的餐叉，從而讓另一位哲學家拿起後邊的這隻開始吃東西。

儘管資源分級能避免死結，但這種策略並不總是實用的，特別是當所需資源的列表並不是事先知道的時候。例如，假設一個工作單元拿著資源3和5，並決定需要資源2，則必須先要釋放5，之後釋放3，才能得到2，之後必須重新按順序取得3和5。對需要存取大量資料庫記錄的電腦程式來說，如果需要先釋放高編號的記錄才能存取新的記錄，那麼執行效率就不會高，因此這種方法在這裡並不實用。

Chandy/Misra解法

1984年，K. Mani Chandy和J. Misra提出了哲學家就餐問題的另一個解法，允許任意的用戶（編號P1, ..., Pn）爭用任意數量的資源。與資源分級解法不同的是，這裡編號可以是任意的。

• 把餐叉湊成對，讓要吃的人先吃，沒餐叉的人得到一張換餐叉券。
• 餓了，把換餐叉券交給有餐叉的人，有餐叉的人吃飽了會把餐叉交給有券的人。有了券的人不會再得到第二張券。
• 保證有餐叉的都有得吃。
  這個解法允許很大的並列性，適用於任意大的問題。

服務生解法

將每個哲學家編號0,1,2,3,4，因此我們得到集合 P ={0,1,2,3,4}，將叉子也編號成0到4，因此叉子F={0,1,2,3,4}，當哲學家P[0]要用餐時，他會需要右手邊的叉子F[0]，和左手邊的叉子F[1]。也就是說哲家學P[i]用餐時會需要叉子F[i]和F[(i+1)%5]

我們定義三個函數如下

服務生

定義了服務生的基本動作，確認叉子是否空閒，並且遞給需要用餐的哲學家。

func waiter_task(pick bool, pid int) bool {
       var i, j = pid, (pid+1)%5
       var has_value int = 1
       if pick {
              has_value = 0
       }
       if fork[i]==has_value && fork[j]==has_value {
              fork[i] = (has_value+1)%2
              fork[j] = (has_value+1)%2
              return true
       }
       return false
}

動作

動作函數定義了哲學家的基本動作，拿起/放下叉子。

func Action(pick bool, pid int) {
       for true {
              // Global var: waiter -> sync.Mutex
              waiter.Lock()
              if waiter_task(pick, pid) {
                     waiter.Unlock()
                     break
              }
              waiter.Unlock()
       }
}

哲學家

定義了哲學家所有的動作

• 如果左右叉都可使用，同時舉起左右手的叉子
  -吃義大利麵，放下左右手的叉子。

func Philosopher(id int) {
       Action(true, id)
       fmt.Println("Philosopher ", id, "pick up the forks, ate and dropped them.")
       Action(false, id)
       exit++
}

服務生解法

package main
import (
       "fmt"
       "sync"
)
var fork [5]int
var waiter sync.Mutex
var exit int
/*
 Method implements the waiter's tasks, 
 Either to pick up the fork
 Or to drop them.
*/
func waiter_task(pick bool, pid int) bool {
       var i, j = pid, (pid+1)%5
       var has_value int = 1
       if pick {
              has_value = 0
       }
       if fork[i]==has_value && fork[j]==has_value {
              fork[i] = (has_value+1)%2
              fork[j] = (has_value+1)%2
              return true
       }
       return false
}
/*
 Method implements the actions to be
 Performed by the waiter.
*/
func Action(pick bool, pid int) {
       for true {
              waiter.Lock()
              if waiter_task(pick, pid) {
                     waiter.Unlock()
                     break
              }
              waiter.Unlock()
       }
}
/*
 Method implements the actions
 Of the philosopher.
*/
func Philosopher(id int) {
       Action(true, id)
       fmt.Println("Philosopher ", id, "pick up the forks, ate and dropped them.")
       Action(false, id)
       exit++
}
// Main
func main(){
       exit = 0
       fmt.Println("Dining Philosophers Problem - Arbitrator Solution")
       // Running five threads and supplying the IDs
       for i:=0; i<5; i++ { go Philosopher(i) }
       for exit!=5 { /* wait for threads to get over */ }
}
One another solution involves logically ordering the actions of the philosophers such that no deadlock occurs. Here, the even philosophers will pick up the right fork first, and the odd philosophers will pick up left fork first. That means:

Algorithm
for Pi in Philosopher's Set:
    if Pi is even Philosopher, then:
        Pick up rigth fork
    else:
        Pick up left fork

哲學家用餐問題解法

package main
import (
    "fmt"
    "sync"
    "time"
)
var fork [5]sync.Mutex
var exit int
func phil(id int) {
    for i := 0; i < 2; i++ {
        if (id+i)%2 == 0 {
            fork[id].Lock()
            fmt.Println("P[", id, "] picked up Right Fork")
            time.Sleep(time.Duration(1) * time.Second)
        } else {
            fork[(id+1)%5].Lock()
            fmt.Println("P[", id, "] picked up Left Fork")
            time.Sleep(time.Duration(1) * time.Second)
        }
    }
    fork[id].Unlock()
    fork[(id+1)%5].Unlock()
    fmt.Println("P[", id, "] ate and dropped the forks")
    exit++
}
func main() {
    fmt.Println("Dining Philosophers Problem")
    for i := 0; i < 5; i++ {
        go phil(i)
    }
    for exit != 5 { /* loop wait till all threads are over */
    }
}