線形化可能性の定義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/30 20:34 UTC 版)
並行システムは、共有データ構造やオブジェクトを介して通信するプロセスの集合体である。並行システムでは、複数のプロセスが同時にオブジェクトにアクセスする可能性があり、プログラマーは期待される結果を推論できる必要があるため、線形化可能性が重要となる。並行システムの実行結果は、完了した操作の順序付けられたシーケンスである履歴となる。 履歴（history）は、一連のスレッドやプロセスがオブジェクトに対して行った呼び出しと応答のシーケンスと定義する。呼び出しは操作の開始であり、応答はその操作の終了を知らせるものと考えることができる。関数を呼び出すたびに、それに続く応答が発生する。これを利用して、オブジェクトのあらゆる用途をモデル化することができる。例えば、2つのスレッド、AとBが両方ともロックを取得しようとし、既に取得されている場合には手を引くとする。これは、両方のスレッドがロック操作を呼び出し、両方のスレッドが応答を受け取り、一方は成功し、一方は失敗したとモデル化される。 Aがロックを呼び出す Bがロックを呼び出す Aが失敗の応答を受け取る Bが成功の応答を受け取る 逐次履歴とは、すべての呼び出しが即座に応答するもので、つまり、呼び出しと応答が瞬時に行われると考えられる。逐次履歴は実際の並行性を持たないため、推論するのは簡単なはずだが、前の例は逐次履歴ではないため、推論するのは困難となる。ここで線形性が必要になる。 履歴 σ {\displaystyle \sigma } が線形化可能なのは、次のような完了した操作の線形順序がある場合である。 σ {\displaystyle \sigma } の中で完了したすべての操作について，その操作は，すべての操作が σ {\displaystyle \sigma } の順に1つずつ完了した場合に返すのと同じ結果を実行時に返す。 op2が始まる（起動する）前にop1が完了する（応答を得る）場合、 σ {\displaystyle \sigma } 内ではop1がop2に先行することになる。 言い換えれば その呼び出しと応答を並べ替えると、逐次的な履歴が得られる。 その逐次履歴は、オブジェクトの逐次定義に基づいて正しいものである。 元の履歴で呼び出しの前に応答があった場合、順次並べ替えてもその前に応答がなければならない。 (ここで最初の2つの箇条書きは直列性と一致していることに注意すべきである。つまり操作は何らかの順序で起こるように見える。最後の点は線形化可能性に特有のものであり，HerlihyとWingの主要な貢献である）。 先ほどのロックの例を、2つの方法で並び替えて見る。 Aがロックを呼び出す Aが失敗の応答を受け取る Bがロックを呼び出す Bが成功の応答を受け取る Aの応答の下にあるBの呼び出しを並べ替えると、連続した履歴になる。すべての操作が明らかな順序で行われるようになったので、これは簡単に推論できる。しかし残念なことに、これはオブジェクトの逐次的な定義とは一致しない（プログラムのセマンティクスとは一致しない）。Aはロックの取得に成功し、Bはその後中止したはずである。 Bがロックを呼び出す Bが成功の応答を受け取る Aがロックを呼び出す Aが失敗の応答を受け取る これは正しい順列の履歴かつ線形化されている。線形化可能性の定義は、呼び出しの前にある応答を並べ替えることを妨げるだけであることに注意する。したがって、元の履歴は確かに線形化可能である． オブジェクト（ヒストリーではなく）は、その使用に関するすべての有効な履歴が線形化できる場合、線形化可能である。なお、これを証明するのは困難とされている。
※この「線形化可能性の定義」の解説は、「線形化可能性」の解説の一部です。
「線形化可能性の定義」を含む「線形化可能性」の記事については、「線形化可能性」の概要を参照ください。
- 線形化可能性の定義のページへのリンク
