線形化可能性

並行プログラミングでは、操作 (または操作のセット) が呼び出しイベントと応答イベントの順序付けられたリストで構成され、応答イベントを追加することで拡張できる場合、その 操作は線形化可能です。

1. 拡張されたリストは、連続した履歴として再表現できます（シリアル化可能です）。
2. その連続した履歴は、元の拡張されていないリストのサブセットです。

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

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

線形化可能性は、1987 年にHerlihyとWingによって一貫性モデルとして初めて導入されました。これには、「アトミック操作とは、同時操作によって中断されない (または中断されない) 操作」など、操作の開始と終了がいつと見なされるかが通常曖昧である、より限定的なアトミックの定義が含まれていました。

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

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

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

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

完了した操作が次のような 線形順序になっている場合、履歴は線形化可能です。${\displaystyle \sigma}$

1. で完了したすべての操作について、操作は、すべての操作が 1 つずつ順番に完了した場合に操作が返す結果と同じ結果を実行時に返します。${\displaystyle \sigma}$${\displaystyle \sigma}$
2. オペレーション op _{1が op 2}が開始（呼び出し）する前に完了（応答を取得）した場合、 op _{1 は}op ₂に先行します。^[1]${\displaystyle \sigma}$

言い換えると：

• 呼び出しと応答を並べ替えて、連続した履歴を生成することができます。
• オブジェクトの順次定義に従って順次履歴が正しいこと。
• 応答が元の履歴で呼び出しに先行していた場合、順次並べ替えでも応答が呼び出しに先行する必要があります。

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

上記のロックの例を並べ替える 2 つの方法を検討してください。

B の呼び出しを A の応答の下に並べ替えると、連続した履歴が生成されます。すべての操作が明らかな順序で行われるため、これは簡単に推測できます。ただし、オブジェクトの連続した定義と一致しません (プログラムのセマンティクスと一致しません)。A はロックを正常に取得し、その後 B が中止されるはずです。

これは、もう 1 つの正しい順次履歴です。これは、順次定義に一致するため、線形化でもあります。線形化可能性の定義は、呼び出しに先行する応答の並べ替えを禁止するだけであることに注意してください。元の履歴には呼び出し前の応答がないため、並べ替えることができます。したがって、元の履歴は確かに線形化可能です。

オブジェクト (履歴とは対照的に) は、その使用に関する有効な履歴がすべて線形化できる場合、線形化可能です。これは証明するのがはるかに難しい主張です。

再び、ロックと相互作用する 2 つのオブジェクトの次の履歴について考えてみましょう。

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

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

この線形化可能性の定義は次のものと同等です。

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

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

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

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

• アトミック読み取り書き込み;
• アトミック スワップ (一部のBurroughs メインフレームの RDLK 命令、および XCHG x86 命令)。
• テストアンドセット;
• フェッチして追加;
• 比較とスワップ;
• リンクをロード/ストア条件付き。

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

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

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

ARM命令セットは、プロセッサに実装された排他的モニタを使用して特定のアドレスのメモリアクセスを追跡することにより、アトミックメモリアクセスを実装するために使用できる命令LDREXと命令を提供します。 ^[4]ただし、とへの呼び出し間でコンテキストスイッチが発生した場合、ドキュメントには、操作を再試行する必要があることを示すために、が失敗することが示されています。64ビットARMv8-Aアーキテクチャの場合、バイト、ハーフワード、ワード、およびダブルワードサイズの命令と命令が提供されます。 ^[5]STREXLDREXSTREXSTREXLDXRSTXR

線形化可能性を実現する最も簡単な方法は、一連の基本操作をクリティカル セクションで実行することです。厳密に言えば、線形化可能性に違反しない限り、独立した操作がクリティカル セクションと重なることは慎重に許可されます。このようなアプローチでは、多数のロックにかかるコストと並列性の向上による利点のバランスを取る必要があります。

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

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

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

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

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

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

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

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

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

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

単純で非アトミックな実装:

インクリメント：

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

読む：

レジスタRの読み取り

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

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

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

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

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

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

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

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

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

インクリメント：

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

読む：

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

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

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

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

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

1. メモリ位置の値を読み取ります。
2. 値に1を加算します。
3. 比較とスワップを使用して増分された値を書き戻します。
4. 比較とスワップによって読み込まれた値が最初に読み取った値と一致しなかった場合は再試行します。

比較とスワップは瞬時に発生する（または発生するように見える）ため、処理中に別のプロセスが場所を更新すると、比較とスワップは必ず失敗します。

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

1. フェッチと増分を使用して、古い値を読み取り、増分された値を書き戻します。

フェッチとインクリメントを使用する方が、ここで示したようないくつかのアルゴリズムではコンペアアンドスワップよりも常に優れています（メモリ参照が少なくて済みます） 。 ^[6]ハーリヒーは以前、フェッチとインクリメントだけでは実装できない他の特定のアルゴリズムではコンペアアンドスワップの方が優れていることを証明しました。そのため、フェッチとインクリメントと比較とスワップ（または同等の命令）の両方を備えたCPU設計は、どちらか一方だけを備えたものよりも優れた選択肢となる可能性があります。^[6]

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

1. ロックを取得し、他のスレッドが同時にクリティカル セクション (手順 2 ～ 4) を実行できないようにします。
2. メモリ位置の値を読み取ります。
3. 値に1を加算します。
4. 増分した値をメモリの場所に書き戻します。
5. ロックを解除します。

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

• アトミックトランザクション
• 一貫性モデル
• 酸
• 読み取りコピー更新(RCU)
• 読み取り、変更、書き込み
• 確認から使用までの時間

• Herlihy, Maurice P.; Wing, Jeannette M. ( 1987)。「並行オブジェクトの公理」。プログラミング言語の原理に関する第 14 回 ACM SIGACT-SIGPLAN シンポジウム議事録 - POPL '87。pp. 13–26。doi :10.1145/ 41625.41627。ISBN 978-0-89791-215-0. S2CID  16017451。
• Herlihy, Maurice P. (1990).高度に並行なデータ構造を実装するための方法論. 第 25 巻. pp. 197–206. CiteSeerX  10.1.1.186.6400 . doi :10.1145/99164.99185. ISBN 978-0-89791-350-8。 {{cite book}}:|journal=無視されました (ヘルプ)
• Herlihy, Maurice P.; Wing, Jeannette M. (1990). 「線形化可能性: 並行オブジェクトの正当性条件」. ACM Transactions on Programming Languages and Systems . 12 (3): 463–492. CiteSeerX  10.1.1.142.5315 . doi :10.1145/78969.78972. S2CID  228785.
• Aphyr. 「強い一貫性モデル」。aphyr.com。Aphyr。2018年4月13日閲覧。