哲学者とのディナー

こんばんは。新卒2年目エンジニアの山下です。

今日は「食事する哲学者の問題」を軸にデッドロックが起こる原因や対応策をGolangを用いて考えます。

食事する哲学者の問題

食事する哲学者の問題は、プログラムの排他制御でデッドロックが起きる問題を、より一般的な問題または比喩として捉えたものです。英語では"Dining Philosophers Problem"と呼ばれており、広く知られています。

この問題は1965年に計算機科学者のエドガー・ダイクストラ(Edsger Dijkstra)が学生に向けて「複数のコンピュータがテープドライブに同時にアクセスすると競合が発生する」というテーマの課題を出したことが発端で、その後コンピュータ科学者のトニー・ホアによって現在の「食事する哲学者の問題」に形を変えたようです。

問題の内容

問題の詳細を確認します。

前提

• 円卓に5人の哲学者が座っている
• 哲学者の前には1人1枚の皿があり、パスタが盛られている
• 各皿の間にはフォークが1本ある
• 哲学者はパスタを食べるためにフォークを2本使う
• 哲学者は考えることと食べることを交互に繰り返す
• 哲学者同士が意思の疎通をすることは無い

問題

上述の前提の上で哲学者がパスタを食べ始めることになるのですが、なんの考えもなしに食べ始めるとフォークが空くまで一生考え続ける哲学者で出る可能性があるみたいです。

例えば哲学者の1人が卓に向かって右のフォークを取ると、右隣に座っている哲学者は左のフォークが使えないので右のフォークを取る。さらに右隣の哲学者も左のフォークが使えないので右のフォークを取る。さらに右隣の.....

という具合に、卓に向かって左のフォークを待ち続ける状態、デッドロックが生まれてしまいます。

画像は白矢印1,2,3,4,5の順にフォークとっていく図です。赤矢印の6手目で左のフォークを取ろうとしますが、ロックが永遠に解除されることはありません。

実験

実際にコーディングしないとわかりづらいと思うので、ここからは実際にGolangを使い順を追って実験してみます。

環境

golangはバージョン1.18.9をDockerで動かします。

docker run --rm -v $(pwd):/app -w /app -it golang:1.18.9-alpine sh

race condition確認のために必要であれば

$ apk add gcc musl-dev

テーブルのセット

まずは哲学者の名前を5つ定義します。どうしても5人目が浮かばなかったので私山下が5人目の哲学者としてパスタを食べることにします。

func main() {

    philosopherNames := []string{
        "ソクラテス",
        "プラトン",
        "アリストテレス",
        "ニーチェ",
        "山下🌟",
    }

}

次にフォーク型と哲学者型を定義します。

フォークには何番目のフォークなのかを示すindexと、データの競合をあえて起こすためにconditionというmapを持たせます。

哲学者には名前、卓に向かって左右に1本ずつフォークを持たせます。

type Fork struct {
    index int
    condition map[string]int
}

type Philosopher struct {
    name      string
    leftFork  *Fork
    rightFork *Fork
}

最後にphilosophersのスライスを作る関数を準備しておきます。

n番目の哲学者の右にn番目のフォークが置かれるようにします。フォークのconditionには汚れを持たせておきます。フォークを使うと汚れがつく設定で、プログラムの中で競合を起こすためにあえて使用します。

func SetTable(philosopherNames []string) []*Philosopher {

    philosopherCount := len(philosopherNames)

    var philosophers = make([]*Philosopher, philosopherCount, philosopherCount)
    var philosopher *Philosopher

    // [[F4, P0, F0], [F0, P1, F1], ... [Fn-2, Pn-1, Fn-1]]の形になるようにフォークと哲学者をセットする
    for i, name := range philosopherNames {

        if i == 0 {
            
            philosopher = &Philosopher{
                name:      philosopherNames[0],
                leftFork:  &Fork{index: philosopherCount - 1, condition: map[string]int{"汚れ": 0}},
                rightFork: &Fork{index: 0, condition: map[string]int{"汚れ": 0}},
            }
        } else if i < philosopherCount-1 {

            philosopher = &Philosopher{
                name:      name,
                leftFork:  philosophers[i-1].rightFork,
                rightFork: &Fork{index: i, condition: map[string]int{"汚れ": 0}},
            }
        } else {

            philosopher = &Philosopher{
                name:      name,
                leftFork:  philosophers[i-1].rightFork,
                rightFork: philosophers[0].leftFork,
            }
        }

        philosophers[i] = philosopher
    }

    return philosophers
}

