pthread のフェアネス (と ocamloptのコンテキストスイッチ)

pthread のスケジューリングがイマイチ公平でないように見えたので各環境での振る舞いについてざっと調べた． (あんまりOCamlと関係ない)

動機

前回のコードは私の環境(MacOSX 10.5.8)ではコンテキストスイッチがなかなか起こらずしばらく片方のスレッドが制御を占有し続けて、もう一方のスレッドが動作しない状況が数秒間続く．
LinuxやOpenBSDではすぐスイッチするので，必ずしも OCamlの処理系が悪いわけではなさそうだ．

実験

できるだけ ocamloptが生成するバイナリのコンテキストスイッチを模倣するようなテストコードを書いた*1．このコードは，スレッド2本を走らせてそれぞれのスレッドでループが回った回数と、(VM?レベルの)コンテキストスイッチの回数を計測する.
パラメータは次の3つ

#define TIMEOUT 50000 // context switch rate, in microseconds
#define WAIT_COUNT 0x10000 // busy wait count
#define EXIT_AFTER 1  // exit after 1 sec

TIMEOUTはコンテキストスイッチの周期、WAIT_COUNT はスレッドに埋め込んだビジーウェイトの長さ、EXIT_AFTER は計測時間だ．
50ミリ秒周期でコンテキストスイッチし1秒後に終了するので、20回スレッドが切り替わるのが理想的だ．

結果1 (Debian 5.0, kernel 2.6.26)

理想的。コメントアウトしたfprintfを実行させても分かりますが、交互に切り替わっています。

SIGALRM. thread0: 1921, thread1: 2260, switch:20
SIGALRM. thread0: 1891, thread1: 2270, switch:20
SIGALRM. thread0: 1867, thread1: 2277, switch:20
SIGALRM. thread0: 1944, thread1: 2301, switch:20
SIGALRM. thread0: 1862, thread1: 2275, switch:20
SIGALRM. thread0: 2021, thread1: 2029, switch:20
SIGALRM. thread0: 1898, thread1: 2241, switch:20
SIGALRM. thread0: 1932, thread1: 2266, switch:20
SIGALRM. thread0: 1923, thread1: 2229, switch:20
SIGALRM. thread0: 1897, thread1: 2213, switch:20
SIGALRM. thread0: 1900, thread1: 2240, switch:20
SIGALRM. thread0: 1921, thread1: 2222, switch:20

結果2 (Mac OS X 10.5.8)

これは…

SIGALRM. thread0: 4251, thread1: 0, switch:0
SIGALRM. thread0: 852, thread1: 3400, switch:1
SIGALRM. thread0: 637, thread1: 3645, switch:2
SIGALRM. thread0: 215, thread1: 4080, switch:1
SIGALRM. thread0: 4303, thread1: 0, switch:0
SIGALRM. thread0: 1721, thread1: 2579, switch:1
(以下略)

超偏ってます。1秒間のうち一度もスイッチしない状況もあるほど。統計とか素人なのでちゃんとした数字は出せませんがこれは偏りすぎている。
(しかし同じバイナリで CPUに負荷をかけた状況下だと

lockedSIGALRM. thread0: 1007, thread1: 2239, switch:13
lockedSIGALRM. thread0: 1609, thread1: 2341, switch:15
lockedSIGALRM. thread0: 1892, thread1: 1914, switch:12
lockedSIGALRM. thread0: 2577, thread1: 1389, switch:14

という数字も出ている)

結果3 (linux, kernel 2.6.18)

おぉ…偏っている…

SIGALRM. thread0: 865, thread1: 6933, switch:1
SIGALRM. thread0: 7, thread1: 8209, switch:1
SIGALRM. thread0: 2, thread1: 4775, switch:1
SIGALRM. thread0: 424, thread1: 7863, switch:1
SIGALRM. thread0: 13, thread1: 7988, switch:1
SIGALRM. thread0: 15, thread1: 7432, switch:1
SIGALRM. thread0: 15, thread1: 8135, switch:1
SIGALRM. thread0: 18, thread1: 7966, switch:1
SIGALRM. thread0: 20, thread1: 7955, switch:1

結果4 (linux, RHEL3, kernel 2.4.21)

がんばってる

SIGALRM. thread0: 1030, thread1: 5666, switch:6
SIGALRM. thread0: 2376, thread1: 4319, switch:3
SIGALRM. thread0: 3982, thread1: 2705, switch:7
SIGALRM. thread0: 4790, thread1: 1893, switch:3
SIGALRM. thread0: 4010, thread1: 2694, switch:5
SIGALRM. thread0: 3981, thread1: 2701, switch:7

議論

(あとで書く)
メモ

そもそも pthread は fairness を保証しているのか(ぉぃ
特殊な状況(ビジーループしかない)のが原因ではないか
- そもそもこんな形で深追いしてもしょうがないのではないか
mutexや条件変数を併用してるから公平でなくなるとかいうことはないか
- じゃ生の pthread スレッド 2本を走らせた場合は公平か
  - 当然公平 (thread0: 4185, thread1: 4287, switch:8307 とか)
kernel 2.6.26 優秀．
- このあたりからは completely fair schedulerというのが入っているらしいがこれが効いているのか。
- sleeper fairness というらしい(wikipediaより)．きっとこれの有無が効いている！！
MacはBSD系というが NetBSDやOpenBSDではどうも fairぽかった (けどカーネルのバージョンの調べ方が分からん)
- Mach カーネル? よくわからん
どこに聞けばわかるかどのソースを深追いすれば分かるのか？
実はもっと正しいやり方があるのか, ソフトウェア側ではどうしようもないのか
- リーズナブルにfairnessが達成できるならそっちのほうがいいよね

*1:相変わらずのなんちゃって英語...