線形化可能性

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
灰色の線形サブ履歴では、b2が発生する前にb0またはb1がいずれかの順序で完了する可能性があるため、bで始まるプロセスには線形化可能な履歴がありません。

並行プログラミングでは、操作(または操作のセット)は、呼び出しイベントと応答イベント(コールバック)の順序付きリストで構成されている場合、線形化可能です。これは、次のような応答イベントを追加することで拡張できます。

  1. 拡張リストは、シーケンシャル履歴として再表現できます(シリアル化可能)。
  2. そのシーケンシャル履歴は、元の拡張されていないリストのサブセットです。

非公式には、これは、呼び出しがシリアル化可能である場合にのみ、変更されていないイベントのリストが線形化可能であることを意味しますが、シリアルスケジュールの応答の一部はまだ返されていません。[1]

並行システムでは、プロセスは共有オブジェクトに同時にアクセスできます。複数のプロセスが1つのオブジェクトにアクセスしているため、1つのプロセスがオブジェクトにアクセスしているときに、別のプロセスがその内容を変更する場合があります。システムを線形化可能にすることは、この問題の1つの解決策です。線形化可能なシステムでは、操作は共有オブジェクト上で重複しますが、各操作は瞬時に行われるように見えます。線形化可能性は強力な正しさの条件であり、オブジェクトが複数のプロセスによって同時にアクセスされたときに可能な出力を制限します。これは、操作が予期しない方法または予測できない方法で完了しないことを保証する安全特性です。システムが線形化可能である場合、プログラマーはシステムについて推論することができます。[2]

線形化可能性の歴史

線形化可能性は、1987年にHerlihy and Wingによって整合性モデルとして最初に導入されました。これには、「アトミック操作は、並行操作によって中断できない(または中断できない)」など、アトミックのより限定的な定義が含まれます。操作が開始および終了すると見なされるとき。

アトミックオブジェクトは、一連の操作が並行して実行され、常に次々に発生するように見えるため、その順次定義から即座に完全に理解できます。矛盾が発生することはありません。具体的には、線形化可能性により、システムの不変条件がすべての操作によって監視および保存されることが保証されます。すべての操作が個別に不変条件を保存する場合、システム全体が保存されます。

線形化可能性の定義

並行システムは、共有データ構造またはオブジェクトを介して通信するプロセスのコレクションで構成されます。線形化可能性は、オブジェクトが複数のプロセスによって同時にアクセスされる可能性があり、プログラマーが期待される結果について推論できる必要があるこれらの並行システムでは重要です。並行システムを実行すると、完了した操作の順序付けられたシーケンスで ある履歴が生成されます。

履歴は、一連のスレッドまたはプロセスによってオブジェクトに対して行われた一連呼び出し応答です呼び出しは操作の開始と考えることができ、応答はその操作の合図された終了です。関数を呼び出すたびに、後続の応答があります。これは、オブジェクトのあらゆる使用をモデル化するために使用できます。たとえば、2つのスレッドAとBの両方がロックを取得しようとし、すでに取得されている場合はバックオフするとします。これは、両方のスレッドがロック操作を呼び出し、次に両方のスレッドが応答を受信するようにモデル化されます。一方は成功し、もう一方は失敗します。

ロックを呼び出す Bがロックを呼び出す Aは「失敗した」応答を取得します Bは「成功した」応答を受け取ります

シーケンシャル履歴とは、すべての呼び出しに即時の応答がある履歴ですつまり、呼び出しと応答は瞬時に行われると見なされます。シーケンシャル履歴には実際の同時実行性がないため、簡単に説明できます。前の例はシーケンシャルではなかったため、推論するのは困難です。これが線形化可能性の出番です。

歴史次のような完了した操作の線形順序がある場合、 線形化可能です。

  1. で完了したすべての操作について、操作は、すべての操作が順番に1つずつ完了した場合に操作が返すのと同じ結果を実行に返します。
  2. op 2が開始(呼び出し)する前に操作op 1が完了(応答を取得)した場合、 op1はop2に先行します。[1]

言い換えると:

  • その呼び出しと応答を並べ替えて、順次履歴を生成できます。
  • そのシーケンシャル履歴は、オブジェクトのシーケンシャル定義に従って正しいです。
  • 元の履歴で応答が呼び出しの前にある場合でも、順次並べ替えでは応答の前にある必要があります。

