代碼版本：Linux4.9 android-msm-crosshatch-4.9-android12
代碼展示
static u64 update_task_demand(struct task_struct *p, struct rq *rq,
int event, u64 wallclock)
{
u64 mark_start = p->ravg.mark_start;
u64 delta, window_start = rq->window_start;
int new_window, nr_full_windows;
u32 window_size = sched_ravg_window;
u64 runtime;
// 用于判斷是否進(jìn)入新窗口的標(biāo)志位
new_window = mark_start < window_start;
// ⑴ 不累加任務(wù)運(yùn)行時(shí)間的條件判斷
if (!account_busy_for_task_demand(rq, p, event)) {
if (new_window)
update_history(rq, p, p->ravg.sum, 1, event);
return 0;
}
// ⑵ 仍在舊窗口中
if (!new_window) {
return add_to_task_demand(rq, p, wallclock - mark_start);
}
// ⑶ 進(jìn)入新窗口
delta = window_start - mark_start;
nr_full_windows = div64_u64(delta, window_size);
window_start -= (u64)nr_full_windows * (u64)window_size;
runtime = add_to_task_demand(rq, p, window_start - mark_start);
update_history(rq, p, p->ravg.sum, 1, event);
if (nr_full_windows) {
u64 scaled_window = scale_exec_time(window_size, rq);
update_history(rq, p, scaled_window, nr_full_windows, event);
runtime += nr_full_windows * scaled_window;
}
window_start += (u64)nr_full_windows * (u64)window_size;
mark_start = window_start;
runtime += add_to_task_demand(rq, p, wallclock - mark_start);
// ⑷ 返回值 runtime
return runtime;
}
代碼邏輯
用于判斷是否進(jìn)入新窗口的標(biāo)志位
WALT 算法中，引入了一個(gè)新的概念：窗口（sched_ravg_window）
先介紹幾個(gè)名詞：
- ws：
window_start，當(dāng)前窗口的開(kāi)始時(shí)間 - ms：
mark_start，當(dāng)前任務(wù)的開(kāi)始時(shí)間 - wc：
wallclock辜御，進(jìn)入 WALT 算法的時(shí)間 -
nr_full_windows，如果進(jìn)入新窗口琳拨，則代表舊窗口到當(dāng)前窗口所經(jīng)歷的完整的窗口個(gè)數(shù) - delta：從任務(wù)開(kāi)始到當(dāng)前時(shí)間/新窗口開(kāi)始時(shí)間所經(jīng)歷的時(shí)長(zhǎng)
窗口分三種情況進(jìn)行劃分：
- 仍在舊窗口中
ws ms wc | | | V V V |---------------|===============| 即進(jìn)入 WALT 算法到時(shí)間還在 window_start 到 window_start + sched_ravg_window 之間 這種情況下等浊，delta = wc - ms，只需要累加進(jìn)任務(wù)時(shí)間抄谐，不需要更新 - 剛離開(kāi)舊窗口渺鹦，進(jìn)入下一個(gè)窗口
ms ws wc | | | V V V |---------------|===============| 即進(jìn)入 WALT 算法到時(shí)間超過(guò)了 window_start + sched_ravg_window 但還沒(méi)超過(guò) window_start + sched_ravg_window * 2 這種情況下，delta 分為兩塊蛹含，一塊是 ws - ms毅厚，一塊是 wc - ws 兩塊都需要累加進(jìn)任務(wù)時(shí)間，但 ws - ms 塊需要進(jìn)行更新浦箱，因?yàn)樗谂f窗口中 - 經(jīng)過(guò)了數(shù)個(gè)窗口后抵達(dá)新窗口
ms ws_tmp ws wc | | | | V V V V |---------------|----------|...|----------|===============| | | |<--- nr_full_windows --->| 即進(jìn)入 WALT 算法到時(shí)間超過(guò)了 window_start + sched_ravg_window * 2 其中經(jīng)過(guò)了 nr_full_windows 個(gè)完整窗口 這種情況下卧斟，delta 分為三塊，一塊是 ws_tmp - ms憎茂，一塊是 wc - ws， 一塊是 sched_ravg_window * nr_full_windows 三塊都需要累加進(jìn)任務(wù)時(shí)間锤岸，但只有 wc - ws 塊不需要進(jìn)行更新竖幔，因?yàn)樗谛麓翱谥?
通過(guò) new_window = mark_start < window_start; 來(lái)判斷是否處在 2、3 種情況之中是偷，如果 new_window == 1拳氢，則處在 2募逞、3 種情況之中，否則處于第 1 種情況馋评。
⑴ 不累加任務(wù)運(yùn)行時(shí)間的條件判斷
static int
account_busy_for_task_demand(struct rq *rq, struct task_struct *p, int event)
{
if (exiting_task(p) || is_idle_task(p))
return 0;
if (event == TASK_WAKE || (!SCHED_ACCOUNT_WAIT_TIME &&
(event == PICK_NEXT_TASK || event == TASK_MIGRATE)))
return 0;
if (event == TASK_UPDATE) {
if (rq->curr == p)
return 1;
return p->on_rq ? SCHED_ACCOUNT_WAIT_TIME : 0;
}
return 1;
}
在函數(shù) account_busy_for_task_demand() 中會(huì)判斷任務(wù)經(jīng)過(guò)的時(shí)間是否是 runnable 或 running 時(shí)間放接，返回 1 則是，返回 0 則不是留特。
- 任務(wù)經(jīng)過(guò)的時(shí)間是 runnable 或 running纠脾，即返回 1 的情況
在當(dāng)前版本內(nèi)核中，SCHED_ACCOUNT_WAIT_TIME默認(rèn)為 1- 任務(wù)更新且任務(wù)在就緒隊(duì)列中蜕青，無(wú)論是不是當(dāng)前任務(wù)
- 其他情況
- 任務(wù)經(jīng)過(guò)的時(shí)間不是 runnable 或 running苟蹈，即返回 0 的情況
- 任務(wù)正在退出
- 任務(wù)是 idle 任務(wù)
- 任務(wù)剛被喚醒
- 任務(wù)更新切任務(wù)不在就緒隊(duì)列中
如果任務(wù)經(jīng)過(guò)的時(shí)間不是 runnable 或 running 時(shí)間，且正好進(jìn)入新窗口右核，就不累加任務(wù)時(shí)間慧脱，直接通過(guò) update_history() 將上一個(gè)窗口中已經(jīng)累加的時(shí)間更新至任務(wù)結(jié)構(gòu)體中（task_struct）。
點(diǎn)擊此處查看 update_history() 代碼詳解贺喝。
⑵ 仍在舊窗口中
根據(jù)開(kāi)頭的分析菱鸥，我們知道這種情況下不需要通過(guò) update_history() 更新時(shí)間，只需要通過(guò) add_to_task_demand() 累加任務(wù)時(shí)間躏鱼。
static u64 add_to_task_demand(struct rq *rq, struct task_struct *p, u64 delta)
{
// 1. 將 delta 時(shí)間進(jìn)行歸一化
delta = scale_exec_time(delta, rq);
// 2. 累加進(jìn) p->ravg.sum 中
p->ravg.sum += delta;
if (unlikely(p->ravg.sum > sched_ravg_window))
p->ravg.sum = sched_ravg_window;
return delta;
}
將歸一化后的任務(wù)時(shí)間累加進(jìn) p->ravg.sum 中氮采，在之后的 update_history() 中會(huì)將 p->ravg.sum 放進(jìn) p->ravg.sum_history 結(jié)構(gòu)體中。
其中挠他，任務(wù)時(shí)間的歸一化是 WALT 算法中的重要部分扳抽。點(diǎn)擊此處查看 scale_exec_time() 代碼詳解。
⑶ 進(jìn)入新窗口
根據(jù)開(kāi)頭的分析殖侵，我們知道進(jìn)入新窗口分為兩種情況贸呢，無(wú)論是哪種情況，都需要累加 ws_tmp - ms 和 wc - ws 兩部分拢军。其中楞陷，如果剛離開(kāi)舊窗口進(jìn)入下一個(gè)窗口，則 ws = ws_tmp茉唉。
我們先處理 ws_tmp - ms 部分：
- 先通過(guò)
delta = window_start - mark_start;計(jì)算總體經(jīng)過(guò)的時(shí)間固蛾； - 再通過(guò)
nr_full_windows = div64_u64(delta, window_size);計(jì)算經(jīng)過(guò)的完整窗口的數(shù)量； - 最后得到 ws_tmp：
window_start -= (u64)nr_full_windows * (u64)window_size; - 累加 ws_tmp - ms 部分時(shí)間：
runtime = add_to_task_demand(rq, p, window_start - mark_start); - 更新 ws_tmp - ms 部分時(shí)間：
update_history(rq, p, p->ravg.sum, 1, event);
然后針對(duì)經(jīng)過(guò)多個(gè)完整窗口情況進(jìn)行時(shí)間更新度陆。此處不需要通過(guò) add_to_task_demand() 累加任務(wù)時(shí)間艾凯，因?yàn)槿蝿?wù)在這些完整窗口中的時(shí)間都是從窗口開(kāi)始到窗口結(jié)束。
- 先對(duì)窗口時(shí)間進(jìn)行歸一化：
scaled_window = scale_exec_time(window_size, rq); - 更新時(shí)間：
update_history(rq, p, scaled_window, nr_full_windows, event);
最后處理 wc - ws 部分懂傀。
- 把 ws 時(shí)間還原：
window_start += (u64)nr_full_windows * (u64)window_size; -
mark_start = window_start;此處不是更新任務(wù)的開(kāi)始時(shí)間趾诗，任務(wù)開(kāi)始時(shí)間在 WALT 算法的done部分進(jìn)行更新。如果任務(wù)開(kāi)始時(shí)間在此處更新，會(huì)影響到 update_cpu_busy_time() 中的計(jì)算恃泪。 - 累加 wc - ws 部分時(shí)間：
runtime += add_to_task_demand(rq, p, wallclock - mark_start);
⑷ 返回值 runtime
最后的返回值 runtime 在該版本內(nèi)核中并未使用到郑兴，它是此次執(zhí)行 update_task_demand() 時(shí)一共累加的任務(wù) runnable 和 running 時(shí)間，也就是上一次 WALT 算法開(kāi)始到這一次 WALT 算法開(kāi)始過(guò)程中贝乎，該任務(wù)的 runnable 和 running 時(shí)間情连。
