線形化可能性
素朴で非アトミックな実装。
インクリメント
レジスタRの値を読む
値に1を加える
新しい値をレジスタRに書き戻す
読み込み
レジスタRの読み出し
この単純な実装では線形化はできない。
値が0になるように初期化された1つのカウンタ・オブジェクトに、2つのプロセスがアクセスしているとする。
最初のプロセスは,レジスタの値を0として読み取る
最初のプロセスは値に1を加え、カウンタの値は1になるはずだが、新しい値をレジスタに書き戻す前に中断(割り込まれ)してしまい、その間に2番目のプロセスが実行される
2つ目のプロセスは、レジスタの値を読み取るが、値はまだ0になっている
2つ目のプロセスは、その値に1を加える
2つ目のプロセスが新しい値をレジスタに書き込み、レジスタの値は1になる
2つ目のプロセスは実行を終了し、1つ目のプロセスは中断したところから実行を続ける。
第1のプロセスは、他のプロセスがすでにレジスタの値を1に更新していることを知らずに、レジスタに1を書き込む
上記の例では、2つのプロセスがインクリメントコマンドを呼び出しましたが、オブジェクトの値は本来の2ではなく、0から1にしか増えなかった。システムが線形化できないために、インクリメント操作の1つが失われた。
上記の例は、データ構造の実装を注意深く考える必要があり、線形性がシステムの正しさにどのような影響を与えるかを示している。
op2が始まる(起動する)前にop1が完了する(応答を得る)場合、 σ {\displaystyle \sigma } 内ではop1がop2に先行することになる。
言い換えれば
その呼び出しと応答を並べ替えると、逐次的な履歴が得られる。
その逐次履歴は、オブジェクトの逐次定義に基づいて正しいものである。
元の履歴で呼び出しの前に応答があった場合、順次並べ替えてもその前に応答がなければならない。
(ここで最初の2つの箇条書きは直列性と一致していることに注意すべきである。つまり操作は何らかの順序で起こるように見える。最後の点は線形化可能性に特有のものであり,HerlihyとWingの主要な貢献である)。
先ほどのロックの例を、2つの方法で並び替えて見る。
Aの応答の下にあるBの呼び出しを並べ替えると、連続した履歴になる。すべての操作が明らかな順序で行われるようになったので、これは簡単に推論できる。しかし残念なことに、これはオブジェクトの逐次的な定義とは一致しない(プログラムのセマンティクスとは一致しない)。Aはロックの取得に成功し、Bはその後中止したはずである。
これは正しい順列の履歴かつ線形化されている。線形化可能性の定義は、呼び出しの前にある応答を並べ替えることを妨げるだけであることに注意する。したがって、元の履歴は確かに線形化可能である.
オブジェクト(ヒストリーではなく)は、その使用に関するすべての有効な履歴が線形化できる場合、線形化可能である。なお、これを証明するのは困難とされている。