Insert your Title here

Size: px

Start display at page:

Download "Insert your Title here"

かげたつにばし
4 years ago
Views:

2 Agenda 並列実行に起因する不具合の摘出なぜ並列実行されるプログラミングは難しいのかデータの競合デッドロックどのようにして静的解析ツールで並列実行の問題を見つけるのか? コーディングの例遅延初期化 (Lazy Initialization) まとめ Page 2

3 トレンド : シングルからマルチコアへ伝統的な性能向上のアプローチはそろそろおしまいクロック周波数の上昇メモリアクセスの高速化そして賢い命令のスケジュールによる最適化はもはや時代遅れ開発チームはマルチコアプロセッサを使用したがっているよりよいパフォーマンスへの近道消費電力でもメリットしかし実際の適用には大きな障害がありますアプリケーションソフトウェアはマルチコアを利用するために変更が必要マルチコアプロセッサを導入しただけではもっている性能はフルに発揮できませんそしてマルチコアプログラミングは難しい Page 3

4 マルチコアはソフトウェア開発を複雑にする + = + = 2 つの命令を持つ 2 つのスレッドでは組み合わせは 6 つ 3 つの命令では 20 の組み合わせとなります Page 4

5 現実世界でのスケジューリング現実世界のソフトウェアは前のスライドの例よりも非常に多くの命令で構成されていますインターリーブはスケジューラーにより決定されます全てのパターンのインターリーブをテストすることは不可能です決められたパターンのインターリーブでさえもテストすることは難しいですシステムのスケジューリングは非常に複雑です決定することは難しい指定されたテストケースでも多くの異なる振る舞いをします引数が同じ場合でも同じ動作をするとは限らない実行の正しさはスケジューリングに依存します競合条件は並列ソフトウェアの悩みの種 Page 5

6 データの競合データの競合は以下の時に発生します : 1. 複数の実行中のスレッドが共有しているデータをアクセスする場合 2. 少なくともひとつのスレッドがデータの値を変更する場合 3. アクセスが明確な同期を使用していない場合データの競合はシステムを矛盾した状態にしますまたデータの競合は検出されることが難しく極めて不可解な稀な ( 困った ) 状況を引き起こします Page 6

7 データの競合の例 Thread 1 Thread 2 count: 10 9 count := count + 1; count := count - 1; count := count + 1; メモリからレジスタに転送してレジスタに 1 を加算してレジスタからメモリに書き戻す Page 7

8 データの競合 Instruction Register Memory load 9-9 increment store wait. load decrement store インターリーブされていない命令では正しい結果が得られます wait. load 9-9 increment load 9-9 decrement store store インターリーブされた命令では誤った結果となる Page 8

9 なぜデータの競合はデバッグが難しいのか稀にしか発生しないということはテスト中に発見するチャンスが少ないということ診断は難しい症状と原因が大きく離れていることがしばしばある再現させることが最大の問題結果が間違った実行のスケジュール再生が難しいスケジューリングは環境に敏感デバッガの使用コンパイラの最適化 I/O 回数の違い外部環境の違いでスケジューリングは変化します開発者はコードを読むときにはひとつのスレッドしか一度に読むことができないスレッドの相互作用の影響は簡単に見落とされる Page 9

10 GrammaTech CodeSonar 重大な一般的な不具合とセキュリティの脆弱性をみつけますプログラム全体でのパス構造解析でのシンボリック実行を使用どのように使用するか : コードやビルドスクリプトの変更は必要なしプログラムは通常通りビルドされ CodeSonar がコンパイルコマンドラインを監視ビルドの一方で CodeSonar はコードを解析し不具合を見つけます見つけた不具合はお客様のマシン上のデータベースに集められますユーザーのログもデータベースに収集されます解析のプロセスは全体で自動化可能です ( 例 : 毎日夜に実行 ) Page 10

