(プログラム） マルチスレッドについて
2009年07月17日06:01
マルチスレッドを使ってプログラムを組むとありとあらゆる不可思議な問題が起こるものだ。 しかもデバッグは至極困難を極め、デザイン上の問題を実際に動かす事によって追跡する事は不可能に近い。
しかしこういったマルチスレッドプログラムで起こる問題というのは、案外とパターンがあるという事がだんだん判明してきた。 そのパターンは全て「哲学者」と「レースコンディション」のいずれかに集約される。
◇
「哲学者」というのは「哲学者食事問題 ( dining philosopher problem)」と呼ばれる問題で、一見するとどこにも問題が無いように見えるのだが、実はそこにデッドロックの元凶が潜んでいる、という問題だ。
http://en.wikipedia.org/wiki/Dining_philosophers_problem
哲学者食事問題の本質は、あるスレッドがふたつ以上のロックを同時に取得するときは、複数のスレッド間で必ず一貫した順番を守らなければいけない、という条件だ。 ロックがＡ・Ｂとあったとき、あるスレッドがＡ・Ｂという順番でロックを取得し、もう一方のスレッドがＢ・Ａという順番でロックを取得すると、高い確率でデッドロックに陥る。 これは要するに、「金をもらったら魚を渡す」という魚屋と「魚をもらったら金を渡す」という客の関係のようなものだ。 とまってしまう。
解決策として、「マネージャー方式」と「階層方式」というものがある。 このふたつは名前は違うが本質的に同じ物だ。
マネージャー方式というのは、次のようなものだ。 Ａ・Ｂとロックがあったとする。 これらを複数のスレッドからロックしなければいけないとする。 この場合、必ず、もうひとつのロックＸを用意し、Ａ・Ｂをロックするときは必ず前もってＸをロックしなければいけない、という約束を作る。 こうする事でロックの順番が一定の法則を持つようにする方式のことだ。 これはつまり、魚屋で買い物をするとき入り口でクーポン券を買ってから魚屋に渡すようなものだ。
階層方式というのは、ロックしなければいけない要素が複数あった場合、それらに番号を振り、必ず大きいものから順にロックする、という約束を作る方式の事だ。 これは壁に「現金先払い」と張り紙をするようなものだ。
これらは、いずれにしても、ふたつ以上のスレッド間でロックの競合が起こったとき、必ず同じ順番でロックを取得するという事を保障すればデッドロックは発生しないという意味だ。
◇
もうひとつは「レースコンディション」だ。 この問題は、スレッドというものが、生成され実行が開始されても、必ずしもきちんと同じ速度で実行されるとは限らないという性質を持っていることと関連している。
各スレッドは時間を分割して実行されるようになっている。 しかしそれぞれのスレッドが必ずしも同じ確立で時間を配分してもらえることは約束されていない。 だから特定のスレッドだけ偶然時間の割り当てが減って極端に実行速度が遅くなってしまう事がある。
このように偶然に特定のスレッドだけが不公平を受ける事はありえる。 それはサーバーが高負荷状態になったときなどにしばしば発生する。
こういう現象のことをスタベーション(starvation) と呼ぶ。 これ以外にもスレッドのスタベーションが起こるケースがいくつかある。
http://en.wikipedia.org/wiki/Resource_starvation
スレッドの同期処理がそのひとつだ。
あるオブジェクトに対して待ち状態に入ったスレッドは、そのオブジェクトにシグナルが到着すると、スレッドが待ち状態から実行状態に戻る。 このとき、待ち状態のスレッドが複数ある場合、シグナルが到着したとき実行状態に戻る事が出来るスレッドはひとつだけだ。 そのときどのスレッドが実行状態に戻るのかは、予想できない。 だから可能性として特定のスレッドだけが不公平に待ち状態のままにおかれてしまうことがある。 これもやはりサーバーが高負荷におかれたときなどに、しばしば発生する。 こうしてスタベーションが発生してしまう。
だから、プログラムを組んだら、そのロジックがどのような順番で呼び出されても絶対に間違った動作をしないように組まなければいけない。
というわけで、マルチスレッドでプログラムを組んでいるとき発生する問題は、必ず、このふたつのうちのどちらかだ。 それさえ理解できれば、マルチスレッドプログラムも怖くない。
◇
しかし、このふたつの約束を守りながらプログラムを組むのは、思ったよりずっと難しい。
何故ならば．．． （続く）
しかしこういったマルチスレッドプログラムで起こる問題というのは、案外とパターンがあるという事がだんだん判明してきた。 そのパターンは全て「哲学者」と「レースコンディション」のいずれかに集約される。
◇
「哲学者」というのは「哲学者食事問題 ( dining philosopher problem)」と呼ばれる問題で、一見するとどこにも問題が無いように見えるのだが、実はそこにデッドロックの元凶が潜んでいる、という問題だ。
http://en.wikipedia.org/wiki/Dining_philosophers_problem
哲学者食事問題の本質は、あるスレッドがふたつ以上のロックを同時に取得するときは、複数のスレッド間で必ず一貫した順番を守らなければいけない、という条件だ。 ロックがＡ・Ｂとあったとき、あるスレッドがＡ・Ｂという順番でロックを取得し、もう一方のスレッドがＢ・Ａという順番でロックを取得すると、高い確率でデッドロックに陥る。 これは要するに、「金をもらったら魚を渡す」という魚屋と「魚をもらったら金を渡す」という客の関係のようなものだ。 とまってしまう。
解決策として、「マネージャー方式」と「階層方式」というものがある。 このふたつは名前は違うが本質的に同じ物だ。
マネージャー方式というのは、次のようなものだ。 Ａ・Ｂとロックがあったとする。 これらを複数のスレッドからロックしなければいけないとする。 この場合、必ず、もうひとつのロックＸを用意し、Ａ・Ｂをロックするときは必ず前もってＸをロックしなければいけない、という約束を作る。 こうする事でロックの順番が一定の法則を持つようにする方式のことだ。 これはつまり、魚屋で買い物をするとき入り口でクーポン券を買ってから魚屋に渡すようなものだ。
階層方式というのは、ロックしなければいけない要素が複数あった場合、それらに番号を振り、必ず大きいものから順にロックする、という約束を作る方式の事だ。 これは壁に「現金先払い」と張り紙をするようなものだ。
これらは、いずれにしても、ふたつ以上のスレッド間でロックの競合が起こったとき、必ず同じ順番でロックを取得するという事を保障すればデッドロックは発生しないという意味だ。
◇
もうひとつは「レースコンディション」だ。 この問題は、スレッドというものが、生成され実行が開始されても、必ずしもきちんと同じ速度で実行されるとは限らないという性質を持っていることと関連している。
各スレッドは時間を分割して実行されるようになっている。 しかしそれぞれのスレッドが必ずしも同じ確立で時間を配分してもらえることは約束されていない。 だから特定のスレッドだけ偶然時間の割り当てが減って極端に実行速度が遅くなってしまう事がある。
このように偶然に特定のスレッドだけが不公平を受ける事はありえる。 それはサーバーが高負荷状態になったときなどにしばしば発生する。
こういう現象のことをスタベーション(starvation) と呼ぶ。 これ以外にもスレッドのスタベーションが起こるケースがいくつかある。
http://en.wikipedia.org/wiki/Resource_starvation
スレッドの同期処理がそのひとつだ。
あるオブジェクトに対して待ち状態に入ったスレッドは、そのオブジェクトにシグナルが到着すると、スレッドが待ち状態から実行状態に戻る。 このとき、待ち状態のスレッドが複数ある場合、シグナルが到着したとき実行状態に戻る事が出来るスレッドはひとつだけだ。 そのときどのスレッドが実行状態に戻るのかは、予想できない。 だから可能性として特定のスレッドだけが不公平に待ち状態のままにおかれてしまうことがある。 これもやはりサーバーが高負荷におかれたときなどに、しばしば発生する。 こうしてスタベーションが発生してしまう。
だから、プログラムを組んだら、そのロジックがどのような順番で呼び出されても絶対に間違った動作をしないように組まなければいけない。
というわけで、マルチスレッドでプログラムを組んでいるとき発生する問題は、必ず、このふたつのうちのどちらかだ。 それさえ理解できれば、マルチスレッドプログラムも怖くない。
◇
しかし、このふたつの約束を守りながらプログラムを組むのは、思ったよりずっと難しい。
何故ならば．．． （続く）
コメント一覧
