2012年2月5日日曜日

並行処理プログラミングをするうえで覚えておくべきこと

"Java並行処理プログラミング ―その「基盤」と「最新API」を究める"を読了。

Java使いではないが、多くのことを吸収できた。

忘れないうちに、並行処理プログラミングをするうえで知っておかなければ
ならないことをまとめておく。


本記事の要約
スレッドセーフ
 同期化
 安全な設計をするための指針
 よりよい設計をするための指針
 生存事故の防止
 試験
 条件キュー


並行処理プログラミングをする場合は、スレッドセーフ性を考慮しなくてはならない。
まずは基本的なところから抑えていこう。

 スレッドセーフ
意味
スレッドセーフであるとは、複数のスレッドからどのような順番でアクセスされても正しくふるまうことである。
呼び出し側にアクセス順番を考慮させたり、同期化を求めるようなことはしてはならない。
同期化についてもまとめておく。



 同期化
 意味
スレッドの排他制御であるsynchronizedなどを利用してスレッドセーフ性を保証することである。

 同期化することで何が保証されるのか
① 更新データの整合性
② メモリの可視性(memory visibility)

①はいいだろう。
あるスレッドがステート(オブジェクトのデータ(フィールド))を変更中に、
別のスレッドがそのステートを変更してはならない。
よくある例では、複数のスレッドが同期化していない変数を加算し続けると
意図した加算結果にならないかもしれないというあである。

②はしばしば忘れられている。
あるスレッドがステートを変えたら、他のスレッドがその変更個所を
タイミングよく見る保証はないのである。
またあるスレッドが二つ以上の値を変更した場合、他のスレッドが
その変更された順番にステートを見ることも保証されない。
つまり、複数のスレッドに共有されるデータを読む場合にも同期化は必要なのである。

可視性の保証にはメモリバリアが使われる。
メモリバリアとは、プロセスのキャッシュをフラッシュ、
または無効化し、
ハードウェア書き込みバッファをフラッシュし、
実行パイプラインを停止することである。

同期化の必要性はどう判断したらいいのだろうか。
 同期化が不要な場合
1. 可変なステート変数を各スレッドで共有しない
ステート変数とはオブジェクトのデータ(フィールド)のことである。
またオブジェクト自身もステート変数になりえる。

共有しないので同期化がが不要であるのは当たり前である。
このことをスレッド拘束されている、ともいう。

2. スタック拘束されるデータ
ローカル変数は実行時のスレッドに拘束される。
ただし、それを公開した場合は拘束は破れる。

3. クラス変数としての利用
staticイニシャライザはクラスの初期化時に、JVMが内部で同期化してくれる。

4. 内部で同期されるよう作ってあるスレッドセーフなオブジェクトの利用
クラスで利用するコンポーネントがスレッドセーフであれば、
構築するクラスにスレッドセーフ性を加える必要はない。

このことをスレッドセーフの移譲という。

ただし、複合アクション(check-then-act、read-modify-write)ではそうではない。
複合アクション全体をステート変数に委譲できればよい。
複合アクションについては下段で別途説明する。

5. ステート変数が不変
不変であるとはコンストラクタの後にそのステートを変えられないことである。
不変なフィールドにfinalを付与しておくことで、
誤った設計を防げる、またステートの判断が容易になる。

ただし、不変なステート変数の同期化が必要な場合がある。
finalをつけていても、である。
それはフィールドが可変オブジェクトを参照している時である。


 同期化が必要な場合
1. 可変なステート変数を各スレッドで共有する場合

2. 複合アクション(check then act、read modify write)
単一のアトミックな操作で更新することを忘れてはならない。
ある値をチェックしてからその結果に基づき何かの操作をするような場合(check then act)や、
ある値を読んで修正して書き戻すような場合(read modify write)は、
その一連のアクションをアトミックに処理しなければならない。

内部で同期されるよう作ってあるスレッドセーフなオブジェクトを
使っていても複合的な操作をする場合は同期を忘れてはらない。




 安全な設計をするための指針
1. 可変なステート変数の同じロックの元での利用
synchronizedさせていても、その中で利用するスレッドセーフなコンポーネントが
同じロックを使うとは限らない
そのためコンポーネントと同じロックを使う必要がある。
これはクライアントサイドロック、または外部ロックと呼ばれる。

2. 意図しないオブジェクトの公開 
公開すべきでないオブジェクトが公開(public)されると、
そのオブジェクトは逸出(escape)したと呼ばれる。JPCERTでも詳しく記載されている。

(問題点)
不定項の保全が難しくなり、スレッドセーフ性を損なう

(逸出する失敗例)
① publicでの公開
公開しないのならprivateにせよ。