11 CodeSonar のコード解析原理ソースコードモデル摘出中間表現解析結果出力 Page 11

12 CodeSonar はどのようにしてデータの競合を見つけるのか CodeSonar は症状ではなく原因にフォーカスするコードを検証してどのスレッドでどのロックを使用しているかの情報を持つアブストラクトモデルを生成します自動的に可能性のあるインターリーブを調査し共有メモリへのアクセスパターンを検証しますコードのどこに問題を含むインターリーブがあるかを見つけますデータの競合が認められた場合 CodeSonar は関係する情報とともに Data Race ウォーニングを通知しますまた CodeSonar は同期構造により発生する問題も検出します例 : デッドロックロックの誤り Page 12

13 デッドロックする銀行処理の例アカウント X からアカウント Y へ送金する手順アカウントXをロックアカウントYをロック指定金額をアカウントXから引き Yに加算アカウントYをアンロックアカウントXをアンロック 2 つのトランザクションを検討してみます $100をアリスからボブへ送金 $50をボブからアリスへ送金 Page 13

14 デッドロック Thread 1 acquire lock for Alice acquire lock for Bob waiting on Thread 2 Alice Bob Thread 2 acquire lock for Bob acquire lock for Alice waiting on Thread 1 Page 14

15 CodeSonar はどのようにしてデッドロックを見つけるのかリソースの順序を確認 Dijkstra が 1965 年に発表した食事する哲学者たちの問題 Conflicting Lock Order ウォーニングは異なるスレッドで同じロックが異なる順序で発行されると検出する CodeSonar はさらにネストされたロックのチェックも行います複数のロックを使用している場合にチェックが行われます同期問題の難しさを強調します Page 15

16 コードの例遅延初期化 (Lazy Initialization) Page 16

17 遅延初期化 (Lazy Initialization) コード例 float *singleton( void ) { static int is_initialized = 0; } static float *actual_data = NULL; if(!is_initialized ) { pthread_mutex_lock( &m ); if(!is_initialized ) { actual_data = (float *)malloc( sizeof( float ) ); *actual_data = 4.2; is_initialized = 1; } pthread_mutex_unlock( &m ); } return actual_data; void *f1( void *a ) { printf( "%f", *singleton() ); } return a; void *f2( void *a ) { printf( "%f", *singleton() ); } return a; Page 17

18 遅延初期化 (Lazy Initialization) 単一の関数 Page 18

19 遅延初期化 (Lazy Initialization) 単一の関数 Page 19

20 遅延初期化 (Lazy Initialization) 並べて比較 Page 20

21 まとめマルチコアの開発は避けられない同時実行に伴うエラーは潜んでいる再現診断除去は難しい見たところ問題がないと思われるデータの競合でさえ場合によっては突然悪い結果をもたらすことがある静的解析ツールで不具合の検出を助けます Page 21

22 CodeSonar の先進的な静的解析プログラム全体の解析 ( モジュール間も含む ) 非常に大規模なコードでの使用が可能なスケーラビリティー重要な不具合の検出バッファオーバラン Null ポインタの参照 0 での割り算初期化されていない変数ヒープ以外の変数の解放解放後メモリの使用競合条件メモリ / リソースのリークユーザー定義のチェックその他多くの不具合 Page 22

23 問い合わせ窓口 GrammaTech 日本総代理店エーアイコーポレーションお問い合わせ資料請求評価版申し込みは Web のお問い合わせ資料申込のフォームをご利用ください Page 23

POSIXスレッド

POSIXスレッド POSIX スレッド (3) システムプログラミング 2011 年 11 月 7 日建部修見同期の戦略単一大域ロックスレッドセーフ関数構造的コードロッキング構造的データロッキングロックとモジュラリティデッドロック単一大域ロック (single global lock) 単一のアプリケーションワイドの mutex スレッドが実行するときに獲得, ブロックする前にリリースどのタイミングでも一つのスレッドが共有データをアクセスする