線形化可能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/01/23 10:14 UTC 版)
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2021年11月) |
並行プログラミングにおいて操作（または操作の集合）は、呼び出しイベントと応答イベント（コールバック）の順序付きリストで構成されており、応答イベントを追加することで以下のように拡張できる場合、線形化可能である。
- 拡張されたリストは逐次履歴として再表現することができる（直列化可能である）。
- その逐次履歴は元の拡張されていないリストの部分集合である。
これは、非公式には、変更されていないイベントのリストは、その呼び出しが直列化可能であるが、直列スケジュールの応答の一部がまだ戻ってきていない場合に限り、線形化可能であることを意味する[1]。
並行システムではプロセスが同時に共有オブジェクトにアクセスできる。複数のプロセスが1つのオブジェクトにアクセスしているため、あるプロセスがオブジェクトにアクセスしている間に、別のプロセスがオブジェクトの内容を変更するという事態が発生することがある。
この例では線形化可能性の必要性を示している。線形化可能なシステムでは、共有されたオブジェクトに対する操作が重なっても、それぞれの操作は瞬時に行われているように見える。線形化可能性は強力な正当性条件であり、複数のプロセスが同時にオブジェクトにアクセスした場合に、どのような出力が可能であるかを制約する。線形化可能性は、操作が予期せぬ方法で完了しないことを保証する安全特性でもある。システムが線形化可能であれば、プログラマーはシステムについて推論することができる[2]。
線形化可能性の歴史
線形化可能性は、1987年にハーリー（Maurice Peter Herlihy）とWingによって初めて一貫性モデルとして紹介された。このモデルは「アトミックな操作とは、同時実行される操作によって割り込みされることがない操作である」といった、より限定的なアトミックの定義を含んでおり、操作の開始と終了がいつであるかについては通常曖昧である。
アトミックなオブジェクトは、逐次的・直列的な定義から即座に完全に理解することができる。並列に実行される一連の操作が常に次々と発生しているように見えることであり、矛盾が生じることはない。具体的には、線形性は、システムの不変性がすべての操作によって観察され、保存されることを保証する。すべての処理が個々に不変性を保持していれば、システム全体としても不変性を保持していることになる。
線形化可能性の定義
並行システムは、共有データ構造やオブジェクトを介して通信するプロセスの集合体である。並行システムでは、複数のプロセスが同時にオブジェクトにアクセスする可能性があり、プログラマーは期待される結果を推論できる必要があるため、線形化可能性が重要となる。並行システムの実行結果は、完了した操作の順序付けられたシーケンスである履歴となる。
履歴（history）は、一連のスレッドやプロセスがオブジェクトに対して行った呼び出しと応答のシーケンスと定義する。呼び出しは操作の開始であり、応答はその操作の終了を知らせるものと考えることができる。関数を呼び出すたびに、それに続く応答が発生する。これを利用して、オブジェクトのあらゆる用途をモデル化することができる。例えば、2つのスレッド、AとBが両方ともロックを取得しようとし、既に取得されている場合には手を引くとする。これは、両方のスレッドがロック操作を呼び出し、両方のスレッドが応答を受け取り、一方は成功し、一方は失敗したとモデル化される。
| Aがロックを呼び出す | Bがロックを呼び出す | Aが失敗の応答を受け取る | Bが成功の応答を受け取る |
逐次履歴とは、すべての呼び出しが即座に応答するもので、つまり、呼び出しと応答が瞬時に行われると考えられる。逐次履歴は実際の並行性を持たないため、推論するのは簡単なはずだが、前の例は逐次履歴ではないため、推論するのは困難となる。ここで線形性が必要になる。
履歴
- 線形化可能性のページへのリンク