② privateなオブジェクトのゲッタ(getter)経由での公開
さらにその公開されたオブジェクトのpublicフィールドから鎖状にアクセスを許してしまうこともある。

③ よそ者のメソッドへのオブジェクトの渡し
よそ者がどのようなコードを作るかは不明であることを肝に銘じること。

④ 内部クラス経由でのオブジェクトの参照
クラス内で別クラスのインスタンス(内部クラス)を作っている場合は、
static宣言されない限り、その外部クラスのインスタンスへの参照が保持される

⑤ コンストラクタ中のthis参照
オブジェクトが正しいステートをもっているのはコンストラクタが終了したときのみである。
公開がコンストラクタの最後に記載していても事前発生は保証されない。

よって以下の用例はすべて誤りである。
・ オブジェクトの構築時にクラスのコンストラクタから呼び出されるよそ者メソッドに、引数として this を渡す。
・ コンストラクタ内でイベントリスナーを設定する。
・ コンストラクタの中でスレッドをスタートさせる(スレッドのコンストラクタにthisを渡す)※スレッドを作るのはよい。



 よりよい設計をするための指針
1. 長時間かかる処理の間はロックをもたない

2. ゲッタ、セッタの積極的な利用
ステート変数がスレッドセーフではなくても、そのデータをprivateに拘束させ、
ロックを利用するよう実装したgetter、setter経由でしかアクセスさせなければ、
スレッドセーフなクラスを構築できる。
同期化すべきオブジェクトやデータを使うあらゆる場所に
synchronized(){}を書く危うさからも逃れられる。
また、同期化をカプセル化するとその同期化ポリシーを強制しやすくなるというメリットもある。

3. 同期化コレクションではなく、並行コレクションの積極的な利用
スケーラビリティは向上し、リスクほとんどない。
JavaのConcurrentHashMapなどである。活用しない手はない。

4. どのロックがどの変数をガードするかアノテーションでドキュメント化しておく
未来の自分のためにも、他の人のためにも。



(その他予備知識)
1. Javaの固有のロックは再入可(リエントラント)
ロックを持ったスレッドがそのロックを再取得可能である。
クラスを継承している場合などオーバーライド時に親と子でロックメソッドで
デッドロックしてしまう。
pthreadsはロックが呼び出しごとに与えられる。


2. GCについて
C++ではオブジェクトをメソッドに渡す際に、移転、一時的な貸し出し、長期的な共同所有など検討が必要。
JavaではGCがあるので所有に関しては検討しなくてもよい。



 生存事故の防止
 事故の種類と対策
1. ライブロック(live lock)
(説明)
スレッドが何度やってもエラーになる操作を繰り返して前進できない状態。
(対策例)
イーサネットでは再試行の仕組みに乱雑性を組み込み、衝突するエラーとトラフィック渋滞の二つを減らす。

2. 飢餓状態(starvation)
(説明)
スレッドがリソースを使い果たし、別スレッドが前進できなくなる状態。

(対策例)
スケールアップやスケールアウト。

3. 資源デッドロック(resource deadlock)
(説明)
ロック待ちではなく資源を待ってデッドロックする状態。
(例)
スレッド1 コネクションXを確保  ⇒  コネクションY待ち
スレッド2   コネクションYを確保  ⇒  コネクションX待ち

(対策例)
設計の見直し。

4. 死の抱擁(deadly embrace)
(説明)
ロックに循環的な依存性がある場合に発生する。
スレッド1がスレッド2が保有する資源を、
スレッド2はスレッド3が保有する資源を、
スレッド3はスレッド1が保有する資源を、ということである。
(例)
有名な食事をする哲学者である。
円形のテーブルに哲学者が座り、彼らの間に箸が1本だけ置かれている。

食事をするには箸は2本必要である。
全員がまず左の箸を先に持ち、
その後右の箸を持とうとするとデッドロックが発生する。

(対策例)
設計の見直し。
上の例であれば、左の箸がとれなければなにもしなくていいが、
右の箸がとれなければ左の箸を置くようにしなければならない。
ただし、ライブロックが発生する可能性があることは頭の片隅に入れておいた方がいいだろう。

5. ロック順デッドロック
(説明1)
複数のスレッドが2つのロックを違う順番で取得する場合に発生する。
左ロック、右ロックの順番でロックを取得する左右メソッドと、
右ロック、左ロックの順番でロックを取得する右左メソッドがあるとする。

スレッド1  左右メソッド呼び出し(左をロック  ⇒  右をロック待ち)
スレッド2    右左メソッド呼び出し(右をロック  ⇒  左をロック待ち)

