体はドクペで出来ている

インフラ、Goの割合が多い技術ブログ

Golangでデッドロックを発生させる

はじめに

最近Go言語による並行処理を使ってお勉強を始めたので学んだことを自分なりの言葉にしてアウトプットしようと思います。

デッドロックを平易に説明する

ものすごく雑に表現すればプログラムにおいて発生する「お見合い状態」のことです。

プログラムの処理単位(プロセス、スレッド、goroutine等)が複数動作している場合、お互いがお互いの終了を待とうとして結果的に永久に処理が進まない状態に陥ってしまうことがあり、これをデッドロックといいます。

デッドロックを起こすサンプルコード

以下のコードを実行すると fatal error: all goroutines are asleep - deadlock! というメッセージと共に異常終了します。

これは全てのgoroutineが待機状態に入ったことでGolangランタイムがデッドロックが発生したと見做した状態です。

https://play.golang.org/p/1Ln7q3P1JPI

deadlock.go

package main

import (
    "sync"
    "time"
)

var (
    muA sync.Mutex
    muB sync.Mutex
)

func main() {
    var wg sync.WaitGroup
    wg.Add(2)
    go doSomething(&muA, &muB, &wg)
    go doSomething(&muB, &muA, &wg)
    wg.Wait()
}

func doSomething(m1, m2 *sync.Mutex, wg *sync.WaitGroup) {
    defer wg.Done()

    m1.Lock()                   // ①
    defer m1.Unlock()           // ②
    time.Sleep(1 * time.Second) // ③

    m2.Lock() // ④
    defer m2.Unlock()
    time.Sleep(1 * time.Second)
}

用語説明

動作の解説

doSomethingは2つのミューテックスと並行処理の待ち合わせを行うためのWaitGroupを引数で受け取ります。処理を開始するとまず1つ目のミューテックスにロックをかけ他のgoroutineがアクセスできないようにします(①)。次に解放を忘れないよう defer でアンロックを予約した上で(②)1秒待機し(③ 何らかの処理待ちを模したものと考えて下さい)更に2つ目のミューテックスでも同じことをします(④)。

ここまで順番に読んでいくと何ら問題は無いように思えます。実際doSomethingを1つだけ実行するとプログラムは正しく終了します。が、上記のコードのように並行且つ2つのミューテックスに対し相互にロックがかかるようdoSomethingを動作させるとデッドロックが発生します。

なぜそうなるのか、視点を変えて流れを追ってみましょう。まず①の時点で1つ目のdoSomethingはmuAに対しロックをかけます。同様に2つ目のdoSomethingはmuBに対しロックをかけます。次に双方が②でアンロックの予約を行いますが、deferは呼ばれた関数の終了時に発動するためこの時点ではロックが解放されていません。そのまま1秒間待機し(③)2つ目のミューテックスのロックを取りにいきます(④)。が、1つ目のdoSomethingはmuAをロックしたままですし2つ目のdoSomethingはmuBをロックしたままです。そして1つ目のdoSomethingはmuBが解放されるまで動作を止め、2つ目のdoSomethingはmuAが解放されるまで動作を止めます。

かくしてお互いがお互いの処理終了を待つ状態に陥ることでデッドロックが発生します。

どのように回避するか

色々なアプローチがありますが、銀の弾丸はありません。以下のようなやり方が参考になりそうです。

  • ミューテックスを呼ぶ順番を固定する(こういう筋肉による解決は一般に避けるべきでしょう)
  • muA, muBをロックするためのミューテックスを別途用意する(これも筋肉的な上に複雑化するので避けたいところです)
  • クリティカルセクションを最小限にする(パフォーマンスの面でも大事)
  • そもそもロックが必要無いアルゴリズムに置き換える(理想)
    • Golangであれば基本的にはチャネルを使うことが推奨されます

回避法の実装例

今回のケースは単純な事例なのでいずれの方法でも上手く解決できていますが、アルゴリズムの変更を除きあらゆる状況でデッドロックを回避できるものではありません。

順序固定

ミューテックス用ミューテックス

最小クリティカルセクション