【WALT】update_task_demand() 代码详解

流泪的小鱼

目录

• 【WALT】update_task_demand() 代码详解
  
  
  
  • 代码展示
    
  • 代码逻辑
    
    
    
    • 用于判断是否进入新窗口的标志位
      
    • ⑴        不累加任务运行时间的条件判断
      
    • ⑵        仍在旧窗口中
      
    • ⑶        进入新窗口
      
    • ⑷        返回值 runtime
      
    
    
  
  

【WALT】update_task_demand() 代码详解

代码版本：Linux4.9 android-msm-crosshatch-4.9-android12
代码展示

1. static u64 update_task_demand(struct task_struct *p, struct rq *rq,
2.                                int event, u64 wallclock)
3. {
4.         u64 mark_start = p->ravg.mark_start;
5.         u64 delta, window_start = rq->window_start;
6.         int new_window, nr_full_windows;
7.         u32 window_size = sched_ravg_window;
8.         u64 runtime;
10.         // 用于判断是否进入新窗口的标志位
11.         new_window = mark_start < window_start;
12.         // ⑴ 不累加任务运行时间的条件判断
13.         if (!account_busy_for_task_demand(rq, p, event)) {
14.                 if (new_window)
15.                         update_history(rq, p, p->ravg.sum, 1, event);
16.                 return 0;
17.         }
18.        
19.         // ⑵ 仍在旧窗口中
20.         if (!new_window) {
21.                 return add_to_task_demand(rq, p, wallclock - mark_start);
22.         }
24.         // ⑶ 进入新窗口
25.         delta = window_start - mark_start;
26.         nr_full_windows = div64_u64(delta, window_size);
27.         window_start -= (u64)nr_full_windows * (u64)window_size;
28.        
29.         runtime = add_to_task_demand(rq, p, window_start - mark_start);
31.         update_history(rq, p, p->ravg.sum, 1, event);
32.         if (nr_full_windows) {
33.                 u64 scaled_window = scale_exec_time(window_size, rq);
35.                 update_history(rq, p, scaled_window, nr_full_windows, event);
36.                 runtime += nr_full_windows * scaled_window;
37.         }
39.         window_start += (u64)nr_full_windows * (u64)window_size;
40.        
41.         mark_start = window_start;
42.         runtime += add_to_task_demand(rq, p, wallclock - mark_start);
43.        
44.         // ⑷ 返回值 runtime
45.         return runtime;
46. }

复制代码

代码逻辑

用于判断是否进入新窗口的标志位

WALT 算法中，引入了一个新的概念：窗口（sched_ravg_window）
先介绍几个名词：

• ws：window_start，当前窗口的开始时间
  
• ms：mark_start，当前任务的开始时间
  
• wc：wallclock，进入 WALT 算法的时间
  
• nr_full_windows，如果进入新窗口，则代表旧窗口到当前窗口所经历的完整的窗口个数
  
• delta：从任务开始到当前时间/新窗口开始时间所经历的时长
  

窗口分三种情况进行划分：

• 仍在旧窗口中
  1.                 ws   ms  wc
  2.                 |    |   |
  3.                 V    V   V
  4. |---------------|===============|
  5. 即进入 WALT 算法到时间还在 window_start 到 window_start + sched_ravg_window 之间
  6. 这种情况下，delta = wc - ms，只需要累加进任务时间，不需要更新

  复制代码
• 刚离开旧窗口，进入下一个窗口
  1.            ms   ws   wc
  2.            |    |    |
  3.            V    V    V
  4. |---------------|===============|
  5. 即进入 WALT 算法到时间超过了 window_start + sched_ravg_window
  6. 但还没超过 window_start + sched_ravg_window * 2
  7. 这种情况下，delta 分为两块，一块是 ws - ms，一块是 wc - ws
  8. 两块都需要累加进任务时间，但 ws - ms 块需要进行更新，因为它在旧窗口中

  复制代码
• 经过了数个窗口后抵达新窗口
  1.            ms   ws_tmp                    ws   wc
  2.            |    |                         |    |
  3.            V    V                         V    V
  4. |---------------|----------|...|----------|===============|
  5.                 |                         |
  6.                 |<--- nr_full_windows --->|
  7. 即进入 WALT 算法到时间超过了 window_start + sched_ravg_window * 2
  8. 其中经过了 nr_full_windows 个完整窗口
  9. 这种情况下，delta 分为三块，一块是 ws_tmp - ms，一块是 wc - ws，
  10. 一块是 sched_ravg_window * nr_full_windows
  11. 三块都需要累加进任务时间，但只有 wc - ws 块不需要进行更新，因为它在新窗口中

  复制代码

通过 new_window = mark_start < window_start; 来判断是否处在 2、3 种情况之中，如果 new_window == 1，则处在 2、3 种情况之中，否则处于第 1 种情况。
⑴        不累加任务运行时间的条件判断

1. static int
2. account_busy_for_task_demand(struct rq *rq, struct task_struct *p, int event)
3. {
4.         if (exiting_task(p) || is_idle_task(p))
5.                 return 0;
6.                
7.         if (event == TASK_WAKE || (!SCHED_ACCOUNT_WAIT_TIME &&
8.                          (event == PICK_NEXT_TASK || event == TASK_MIGRATE)))
9.                 return 0;
11.         if (event == TASK_UPDATE) {
12.                 if (rq->curr == p)
13.                         return 1;
14.                 return p->on_rq ? SCHED_ACCOUNT_WAIT_TIME : 0;
15.         }
17.         return 1;
18. }

复制代码

在函数 account_busy_for_task_demand() 中会判断任务经过的时间是否是 runnable 或 running 时间，返回 1 则是，返回 0 则不是。

• 任务经过的时间是 runnable 或 running，即返回 1 的情况
  在当前版本内核中，SCHED_ACCOUNT_WAIT_TIME 默认为 1
  
  
  
  • 任务更新且任务在就绪队列中，无论是不是当前任务
    
  • 其他情况
    
  
  
• 任务经过的时间不是 runnable 或 running，即返回 0 的情况
  
  
  
  • 任务正在退出
    
  • 任务是 idle 任务
    
  • 任务刚被唤醒
    
  • 任务更新切任务不在就绪队列中
    
  
  

如果任务经过的时间不是 runnable 或 running 时间，且正好进入新窗口，就不累加任务时间，直接通过 update_history() 将上一个窗口中已经累加的时间更新至任务结构体中（task_struct）。
点击此处查看 update_history() 代码详解。
⑵        仍在旧窗口中

根据开头的分析，我们知道这种情况下不需要通过 update_history() 更新时间，只需要通过 add_to_task_demand() 累加任务时间。

1. static u64 add_to_task_demand(struct rq *rq, struct task_struct *p, u64 delta)
2. {
3.         // 1. 将 delta 时间进行归一化
4.         delta = scale_exec_time(delta, rq);
5.         // 2. 累加进 p->ravg.sum 中
6.         p->ravg.sum += delta;
7.         if (unlikely(p->ravg.sum > sched_ravg_window))
8.                 p->ravg.sum = sched_ravg_window;
10.         return delta;
11. }

复制代码

将归一化后的任务时间累加进 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()

来源:https://www.cnblogs.com/cyrusandy/p/17529893.html
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！