ウェイトフリーダム

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

ウェイトフリーダム（Wait-freedom）

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/11 05:42 UTC 版)

「Lock-freeとWait-freeアルゴリズム」の記事における「ウェイトフリーダム（Wait-freedom）」の解説

Wait-freedom（ウェイトフリーダム）は、システム全体のスループット保証とスタベーション防止を組み合わせた、最強のノンブロッキング進行保証である。アルゴリズムはすべての操作に、その操作が完了するまでにアルゴリズムが取るステップ数の制限がある場合、ウェイトフリーとなる。この特性は、リアルタイムシステムにとって重要であり、性能コストが高すぎない限り、常にあった方が良いものである。 1980年代には，すべてのアルゴリズムがウェイトフリーで実装できることが示され、ユニバーサルコンストラクションと呼ばれるシリアルコードからの変換が数多く実証されている。しかし結果として得られる性能は、一般的にはナイーブなブロッキング設計にさえも及ばない。その後、いくつかの論文でユニバーサルコンストラクションの性能が改善されたが、それでも性能はブロッキングデザインを大きく下回っている。 ウェイトフリーなアルゴリズムを作ることの難しさについては、いくつかの論文で研究されている。例えば、広く利用されているアトミックな条件付きプリミティブであるCASやLL/SCでは、多くの一般的なデータ構造に対して、スレッド数に応じてメモリコストが線形に増加することなく、スタベーションのない実装を行うことができないことが示されている。 しかし実際には、この下限値は実際の障害にはならない。というのもスレッドごとに共有メモリにキャッシュラインや排他的予約グラニュール（ARMでは最大2KB）を使ってストアを行うことは、実用的なシステムではコストがかかりすぎるとは考えられていないからである。 ウェイトフリーなアルゴリズムは、2011年までは研究でも実践でも稀だった。しかし2011年、KoganとPetrankは、一般的なハードウェアで一般的に利用可能なCASプリミティブをベースにしたウェイトフリーキューを発表した。彼らの構築は、実際によく使われる効率的なキューであるMichaelとScottのロックフリーキューを拡張したものである。KoganとPetrankによる後続の論文では、ウェイトフリーのアルゴリズムを高速化するための手法を提供し、この手法を用いてウェイトフリーキューを実質的にロックフリーのものと同程度に高速化した。続くTimnat and Petrankの論文では、ロックフリーのデータ構造からウェイトフリーのデータ構造を自動的に生成するメカニズムを提供した。このようにして、現在では多くのデータ構造でウェイトフリーな実装が可能となっている。