ライブネス
From Wikipedia, the free encyclopedia
ライブネスとは、並行システムの特性の1つで、同時実行されるコンポーネント（プロセス）がクリティカルセクション（複数のプロセスが同時に実行できないプログラムの部分）で「交代」しなければならないにもかかわらず、システムが進行することを意味する[1]。ライブネスの保証は、オペレーティングシステムや分散システムにおいて重要な特性である[2]。
より一般的には「何か良いことが最終的に起こる」ことを示すのがライブネス特性であり、「何か悪いことが起こらない」ことを示すのが安全性特性である。安全特性に違反した場合、その違反（「悪い」イベントの発生）を示す有限実行が必ず存在するが、ライブネス特性は、分散システムの有限実行では、「良い」イベントが後になっても発生する可能性があるため、違反できない。最終的な一貫性はライブネス特性の一例である。すべての線形時間特性は、安全性特性とライブネス特性の交点として表すことができる。与えられた安全性特性の違反が有限の目撃者を認めるのに対し、ライブネス特性の違反は、証明として使用できる有限の目撃者がいないため、立証が困難な場合がある。
ライブネスにはいくつかの形態があります。以下のものは、ある相互排除（ミューテックス）装置で保護されたクリティカル・セクションを持つマルチプロセス・システムの観点から定義されています。すべてのプロセスがミューテックスを正しく使用していると仮定し、クリティカルセクションの実行が終了することを進捗と定義する。
- デッドロックからの解放は、弱いながらもライブネスの一形態である。複数のプロセスと、相互排除装置で保護された1つのクリティカルセクションを持つシステムを考える。このようなシステムは、ある時点であるプロセス群がクリティカルセクションへのアクセスをめぐって競合しているときに、後の時点であるプロセスが最終的に前進する場合、デッドロックフリーであると言われます。そのプロセスは前述のグループに属する必要はなく、それ以前あるいはそれ以降にアクセスを得たかもしれない。
- スタベーションからの自由（または「有限のバイパス」）は、デッドロックの自由よりも強力なライブ性保証です。これは、臨界領域へのアクセスを争うすべてのプロセスが、最終的に進歩することを意味する。スタベーションのないシステムは、デッドロックのないシステムでもある。
- さらに強力なのが bounded bypass の要件である。これは、n個のプロセスが臨界領域へのアクセスを競っている場合、ある関数fについて他のプロセスから最大f(n)回バイパスされた後、各プロセスが進展することを意味している。
ライブネスと安全性
B. Alpernによれば、デッドロックフリーは安全性の性質である。Alpernは、システムの状態が、デッドロックがある状態（赤の状態）と、デッドロックがない状態（緑の状態）に分けられることを前提としている。システムが永遠に緑の状態にとどまる（あるいは、赤の状態にならない）という性質は、安全性の性質である。しかし、緑の状態と赤の状態の区別がつかない場合、最終的にシステム内のいずれかのプロセスが進化するという性質をライブネス性質という。
