【WALT】update_task_demand() 程式碼詳解

程式碼版本：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;

	// 用於判斷是否進入新視窗的標誌位
	new_window = mark_start < window_start;
	// ⑴ 不累加任務執行時間的條件判斷
	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);
	}

	// ⑶ 進入新視窗
	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;
}

程式碼邏輯

用於判斷是否進入新視窗的標誌位

WALT 演演算法中，引入了一個新的概念：視窗（sched_ravg_window）

先介紹幾個名詞：

• ws：window_start，當前視窗的開始時間
• ms：mark_start，當前任務的開始時間
• wc：wallclock，進入 WALT 演演算法的時間
• nr_full_windows，如果進入新視窗，則代表舊視窗到當前視窗所經歷的完整的視窗個數
• delta：從任務開始到當前時間/新視窗開始時間所經歷的時長

視窗分三種情況進行劃分：

1. 仍在舊視窗中

                   ws   ms  wc
                   |    |   |
                   V    V   V
   |---------------|===============|
   即進入 WALT 演演算法到時間還在 window_start 到 window_start + sched_ravg_window 之間
   這種情況下，delta = wc - ms，只需要累加進任務時間，不需要更新
   

2. 剛離開舊視窗，進入下一個視窗

              ms   ws   wc
              |    |    |
              V    V    V
   |---------------|===============|
   即進入 WALT 演演算法到時間超過了 window_start + sched_ravg_window
   但還沒超過 window_start + sched_ravg_window * 2
   這種情況下，delta 分為兩塊，一塊是 ws - ms，一塊是 wc - ws
   兩塊都需要累加進任務時間，但 ws - ms 塊需要進行更新，因為它在舊視窗中
   

3. 經過了數個視窗後抵達新視窗

              ms   ws_tmp                    ws   wc
              |    |                         |    |
              V    V                         V    V
   |---------------|----------|...|----------|===============|
                   |                         |
                   |<--- nr_full_windows --->|
   即進入 WALT 演演算法到時間超過了 window_start + sched_ravg_window * 2
   其中經過了 nr_full_windows 個完整視窗
   這種情況下，delta 分為三塊，一塊是 ws_tmp - ms，一塊是 wc - ws，
   一塊是 sched_ravg_window * nr_full_windows
   三塊都需要累加進任務時間，但只有 wc - ws 塊不需要進行更新，因為它在新視窗中
   

通過 new_window = mark_start < window_start; 來判斷是否處在 2、3 種情況之中，如果 new_window == 1，則處在 2、3 種情況之中，否則處於第 1 種情況。

⑴ 不累加任務執行時間的條件判斷

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

在函數 account_busy_for_task_demand() 中會判斷任務經過的時間是否是 runnable 或 running 時間，返回 1 則是，返回 0 則不是。

1. 任務經過的時間是 runnable 或 running，即返回 1 的情況
   在當前版本核心中，SCHED_ACCOUNT_WAIT_TIME 預設為 1
   • 任務更新且任務在就緒佇列中，無論是不是當前任務
   • 其他情況
2. 任務經過的時間不是 runnable 或 running，即返回 0 的情況
   • 任務正在退出
   • 任務是 idle 任務
   • 任務剛被喚醒
   • 任務更新切任務不在就緒佇列中

如果任務經過的時間不是 runnable 或 running 時間，且正好進入新視窗，就不累加任務時間，直接通過 update_history() 將上一個視窗中已經累加的時間更新至任務結構體中（task_struct）。
點選此處檢視 update_history() 程式碼詳解。

⑵ 仍在舊視窗中

根據開頭的分析，我們知道這種情況下不需要通過 update_history() 更新時間，只需要通過 add_to_task_demand() 累加任務時間。

static u64 add_to_task_demand(struct rq *rq, struct task_struct *p, u64 delta)
{
	// 1. 將 delta 時間進行歸一化
	delta = scale_exec_time(delta, rq);
	// 2. 累加進 p->ravg.sum 中
	p->ravg.sum += delta;
	if (unlikely(p->ravg.sum > sched_ravg_window))
		p->ravg.sum = sched_ravg_window;

	return delta;
}

將歸一化後的任務時間累加進 p->ravg.sum 中，在之後的 update_history() 中會將 p->ravg.sum 放進 p->ravg.sum_history 結構體中。

其中，任務時間的歸一化是 WALT 演演算法中的重要部分。點選此處檢視 scale_exec_time() 程式碼詳解。

⑶ 進入新視窗

根據開頭的分析，我們知道進入新視窗分為兩種情況，無論是哪種情況，都需要累加 ws_tmp - ms 和 wc - ws 兩部分。其中，如果剛離開舊視窗進入下一個視窗，則 ws = ws_tmp。

我們先處理 ws_tmp - ms 部分：

• 先通過 delta = window_start - mark_start; 計算總體經過的時間；
• 再通過 nr_full_windows = div64_u64(delta, window_size); 計算經過的完整視窗的數量；
• 最後得到 ws_tmp：window_start -= (u64)nr_full_windows * (u64)window_size;
• 累加 ws_tmp - ms 部分時間：runtime = add_to_task_demand(rq, p, window_start - mark_start);
• 更新 ws_tmp - ms 部分時間：update_history(rq, p, p->ravg.sum, 1, event);

然後針對經過多個完整視窗情況進行時間更新。此處不需要通過 add_to_task_demand() 累加任務時間，因為任務在這些完整視窗中的時間都是從視窗開始到視窗結束。

• 先對視窗時間進行歸一化：scaled_window = scale_exec_time(window_size, rq);
• 更新時間：update_history(rq, p, scaled_window, nr_full_windows, event);

最後處理 wc - ws 部分。

• 把 ws 時間還原：window_start += (u64)nr_full_windows * (u64)window_size;
• mark_start = window_start; 此處不是更新任務的開始時間，任務開始時間在 WALT 演演算法的 done 部分進行更新。如果任務開始時間在此處更新，會影響到 update_cpu_busy_time() 中的計算。
• 累加 wc - ws 部分時間：runtime += add_to_task_demand(rq, p, wallclock - mark_start);

⑷ 返回值 runtime

最後的返回值 runtime 在該版本核心中並未使用到，它是此次執行 update_task_demand() 時一共累加的任務 runnable 和 running 時間，也就是上一次 WALT 演演算法開始到這一次 WALT 演演算法開始過程中，該任務的 runnable 和 running 時間。

點選此處回到 WALT 入口函數 update_task_ravg()