Deadlock in ULE scheduler
FreeBSD Errata Notice
今年二件目の FreeBSD Errata Notice です（Security Advisory ではありません）。要は深刻なバグ報告です。今回のスケジューラに関する不具合はちょっと面白いので詳しくみてみたいと思います(社内サーバは更新済です)。
以下はErrataを適当に訳したものです。
I. 背景
FreeBSD には二種類のスケジューラがあります：古くからの 4BSD スケジューラと、SMP を考慮した ULE と呼ばれる新しいスケジューラです。4BSD スケジューラは FreeBSD 7.0 までのデフォルトスケジューラでした。FreeBSD 7.1 からのデフォルトスケジューラは ULE となっています。
スケジューラは CPU 時間をスレッドに割り当て、スレッドを CPU に割り当てる役割を持っています。実行可能、つまり、I/O やメモリ割り当て、ロック要求といったブロッキング操作の終了を待っていないスレッドは、何れかの CPU に割り当てられた上でその CPU の実行キューに入れられます。各々のスレッドと各 CPU の実行キューは異なるロックで保護されています。
II. 問題の解説
スレッドがある CPU から別の CPU へ再割り当てされる時、スケジューラはまずスレッドのロックを取得し、次いで移行元 CPU の実行キューロックを解放します。スケジューラは移行先 CPU の実行キューロックを要求し、スレッドをキューに入れて移行先 CPU に通知するまでこのロックを保持します。最後にスレッドロックを解放する前に移行元 CPU の実行キューを再要求します。移行先 CPU の実行キューに到着した再割り当てスレッドの通知により、移行先 CPU のスレッドは処理開始前にそのスレッドのロックを取得します。
もし、同時に三つ目のスレッドが移行元と移行先の双方の CPU の実行キューロックを取得しようとすると、三竦みデッドロックが発生し得ます。
- 二番目のスレッドが移行先 CPU の実行キューを取得したが、最初のスレッドのロックを取得していない。
- 三番目のスレッドが移行元 CPU の実行キューロックを取得し、移行先 CPU の実行キューロックを待っている（これは二番目のスレッドでロックされている）。
- 最初のスレッドが自身のロックを解除するために移行元 CPU の実行キューロックを待っているが、これは三番目のスレッドが保持している。
結果として双方の CPU の実行キューがロックされ、三つのスレッドのそれぞれが異なるスレッドが保持するロックを待っていることになります。こうしてシステム内の CPUがお互いのロックを要求する状態に落ち込んでしまいます。
訳はここまで。今後コア数が増えてくると再現が困難な任意の長さのデッドロックチェーンが発生し得たわけで、この辺りで見つかって良かったと思います。