ざっとで良いのでテストも書きましょう

package main

import "testing"

func Test_SetTable(t *testing.T) {

    philosopherNames := [5]string{
        "ソクラテス",
        "プラトン",
        "アリストテレス",
        "ニーチェ",
        "山下🌟",
    }

    philosophers := SetTable([]string{
        "ソクラテス",
        "プラトン",
        "アリストテレス",
        "ニーチェ",
        "山下🌟",
    })

    // 最初のフォークと最後のフォークが同じか
    if philosophers[0].leftFork.index != philosophers[len(philosopherNames)-1].rightFork.index {
        t.Errorf(
            "最初の哲学者の左のフォークのインデックスが%dではなく%dがセットされています",
            len(philosopherNames)-1,
            philosophers[0].leftFork.index,
        )
    }

    for i, philosopher := range philosophers {

        // 哲学者全員がテーブルについているか
        if philosopher.name != philosopherNames[i] {
            t.Errorf("%d番目の哲学者に%sがセットされています", i, philosopher.name)
        }

        // フォークの位置は適切か
        if philosopher.rightFork.index != i {
            t.Errorf("%d番目の哲学者の右のフォークに%dがセットされています", i, philosopher.rightFork.index)
        }
        if i > 0 && philosopher.leftFork != philosophers[i-1].rightFork {
            t.Errorf("哲学者%d番の左のフォークに左隣の哲学者の右のフォークが入っていません", i)
        }
    }
}

$ go test .
ok  	table-set	0.001s

食事を実装する

哲学者とフォークの準備ができたのでディナーを始めます。

まずは1人ずつ順番(直列)に食べます。哲学者たちは卓に向かって右のフォークをとった後に左のフォークを取るようにします。フォークをとるとそのフォークには汚れがたまります。

フォークをとって食事をした後は哲学者なので約1秒間のシンキングタイムです。

func (philosopher *Philosopher) Eat() {

    fmt.Printf("%sが\n\t%d番のフォークを取ります\n", philosopher.name, philosopher.rightFork.index)
    for i := 0; i < 1000; i++ {
        philosopher.rightFork.condition["汚れ"] += 1
    }

    fmt.Printf("%sが\n\t%d番のフォークを取ります\n", philosopher.name, philosopher.leftFork.index)
    for i := 0; i < 1000; i++ {
        philosopher.leftFork.condition["汚れ"] += 1
    }

    fmt.Printf("%sは食事中\n", philosopher.name)
    time.Sleep(1 * time.Second)
    fmt.Printf("%sがフォークをおきます\n", philosopher.name)

  fmt.Printf("%sは考え中\n", philosopher.name)
    time.Sleep(1 * time.Second)
}

func Dine(philosophers []*Philosopher) {

    for _, philosopher := range philosophers {

        philosopher.Eat()
    }
}

func main() {

    philosopherNames := [5]string{
        "ソクラテス",
        "プラトン",
        "アリストテレス",
        "ニーチェ",
        "山下🌟",
    }

    startTime := time.Now()
    Dine(SetTable(philosopherNames[:]))
    fmt.Printf("\n\n全員の食事が終わるまで %vmsかかりました\n", time.Since(startTime).Milliseconds())
}

全員が右のフォーク→左のフォークの順フォークをとり、食事ができています。

$ go run .
ソクラテスが
    0番のフォークを取ります
ソクラテスが
    4番のフォークを取ります
ソクラテスは食事中
ソクラテスがフォークをおきます
ソクラテスは考え中
プラトンが
    1番のフォークを取ります
プラトンが
    0番のフォークを取ります
プラトンは食事中
プラトンがフォークをおきます
プラトンは考え中
アリストテレスが
    2番のフォークを取ります
アリストテレスが
    1番のフォークを取ります
アリストテレスは食事中
アリストテレスがフォークをおきます
アリストテレスは考え中
ニーチェが
    3番のフォークを取ります
ニーチェが
    2番のフォークを取ります
ニーチェは食事中
ニーチェがフォークをおきます
ニーチェは考え中
山下🌟が
    4番のフォークを取ります