(ここでの最初の2つの箇条書きは直列化可能性と一致することに注意してください。操作はある順序で発生するように見えます。これは線形化可能性に固有の最後の点であり、したがってHerlihyとWingの主な貢献です。)[1]

上記のロックの例を並べ替える2つの方法を見てみましょう。

ロックを呼び出す Aは「失敗した」応答を取得します Bがロックを呼び出す Bは「成功した」応答を受け取ります

Aの応答の下でBの呼び出しを並べ替えると、順次履歴が生成されます。すべての操作が明白な順序で行われるようになったため、これは簡単に推論できます。残念ながら、オブジェクトのシーケンシャル定義と一致しません(プログラムのセマンティクスと一致しません)。Aはロックを正常に取得し、Bはその後中止する必要があります。

Bがロックを呼び出す Bは「成功した」応答を受け取ります ロックを呼び出す Aは「失敗した」応答を取得します

これは別の正しいシーケンシャル履歴です。線形化でもあります!線形化可能性の定義は、呼び出しに先行する応答が並べ替えられることを排除するだけであることに注意してください。元の履歴には呼び出し前に応答がなかったため、必要に応じて並べ替えることができます。したがって、元の履歴は確かに線形化可能です。

オブジェクト(履歴ではなく)は、その使用のすべての有効な履歴を線形化できる場合、線形化可能です。これは証明するのがはるかに難しいアサーションであることに注意してください。

線形化可能性と直列化可能性

次の履歴について考えてみます。ここでも、2つのオブジェクトがロックと相互作用しています。

ロックを呼び出す 正常にロック Bはロック解除を呼び出します Bは正常にロックを解除します ロック解除を呼び出します 正常にロック解除

AとBの両方がロックを保持するポイントがあるため、この履歴は無効です。さらに、順序付けルールに違反せずに、有効なシーケンシャル履歴に並べ替えることはできません。したがって、線形化可能ではありません。ただし、直列化可能性の下では、Bのロック解除操作はAの元のロックのに移動できます。これは有効な履歴です(オブジェクトがロック状態で履歴を開始すると仮定)。

Bはロック解除を呼び出します Bは正常にロックを解除します ロックを呼び出す 正常にロック ロック解除を呼び出します 正常にロック解除

AとBの間で通信する代替手段がない場合、この並べ替えは賢明です。並べ替えの制限により、複数の線形化可能なオブジェクトが全体として線形化可能であることが保証されるため、個々のオブジェクトを個別に検討する場合、線形化可能性が向上します。

線形化ポイント

この線形化可能性の定義は、次のようになります。

  • すべての関数呼び出しには、呼び出しと応答の間のある瞬間に線形化ポイントがあります。
  • すべての関数は、線形化ポイントで即座に発生し、シーケンシャル定義で指定されたとおりに動作するように見えます。

この代替案は通常、証明するのがはるかに簡単です。また、主にその直感性により、ユーザーとして推論するのもはるかに簡単です。瞬時に、または不可分に発生するこの特性により、より長い「線形化可能」の代わりにアトミックという用語が使用されます。[1]

以下の例では、コンペア・アンド・スワップに基づいて構築されたカウンターの線形化ポイントは、最初の(そして唯一の)成功した​​コンペア・アンド・スワップ更新の線形化ポイントです。ロックを使用して構築されたカウンターは、ロックが保持されている間はいつでも線形化すると見なすことができます。これは、競合する可能性のある操作がその期間中の実行から除外されるためです。

プリミティブアトミック命令

[関連性の質問]

プロセッサには、ロックおよびロックフリーおよび待機フリーのアルゴリズムを実装するために使用できる命令があります。割り込みを一時的に禁止し、現在実行中のプロセスをコンテキストスイッチできないようにする機能も、ユニプロセッサで十分です。これらの命令は、コンパイラおよびオペレーティングシステムの作成者によって直接使用されますが、高水準言語のバイトコードおよびライブラリ関数として抽象化および公開されます。

