BORE (Burst-Oriented Response Enhancer) CPU Scheduler

GitHub repo: https://github.com/firelzrd/bore-scheduler

BORE 排程器著重在透過犧牲些許 fairness 來換取較低的 interactive task 的 scheduling latency。此外，其建構在 CFS 之上，並只對更新 vruntime 的程式碼做調整，整體改動相對其他非官方 CPU 排程器 (例如：CacULE, TT, Baby, Project C, MuQSS ^{本文最下方提供相關超連結}) 可以說是相當小。

burst time 機制

BORE 在 sched_entity 結構體中加入一名為 burst_time 的成員，用於紀錄給定 schedule entity 總共的 CPU time (實際使用 CPU 的時間)，並輔助 burst score (用於取得 task 權重值的 index) 的計算，burst score 越高 (使用越多 CPU 時間)，代表 task 越不可能是 interactive task，因此 vruntime 增加的幅度就越大，以使得 interactive task 有較好的 scheduling latency 表現：

@@ -885,6 +897,19 @@ static void update_curr(struct cfs_rq *cfs_rq)
 	curr->sum_exec_runtime += delta_exec;
 	schedstat_add(cfs_rq->exec_clock, delta_exec);
 
+#ifdef CONFIG_SCHED_BORE
+	curr->burst_time += delta_exec;
+	if(sched_feat(BURST_PENALTY)) {
+		msb = fls64(curr->burst_time >> sched_burst_granularity);
+		hi = msb << 10;
+		lo = curr->burst_time << (65 - msb) >> 54;
+		burst_score = min((hi | lo) * sched_burst_penalty_scale >> 20, (u32)39);
+		curr->vruntime += mul_u64_u32_shr(
+			calc_delta_fair(delta_exec, curr),
+			sched_prio_to_wmult[burst_score], 22);
+	}
+	else
+#endif // CONFIG_SCHED_BORE
 	curr->vruntime += calc_delta_fair(delta_exec, curr);
 	update_min_vruntime(cfs_rq);

首先，上述函式 update_curr 主要在 scheduler tick 時呼叫，而 delta_exec 表示 task 從獲得 CPU 使用權到目前為止所使用的時間(奈秒)。

接下來，第 8 ~ 10 行可以看作是對 burst time 以 2 為底取 log。因為這麼做我們會遺失一些位元，所以這操作分為 hi 及 lo 兩部份，前者也就是取完 log 的結果，而將其左移 10 個位元是為了給 lo 預留空間。

在第 10 行可看到 burst time 先被左移了 (65 - msb) 位元再右移 54 位元。這邊可以看作是將 burst time 的有效資料位移至 MSB，接下來的右移的用意是只保留有效資料的最高的 10 個位元，也就是相對低位元來說較具影響力的幾個位元。

至此，我們得知 lo 所保存的是取 log 時所失去的最高的 10 個位元。

往下看到第 11 行，這邊取得即是待會要去 sched_prio_to_wmult 查表用的 index。首先 (hi | lo) 用於將稍早計算完的對數以及遺失的位元合為一體，接著對其做 scaling，也就是乘以 sched_burst_penalty_scale，後者總是大於 1024 (增加精度)，其預設為 1217 (1.18x，以 1024 當作 1.0x 換算)。

接著，由於 (hi | lo) 以及 sched_burst_penalty_scale 都有 10 位元的精度，所以兩數相乘後，我們要把該精度褪去，也就是其中的右移 20 位元。最後，將結果與 39 (sched_prio_to_wmult table 中最大的 index) 相比，取最小者作為 burst score。

再往下，可以看到 vruntime 的指派，相關計算首先將 task 時間乘以對 sched_prio_to_wmult 查表後得到的數值，burst score 越高，查表得到的數值越大，進而讓相乘後的商越大，使得 vruntime 成長幅度越大 (越大 sched 越慢挑選此 task 來執行)。

此外，其實相乘後的商是有衰退過的 (右移 22 位元)，這個衰退是為了避免 vruntime 的增加過於快速。而此 22 位元並不是隨便挑選的，1 << 22 是 4,194,304，這對應到 sched_prio_to_wmult 的第 20 個元素，也就是 nice=0 時的 task weight：

/*
 * Inverse (2^32/x) values of the sched_prio_to_weight[] array, precalculated.
 *
 * In cases where the weight does not change often, we can use the
 * precalculated inverse to speed up arithmetics by turning divisions
 * into multiplications:
 */
const u32 sched_prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

測試

實際比較 BORE 相較 CFS 究竟給 interactive task 帶來多少 scheduling latency 的提昇。

以 jitterdebugger 搭配 stress-ng 量測

此搭配為 BORE 作者使用的量測方式之一。在這項實驗中，jitterdebugger 扮演的是 interactive task，而 stress-ng 扮演的則是背景 workload。以下實驗在 AMD 3700X (16 threads) 機器上進行，測試時間為 10 分鐘。

當 stress-ng 建立的 stressor 數量相等於 CPU 總數時，BORE 與 CFS 的結果是相似的。但當 stress-ng 生成超過 CPU 總數時 (目前以 48 個 stressor 為例)，可看出 BORE 的表現較佳。

產生工作負載以測試排程器:

$ sudo ./jitterdebugger -D 10m -c 'stress -c 48' -o res

製圖：

$ ./jitterplot  --output res.jpg hist res/results.json

下圖為 jitterdebugger 的量測結果 (使用其附帶工具繪製)，以 histogram 呈現。縱軸為次數，橫軸為時間 (

$\mu s$) 分佈。從圖中可看出 BORE 在每個 CPU 的平均 scheduling latency 的表現較 CFS 佳，tail latency (圖例中的 max) 的部份也是如此。

• CFS
  

• BORE