2013-02-06

デッドロックを回避しようとかいう話になって、隣の人が「CASがあればロックフリーできるしデッドロックしない、mutexとかいらん」とか言ってたので「いやロックフリーとか騙されてると思うが」と言ったら、「騙されてるとかなに？ちゃんと文章におこせよ」とか言われたので書いておく。

まあロックフリーつっても、Linuxの中でRCUとかいうのが使われてる程度の知識しか無いし、そもそもRCUってロックフリーなのかどうかも知らないので、危険だからあんまり触れないようにしてたのだけど、まあ、書けと言われたし書く。(受動的ブログ)

基本的には

肝心な時に役に立たないのでは
デッドロックしなければいいってもんでも無いと思うが

の、二点。

まず、肝心な時に役に立たないのでは？というのは、多分、ロックとか面倒になるのって、ドライバというか、状態を持ったハードウェアとかネットワーク外部の処理が絡んでる時だと思うのだけど、そういう時にロックフリーとかTMとかの投機的な奴らって無力なんじゃないの？という気が。

CPUだけで問題が解決するようなマルチスレッドって、大体データが大量にあるから、複雑なタスクのやりとりみたいなのってあんまり必要無くて、いや、まあ、エンコーダとかゲームとかあるが…大体データ並列できないような場合って同期コストがでかいから面倒、みたいな状態で、そういう時って、投機実行のリトライのコストとかも無視できないと思うのだよな。とすると、まあ、結局投機実行では解決できなくて、よく考えるしかなくて、そういう状況でロックフリー的な挙動って役に立つのか疑問。

本当にデッドロックが恐いのは、多分、ドライバで、非同期に動く相手の状態が読みにくくて辛いとかだと思う。僕はそこまでシビアなドライバはやったことないが、まあ、印象として。で、そういう計算以外の機能を持った並列実行の時に、投機実行とか無理ではないの？という気がする。例えば、HDDに書き込むとか、ネットワークの向こうからデータが届いたとか、人間が操作したとか。
もちろん、よく考えれば、投機実行可能なところもあると思うけど、そのよく考えるコストってもうMutexかセマフォかTMかlock-freeかとか関係無くね？という印象。

二点目は、デッドロックしなければいいというものではないと思う、という点。

Wikipedia にはデッドロックの回避方法のひとつとして http://ja.wikipedia.org/wiki/%E3%83%87%E3%83%83%E3%83%89%E3%83%AD%E3%83%83%E3%82%AF#Lock-free_.E3.81.A7.E3.81.AE.E5.9B.9E.E9.81.BF 「Lock-freeとWait-freeアルゴリズムでもデッドロックを回避できる。」とか超簡潔な説明が書いてあるが…

まあ、これが納得できなくて…
http://d.hatena.ne.jp/w_o/20100131#1264938874
この時にも「デッドロックしないとかインチキだ」とか書いてて、実際そういう質問をした記憶があるので、3年前から成長してない感すごい。

Mutexを使った場合に起こるデッドロックも、別に本人が望んでデッドロックしてるわけではなくて、うっかり見逃しててデッドロックしてるのだと思う。多分。

func_nest3() {
   lock(B);     // ここでロックしてるの忘れてた
   updateB1(B);
   unlock(B);
}

func_nest2() { func_nest3(); }
func_nest1() { func_nest2(); }

func1() {
   lock(A);
   updateA1(A);
   func_nest1();
   updateA2(A);
   unlock(A);
}

func2() {
    lock(B);
    updateB2(B);

    lock(A);
    updateA3(A);
    unlock(A);

    updateB3(B);
    unlock(B);
}

イメージとしてはこんな感じで、実際の処理は、thread1がfunc1, thread2がfunc2 を実行したとして、

 thread1: lock(A) -> updateA1(A) -> lock(B) -> 死亡
 thread2: lock(B) -> updateB1(B) -> lock(A) -> 死亡

こんな感じになる。

これが、投機的な挙動をすると、

 thread1: lock(A) -> updateA1(A) -> lock(B) --------------------------------------------> abort -> lock(B) -> updateB1(B) -> unlock(B) -> (もう一回Aでabortするが略)
 thread2: lock(B) -> updateB2(B) -> lock(A) -> updateA3(A) -> unlock(A) -> updateB3(B) -> unlock(B) -> done

で、めでたくデッドロックは回避されるわけだ。

が、少しfunc1を書いた人の気分になってほしいのだが、この時、プログラムの意思としては、

func_nest3() {
   lock(B);     // ここでロックしてるの忘れてた
   updateB1(B);
   unlock(B);
}

func_nest2() { func_nest3(); }
func_nest1() { func_nest2(); }

func1() {
   lock(A);          -+-
   updateA1(A);       |
   func_nest1();      | この間でA/B両方あわせてアトミックな操作をやりたかった
   updateA2(A);       |
   unlock(A);        -+-
}

と、いう意思を持ってた可能性って、それなりにあると思うのだよな。つまり、

updateA1 -> updateB1 -> updateA2

という操作を、アトミックにやりたかった、と。func1単体で見た場合、そういう挙動をしてるわけで、それが意図した処理であるというのは、十分考えられる範囲だと思う。

で、その時↓

 thread1: lock(A) -> updateA1(A) -> lock(B) --------------------------------------------> abort -> lock(B) -> updateB1(B) -> unlock(B) -> (もう一回Aでabortするが略)
 thread2: lock(B) -> updateB2(B) -> lock(A) -> updateA3(A) -> unlock(A) -> updateB3(B) -> unlock(B) -> done

みたいな、投機的な挙動をしてしまうと、おそらく、その意思は汲み取られていない。つまり、操作の順序として、

updateB2 -> updateA3 -> updateB3 -> updateB1 -> updateA1 -> updateB1 -> updateA2
                                    ^^^^^^^^
                                    これ何？

という順序になってしまうと。

まーデッドロックして死亡するのと、値多少違っても生き続けるのと、どっちがいいかというのは、その人のバックグラウンドの違いもあって、地味に宗教戦争になりがちなので、あんまり言及したくないが、個人的には死んだら止まって欲しいよなー。

その問題はまあいいとしても、つまり、ロックフリーにしたからといって、「本来アトミックに操作しないといけないのをうっかりして間違えた」という問題が解決してるわけではなくて、別の形になって出現しているだけでは？という気がするので、まーなんか騙されてる気がするんだよなーという話だった。

ちなみにTMだと、ネストした衝突も検出できるので問題が多少解決してて、一貫性の問題もデッドロックの問題も解決するわけだが、この時、問題としては、「予想に反してスケールしない」という形で出てくることになる、と思う。個人的には「予想に反してスケールしない」が許されるなら、そもそもマルチスレッドで書く必要無くね？という気がするが、これも宗教戦争の香りがするのであんまり言及しない。

w_o’s diary

もしかして: ロックフリーだまされてる

なんか