ほとんどの[要出典] プロセッサには、メモリに関してアトミックではないストア操作が含まれています。これには、複数ワードのストアと文字列操作が含まれます。ストアの一部が完了したときに優先度の高い割り込みが発生した場合は、割り込みレベルが戻ったときに操作を完了する必要があります。割り込みを処理するルーチンは、変更されるメモリを変更してはなりません。割り込みルーチンを作成するときは、これを考慮することが重要です。

割り込みなしで完了する必要のある命令が複数ある場合は、一時的に割り込みを無効にするCPU命令を使用します。これは、ほんの数命令に保つ必要があり、割り込みに対する許容できない応答時間や割り込みの喪失を回避するために、割り込みを再度有効にする必要があります。マルチプロセッサ環境では、割り込みが発生するかどうかに関係なく、各CPUがプロセスに干渉する可能性があるため、このメカニズムでは不十分です。さらに、命令パイプラインが存在する場合、Cyrix comaバグのように、中断できない操作が無限ループに連鎖してサービス拒否攻撃を引き起こす可能性があるため、セキュリティ上のリスクがあります。

C標準SUSv3sig_atomic_t、単純なアトミック読み取りと書き込みを提供します。インクリメントまたはデクリメントは、アトミックであることが保証されていません。[3]より複雑な不可分操作がC11で利用可能であり、これはを提供しますstdatomic.hコンパイラーは、ハードウェア機能またはより複雑なメソッドを使用して操作を実装します。例はGCCのlibatomicです。

ARM命令セットは、プロセッサに実装された専用モニターを使用して特定のアドレスのメモリアクセスを追跡することにより、アトミックメモリアクセスを実装するために使用できる命令を提供LDREXします。[4] ただし、の呼び出しの間でコンテキストスイッチが発生した場合、ドキュメントには失敗することが記載されており、操作を再試行する必要があることを示しています。 STREXLDREXSTREXSTREX

高レベルの不可分操作

線形化可能性を実現する最も簡単な方法は、クリティカルセクションでプリミティブ操作のグループを実行することです。厳密に言えば、線形化可能性に違反しない限り、独立した操作がクリティカルセクションとオーバーラップすることを慎重に許可できます。このようなアプローチでは、多数のロックのコストと並列処理の増加によるメリットのバランスをとる必要があります。

研究者に好まれる別のアプローチ(ただし、ソフトウェア業界ではまだ広く使用されていません)は、ハードウェアによって提供されるネイティブのアトミックプリミティブを使用して線形化可能なオブジェクトを設計することです。これには、利用可能な並列処理を最大化し、同期コストを最小化する可能性がありますが、オブジェクトが正しく動作することを示す数学的証明が必要です。

これら2つの有望なハイブリッドは、トランザクションメモリの抽象化を提供することです。クリティカルセクションと同様に、ユーザーは他のスレッドから分離して実行する必要があるシーケンシャルコードにマークを付けます。次に、実装により、コードがアトミックに実行されるようになります。このスタイルの抽象化は、データベースと対話するときに一般的です。たとえば、Spring Frameworkを使用する場合、メソッドに@Transactionalアノテーションを付けると、囲まれたすべてのデータベースインタラクションが単一のデータベーストランザクションで確実に発生します。トランザクションメモリはさらに一歩進んで、すべてのメモリ相互作用がアトミックに発生することを保証します。データベーストランザクションと同様に、トランザクション、特にデータベースおよびメモリ内トランザクションの構成に関して問題が発生します。

線形化可能なオブジェクトを設計する際の一般的なテーマは、オールオアナッシングインターフェイスを提供することです。操作が完全に成功するか、失敗して何もしません。ACIDデータベースでは、この原則をアトミック性と呼んでいます。)操作が失敗した場合(通常は同時操作が原因)、ユーザーは再試行する必要があり、通常は別の操作を実行します。例えば:

  • Compare-and-swapは、場所の内容が指定された古い値と一致する場合にのみ、新しい値を場所に書き込みます。これは通常、read-modify-CASシーケンスで使用されます。ユーザーは場所を読み取り、書き込む新しい値を計算して、CAS(コンペアアンドスワップ)で書き込みます。値が同時に変更されると、CASは失敗し、ユーザーは再試行します。
  • Load-link / store-conditionalは、このパターンをより直接的にエンコードします。ユーザーは、load-linkを使用して場所を読み取り、書き込む新しい値を計算して、store-conditionalを使用して書き込みます。値が同時に変更された場合、SC(ストア条件付き)は失敗し、ユーザーは再試行します。
  • データベーストランザクションでは、同時操作(デッドロックなど)が原因でトランザクションを完了できない場合、トランザクションは中止され、ユーザーは再試行する必要があります。

