Loading article…
コンピュータサイエンスにおいて、相互排他は並行性制御の特性であり、競合状態を防止するために設けられています。これは、ある実行スレッドが、既にクリティカルセクションにアクセスしている間は、そのクリティカルセクションに進入してはならないという要件です。クリティカルセクションとは、実行スレッドが共有リソースまたは共有メモリにアクセスする時間間隔を指します。
共有リソースはデータオブジェクトであり、2 つ以上の同時スレッドがその変更を試みています (同時読み取り操作は 2 つまで許可されますが、同時書き込み操作は 2 つまで、または読み取りと書き込みが 1 つずつ行われるとデータの不整合が発生するため許可されません)。相互排他アルゴリズムにより、プロセスがデータオブジェクト (クリティカル セクション) に対して書き込み操作を実行している場合、最初のプロセスがデータオブジェクト (クリティカル セクション) への書き込みを完了し、他のプロセスが読み書きできるようにオブジェクトを解放するまで、他のプロセスやスレッドが同じオブジェクトにアクセスしたり変更したりすることが許可されません。
相互排他性の要件は、エドガー・W・ダイクストラが1965年の画期的な論文「並行プログラミング制御における問題の解決」[ 1 ] [ 2 ]で初めて特定し解決したもので、これは並行アルゴリズムの研究における最初のトピックとして評価されている。[ 3 ]
相互排他が実際に重要である理由の簡単な例として、2番目と3番目の要素を削除する4つの要素からなる単方向連結リストを視覚化することができます。他の2つのノードの間にあるノードの削除は、前のノードの次のポインタを次のノードを指すように変更することによって実行されます（つまり、ノードiが削除される場合、ノードi - 1の次のポインタがノードi + 1を指すように変更され、それによって連結リストからノードiへの参照が削除されます）。このような連結リストが複数の実行スレッド間で共有されている場合、2つの実行スレッドが同時に2つの異なるノードを削除しようとする可能性があります。1つの実行スレッドがノードi - 1の次のポインタをノードi + 1を指すように変更し、別の実行スレッドがノードiの次のポインタをノードi + 2を指すように変更します。両方の削除操作は正常に完了しますが、連結リストの目的の状態は達成されません。ノードi - 1の次のポインタがノードi + 1を指しているため、ノードi + 1はリストに残ります。
この問題（競合状態と呼ばれる）は、相互排他性の要件を用いることで回避できる。相互排他性によって、リストの同じ部分への同時更新が発生しないようにすることができる。
相互排他という用語は、あるスレッドがメモリ アドレスに書き込みを行っている間に、そのメモリ アドレスが他の 1 つ以上のスレッドによって操作または読み取られている状況を指す場合にも使用されます。
相互排他が解決する問題は、リソース共有の問題です。各プロセスが処理中に共有リソースを排他的に制御する必要がある場合、ソフトウェアシステムは複数のプロセスによる共有リソースへのアクセスをどのように制御できるのでしょうか？この問題に対する相互排他による解決策は、プロセスがクリティカルセクションと呼ばれる特定のコードセグメント内にある間だけ共有リソースを利用可能にすることです。そして、リソースが使用されるプログラム部分の各実行を制御することで、共有リソースへのアクセスを制御します。
この問題に対する有効な解決策は、少なくとも以下の2つの特性を備えている必要がある。
デッドロックフリーは、以下の特性のいずれか、または両方を実装するように拡張できます。
すべてのプロセスのプログラムは4つのセクションに分割でき、その結果4つの状態が生じます。プログラムの実行は、これらの4つの状態を順番に循環します。[ 5 ]
プロセスがクリティカルセクションに入るには、まず試行セクションを実行し、クリティカルセクションへのアクセス権を取得するまで待機する必要があります。プロセスがクリティカルセクションを実行し、共有リソースの使用を終えたら、他のプロセスが使用できるようにリソースを解放するために終了セクションを実行する必要があります。その後、プロセスは非クリティカルセクションに戻ります。
単一プロセッサシステムでは、相互排他を実現する最も簡単な解決策は、プロセスのクリティカルセクション中に割り込みを無効にすることです。これにより、割り込みサービスルーチンが実行されなくなり（事実上、プロセスがプリエンプトされるのを防ぎます）。この解決策は効果的ですが、多くの問題を引き起こします。クリティカルセクションが長い場合、タイマー割り込みが処理されなくなるため、クリティカルセクションが実行されるたびにシステムクロックがずれ、クリティカルセクション中は時間を追跡できなくなります。また、プロセスがクリティカルセクション中に停止すると、制御は他のプロセスに戻されず、事実上システム全体が停止します。相互排他を実現するためのより洗練された方法は、ビジーウェイトです。
ビジーウェイトは、シングルプロセッサシステムとマルチプロセッサシステムの両方で有効です。共有メモリとアトミックなテストアンドセット命令を使用することで、相互排他が実現されます。プロセスは共有メモリ内の特定のアドレスに対してテストアンドセットを実行でき、この操作はアトミックであるため、一度にフラグを設定できるプロセスは1つだけです。フラグの設定に失敗したプロセスは、他のタスクを実行して後で再試行するか、プロセッサを別のプロセスに解放して後で再試行するか、フラグの取得に成功するまでフラグをチェックしながらループを続けるかのいずれかを選択できます。プリエンプションは引き続き可能なので、この方式では、プロセスがロックを保持したまま停止した場合でも、システムは動作を継続できます。
データ構造の相互排他を実現するために使用できるアトミック操作は他にもいくつかありますが、その中でも最も有名なのが比較交換（CAS）です。CASは、各ノードが実行したい操作を表すリンクリストを作成することで、任意の共有データ構造に対して待機不要の相互排他を実現するために使用できます。CASは、新しいノードの挿入中にリンクリスト[ 6 ]内のポインタを変更するために使用されます。CASで成功できるプロセスは1つだけです。同時にノードを追加しようとする他のすべてのプロセスは、再度試行する必要があります。各プロセスはデータ構造のローカルコピーを保持し、リンクリストを走査しながら、リストの各操作をローカルコピーに対して実行できます。
ハードウェアによるサポートに加え、ビジーウェイトを利用して相互排他を実現するソフトウェアソリューションも存在する。例としては以下のようなものがある。
これらのアルゴリズムは、実行するプラットフォームで順不同実行が使用されている場合は機能しません。プログラマは、スレッド内のメモリ操作の厳密な順序を指定する必要があります。 [ 8 ]
多くの場合、オペレーティングシステムのマルチスレッドライブラリが提供する同期機能を使用する方が望ましい。この機能は、ハードウェアサポートが利用可能な場合はそれを活用し、必要に応じてソフトウェアメカニズムにフォールバックすることができる。たとえば、オペレーティングシステムのロック機能が使用され、スレッドが既に保持されているロックを取得しようとすると、オペレーティングシステムはコンテキストスイッチを介してスレッドを一時停止し、別の実行可能なスレッドをスケジュールするか、実行可能な他のスレッドがない場合はプロセッサを低電力状態に置くことができる。その結果、最新の相互排他技術のほとんどは、キューイングとコンテキストスイッチに依存することで、レイテンシとビジーウェイトを削減することを目的としている。ただし、スレッドを一時停止して後で復元するオーバーヘッドが、特定のシナリオでスレッドがロックが利用可能になるまで待つ時間よりも明らかに大きい場合は、そのコンテキストではスピンロックが許容できる解決策となる可能性がある。[ 9 ] [ 10 ]
バイナリのテスト&セットレジスタが1つあれば、相互排他問題に対するデッドロックのない解決策を提供できます。しかし、テスト&セットレジスタを使用して構築された解決策は、試行セクションで捕捉された一部のプロセスが飢餓状態になる可能性につながります。[ 4 ]実際、ロックアウトを回避するには、異なるメモリ状態が必要です。無制限の待機を回避するには、n個の異なるメモリ状態が必要です。[ 11 ]
相互排他アルゴリズムのほとんどは、クリティカルセクション内でプロセスが実行されている間は障害が発生しないという前提で設計されています。しかし、実際にはそのような障害はよくあることです。たとえば、突然の電源喪失やインターコネクトの不具合により、クリティカルセクション内のプロセスが回復不能なエラーを経験したり、継続できなくなったりする可能性があります。このような障害が発生した場合、従来の耐障害性のない相互排他アルゴリズムではデッドロックが発生したり、重要な活性特性が損なわれたりする可能性があります。この問題に対処するために、クラッシュリカバリメカニズムを使用したいくつかのソリューションが提案されています。[ 12 ]
上記で説明した解決策は、以下の同期プリミティブを構築するために使用できます。
相互排他には多くの副作用があります。例えば、古典的なセマフォではデッドロックが発生します。デッドロックとは、一方のプロセスがセマフォを取得し、もう一方のプロセスが別のセマフォを取得し、両方のプロセスがもう一方のセマフォが解放されるまで待機する状態です。その他の一般的な副作用としては、飢餓状態（プロセスが実行を完了するのに十分なリソースを得られなくなる状態） 、優先度逆転（優先度の高いスレッドが優先度の低いスレッドを待機する状態）、高レイテンシ（割り込みへの応答が遅い状態）などがあります。
上記の影響を排除することを目的とした研究が多く行われており、多くの場合、非ブロッキング進行を保証することを目標としています。完璧なスキームは知られていません。ブロッキングシステムコールは、プロセス全体をスリープさせるために使用されていました。このようなコールがスレッドセーフになるまでは、プロセス内の単一のスレッドをスリープさせるための適切なメカニズムはありませんでした（ポーリングを参照）。[ 13 ]
{{citation}}: CS1メンテナンス: ISBNを使用した作業パラメータ (リンク)