non-blocking algorithms

参考wiki
1.概要

non-blockingアルゴリズム:1つのスレッドの失敗または一時停止は、他のスレッドの失敗または一時停止を招くことはありません.システム-wide progressが保証される場合、non-blockingアルゴリズムはlock-freeである.per-thread progressが保証されている場合はwait-freeです.

2.non-blockingアルゴリズムを導入する理由

従来のロック方法には何か問題がありますか?従来のマルチスレッドプログラミング方法は、ロックを使用して共有リソースへのアクセスを同期することである.プログラマは、同期原語メカニズム(mutexes,semaphores,cirtical sections)を使用して、スレッドが同時に実行されないことを確認し、共有データ構造が破損しないことを確認します.しかし、多くの場合、ブロックスレッドは私たちが望んでいるものではありません.1)ブロックされたスレッドが常に高優先度またはリアルタイムタスク2)ロック間のインタリーブを実行している場合、deadlock,livelock,priority inversion 3)粗粒度ロック(coarse-grained locking)と細粒度ロック(fine-grained locking)の間のトレードオフを招き、前者は並列を著しく減少させ、後者はロックのオーバーヘッドを増加させ、エラーを発生しやすい.

non-blockingにはどんなメリットがありますか?1)上記の欠点の影響を受けない2)割り込み処理プログラムにおいても安全(interrupt handlers)であり,プリエンプトされたスレッドが回復できなくても進捗は維持できる可能性がある.ただし、強制的に占有されたスレッドはロックの所有者である可能性があるため、ロックを使用することはできません.しかし,この問題は臨界領域で割り込み要求を閉じることによって回避できる.3)lock-freeデータ構造は、シリアルアクセスを維持することなく、マルチコアプロセッサ上でより良いパフォーマンスを得ることができる共有データ構造のパフォーマンスを向上させることができます.

3.実現

少数の場合を除いて、non-blockingアルゴリズムは原子のread-modify-write原語を使用し、この原語ハードウェアは提供しなければならず、最も有名なのはCASである.read-modify-write(wiki参照):test-and-set、fetch-and-add、compare-and-swap、LL/SCを含む原子操作のクラスを表し、これらの操作はメモリ位置を同時に読み書きします.これらの操作は、マルチスレッドアプリケーションにおいてデータ競合を防止することができる.一般的にmutexesまたはsemaphoresを実装するために用いられ、non-blocking同期でもよく用いられる.

臨界領域は、基本的にこれらの原語に基づく標準インタフェースを用いて実現される.(一般的には、これらの原語で実現される臨界領域でも閉塞が発生する).

ソフトウェアtransactional memoryは、効率的なnon-blockingコードを書く標準抽象を提供することを約束した.STMについて(wiki参照):データベーストランザクションと同様の同時制御メカニズムで、同時計算で共有メモリへのアクセスを制御します.ロック同期に基づく代替案です.1つのトランザクションとは、共有メモリのいくつかのカラムの読み取りおよび書き込みロジックが一瞬にして発生し、その間のステータスが他のトランザクションには表示されないことを意味します.

stacks queues setsおよびhash tablesのnon-blockingバージョンは、プログラム間で非同期でデータを交換することを保証します.Herb Sutter queue Herb Sutter queue

一部のデータ構造は、1)a single-reader single-writer ring buffer FIFOメモリバリア実装(memory barrier)2)Read-copy-update with a single writer and any number of readers読者はwait-freeである.ライターはlock-freeで、Read-copy-update(wiki参照)についてメモリを回収する必要があるまで:読み取り性能が重要な場所であり、space-time tradeoffの一例でもあり、より多くの空間でより良い性能を取り替える.(更新されたreaderは新しい値を読み取ることができる)RCUによって保護された共有データ構造では、読み取り操作はロックを必要とせずにアクセスできるが、書き込み操作はアクセス時にまず1つのコピーをコピーし、その後コピーを修正し、最後に適切なタイミングで元のデータを指すポインタを新しい修正されたデータに再指向する.このタイミングは、そのデータを参照しているすべてのCPUが共有データの操作を終了することである.Linuxカーネルにおけるメモリ管理はRCUメカニズムに多く応用されている.各メモリオブジェクトに原子カウンタを追加して、オブジェクトの現在のアクセス数を続行します.他のプロセスがオブジェクトにアクセスしていない場合(カウンタは0)、メモリの回収が許可されます.3)Read-copy-update with multiple writers and any number of readers. 読者はwait-freeです.ライターは通常lockで通過し、obstruction-free

ではない.

いくつかのライブラリはlock-freeテクニックC++libcds liblfds Concurrency Kit

を使用しています.
4.同時性レベル
4.1 wait-freedom待機なし同時(non-blocking)

は最強レベルの進化保証であり、system-wide throughput with starvation-freedomを保証する.Wait-freedomとは、各スレッドが外部条件を待つことなく常に実行され、プロセス全体の任意の操作が限られたステップで完了することを意味します.これは、最も高い同時レベルであり、ブロックはありません.リアルタイムシステムには重要です.

