Goではgoroutineと呼ばれるGoで管理された軽量なスレッドを使って、並行処理を書くことができます。

手軽に並行処理を書けるところがGoの魅力の一つだと思いますが、並行処理ならではの問題が発生することがあります。

今回は起こりやすい問題の一つである「デッドロック」で遊んでみたいと思います。

デッドロックとは

Wikipediaの説明によると下記のとおりです。

互いにロックを取り合って動かなくなる状態ですね。

余談ですがデッドロックと聞くと、映画の人質とブツの交換シーンを思い出します。 悪役は先にブツを出せと要求し人質を開放しませんが、主人公は人質が先だといってブツをだしません。 完全に膠着状態であります。

こんな説明より、コードを見たほうが理解がはやいと思いますのでコードに登場していただきましょう。

package main

import (
	"sync"
	"time"
)

func main() {
	var (
		wg  sync.WaitGroup
		mu1 sync.Mutex
		mu2 sync.Mutex
	)

	foo := func(a, b *sync.Mutex) {
		defer wg.Done()

		a.Lock()
		defer a.Unlock()

		time.Sleep(1 * time.Second)

		b.Lock()
		defer b.Unlock()
	}

	wg.Add(2)
	go foo(&mu1, &mu2)
	go foo(&mu2, &mu1)
	wg.Wait()
}

ポイントはfoo関数の引数の順番を入れ替えている所です。goroutineによって平行に実行されるAとBのfoo関数は、ほぼ同時に実行されます。その結果、Aではmu1の、Bではmu2のロックを取得します。

1秒間のスリープを入れているのは、確実にAとBでロックを取得させるためです。
スリープが終わると、Aはmu2のロックを、Bはmu1のロックを取得しようとしてデッドロックになります。

デッドロックになる条件

シンプルなデッドロックになるコードを書いてみましたが、案外デッドロックになるコードをワザと書こうと思うと難しかったりします。真のデッドロッカーになるためには、デッドロックになる条件を知っておきたいものです。

ここでも、Wikipediaに登場していただきましょう。

ご存じの方も多いと思いますが、Edward G. Coffman, Jr.さんの「Coffman conditions」です。

1. Mutual exclusion
   最低でも1つのリソースをロックする必要があり、リソースを使用できるプロセスは1つだけ
   
2. Hold and wait or resource holding
   プロセスが最低でも1つのリソースをロックしている状態で、追加で他のプロセスでロックされているリソースを要求する
   
3. No preemption
   リソースのロックは、ロックしたプロセスからしか開放できない、リソースを横取りできない
   
4. Circular wait
   プロセスAは、プロセスBがロックしているリソースを使用しようと待機するが、プロセスBもプロセスAのリソースを使用しようと待機する
   

この条件がすべて満たされるとデッドロックが発生します。

それでは、この条件を先ほどのコードと照らし合わせていきます。

1. Mutual exclusionは、foo関数に渡されたmutexをロックしています。そもそもMutexは、Mutual exclusion（排他制御）するために存在しており、goroutine間で排他できるので、この条件を満たしています。
   
2. Hold and wait or resource holdingは、foo関数は、引数aをロックしてさらに引数bをロックしようとしているので、この条件を満たしています。
   
3. No preemptionは、外部から強制的にロックを解除する仕組みを実装していないので、この条件を満たしています。
   
4. Circular waitは、上で書いたとおり、foo関数にMutexを渡す順番を変えることで、循環待機する状態になっており、この条件を満たしています。
   

ですので、これで健全なデッドロックの出来上がりというわけです。

少し複雑な例

もうすこし複雑な例を見ていきます。

package main

import (
	"sync"
	"time"
)

type Card struct {
	mu  sync.Mutex
	num int
}

func NewCard(num int) *Card {
	return &Card{num: num}
}

func main() {
	var wg sync.WaitGroup

	c1 := NewCard(1)
	c2 := NewCard(2)
	c3 := NewCard(3)

	foo := func(a, b *Card) {
		defer wg.Done()

		a.mu.Lock()
		av := a.num
		defer a.mu.Unlock()

		time.Sleep(1 * time.Second)

		b.mu.Lock()
		bv := b.num
		defer b.mu.Unlock()

		a.num = bv
		b.num = av
	}

	wg.Add(3)
	go foo(c1, c2)
	go foo(c2, c3)
	go foo(c3, c1)
	wg.Wait()
}

基本的には同じですが、今回は「c1」「c2」「c3」の三つで循環しています。 「c1」と「c2」、「c2」「c3」を交換するだけだとデッドロックは発生しませんが、 「c3」と「c1」も同時に交換することで循環が発生してデッドロックになります。

まとめ

今回はデッドロックが発生する条件（Coffman conditions）を確認して、健全なデッドロックを実装できるように調査しました。

なぜかわからないけどデッドロックになって焦る場面も多いですが、今回確認した条件を確認すると、原因を調査しやすくなるかと思います。
デッドロックを予防したり、防止する方法もあるので、気になった方は調べてみてはいかがでしょうか。

この記事を書いた人

tkr2f事業開発部 web application engineer

2008年にアーティスへ入社。
システムエンジニアとして、SI案件のシステム開発に携わる。
その後、事業開発部の立ち上げから自社サービスの開発、保守をメインに従事。
ドメイン駆動設計（DDD）を中心にドメインを重視しながら、保守可能なソフトウェア開発を探求している。

この執筆者の最新記事

この執筆者の記事一覧

• 2024年3月21日WEB安全性、速度、並行性を兼ね備えた言語と、巷でうわさのRustを覗いてみる（スレッド編 その1）
• 2024年1月12日WEB安全性、速度、並行性を兼ね備えた言語と、巷でうわさの「Rust」を覗いてみる（スマートポインタ編 その2）
• 2023年10月13日WEB安全性、速度、並行性を兼ね備えた言語と、巷でうわさの「Rust」を覗いてみる（スマートポインタ編 その1）
• 2023年8月10日WEBプログラミングにおける並行処理と並列処理の違いとは？真に同時な並列処理はかけるのか？