線形化可能性のソースを表示

{{出典の明記| date = 2021-11}}
[[並行計算|並行プログラミング]]において操作（または操作の集合）は、呼び出しイベントと応答イベント（コールバック）の順序付きリストで構成されており、応答イベントを追加することで以下のように拡張できる場合、'''線形化可能'''である。

#拡張されたリストは逐次履歴として再表現することができる（直列化可能である）。
#その逐次履歴は元の拡張されていないリストの[[部分集合]]である。

これは、非公式には、変更されていないイベントのリストは、その呼び出しが[[直列化可能性|直列化可能]]であるが、直列スケジュールの応答の一部がまだ戻ってきていない場合に限り、線形化可能であることを意味する<ref name=":0" />。

並行システムでは[[プロセス]]が同時に共有オブジェクトにアクセスできる。複数の[[プロセス]]が1つの[[オブジェクト]]にアクセスしているため、あるプロセスがオブジェクトにアクセスしている間に、別のプロセスがオブジェクトの内容を変更するという事態が発生することがある。

この例では線形化可能性の必要性を示している。線形化可能なシステムでは、共有された[[オブジェクト]]に対する操作が重なっても、それぞれの操作は瞬時に行われているように見える。線形化可能性は強力な[[正当性]]条件であり、複数のプロセスが同時にオブジェクトにアクセスした場合に、どのような出力が可能であるかを制約する。線形化可能性は、操作が予期せぬ方法で完了しないことを保証する安全特性でもある。システムが線形化可能であれば、[[プログラマー]]はシステムについて推論することができる<ref>{{Cite journal|last=Shavit, Nir and Taubenfel,Gadi|year=2016|title=The Computability of Relaxed Data Structures: Queues and Stacks as Examples|url=http://www.faculty.idc.ac.il/gadi/MyPapers/2015ST-RelaxedDataStructures.pdf|journal=Distributed Computing|volume=29|issue=5|pages=396–407|doi=10.1007/s00446-016-0272-0|s2cid=16192696}}</ref>。

== 線形化可能性の歴史 ==
線形化可能性は、1987年にハーリー（Maurice Peter Herlihy）と[[:en:Wing|Wing]]によって初めて[[一貫性]]モデルとして紹介された。このモデルは「アトミックな操作とは、同時実行される操作によって割り込みされることがない操作である」といった、より限定的なアトミックの定義を含んでおり、操作の開始と終了がいつであるかについては通常曖昧である。

アトミックなオブジェクトは、逐次的・直列的な定義から即座に完全に理解することができる。並列に実行される一連の操作が常に次々と発生しているように見えることであり、矛盾が生じることはない。具体的には、線形性は、システムの不変性がすべての操作によって観察され、保存されることを保証する。すべての処理が個々に不変性を保持していれば、システム全体としても不変性を保持していることになる。

== 線形化可能性の定義 ==
並行システムは、共有データ構造やオブジェクトを介して通信するプロセスの集合体である。並行システムでは、複数のプロセスが同時にオブジェクトにアクセスする可能性があり、プログラマーは期待される結果を推論できる必要があるため、線形化可能性が重要となる。並行システムの実行結果は、完了した操作の順序付けられたシーケンスである履歴となる。

履歴（history）は、一連のスレッドやプロセスがオブジェクトに対して行った呼び出しと応答のシーケンスと定義する。呼び出しは操作の開始であり、応答はその操作の終了を知らせるものと考えることができる。関数を呼び出すたびに、それに続く応答が発生する。これを利用して、オブジェクトのあらゆる用途をモデル化することができる。例えば、2つのスレッド、AとBが両方ともロックを取得しようとし、既に取得されている場合には手を引くとする。これは、両方のスレッドがロック操作を呼び出し、両方のスレッドが応答を受け取り、一方は成功し、一方は失敗したとモデル化される。

{| border="1" cellspacing="0"
| Aが''ロック''を呼び出す
| Bが''ロック''を呼び出す
| Aが''失敗''の応答を受け取る
| Bが''成功''の応答を受け取る
|}

逐次履歴とは、すべての呼び出しが即座に応答するもので、つまり、呼び出しと応答が瞬時に行われると考えられる。逐次履歴は実際の並行性を持たないため、推論するのは簡単なはずだが、前の例は逐次履歴ではないため、推論するのは困難となる。ここで線形性が必要になる。

履歴<math>\sigma</math>が線形化可能なのは、次のような完了した操作の線形順序がある場合である。

# <math>\sigma</math>の中で完了したすべての操作について，その操作は，すべての操作が<math>\sigma</math>の順に1つずつ完了した場合に返すのと同じ結果を実行時に返す。
# op<sub>2</sub>が始まる（起動する）前にop<sub>1</sub>が完了する（応答を得る）場合、<math>\sigma</math>内ではop1がop2に先行することになる<ref name=":0">{{Cite journal|author1=Herlihy, Maurice P.  |author2=Wing, Jeannette M.|year=1990|title=Linearizability: A Correctness Condition for Concurrent Objects|journal=ACM Transactions on Programming Languages and Systems|volume=12| issue = 3|pages=463–492|doi=10.1145/78969.78972|citeseerx=10.1.1.142.5315|s2cid=228785}}</ref>。

言い換えれば

*その呼び出しと応答を並べ替えると、逐次的な履歴が得られる。
*その逐次履歴は、オブジェクトの逐次定義に基づいて正しいものである。
*元の履歴で呼び出しの前に応答があった場合、順次並べ替えてもその前に応答がなければならない。

(ここで最初の2つの箇条書きは直列性と一致していることに注意すべきである。つまり操作は何らかの順序で起こるように見える。最後の点は線形化可能性に特有のものであり，HerlihyとWingの主要な貢献である）<ref name=":0" />。

先ほどのロックの例を、2つの方法で並び替えて見る。

{| border="1" cellspacing="0"
| Aが''ロック''を呼び出す
| Aが''失敗''の応答を受け取る
| Bが''ロック''を呼び出す
| Bが''成功''の応答を受け取る
|}

Aの応答の下にあるBの呼び出しを並べ替えると、連続した履歴になる。すべての操作が明らかな順序で行われるようになったので、これは簡単に推論できる。しかし残念なことに、これはオブジェクトの逐次的な定義とは一致しない（プログラムのセマンティクスとは一致しない）。Aはロックの取得に成功し、Bはその後中止したはずである。

{| border="1" cellspacing="0"
| Bが''ロック''を呼び出す
| Bが''成功''の応答を受け取る
| Aが''ロック''を呼び出す
| Aが''失敗''の応答を受け取る
|}

これは正しい順列の履歴かつ線形化されている。線形化可能性の定義は、呼び出しの前にある応答を並べ替えることを妨げるだけであることに注意する。したがって、元の履歴は確かに線形化可能である．

オブジェクト（ヒストリーではなく）は、その使用に関するすべての有効な履歴が線形化できる場合、線形化可能である。なお、これを証明するのは困難とされている。

== 線形化可能性と直列化可能性 ==
次のような履歴があるとする。これも2つのオブジェクトがロックを使って相互作用する。

{| border="1" cellspacing="0"
| Aがロックを呼び出す
| Aが成功の応答を受け取る
| Bがロック解除を呼び出す
| Bがロック解除に成功する
| Aがロック解除を呼び出す
| Aがロック解除に成功する
|}

この履歴は、AとBの両方がロックを保持している時点があるため有効ではない。さらに順序規則に違反しない限り、有効な順序履歴に並び替えることはできない。したがって線形化可能ではない。しかし直列化可能性の下では、Bのロック解除操作をAの最初のロックの「前」に移動させることができ、これは有効な履歴となる（オブジェクトがロック状態で履歴を開始したと仮定）。

{| border="1" cellspacing="0"
| Bがロック解除を呼び出す
| Bがロック解除に成功する
| Aがロックを呼び出す
| Aがロックに成功する
| Aがロック解除を呼び出す
| Aがロック解除に成功する
|}

この並び替えは、AとBの間で別の通信手段がない場合には意味がある。並び替えの制限により複数の線形化可能なオブジェクトが全体として線形化可能であることが保証されるため、個々のオブジェクトを個別に検討する場合には、線形化可能性が向上する。

== 線形化ポイント ==
線形化可能性のこの定義は、次のものと同等である。

* すべての関数の呼び出しは、その呼び出しと応答の間のある瞬間に線形化点（線形化ポイント）を持つ。
* すべての関数はその線形化点（線形化ポイント）で瞬時に発生しているように見え、逐次定義で指定された通りに動作する。

この方法は、通常、証明するのがはるかに簡単である。また、直感的に理解できることから、ユーザーとしても推論しやすいものとなっている。この瞬間的に発生する、あるいは不可分に発生するという特性から、長い「線形化可能」の代わりに「アトミック」という用語が使われている<ref name=":0" />。

以下の例では、compare-and-swapで作られたカウンターの線形化ポイントは、最初の（そして唯一の）compare-and-swap更新の成功の線形化ポイントとなる。ロックを使用したカウンターは、ロックが保持されている間は、競合する可能性のある操作が実行されないため、いつでも線形化されると考えることができる。

== 線形化可能性の例 ==
=== カウンター ===
線形化可能性の威力と必要性を示すために、異なるプロセスがインクリメントできる単純なカウンタを考える。

複数のプロセスがアクセスできるカウンタオブジェクトを実装する。多くの一般的なシステムでは、あるイベントの発生回数を記録するためにカウンターを使用している。

カウンターオブジェクトは、複数のプロセスからアクセスでき、2つの操作が可能である。

* インクリメント：カウンターに格納されている値に1を加え、確認応答を返す。
* 読み込み：カウンターに格納されている現在の値を変更せずに返す。

このカウンターオブジェクトを、共有レジスタを使って実装する。

最初の試みは、線形化できないことがわかっているので、プロセス間で1つの共有レジスタを使用して、次のような実装を行う。

==== ノンアトミック ====
素朴で非アトミックな実装。

'''インクリメント'''

#レジスタ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つが失われた。

上記の例は、データ構造の実装を注意深く考える必要があり、線形性がシステムの正しさにどのような影響を与えるかを示している。

==== アトミック ====
線形化可能なアトミックカウンタオブジェクトを実装するために，これまでの実装を変更し，各プロセスPiが独自のレジスタRiを使用するようにする。

各プロセスは、以下のアルゴリズムに従ってインクリメントとリードを行う。

'''インクリメント'''

#レジスタRiの値を読み込む
#その値に1を加える
#新しい値をRiに戻す

'''読み込み'''

#レジスタ R1,R2...Rn を読む
#すべてのレジスタの合計を返す

この実装では最初の実装の問題点が解決されている。このシステムでは、インクリメント演算は書き込みステップで線形化されている。インクリメント演算の線形化可能性ポイントは、その演算がレジスタRiに新しい値を書き込むときとなる。読み取り操作は、読み取りによって返された値が、各レジスタRiに格納されたすべての値の合計に等しいとき、システムのある時点で線形化される。

これは些細な例ではあるが、実際のシステムでは操作はより複雑になり、導入されるエラーも極めて微妙なものになる。例えば、64ビットの値をメモリーから読み出す場合、実際には2つの32ビットのメモリーロケーションを2回連続して読み出すように実装されることがある。プロセスが最初の32ビットだけを読み取った後、2番目の32ビットを読み取る前にメモリー内の値が変更された場合、元の値でも新しい値でもなく、混ざった値を持つことになる。

さらにプロセスの実行順序によっても結果が変わってしまうため、このようなエラーの検出、再現、デバッグは困難である。

==== 比較・交換 ====
多くのシステムでは、アトミックな比較スワップ命令が用意されている。これはメモリーロケーションから値を読み取り、その値とユーザーが指定した「期待値」を比較し、両者が一致した場合に「新しい」値を書き出し、更新が成功したかどうかを返すものである。これを利用してノンアトミックカウンターのアルゴリズムを以下のように修正することができる。

#メモリーロケーションの値を読み取る
#その値に1を加える
#比較スワップ機能を使って、増加した値を書き戻す
#比較スワップによって読み込まれた値が、最初に読み込んだ値と一致しない場合は再試行する

比較スワップは瞬時に行われる（ように見える）ので、進行中に他のプロセスがその場所を更新した場合、比較スワップは確実に失敗する。

== 関連項目 ==
*[[Lock-freeとWait-freeアルゴリズム]]
*[[一貫性モデル (ソフトウェア)]]
*[[逐次一貫性]]
*[[厳密な一貫性]]
*[[不可分操作]]
*[[因果整合性]]
*[[結果整合性]]
*[[メモリオーダリング]]

==脚注==
{{reflist|2}}

== 参考文献 ==
* {{cite book | doi=10.1145/41625.41627 | title=Axioms for Concurrent Objects | year=1987 | last1=Herlihy | first1=Maurice P. | last2=Wing | first2=Jeannette M. | journal=Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL '87 | pages=13 | isbn=978-0-89791-215-0| s2cid=16017451 | url=http://repository.cmu.edu/cgi/viewcontent.cgi?article=2597&context=compsci }}
* {{cite book | doi=10.1145/99164.99185 | title=A Methodology for Implementing Highly Concurrent Data Structures | year=1990 | last1=Herlihy | first1=Maurice P. | journal=ACM SIGPLAN Notices | volume=25 | issue=3 | pages=197–206 | isbn=978-0-89791-350-8| citeseerx=10.1.1.186.6400 }}
* {{cite journal | doi=10.1145/78969.78972 | title=Linearizability: A Correctness Condition for Concurrent Objects | year=1990 | last1=Herlihy | first1=Maurice P. | last2=Wing | first2=Jeannette M. | journal=ACM Transactions on Programming Languages and Systems | volume=12 | issue=3 | pages=463–492| citeseerx=10.1.1.142.5315 | s2cid=228785 }}
* {{cite web|author=Aphyr|title=Strong Consistency Models|url=https://aphyr.com/posts/313-strong-consistency-models|website=aphyr.com|publisher=Aphyr|access-date=13 April 2018}}

{{DEFAULTSORT:せんけいかかのうせい}}
[[Category:トランザクション処理]]
[[Category:並行性制御]]