Kernel/VM Advent Calendar 2日目: PV ticketlock ってなんですか＞＜
今日もゆっくり Xen の ML をながめているとこんなスレッドを発見
http://permalink.gmane.org/gmane.comp.emulators.xen.devel/93598
ticket lock? "without expandig spinlock"? lock の一種か? なんじゃこりゃ?
ということで調べてみました。
そもそも spinlock って
spinlock は Linux でよく使われている lock のひとつ。基本的に
- lock とる
- とれなかったらとれるまで spin する (無限ループ)
- なんかやる
- lock 解除
というもので、 1. lock の中身が短く かつ 2. lock の中で sleep しない 場合に使われます。
その実装はアーキテクチャによりますが、 x86 では昔はこのようになっていました。
- lock に使われる数値がある
- 最初は その「lock値」は "1"
- lock 取得時に atomic に「lock値」を 1 減らして、結果が 0 かどうかを見る
- 結果が負であれば spin する
- なんかやる
- 「lock値」を "1" に戻す
そして ticket lock へと
この実装はとても速く、また「lock値」を見てやれば "どれぐらいのスレッドが同時に lock をとろうとしているか" がわかるというメリットがありました。
しかし、ひとつのスレッドの処理が終わった後、次にどのスレッドが起動されるかわからない という「アンフェアな」デメリットがあり、これはレイテンシにも悪影響になります。
| lock値 | スレッドA | スレッドB | スレッドC | スレッドD | スレッドE |
| 1 | - | - | - | - | - |
| 0 | lock | - | - | - | - |
| -1 | working | lock | - | - | - |
| -2 | working | spin | lock | - | - |
| -3 | working | spin | spin | lock | - |
| -4 | working | spin | spin | spin | lock |
| 1 | unlock | spin | spin | spin | spin |
| 0 | - | spin | spin | spin | lock |
このように、ずっと待ってたスレッドをさしおいて スレッドEが走ることもありうるわけです。
ということで、これを解消するべく ticket spinlock が導入されました。
ticket spinlock は "Next" と "Owner" という2つの数値を使い、銀行やら役所にある整理券と同じような動きをします。 "Next" が「入口に置いてある整理券」 "Owner" が「窓口で現在処理中の整理券番号の表示」となります。
- 初めは "Next" = "Owner" = 0 で開始
- "Next" を atomic に 1 増やす (整理券をとる)
- 増やす*前*の "Next" == "Owner" かどうか確認 (取った整理券が窓口表示の番号と同じなら窓口へ)
- 違ったら spin しながら 「増やす*前*の "Next" == "Owner"」になるのを待つ (窓口表示を見ながら待ちます)
- なんかする (窓口でいろいろ)
- "Owner" を atomic に 1 増やす (窓口表示が 1 増える)
こうすることで、さっきのケースでも A->B->C->D->E という順番が保証されるようになります。
| Next | Owner | スレッドA | スレッドB | スレッドC | スレッドD | スレッドE |
| 0 | 0 | - | - | - | - | - |
| 1 | 0 | lock | - | - | - | - |
| 2 | 0 | working | lock | - | - | - |
| 3 | 0 | working | spin | lock | - | - |
| 4 | 0 | working | spin | spin | lock | - |
| 5 | 0 | working | spin | spin | spin | lock |
| 5 | 1 | unlock | spin | spin | spin | spin |
| 5 | 1 | - | lock | spin | spin | spin |
| 5 | 1 | - | working | spin | spin | spin |
PV spinlock
この spinlock ですが、 VM の中で動いているゲストの spinlock 取得は効率があまりよくなく、特に ticket spinlock とはかなり相性が悪いようです。 (Xen のスケジューラのパフォーマンスに依存してしまう)
http://www.valinux.co.jp/contents/tech/eventreport/0806xensummit.html
特に最近のLinux kernelに取り込まれた「ticket spin lock」と仮想環境とは相性が悪くカーネルコンパイルでCPUサイクルの99%以上がスピンロック取得に無駄に使われ、10sの仕事に45分無駄にされていることになる。いくつかの提案と改善されたベンチマーク結果が示された。
動画: http://vimeo.com/12738341
スライド: http://www.xen.org/files/xensummitboston08/LHP.pdf
と、そこで今では "PV spinlock" という guest 時専用の spinlock 処理で、 guest 上の spinlock を置き換えています。
これは基本的には昔の spinlock と変わりません。違いは
- 2^16 回だけ spin する
- それでも lock がとれなければ、 cpu ごとの event channel に登録して block する (ようするに mutex ぽく sleep するみたいなものでしょう…)
この 「2^16 回」というのは 「98%のlockが取得できる回数」です。 (参考 Thomas Friebel: Xen Summit talk "Preventing Guests from Spinning Around") これによって残り2%の時間を食う lock を寝させて処理の時間を削減できるようになります。
やっと PV ticket lock
さて、ここまでで guest 上の spinlock の問題は解決したわけですが、この実装は「基本的には昔の spinlock と変わらない」のでもちろん昔の spinlock にあった問題が残っていますし、さらに二つの別の問題もあります。
- 物理マシンでの spinlock と実装が異なる
- spinlock 関係の全ての処理に "PV spinlok" をするための処理の overhead が必要
これを変更し
- 上限回数までは ticket spinlock する
- それでも lock できなかった場合に、 Xen に処理を渡し block する
というのが、 "PV ticket lock" になります。 これによって overhead は
- lock をとろうと指定回数だけ spin する処理の部分
- block していた時に block していたものを起こす処理の部分
だけになります。後者はあまり起こらないケースなので、ほとんどの場合 lock をとろうとする時だけ overhead がかかるようになるわけです。
ということで、結構良さげなパッチなのですが……
This code survives for a while with moderate testing, (make -j 100 on
8 VCPUs on a 4 PCPU system), but locks up after about 20 iterations,
so there's still some race/deadlock in there (probably something
misordered), but I think the basic approach is sound.
まだどっかで deadlock してるんかいっ…!
まぁ…今後修正されるでしょう…。 kvm にもメリットありますし期待ですね。