原子操作実装を直接呼び出すことができるアルゴリズムまたはプログラムは、以下のincrement_のようなWait-freeに属すると簡単に考えることができる.reference_counter関数はwait-freeで、atomic_をカプセル化しています.incrementという原子自己増殖原語では、複数のスレッドが同じメモリ変数を同時に呼び出すことができ、ブロックする必要はありません(実際にはブロックされています.バスロックレベルです).CASクラスの呼び出しはwait-freeではありません.wait-freeの原語には内部ループが含まれていないことに注意してください.CAS原語は通常、「成功するまでループ」のループの内部に含まれます.

wait-freeの最新実装

Kogan, Alex; Petrank, Erez (2011). *Wait-free queues with multiple enqueuers and dequeuers*. Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 223–234. [doi](https://en.wikipedia.org/wiki/Digital_object_identifier "Digital object identifier"):[10.1145/1941553.1941585](https://doi.org/10.1145/1941553.1941585). [ISBN](https://en.wikipedia.org/wiki/International_Standard_Book_Number "International Standard Book Number") [978-1-4503-0119-0](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4503-0119-0 "Special:BookSources/978-1-4503-0119-0").

Kogan, Alex; Petrank, Erez (2012). *A method for creating fast wait-free data structures*. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 141–150. [doi](https://en.wikipedia.org/wiki/Digital_object_identifier "Digital object identifier"):[10.1145/2145816.2145835](https://doi.org/10.1145/2145816.2145835). [ISBN](https://en.wikipedia.org/wiki/International_Standard_Book_Number "International Standard Book Number") [978-1-4503-1160-1](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4503-1160-1 "Special:BookSources/978-1-4503-1160-1").

Kogan, Alex; Petrank, Erez (2012). *A method for creating fast wait-free data structures*. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 141–150. [doi](https://en.wikipedia.org/wiki/Digital_object_identifier "Digital object identifier"):[10.1145/2145816.2145835](https://doi.org/10.1145/2145816.2145835). [ISBN](https://en.wikipedia.org/wiki/International_Standard_Book_Number "International Standard Book Number") [978-1-4503-1160-1](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4503-1160-1 "Special:BookSources/978-1-4503-1160-1").

4.2 lock-freedomロックなし同時(non-blocking)

は単一スレッドstarveを許可するがsystem-wide throughput.十分な時間実行されるスレッドのうち、少なくとも1つのスレッドが進化できるのはlock-freeである.Lock-freedomとは、システム全体が全体として稼働していることを意味し、システム内部の単一スレッドが一定期間飢餓する可能性があります.これはwait-freedomよりも弱い同時レベルですが、システム全体的にはブロックされていません.すべてのwait-freeのアルゴリズムは明らかにlock-freeの要求を満たしている.ロックフリーアルゴリズムは、通常、原語CASを同期することによって実現される.

スレッドが一時停止されると、lock−freeアルゴリズムは、残りのスレッドが依然として進化することを保証することができる.したがって、2つのスレッドが同じmutex lockまたはspinlockと競合する場合、アルゴリズムはlock-freeではありません.ロックを取得したスレッドが停止すると、別のスレッドがブロックされるためです.

いくつかの無限の動作は、アルゴリズムがlock−freeである場合、いくつかのプロセッサ上で有限ステップで完了することができる.wait-freeはすべての処理が有限ステップで完了することを要求し、lock-freeは部分的に有限ステップで完了することを要求する.

ロックレスアルゴリズムは4つの段階で実行できます:自分の操作を完了します;assisting an obstructing操作;abort obstructing操作;待ちます.assist,abort or waitのタイミングは競合マネージャによって決定され,より良いスループット(throughput)や高優先度の操作の低遅延を保証するために最適化することができる.

4.3 obstruction-freedom (non-blocking)

は、任意の時点で、obstruction-freeという限られたステップで、独立したスレッド(すべてのobstrctingスレッドが保留されている)がその動作を完了することができる.bstruction-freeとは、任意の時点で、孤立した実行スレッドの各操作が有限ステップ内で終了することを意味する.競合がない限り、スレッドは継続的に実行され、共有データが変更されると、Obstruction-freeは完了した一部の操作を中止し、ロールバックすることを要求し、obstruction-freeはコンカレントレベルがより低い非ブロックコンカレントであり、このアルゴリズムは競合操作が発生しない場合に単一プログラムの実行進捗保証を提供する.すべてのLock-FreeのアルゴリズムはObstruction-freeである.

obstruction-freedomは、任意の部分的に完了した操作を中止し、変更をロールバックできることを要求します.同時ヘルプを破棄すると、より簡単なアルゴリズムが実現され、検証が容易になります.競合マネージャは、継続的なlive-lockingを防止する必要があります.

いくつかのobstruction-freedomアルゴリズムは、データ構造において1対の「コンシステンシタグ」を使用する.データ構造の読み取りは、まず一貫性フラグを読み取り、その後、関連するデータを内部バッファに読み込む.次に、別のタグを読み込み、2つのタグを比較します.タグが同じ場合、データは一致します.現在のリード・プロシージャが別のデータ構造を更新するプロセスによって中断される可能性があるため、タグが一致しない可能性があります.この場合、プロセスは内部バッファのデータを破棄し、再試行します.

4.4 blockingアルゴリズム——一般ロック