iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
自我挑戰組

當你凝視linux, linux也在凝視你系列 第 8

Day8 初探CFS 中

前言

昨天要處裡要返回台北的家當,所以只有簡單的介紹CFS 是什麼,以及CFS使用了什麼樣的資料結構,今天讓我們來看看到底CFS內部到底在做什麼事情。

vruntime

首先要了解的就是vruntime, 在CFS 裡面vruntime有著舉足輕重的地位,vruntime 代表的意義就是 virtual runtime,顧名思義就是行程到目前為止所運行的虛擬時間,所以對CFS 而言,為了公平起見,讓大家都能夠享有公平的運行時間,CFS會挑出vruntime最小的行程執行,也就是利用昨天講過的RB-tree的 left-most node。

那麼到底vruntime為何而生呢? 先想想CFS 會挑選vruntime 最小的行程執行, 優先權比較高的行程,應該要擁有優先執行的權利,所以應該要找到一個方法,可以讓優先權比較高的行程,能夠擁有相對小的vruntime,才能夠讓這些行程優先執行。

在Linux 裡面會透過 p->se.load 讀取行程p的權重資訊, 在Linux內的權重,會用nice 值來表示,範圍由 -20~19 數字越大代表優先權越小,行程默認的 nice 值是0,可以理解成總共有40個階級。 如果有一個行程 nice值由0 變成1,代表該行程相對於其他nice 值是0 的行程,獲得的時間要少10% ,因此nice值少1 ,代表優先權上升,也代表獲得的CPU時間會多10%,Linux內規定,當nice值是0的時候,權重值是1024。

在nice值的計算上,Linux用了很有趣的技巧,與其每次都計算到底比例是多少,不如直接建一個表作近似就可以了!! 在vruntime的部分, Linux 用了兩個表,兩個列表都放在 kernel/shed/core.c

第一個是nice值對應的權重值

const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

第二個是 2^32 / 權重值

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,
};

第二個表我們會在明天用到,第一個表就是用來近似的。
舉個簡單的例子,如果有兩個行程 nice值都是0,權重值都是1024,兩個行程都能得到50%的 CPU時間,如果其中一個行程的nice值變成1, 這樣他獲得的 CPU時間應該會變成 45% 約等於 820/(1024+820), 反之nice 值為0的行程獲得的 CPU時間會是 55% 約等於 1024/(1024+820),也因為使用了查表計算,能夠將計算簡化。

今天講完了權重表格的用法與CFS的概念,明天要看看到底 vruntime如何計算,以及第二個表格到底要做什麼用。


上一篇
Day7 初探CFS scheduler (上)
下一篇
Day9 初探CFS 下
系列文
當你凝視linux, linux也在凝視你30

尚未有邦友留言

立即登入留言