(対策1)
すべてのスレッドに固定的順番でロックを入手させる
ロックの循環性依存性はなくなるためデッドロックは起きない。
(例)
銀行口座などでXとYの間で資金を移転させる場合はどのようにロックさせればよいか。
XからYへの送金、YからX送金のパターンがあるため順番を制御できなさそうである。
しかし、口座番号などのユニークで不変な比較可能なキーを使い、
X、Yどちらからの送金でも固定的な順番でロックさせれば対応は可能である。
比較可能なキーがなければ、アカウント名を元にハッシュ値を求めそれをキーにすればいいだろう。

口座番号X < 口座番号Yなら
synchronized(Xロック) {
  synchronized(Yロック) {
    処理
  }
}

(説明2)
デッドロックの検出が分かりやすい場合だけとは限らない。
ロックを保持した状態で別のメソッドを呼ぶような場合、
その別メソッドがロックを保持する場合デッドロックとなる可能性がある。
(例)
スレッド1 クラスA メソッド1(クラスAロック)  ⇒  クラスBメソッド2(クラスBロック待ち)
スレッド2   クラスB メソッド1(クラスBロック)  ⇒  クラスAメソッド2(クラスAロック待ち)

// クラスA側
synchronized(クラスAロック) メソッド1 {
  共有変数の閲覧・操作
  クラスB側メソッド1
}
synchronized(クラスAロック) メソッド2 {
  共有変数の閲覧・操作
}

// クラスB側
synchronized (クラスBロック) メソッド1{
  共有変数の閲覧・操作
  クラスA側メソッド1
}
synchronized (クラスBロック) メソッド2{
  共有変数の閲覧・操作
}

(対策2)
オープンコール(ロックを保有しないでメソッドを呼び出す)を使うよう努力する。
上の例では、メソッド全体をsynchoronizedするのではなく、共有ステートに関係ある操作だけをガードさせる。
// クラスA側
メソッド1 {
  synchronized(クラスAロック) メソッド1 {
    共有変数の閲覧・操作
  }
  クラスB側メソッド1
}

// クラスB側
メソッド1 {
  synchronized(クラスBロック) メソッド1 {
    共有変数の閲覧・操作
  }
  クラスA側メソッド1
}



 実行性能
アムダールの法則は知っていよう。
複数のプロセッサを使ったときの理論上の性能向上の度合いを予測するのによく使われる。
この数式から、プロセッサの数を増やし、並行プログラミングしていても、
直列実行の部分があるとスループットの増加は抑えられるということが分かる。

例えばJavaのキューの実装を比較すると、ConcurrentLinkedQueueの方が
同期化させて利用するLinkedListよりも性能がいい。直列化の程度が違うためだ。
ノンブロッキングのキューのアルゴリズムを使っていることが起因である。

スケーラビリティをどう向上させるか検討しよう。
考え方の基本はロックの粒度を小さくし、ロックの範囲を狭めることである。

1. ロック分割(lock splitting)の利用
争奪の激しいロックを分割する。

2. ロックストライピング(lock striping)
ロック分割をさらに拡張する。

m個のオブジェクトの操作をn個のロックに担当させる。
例えばオブジェクトが5つ、ロックが3つだとする。
オブジェクト[0] ⇒ lock[ 0 % 3 (==0)]
オブジェクト[1] ⇒ lock[ 1 % 3 (==1)]
オブジェクト[2] ⇒ lock[ 2 % 3 (==2)]
オブジェクト[3] ⇒ lock[ 3 % 3 (==0)]
オブジェクト[4] ⇒ lock[ 4 % 3 (==1)]

synchronized (ロック[ 0 % 3]) {
  オブジェクト[0]
}
synchronized (ロック[ 1 % 3]) {
  オブジェクト[1]
}

あるオブジェクトではなく、オブジェクト全体への操作をする場合は、、
排他アクセスのため全ロックを取得することになり単一のロックより困難になる。

3. リーダ-ライタロックの利用
排他ロックではなくリーダ-ライタロックを使うと排他モード、共有モードの選択ができる。
書き換え作業と読むだけの作業とでロックのモードが変えられる。

・ どのスレッドもロックを保持していない場合
他のスレッドは排他モードあるいは共有モードでロックを獲得できる

・ あるスレッドが排他モードでロックを保持している場合
他のスレッドは排他モードも共有モードでもロックを獲得できない

・ あるスレッドが共有モードでロックを保持を保持している場合
他のスレッドは共有モードでは獲得できる、排他モードでは獲得できない

排他をテレビのチャネル変え、共有をテレビを見ることだとイメージすると分かりやすい。
状態を変更しない読み込みに見える操作がリソースの状態を変更することもあるので注意すること。
ファイルを開き一行ずつgetする操作はファイルポインタを操作している。

4. ノンブロッキングの利用
そもそもロックしないという手段もある。
ロックの代わりに、ハードウェアで実装されているCAS(Compare-And-Swap)のような
低レベルな並行操作単位でスレッドセーフ性を維持することも可能である。
設計と実装がやや難しい。



 試験
