Orz日記 by Akio Morita

_ [FreeBSD]ULEスケジュラーをいじってみる

昨日のパッチで nice付きのバッチプロセスを idle queueへ突っ込むとidle queue内でラウンドロビンしない (timeshare queueじゃ無いからなぁ…)上に、 timeshare queueでプロセッサーが埋まると動かない(idleだからだが)

したがって、fork-waitモデルでnice付き worker processを大量に抱えるモデルだと worker process間の公平性が損なわれる、 他のタスクロードがある場合、worker processが idle queue内でストールし 続ける問題があるので、実用的には無理なので別案を試してみた。

nice値によらず timeshare queueでは定期的(多少、優先度による配給順の 偏りがあるが大きく偏らない)にtime sliceが配られるので、 time slice消費し尽した後に thread rescheduleを要求する sched_clock側に細工をしてみた

具体的には下記のパッチで、配給されるtime sliceの消費速度に nice値で荷重を付けることで、nice付きプロセスへの プロセッサー割り当てを減らすアプローチである

プロセスへのプロセッサ割り当てをnice値によって傾斜配分するという点に 関しては、期待通りで、nice付きでCPU時間を貪り食うプロセスが timeshare queueが埋まっている状況であっても、 nice無しのプロセスに積極的にプロセッサ時間が割り当てられるので、 フォアグラウンドの演算タスクの応答性がかなり改善した

運用上の主な問題は二つある。

一つ目は、thread queueがプロセッサ単位なため、プロセッサ時間の 傾斜配分はプロセッサ毎のthread queue内での分配となるために、 同一のnice値が付いたプロセスであっても、挿入されたthread queueの 混雑状況で、thread queueを跨いだプロセス間のプロセッサ時間の 割り当てが公平とならない点

二つ目は、time ticks毎の処理を変えてるだけなので、time sliceの配給単位と 最小のtime slice単位から決まる比率を越えるバイアスをかけられない点である (実測では、1:9程度の実行比率ぐらいが限界)

本当は、指数関数的な傾斜配分で沈めてるプロセスには 1/100程度のプロセッサ時間割り当てに抑えたいのだが…

実行時間が長く優先度の低い並列worker processを公平に駆動するには、 スケジューリング単位よりも長いスパンでプロセッサ割り当て時間比率を 統計し、スケジューリング集合内での nice値毎の割り当て比率が 所望の比率に収斂するように割り当てるtime sliceを管理する必要がある。 また、プロセッサ毎のthread queue間で実行時間の公平性を担保するために theradを入れ替えも必要となる(CPU affinity的には損になるが)

特に、shared memory経由で worker process間のメッセージパッシングを 行なう系の実装では、worker process間のプロセッサ割り当て時間の 均衡が崩れると性能の劣化につながることが懸念される

Index: sys/kern/sched_ule.c
===================================================================
--- sys/kern/sched_ule.c	(revision 306791)
+++ sys/kern/sched_ule.c	(working copy)
@@ -2286,10 +2286,28 @@
 	 * Force a context switch if the current thread has used up a full
 	 * time slice (default is 100ms).
 	 */
+#if 0
 	if (!TD_IS_IDLETHREAD(td) && ++ts->ts_slice >= tdq_slice(tdq)) {
 		ts->ts_slice = 0;
 		td->td_flags |= TDF_NEEDRESCHED | TDF_SLICEEND;
 	}
+#endif
+	if (!TD_IS_IDLETHREAD(td)) {
+		if (td->td_proc->p_nice > 0 && tdq_slice(tdq) > ts->ts_slice) {
+			const int nice = td->td_proc->p_nice;
+			const int exp1m_nice = (3 * nice * nice + 256) * (3 * nice + 16) - 4096;
+#ifdef SMP
+			ts->ts_slice += imax(0, (exp1m_nice + (sched_random() % 4096)) / 4096);
+#else
+			ts->ts_slice += imax(0, (exp1m_nice                          ) / 4096);
+#endif
+		}
+		if (++ts->ts_slice >= tdq_slice(tdq)) {
+			ts->ts_slice = imax(0, ts->ts_slice - tdq_slice(tdq));
+			td->td_flags |= TDF_NEEDRESCHED | TDF_SLICEEND;
+
+		}
+	}
 }

 u_int