線形化可能性の例

カウンター

線形化可能性の能力と必要性を示すために、さまざまなプロセスが増分できる単純なカウンターを検討します。

複数のプロセスがアクセスできるカウンターオブジェクトを実装したいと思います。多くの一般的なシステムは、イベントが発生した回数を追跡するためにカウンターを利用します。

カウンターオブジェクトには複数のプロセスからアクセスでき、2つの操作が可能です。

  1. インクリメント-カウンターに格納されている値に1を加算し、確認応答を返します
  2. 読み取り-カウンターに格納されている現在の値を変更せずに返します。

共有レジスタを使用して、このカウンタオブジェクトの実装を試みます

線形化不可能であることがわかる最初の試みは、プロセス間で1つの共有レジスタを使用する次の実装です。

非アトミック

素朴で非原子的な実装:

インクリメント:

  1. レジスタRの値を読み取ります
  2. 値に1を追加します
  3. 新しい値をレジスタRに書き戻します

読む:

レジスタRの読み取り

次の例に示すように、この単純な実装は線形化できません。

値0を持つように初期化された単一のカウンターオブジェクトにアクセスする2つのプロセスが実行されていると想像してください。

  1. 最初のプロセスは、レジスタの値を0として読み取ります。
  2. 最初のプロセスは値に1を加算し、カウンターの値は1である必要がありますが、新しい値をレジスターに書き戻す前に、2番目のプロセスが実行されている間に中断される可能性があります。
  3. 2番目のプロセスは、レジスタ内の値を読み取りますが、これはまだ0に等しいです。
  4. 2番目のプロセスは、値に1を追加します。
  5. 2番目のプロセスは新しい値をレジスタに書き込みます。レジスタの値は1になります。

2番目のプロセスの実行が終了し、最初のプロセスは中断したところから実行を継続します。

  1. 最初のプロセスは1をレジスタに書き込みますが、他のプロセスがレジスタの値をすでに1に更新していることを認識していません。

上記の例では、2つのプロセスがincrementコマンドを呼び出しましたが、オブジェクトの値は、本来あるべき2ではなく0から1にしか増加しませんでした。システムが線形化できないため、増分操作の1つが失われました。

上記の例は、データ構造の実装を慎重に検討する必要があることと、線形化可能性がシステムの正確性にどのように影響するかを示しています。

アトミック

線形化可能またはアトミックカウンターオブジェクトを実装するには、以前の実装を変更して、各プロセスPi独自のレジスタRiを使用するようにします

各プロセスは、次のアルゴリズムに従って増分および読み取りを行います。

インクリメント:

  1. レジスタRiの値を読み取ります
  2. 値に1を追加します。
  3. 新しい値をRiに書き戻します

読む:

  1. レジスタR1 、 R 2 、... Rnを読み取ります
  2. すべてのレジスタの合計を返します。

この実装は、元の実装の問題を解決します。このシステムでは、インクリメント操作は書き込みステップで線形化されます。インクリメント操作の線形化ポイントは、その操作がレジスタRiに新しい値を書き込むときです読み取りによって返される値が各レジスタRiに格納されているすべての値の合計に等しい場合、読み取り操作はシステム内のあるポイントに線形化されます

これは簡単な例です。実際のシステムでは、操作がより複雑になる可能性があり、発生するエラーは非常に微妙です。たとえば、メモリから64ビット値を読み取ることは、実際には2つの32ビットメモリ位置の2つの連続した読み取りとして実装される場合があります。プロセスが最初の32ビットのみを読み取り、次の32ビットを読み取る前にメモリ内の値が変更された場合、元の値も新しい値もありませんが、混合された値になります。

さらに、プロセスが実行される特定の順序によって結果が変わる可能性があり、そのようなエラーの検出、再現、およびデバッグが困難になります。

コンペアアンドスワップ