試験をする目的は以下の4つだろうか。
 目的
① スレッドセーフ性の確認
② スループット(一定時間内に一連の宇平公タスクが完了する量)の確認
③ 応答性(アクションのリクエストと完了の間の時間)の確認
④ スケーラビリティ(より多くの資源が仮ようになった時のスループットの改善)の確認

 落とし穴
試験時には落とし穴があるので気をつけること。
1. ガーベッジコレクション(GC)
(落とし穴)
GCが結果に偏りを与える。
(対策)
GCが一定の回数動くだけの長時間の試験をする。
もしくはGCが一回も動かない状態での試験を実施する。

2. Javaの動的コンパイル
(落とし穴)
Javaの動的コンパイルは、以下の時間を勘案しなくてはならない。
インタプリタでの処理+コンパイル時間+コンパイル後のバイトコードでの処理である。
(対策)
プログラムを長時間動かす。
もしくはコンパイルされたコードで試験する。

3. コンパイラの最適化
(落とし穴1)
例えば、連続する正数をテストデータとする場合、コンパイラが事前に計算してしまうことがある。
(対策1)
乱数を使う。
ただし、スレッドセーフな乱数を使うとテストに同期化が発生し、
ここがボトルネックになることもあるので注意。

(落とし穴2)
例えば、複雑な計算をさせてもそれが利用されなければ最適化によりスキップされる可能性がある。
これをデッドコードの排除という。
(対策2)
何かに使っていることを示すために結果をプリントするなりさせる。
かつ結果が予測不可能にさせる。

 その他
コア数を少なくし、スイッチアウトされる状態が高くさせスレッドの
重なり具合を多様化させることで、スレッドセーフ性を確かめる。



 条件待機
条件待機の基本的な構文は以下だろう。
※if文ではなく、whileを使うことが一般的である。条件が成立していない場合でも、何らかの原因で戻ってきてしまうことがあるから、らしい。

ロックの入手 {
  while(条件が真) {
    待ち(waitする。この時にロックを手放す)
    ※大気中にインタラプトされたりタイムアウトすれば失敗させることもある)
    起きる(他スレッドからnotifyなどで通知され、ロックの再取得)
  }
  アクションの実行
  ロックを手放す
}

条件待機の注意点をまとめておく。

 前進すべきか停止すべきかの条件文の注意点
1. 条件を調べる前に条件がロックされていること
なぜ条件を調べる際にロックが必要なのか。
それは、例えばキューは空か、一杯か、などステート変数が条件に使われているはずであるからである。
ステート変数はロックでガードしなければならない。
それゆえ条件もロックされていなければならない。

2. 条件を構成するステート変数は、それにひもづいているロックでガードすること
synchoronizedなどのロックのオブジェクトとwait/notifyを呼び出すオブジェクトは同じでなければならない。


 条件待機(wait)するときの注意点
1. waitを呼ぶ前には必ず前進すべきか停止すべきかの条件が調べられていること

2. waitからリターンした後にも条件を調べること
起こされた後に、別スレッドが条件を変えるかもしれないからである。

while (条件が真) {
  wait
}

 通知(nofity/notifyAll or signal/signalAll)するときの注意点
1. waitさせたままにしない
誰かが確実に通知すること。

2. notify、notifyAllを呼び出す時には、waitの時と同様に条件に結びついているロックを保持させること

3. 通知した後はすぐにロックを手放すこと
waitを呼び出したスレッドが待っているためである。


 通知のnotifyAll(signalAll)ではなくnotify(signal)が使える条件
1. 通知がただ一つのスレッドの前進させる場合
例えば、全スレッドがスタートラインに立つまで待たせておき、
一斉にスタートさせるような用途には使えない。

2. ただ一つの同じ形の条件変数でwaitをしている場合

以下のような例が考えられるためである。
スレッドAが条件1が満たされずでwaitしている。
スレッドBが条件2が満たされずでwaitしている。
スレッドCは条件1を満たすある処理を実行しnotifyを投げる。
しかし起こされたのがBであった。

一つのロックに対して、満杯ではない、と、空ではない、の複数の条件変数を作ることもできる。

// notFull(満杯ではない条件変数)
// notEmpty(空ではない条件変数)

put ロック {
  while(満杯) notFull.wait
    処理
    notEmpty.notify(signal)
 }

take ロック {
  while(空) notFull.wait
    処理
    notEmpty.notify(signal)
}


◆ 最後に

詳細は下記書籍を見てほしい。
Javaを使ったことがなくても参考になることが多いはずである。


書籍内、自分メモ。
Log記録アプリ P.174
スレッドプールのサイズを決める P.193
静的分析でコードレビュー P.304


0 件のコメント:

コメントを投稿