グローバルナビゲーションへ

本文へ

フッターへ

お役立ち情報Blog



Golangでデッドロックを作って遊んでみる~並行処理でデッドロックを起こさないために~

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

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

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

デッドロックとは

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

デッドロック (英: deadlock) とは、特に計算機科学において、2つ以上のスレッドあるいはプロセスなどの処理単位が互いの処理終了を待ち、結果としてどの処理も先に進めなくなってしまうことを言う。Wikipedia

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

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

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

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

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

デッドロックになる条件

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

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

Necessary conditions

A deadlock situation on a resource can arise if and only if all of the following conditions hold simultaneously in a system:[5]

  1. Mutual exclusion: At least one resource must be held in a non-shareable mode. Otherwise, the processes would not be prevented from using the resource when necessary. Only one process can use the resource at any given instant of time.[6]
  2. Hold and wait or resource holding: a process is currently holding at least one resource and requesting additional resources which are being held by other processes.
  3. No preemption: a resource can be released only voluntarily by the process holding it.
  4. Circular wait: each process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, P = {P1, P2, …, PN}, such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3 and so on until PN is waiting for a resource held by P1.[3][7]

These four conditions are known as the Coffman conditions from their first description in a 1971 article by Edward G. Coffman, Jr.[7]

While these conditions are sufficient to produce a deadlock on single-instance resource systems, they only indicate the possibility of deadlock on systems having multiple instances of resources.[8] 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を渡す順番を変えることで、循環待機する状態になっており、この条件を満たしています。

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

少し複雑な例

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

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

まとめ

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

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

The following two tabs change content below.

tkr2f

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

FOLLOW US

最新の情報をお届けします