Hatena::ブログ(Diary)

Emacs ひきこもり生活 このページをアンテナに追加 RSSフィード

2010-12-08

Kernel/VM Advent Calendar 2日目: PV ticketlock ってなんですか><

| 23:53 |  Kernel/VM Advent Calendar 2日目: PV ticketlock ってなんですか><を含むブックマーク

今日もゆっくり XenML をながめているとこんなスレッドを発見

no title

ticket lock? "without expandig spinlock"? lock の一種か? なんじゃこりゃ?

ということで調べてみました。

そもそも spinlock って

spinlock は Linux でよく使われている lock のひとつ。基本的に

  • lock とる
  • なんかやる
  • 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-----
0lock----
-1workinglock---
-2workingspinlock--
-3workingspinspinlock-
-4workingspinspinspinlock
1unlockspinspinspinspin
0-spinspinspinlock

このように、ずっと待ってたスレッドをさしおいて スレッド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 という順番が保証されるようになります。

NextOwnerスレッドAスレッドBスレッドCスレッドDスレッドE
00-----
10lock----
20workinglock---
30workingspinlock--
40workingspinspinlock-
50workingspinspinspinlock
51unlockspinspinspinspin
51-lockspinspinspin
51-workingspinspinspin

PV spinlock

この spinlock ですが、 VM の中で動いているゲストの spinlock 取得は効率があまりよくなく、特に ticket spinlock とはかなり相性が悪いようです。 (Xen のスケジューラのパフォーマンスに依存してしまう)

お探しのページが見つかりませんでした | VA Linux Systems Japan株式会社

特に最近の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 にもメリットありますし期待ですね。

参考文献

Ticket spinlocks [LWN.net]

トラックバック - http://d.hatena.ne.jp/meech/20101208/1291819984