ほとんどのシステムは、メモリ位置から読み取り、値をユーザーが提供する「期待される」値と比較し、2つが一致する場合は「新しい」値を書き出して、更新が成功したかどうかを返すアトミックなコンペアアンドスワップ命令を提供します。 。これを使用して、非アトミックカウンターアルゴリズムを次のように修正できます。

  1. メモリ位置の値を読み取ります。
  2. 値に1を追加します。
  3. コンペアアンドスワップを使用して、増分値を書き戻します。
  4. コンペアアンドスワップによって読み込まれた値が最初に読み込んだ値と一致しなかった場合は、再試行してください。

コンペアアンドスワップは瞬時に発生する(または発生しているように見える)ため、進行中に別のプロセスが場所を更新した場合、コンペアアンドスワップは失敗することが保証されます。

フェッチアンドインクリメント

多くのシステムは、メモリ位置から読み取り、無条件に新しい値(古い値に1を加えたもの)を書き込み、古い値を返すアトミックなフェッチおよびインクリメント命令を提供します。これを使用して、非アトミックカウンターアルゴリズムを次のように修正できます。

  1. fetch-and-incrementを使用して、古い値を読み取り、インクリメントされた値を書き戻します。

フェッチアンドインクリメンタルを使用すると、コンペアアンドスワップよりも一部のアルゴリズム(ここに示すようなアルゴリズム)の方が常に優れています[ 5]。フェッチアンドインクリメントのみを使用してまったく実装できない他のアルゴリズム。したがって、フェッチアンドインクリメントとコンペアアンドスワップ(または同等の命令)の両方を備えたCPU設計は、どちらか一方のみを備えたものよりも優れた選択肢となる可能性があります。[5]

ロック

別のアプローチは、ナイーブアルゴリズムをクリティカルセクションに変え、ロックを使用して他のスレッドがそれを中断するのを防ぐことです。非アトミックカウンターアルゴリズムをもう一度修正します。

  1. クリティカルセクション(ステップ2〜4)を同時に実行することから他のスレッドを除外して、ロックを取得します。
  2. メモリ位置の値を読み取ります。
  3. 値に1を追加します。
  4. インクリメントされた値をメモリ位置に書き戻します。
  5. ロックを解除します。

この戦略は期待どおりに機能します。ロックは、解放されるまで他のスレッドが値を更新するのを防ぎます。ただし、アトミック操作を直接使用する場合と比較すると、ロックの競合により大きなオーバーヘッドが発生する可能性があります。したがって、プログラムのパフォーマンスを向上させるには、単純なクリティカルセクションを非ブロッキング同期のアトミック操作に置き換えることをお勧めします(コンペアアンドスワップおよびフェッチアンドインクリメントを使用したカウンターに対して行ったように)。逆ですが、残念ながら、大幅な改善は保証されておらず、ロックフリーアルゴリズムは簡単に複雑になりすぎて、努力する価値がありません。

も参照してください

参照

  1. ^ a b c d Herlihy、Maurice P .; ウィング、ジャネットM.(1990)。「線形化可能性:並行オブジェクトの正当性条件」。プログラミング言語とシステムに関するACMトランザクション12(3):463–492。CiteSeerX10.1.1.142.5315 _ 土井10.1145/78969.78972S2CID228785 _
  2. ^ Shavit、NirおよびTaubenfel、Gadi(2016)。「緩和されたデータ構造の計算可能性:例としてのキューとスタック」(PDF)分散コンピューティング29(5):396–407。土井10.1007/s00446-016-0272-0S2CID16192696_  {{cite journal}}:CS1 maint:複数の名前:著者リスト(リンク
  3. ^ ケリスク、マイケル(2018年9月7日)。Linuxプログラミングインターフェイススターチプレスはありません。ISBN 9781593272203–Googleブックス経由。
  4. ^ 「ARM同期プリミティブ開発記事」
  5. ^ a b フィッチ、信仰; ヘンドラー、ダニー; Shavit、Nir(2004)。「条件付き同期プリミティブの固有の弱点について」。分散コンピューティングの原理に関する第23回ACMシンポジウムの議事録–PODC'04ニューヨーク州ニューヨーク:ACM。pp。80–87。土井10.1145/1011767.1011780ISBN 978-1-58113-802-3S2CID9313205 _

さらに読む