山下🌟が
    3番のフォークを取ります
山下🌟は食事中
山下🌟がフォークをおきます
山下🌟は考え中


全員の食事が終わるまで 10041msかかりました

哲学者は食事に約1秒、考えることに約1秒使うので、汚れの処理も合わせると合計で約10秒かかっています。これをgoroutineを使って一度に複数人で同時に食事をするようにします。

とりあえずEatに「go」をつけてみます。

func Dine(philosophers []*Philosopher) {

    for _, philosopher := range philosophers {

    // goroutineで同時に食事させる
        go philosopher.Eat()
    }
}

$ go run .


全員の食事が終わるまで 0msかかりました

....waitGroupで待ちましょう。

func (philosopher *Philosopher) Eat(wg *sync.WaitGroup) {

    defer wg.Done()
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

func Dine(philosophers []*Philosopher) {

    wg := &sync.WaitGroup{}

    for _, philosopher := range philosophers {

        wg.Add(1)
        go philosopher.Eat(wg)
    }

    wg.Wait()
}

再度実行してみるとエラーなく2秒弱で終わりました。

よくみてみると1つのフォークが複数人から同時に使用されています....

$ go run .
山下🌟が
    4番のフォークを取ります
プラトンが
    1番のフォークを取ります
山下🌟が
    3番のフォークを取ります
プラトンが
    0番のフォークを取ります
山下🌟は食事中
アリストテレスが
    2番のフォークを取ります
アリストテレスが
    1番のフォークを取ります
アリストテレスは食事中
ニーチェが
    3番のフォークを取ります
プラトンは食事中
ニーチェが
    2番のフォークを取ります
ソクラテスが
    0番のフォークを取ります
ソクラテスが
    4番のフォークを取ります
ソクラテスは食事中
ニーチェは食事中
山下🌟がフォークをおきます
山下🌟は考え中
ソクラテスがフォークをおきます
アリストテレスがフォークをおきます
アリストテレスは考え中
ソクラテスは考え中
プラトンがフォークをおきます
プラトンは考え中
ニーチェがフォークをおきます
ニーチェは考え中


全員の食事が終わるまで 2007msかかりました

もう一度実行してみます。すると今度は「concurrent map writes」と怒られてしまいます。

golnagではgoroutineから同時に1つのmapにアクセスする事を禁止しています。今回の例では「philosopher.rightFork.condition["汚れ"] += 1」の部分でエラーが発生しています。

$ go run .
山下🌟が
    4番のフォークを取ります
ソクラテスが
    0番のフォークを取ります
山下🌟が
    3番のフォークを取ります
ソクラテスが
    4番のフォークを取ります
山下🌟は食事中
ソクラテスは食事中
ニーチェが
    3番のフォークを取ります
ニーチェが
    2番のフォークを取ります
アリストテレスが
    2番のフォークを取ります
fatal error: concurrent map writes

同時にアクセスする問題を解決するために、フォークをロックしてしまいます。ロックにはsync.Mutextを使用します。

フォークを取る際にLock()でロックし、食事が終わってフォークを置く際にはUnlock()でロックを解除します。これで同時にフォークが使用される問題とmapへのアクセスで発生するエラーもなくなるはずです。

type Fork struct {
    sync.Mutex
    index     int
    condition map[string]int
}

func (philosopher *Philosopher) Eat(wg *sync.WaitGroup) {

    defer wg.Done()

    philosopher.rightFork.Lock() //既にロックされている場合はロックが解除されるまで待ちます
    fmt.Printf("%sが\n\t%d番のフォークを取ります\n", philosopher.name, philosopher.rightFork.index)
    for i := 0; i < 1000; i++ {
        philosopher.rightFork.condition["汚れ"] += 1
    }

    philosopher.leftFork.Lock()
    fmt.Printf("%sが\n\t%d番のフォークを取ります\n", philosopher.name, philosopher.leftFork.index)
    for i := 0; i < 1000; i++ {
        philosopher.leftFork.condition["汚れ"] += 1
    }

    fmt.Printf("%sは食事中\n", philosopher.name)
    time.Sleep(1 * time.Second)
    fmt.Printf("%sがフォークをおきます\n", philosopher.name)
    philosopher.rightFork.Unlock()
    philosopher.leftFork.Unlock()

    fmt.Printf("%sは考え中\n", philosopher.name)
    time.Sleep(1 * time.Second)
}

問題なく実行できました。

$ go run .
山下🌟が
    4番のフォークを取ります
山下🌟が
    3番のフォークを取ります
山下🌟は食事中
プラトンが
    1番のフォークを取ります
ソクラテスが
    0番のフォークを取ります
アリストテレスが
    2番のフォークを取ります
山下🌟がフォークをおきます
山下🌟は考え中
ニーチェが
    3番のフォークを取ります
ソクラテスが
    4番のフォークを取ります
ソクラテスは食事中
ソクラテスがフォークをおきます
ソクラテスは考え中
プラトンが
    0番のフォークを取ります
プラトンは食事中
プラトンがフォークをおきます
プラトンは考え中
アリストテレスが
    1番のフォークを取ります
アリストテレスは食事中
アリストテレスがフォークをおきます
アリストテレスは考え中
ニーチェが
    2番のフォークを取ります
ニーチェは食事中
ニーチェがフォークをおきます
ニーチェは考え中


全員の食事が終わるまで 6018msかかりました

ところが何度か実行していると「all goroutines are asleep - deadlock!」と表示され、エラーが発生しました。デッドロックが起きているようです。

テーブルにある全てのフォークを各哲学者が持ってしまっているので、誰もパスタを食べることができない状況です...今回は右のフォーク→左のフォークの順で手にとるようにしているので、今は全員の右手にフォークがある状態ですね。記事の冒頭で挙げたデッドロックの例と同じです。

$ go run .
山下🌟が
    4番のフォークを取ります
プラトンが
    1番のフォークを取ります
アリストテレスが
    2番のフォークを取ります
ニーチェが
    3番のフォークを取ります
ソクラテスが
    0番のフォークを取ります
fatal error: all goroutines are asleep - deadlock!

解決策

デッドロックが起きるには全員がフォークを1本持つ状況が必要です。それを回避するため、フォークを取るときは常に若い番号のフォークを取るように修正します。

哲学者がフォークを取るときに、常に若い番号のフォークを取るようにすれば、ロック解除待ちになったとしても、必ずいずれ解除されるロックを待つことになります。

数字と矢印だらけで分かりづらいですが、P0から番号の若い番号のフォークを取るようにした場合の絵です。P1がF0を取ろうとしますが、既にP0が取っているので使い終わるまで待ちます。P0はF0をとった後にF4を取るので食事が終わればF0とF4は空き状態になるので、P1がF0を取ることができます。P1はF0を取ったのでF1を取ろうとしますが、既にP2がF1を持っています。しかしP4がF4を取ってF3が空き、P3がF3を取ってP2が空き、P2がF2を取ってF1が空きます。最後にP1がF0を取れば全員が食事を終えられます。

P0→P1→P2→P3→P4の順でフォークを取るとは限らないのでは? と思うかもしれません。その通りです。実際コンソールを見ると

山下🌟が
    4番のフォークを取ります
プラトンが
    1番のフォークを取ります
アリストテレスが
    2番のフォークを取ります
ニーチェが
    3番のフォークを取ります
ソクラテスが

と表示されています。Pと添字を使うと「P4→P1→P2→P3→P0」の順です。この場合も若い番号のフォークを取ればデッドロックは起きません。

1. 　P4がF3を取る
2. 　P1がF0を取る
3. 　P2がF1を取る
4. 　P3がF2を取る
5. 　P0がF0を取ろうとするがP1が持っているので待つ
6. 　P4がF4を取る→F4F3が空く
7. 　P3がF3を取る→F2が空く
8. 　P2がF2を取る→F1が空く
9. 　P1がF1を取る→F0が空く
10. 　P0がF1を取る

説明はこれくらいにして実際に試してみましょう。

func (philosopher *Philosopher) Eat(wg *sync.WaitGroup) {

    defer wg.Done()

    if philosopher.leftFork.index > philosopher.rightFork.index {

        // 左のフォーク > 右のフォークの場合は右のフォークから取る
        philosopher.rightFork.Lock()
        fmt.Printf("%sが\n\t%d番のフォークを取ります\n", philosopher.name, philosopher.rightFork.index)
        for i := 0; i < 10000; i++ {
            philosopher.rightFork.condition["汚れ"] += 1
        }

        philosopher.leftFork.Lock()
        fmt.Printf("%sが\n\t%d番のフォークを取ります\n", philosopher.name, philosopher.leftFork.index)
        for i := 0; i < 10000; i++ {
            philosopher.leftFork.condition["汚れ"] += 1
        }
    } else {
        // 左のフォーク <= 右のフォークの場合は左のフォークから取る

        philosopher.leftFork.Lock()
        fmt.Printf("%sが\n\t%d番のフォークを取ります\n", philosopher.name, philosopher.leftFork.index)
        for i := 0; i < 10000; i++ {
            philosopher.leftFork.condition["汚れ"] += 1
        }

        philosopher.rightFork.Lock()
        fmt.Printf("%sが\n\t%d番のフォークを取ります\n", philosopher.name, philosopher.rightFork.index)
        for i := 0; i < 10000; i++ {
            philosopher.rightFork.condition["汚れ"] += 1
        }
    }

    fmt.Printf("%sは食事中\n", philosopher.name)
    time.Sleep(1 * time.Second)
    fmt.Printf("%sがフォークをおきます\n", philosopher.name)
    philosopher.rightFork.Unlock()
    philosopher.leftFork.Unlock()

    fmt.Printf("%sは考え中\n", philosopher.name)
    time.Sleep(1 * time.Second)
}

実行します。

$ go run .
山下🌟が
    3番のフォークを取ります
山下🌟が
    4番のフォークを取ります
プラトンが
    0番のフォークを取ります
アリストテレスが
    1番のフォークを取ります
山下🌟は食事中
ニーチェが
    2番のフォークを取ります
山下🌟がフォークをおきます
山下🌟は考え中
ニーチェが
    3番のフォークを取ります
ニーチェは食事中
ニーチェがフォークをおきます
アリストテレスが
    2番のフォークを取ります
ニーチェは考え中
アリストテレスは食事中
アリストテレスがフォークをおきます
アリストテレスは考え中
プラトンが
    1番のフォークを取ります
プラトンは食事中
プラトンがフォークをおきます
プラトンは考え中
ソクラテスが
    0番のフォークを取ります
ソクラテスが
    4番のフォークを取ります
ソクラテスは食事中
ソクラテスがフォークをおきます
ソクラテスは考え中


全員の食事が終わるまで 6022msかかりました

何度実行してもデッドロックの可能性がなくなったのかどうかは結果からは分かりませんが、きっとロジックは問題ないはずです。

今回は全員が食事を1回して終わりにしていますが、これを2、3回と増やしても問題ないです。常にP0のような「逆のフォークを先に取る」人が1人いればデッドロックは起きません。

最後にテストを書いて終わります。

func Test_Eat(t *testing.T) {

    wg := &sync.WaitGroup{}

    philosopher := &Philosopher{
        name:      "山下",
        leftFork:  &Fork{index: 0, condition: map[string]int{"汚れ": 0}},
        rightFork: &Fork{index: 1, condition: map[string]int{"汚れ": 0}},
    }

    wg.Add(1)
    philosopher.Eat(wg)
    wg.Wait()

    if philosopher.leftFork.condition["汚れ"] != 10000 {
        t.Errorf("汚れに期待されていない「%d」がたまっています", philosopher.leftFork.condition["汚れ"])
    }
    if philosopher.rightFork.condition["汚れ"] != 10000 {
        t.Errorf("汚れに期待されていない「%d」がたまっています", philosopher.rightFork.condition["汚れ"])
    }
}

func Test_Dine(t *testing.T) {

    philosophers := SetTable([]string{
        "ソクラテス",
        "プラトン",
        "アリストテレス",
        "ニーチェ",
        "山下🌟",
    })

    Dine(philosophers)

    for _, philosopher := range philosophers {

        if philosopher.leftFork.condition["汚れ"] != 20000 {
            t.Errorf(
                "%d番目のフォークの汚れに期待されていない「%d」がたまっています",
                philosopher.leftFork.index,
                philosopher.leftFork.condition["汚れ"],
            )
        }
        if philosopher.rightFork.condition["汚れ"] != 20000 {
            t.Errorf(
                "%d番目のフォークの汚れに期待されていない「%d」がたまっています",
                philosopher.rightFork.index,
                philosopher.rightFork.condition["汚れ"],
            )
        }
    }
}