競合状態、相互排他、同期、並列スローダウン

ウィキペディア小見出し辞書

競合状態、相互排他、同期、並列スローダウン

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/25 13:20 UTC 版)

「並列計算」の記事における「競合状態、相互排他、同期、並列スローダウン」の解説

並列プログラムにおけるサブタスクをスレッドと呼ぶ。システムによってはさらに小さく軽量なスレッドであるファイバーを使っており、もっと大きな単位であるプロセスを使っているシステムもある。いずれにしても、並列プログラムのサブタスクをここではスレッドと呼ぶ。 スレッドは、スレッド間で共有している何らかの変数を更新することがよくある。2つのスレッドの命令実行順序は一定ではない。例えば、次のようなプログラムを考える。 スレッド A スレッド B 1A: 変数 V を読む 1B: 変数 V を読む 2A: 変数 V の値に1を加算 2B: 変数 V の値に1を加算 3A 変数 V に値を書き戻す 3B: 変数 V に値を書き戻す 命令1Bが1Aと3Aの間に実行された場合、または命令1Aが1Bと3Bの間に実行された場合、このプログラムは間違ったデータを生成する。これを競合状態と呼ぶ。プログラマは相互排他のためにロックを使わなければならない。ロックとはプログラミング言語の構成要素であり、あるスレッドが変数の制御権を獲得すると、それがアンロックされるまで他のスレッドから読み書きできないようにする。ロックを獲得したスレッドはクリティカルセクション（プログラムの中で何らかの変数に排他的にアクセスする必要がある部分）を実行でき、それが完了したらそのデータをアンロックする。 従って、プログラムを正しく実行するには、上のプログラムを以下のようにロックを使って書き直す必要がある。 スレッド A スレッド B 1A: 変数 V をロック 1B: 変数 V をロック 2A: 変数 V を読む 2B: 変数 V を読む 3A: 変数 V の値に1を加算 3B: 変数 V の値に1を加算 4A 変数 V に値を書き戻す 4B: 変数 V に値を書き戻す 5A: 変数 V をアンロック 5B: 変数 V をアンロック 一方のスレッドが変数 V をロックできた場合、もう一方は V がアンロックされるまで待たされることになる。これによってプログラムの正しい実行が保証される。ロックはプログラムの正しい実行の保証には必須だが、それによってプログラムの実行速度は大幅に低下する。 複数の変数のロックには複数のロックが必要であり、それによってデッドロックが発生する可能性が生じる。不可分なロックは複数の変数を一度にロックするものである。その場合、対象変数群の一部がロックできなければ、全体のロックができないと見なされる。個別にロックされる2つの変数をロックする必要のあるスレッドが2つ存在したとして、一方のスレッドが一方の変数だけをロックし、もう一方のスレッドがもう一方の変数だけをロックするという状況が発生しうる。このような場合、双方のスレッドはロックできていない変数をロックしようとして待ち続け、結果としてデッドロックとなる。 多くの並列プログラムでは、サブタスク群が同期して動作することを要求する。この用途で使われるものとしてバリアがある。バリアは一般にソフトウェアロックを使って実装される。その種のアルゴリズムとしてLock-freeとWait-freeアルゴリズムがある。これはロックもバリアも使わずに全てを実現するものである。ただし、実装は難しく、データ構造の設計を慎重に行う必要がある。 並列化によって必ず性能が向上するとは限らない。一般にタスクを細分化してスレッド数を増やしていくと、スレッド間の通信に費やす時間が増大していく。すると、ある時点で通信オーバーヘッドが処理時間を支配するようになり、それ以上の並列化（スレッド数の増加）は単に処理時間の遅延を招くことになる。この現象を並列スローダウンと呼ぶ。