PRINCIPIA
Products Seminar About Us

デッドロック発見器を作って学ぶマルチスレッドプログラミング ★共有変数編★

参加者が自分の好きなプログラミング言語でデッドロック発見器を作り，それを使ってマルチスレッドプログラミングを学ぶハンズオンセミナーです．

作っていただくデッドロック発見器はマルチスレッドプログラムの動き全体を状態遷移図として可視化し，その過程でデッドロック状態を発見するというものです．以下にデッドロック発見器の出力例を示しました．

水色の状態は初期状態で，赤い状態がデッドロック状態です．デッドロック状態からは遷移が1つも出ていないので，この状態に達するとプログラムは停止してしまうことがわかります．動作し続けるパスもあり，必ず再現するわけではないというマルチスレッドプログラムに特徴的な問題であることが見てとれます．

セミナーのゴールは，自分で作ったデッドロック発見器を問題に適用して，このような出力を得ることです．

状態遷移図

マルチスレッドプログラミングの教科書を見ると，典型的なアルゴリズムが解説されています．それが自分のプログラムでそのまま使える場合はよいのですが，そうではない場合は一部を変更したり新しいアルゴリズムを考案したりすることになります．ところがマルチスレッドプログラミングというのは難しいもので，少し修正しただけで動かなくなったり，一見うまく動いているように見えても長時間動かしていると時々おかしくなる，というようなことが起こったりします．このようなときはどうしたらよいのでしょうか．

こういうときに役に立つのは基礎的な理論の力です．プログラムの動きとは何か，それらを複数並行に走らせるマルチスレッドプログラムの動きとは何か，といった基本的なことがらを明確にすると，プログラムの動きをデータとして表現することができます．プログラムの動きがデータになればプログラムで操作ができます．すると計算機のパワーを使ってプログラムの動きを調べ尽くし，おかしなところがないかどうかチェックすることができます．つまり理論の力を借りてプログラムの動きを調べるプログラムを作ることで問題に対処しようというわけです．

実はそのような方針で作られたツールはたくさんあります．しかし使いこなすためには基礎となる理論を学ぶ必要があり，やや敷居が高く感じる人が多いようです．理論が難しいということもありますが，抽象的な理論はなかなか頭に染み込まず，実際の問題との関係が見えにくいという感想をよく聞きます．

そこでこのセミナーでは，理論の中でももっとも基礎的で簡単な部分だけを使い，プログラムの動きを調べるプログラムを自ら作るというアプローチを採用します．理論を理解するもっともよい方法は，実際に使ってみることです．プログラミングの場合でいえばプログラムを書いてみることです．教科書を読んだだけではわかったつもり，本当に理解できたと思えるのはあれこれ調査・試行錯誤してプログラムを書いたときであることは誰もが経験的に感じていることでしょう．自分のものにするというのは，教科書に書いてあることを自分で再現・応用できるようになるということだと思います．

このセミナーにはもう1つ特徴があります．解決すべき問題に集中するためには慣れた道具を使う方がよいでしょう．そこで使用するプログラミング言語は参加者が自由に選ぶ，というスタイルにしました．サンプル実装は C 言語版と OCaml 版の2つを用意してあります．参加者は自分のペースで作業を進めることができます．たとえば次のような方針があります：

サンプル実装は疑似コードではなく実際に動くプログラムなので，実装する自信はないけれども動かしたりコードを読んで質問したりして理解したいという人でも参加できます．一方，余力のある人向けには発展課題も用意してあります．

デッドロック発見器ができたら次は応用です．実際のマルチスレッドプログラムに適用してみます．基本的な3つの例を用意しました．サンプル実装でも参加できます．余力のある人は自分が興味のあるプログラムに適用してみてください．わかる範囲で質問もお受けします．

上に示した状態遷移図の例からもわかるように，デッドロック発見器が教えてくれるのはデッドロックがある・ないということと，ある場合にはその状態と初期状態からの実行パスです．しかし「なぜデッドロックするのか？」という問いには答えてくれません．実行パスを読み解いてデッドロックする理由（設計やアルゴリズムの間違い）を理解するのは人間の仕事です（いまのところ）．実は，この実行パスを読み解くという作業がマルチスレッドプログラミングの力をつけてくれるとても有効なトレーニングになります．デッドロック発見器はプログラマがコーディング時に想定していなかった組み合わせのパスを確実に見つけてくるからです．この読み解き作業を数多くこなしていくと，想定できる範囲が広がり，危ないコーディングに気づけるようになります．正しいフィードバックと深い思考を数多く経験することによって直感が働くように脳を鍛えるということだと思います．

プログラミングの分野では次々と新しい技術が登場し，急激に変化を続けていますが，一方で基礎的な理論の価値はそうそう変わらないものです．一度身に着ければ一生役に立つ理論を，自ら手を動かし，講師と対話することで深く効率よく習得できるこのセミナーにぜひご参加ください．自分で作ったツールというのは愛着のわくものです．作って楽しく，使って役に立ち，継続的に育てる楽しみもあります．

プログラム

A. マルチスレッドの理論的モデル

デッドロック発見器の基礎となる理論的モデルを解説します．

  1. プログラムと状態遷移
  2. 相互作用（共有変数とメッセージパッシング）

B. デッドロック発見器の設計と実装

はじめに OCaml と C による実装例を元にデッドロック発見器のしくみを解説します．それを参考に自分の発見器を設計・実装します．

  1. 共有変数とプロセス（スレッド）の表現
  2. 並行合成（グラフの生成と探索）
  3. 可視化（状態遷移グラフ，デッドロックへのパス）

C. 応用：同期オブジェクトのモデル化と検査・分析

作ったデッドロック発見器を使って，マルチスレッドプログラムの設計問題を扱ってみます．

  1. ミューテックスによる排他制御
  2. キューによる非同期通信
  3. 条件変数によるキューの実装

セミナー参加の前提条件

前提知識

必要なもの

プログラムの規模

デッドロック発見器本体サンプル実装の規模は次のとおりです．

しくみを明らかにするために，エラー処理やメモリ解放などは意図的に省略しています．

C言語版の方が少し機能が多くなっています：

同様の拡張を OCaml 版に対して行うことはそれほど難しくないのですが，OCaml 版はリファレンスとしてシンプルさを保ちたいのでこのような形になっています．

調べる対象となるマルチスレッドプログラムは，状態遷移モデルとして表現します．このセミナー内ではモデル記述言語やパーサは作らないので，C言語の構造体初期化子または OCaml のデータ構造として手作業で記述します．例で扱うモデルは40行～170行程度です．

グラフ探索（幅優先探索または深さ優先探索）のプログラムを書くことになるので，すでに訪れたノードを記録するためにハッシュ表またはそれに類するデータ構造（辞書，マップなど）と，未調査のノードを格納しておくキューまたはスタックが必要です．OCaml 版では標準ライブラリの Hashtbl と Queue を使っています．C言語版では簡易な実装を用意しました．使用するプログラミング言語のライブラリに適切なものがない場合は自分で用意する必要があります．セミナーの時間は限られているので，本来の問題に集中するために事前に用意しておくとよいかもしれません．ノードはデッドロック発見器の利用者が定義する共有変数の値を含むので，任意の型をキーとすることのできるハッシュ表が必要です．

参考書

作品紹介

デッドロック発見器を使った事例や，前回のセミナーに参加された人の作品を紹介しています．

© 2013-2023 PRINCIPIA Limited