翼度科技»论坛 云主机 LINUX 查看内容

【WALT】update_history() 代码详解

5

主题

5

帖子

15

积分

新手上路

Rank: 1

积分
15
@
目录

【WALT】update_history() 代码详解

代码版本:Linux4.9 android-msm-crosshatch-4.9-android12
代码展示
  1. static void update_history(struct rq *rq, struct task_struct *p,
  2.                          u32 runtime, int samples, int event)
  3. {
  4.         u32 *hist = &p->ravg.sum_history[0];
  5.         int ridx, widx;
  6.         u32 max = 0, avg, demand, pred_demand;
  7.         u64 sum = 0;
  8.         u64 prev_demand;
  9.         // ⑴ 判断是否更新任务信息
  10.         if (!runtime || is_idle_task(p) || exiting_task(p) || !samples)
  11.                 goto done;
  12.        
  13.         // ⑵ 更新历史窗口数据
  14.         prev_demand = p->ravg.demand;
  15.        
  16.         widx = sched_ravg_hist_size - 1;
  17.         ridx = widx - samples;
  18.         for (; ridx >= 0; --widx, --ridx) {
  19.                 hist[widx] = hist[ridx];
  20.                 sum += hist[widx];
  21.                 if (hist[widx] > max)
  22.                         max = hist[widx];
  23.         }
  24.         for (widx = 0; widx < samples && widx < sched_ravg_hist_size; widx++) {
  25.                 hist[widx] = runtime;
  26.                 sum += hist[widx];
  27.                 if (hist[widx] > max)
  28.                         max = hist[widx];
  29.         }
  30.         p->ravg.sum = 0;
  31.         // ⑶ 计算 demand
  32.         if (sched_window_stats_policy == WINDOW_STATS_RECENT) {
  33.                 demand = runtime;
  34.         } else if (sched_window_stats_policy == WINDOW_STATS_MAX) {
  35.                 demand = max;
  36.         } else {
  37.                 avg = div64_u64(sum, sched_ravg_hist_size);
  38.                 if (sched_window_stats_policy == WINDOW_STATS_AVG)
  39.                         demand = avg;
  40.                 else
  41.                         demand = max(avg, runtime);
  42.         }
  43.         // ⑷ 计算 pred_demand
  44.         pred_demand = predict_and_update_buckets(rq, p, runtime);
  45.         trace_print_pred_demand(pred_demand, demand);
  46.         // ⑸ 将 demand 与 pred_demand 更新到 rq 中
  47.         if (!task_has_dl_policy(p) || !p->dl.dl_throttled) {
  48.                 if (task_on_rq_queued(p))
  49.                         p->sched_class->fixup_walt_sched_stats(rq, p, demand,
  50.                                                                pred_demand);
  51.                 else if (rq->curr == p)
  52.                         walt_fixup_cum_window_demand(rq, demand);
  53.         }
  54.         // ⑹ 更新任务信息
  55.         p->ravg.demand = demand;
  56.         p->ravg.coloc_demand = div64_u64(sum, sched_ravg_hist_size);
  57.         p->ravg.pred_demand = pred_demand;
  58. done:
  59.         trace_sched_update_history(rq, p, runtime, samples, event);
  60. }
复制代码
代码逻辑

update_history() 是在 WALT 算法中,任务执行到新的一个窗口的时候,对旧窗口内数据进行更新并对新窗口内 demand 进行预测的一个函数。
参数解释:

  • update_history(struct rq *rq, struct task_struct *p, u32 runtime, int samples, int event)
    p 和 rq:当前要更新信息的任务以及任务所在的运行队列(就绪队列)
    runtime:在 update_task_demand() 中记录的任务的运行时间
    samples:在 update_task_demand() 中记录的窗口数。如果记录的是上一个窗口的,或者是 n 个窗口前的某个窗口的,samples = 1;如果记录的是前 n 个窗口,samples = n,且每个窗口的执行时间都是窗口大小的归一化值。
  • u32 hist = &p->ravg.sum_history[0];
    hist 是一个指向 p->ravg.sum_history[0] 的指针。
    p->ravg.sum_history 是一个长度为 RAVG_HIST_SIZE_MAX 的数组,存放的是过去 RAVG_HIST_SIZE_MAX 个窗口中的任务的执行时间。
    此处的任务执行时间是在 update_task_demand() 中通过 scale_exec_time() 进行归一化后的时间。
    RAVG_HIST_SIZE_MAX 是用来计算 demand 所需要的窗口的数量。当前版本内核中 RAVG_HIST_SIZE_MAX 默认为 5。
  • int ridx, widx;
    用来更新 p->ravg.sum_history 所需的参数。
  • u32 max = 0, avg, demand, pred_demand;
    max 是 p->ravg.sum_history 中的最大值;avg 是 p->ravg.sum_history 中的平均值。
    demand:通过 p->ravg.sum_history 中的值来预测下一个窗口中负载的情况,即任务可能在下一个窗口中的运行时长的归一化值。这个值通常用于任务选核、迁核。
    pred_demand:根据桶算法来预测下一个窗口中负载的情况。这个值通常用于调频。
  • u64 sum = 0;
    sum 是 p->ravg.sum_history 中的所有值的和。
  • u64 prev_demand;
    这个值记录上一个窗口中计算而得的 demand 值。
⑴ 判断是否更新任务信息

if (!runtime || is_idle_task(p) || exiting_task(p) || !samples)

  • 如果上个窗口内没有执行时间;
  • 如果任务是 idle 任务;
  • 如果任务正在退出;
  • 如果 samples == 0,
就直接结束,不进行更新。
⑵ 更新历史窗口数据

先通过 prev_demand = p->ravg.demand; 保存上一个窗口的 demand。
sum_history[RAVG_HIST_SIZE_MAX]

介绍一下保存历史窗口负载的数组 sum_history[RAVG_HIST_SIZE_MAX]。
默认情况下,sched_ravg_hist_size = RAVG_HIST_SIZE_MAX = 5,其中 sched_ravg_hist_size 可以根据需求来进行调整。
widx = sched_ravg_hist_size - 1; widx 是设定中最旧窗口的下标。“设定中”的意思是,如果 sched_ravg_hist_size 不等于 RAVG_HIST_SIZE_MAX,那么 sum_history[widx] 指向的就是我们调整窗口数量之后的最旧的窗口。
ridx = widx - samples; ridx 是更新之后的最旧窗口的下标。“更新之后”的意思是,我们要保证 sum_history[0] 始终是上一个窗口的执行时间,如果更新了不止一个窗口,如更新了 samples 个窗口,那么最旧的 samples 个窗口就要被舍弃,同时将前面还未被舍弃的窗口往后挪 samples 个位置,这样才能将第 0 个位置留给上一个窗口。
执行过程如下:
  1. 设 samples = 2,即本次更新了 2 个窗口
  2. sum_history:[  a  ] [  b  ] [  c  ] [  d  ] [  e  ]
  3.                0       1       2       3       4
  4.                ↑       ↑       ↑       ↑       ↑
  5.                               ridx            widx
  6. 第一个 for 循环:
  7.         for (; ridx >= 0; --widx, --ridx) {
  8.                 hist[widx] = hist[ridx];
  9.                 // 累加剩余的旧窗口的值
  10.                 sum += hist[widx];
  11.                 // 计算最大值
  12.                 if (hist[widx] > max)
  13.                         max = hist[widx];
  14.         }
  15. 第一次循环后结果:
  16. sum_history:[  a  ] [  b  ] [  c  ] [  d  ] [  c  ]
  17.                0       1       2       3       4
  18.                ↑       ↑       ↑       ↑       ↑
  19.                       ridx            widx
  20. 第二次循环后结果:
  21. sum_history:[  a  ] [  b  ] [  c  ] [  b  ] [  c  ]
  22.                0       1       2       3       4
  23.                ↑       ↑       ↑       ↑       ↑
  24.               ridx            widx
  25. 第三次循环后结果:
  26. sum_history:[  a  ] [  b  ] [  a  ] [  b  ] [  c  ]
  27.                0       1       2       3       4
  28.                ↑       ↑       ↑       ↑       ↑
  29.       ridx            widx
  30. 第二个 for 循环的开头将 widx 设置为 0:
  31. sum_history:[  a  ] [  b  ] [  a  ] [  b  ] [  c  ]
  32.                0       1       2       3       4
  33.                ↑       ↑       ↑       ↑       ↑
  34.       ridx    widx      
  35.         for (widx = 0; widx < samples && widx < sched_ravg_hist_size; widx++) {
  36.                 hist[widx] = runtime;
  37.                 // 累加新窗口的值
  38.                 sum += hist[widx];
  39.                 // 计算最大值
  40.                 if (hist[widx] > max)
  41.                         max = hist[widx];
  42.         }
  43. 第一次循环后结果:
  44. sum_history:[ s_w ] [  b  ] [  a  ] [  b  ] [  c  ]
  45.                0       1       2       3       4
  46.                ↑       ↑       ↑       ↑       ↑
  47.       ridx            widx      
  48. 第一次循环后结果:
  49. sum_history:[ s_w ] [ s_w ] [  a  ] [  b  ] [  c  ]
  50.                0       1       2       3       4
  51.                ↑       ↑       ↑       ↑       ↑
  52.       ridx                    widx
  53. 因为 samples > 1 的时候 runtime 都是 scaled_window,所以填入的都是 s_w。
复制代码
最后令 p->ravg.sum = 0; ,进行下一次 WALT 算法中 runtime 的累加。
⑶ 计算 demand

在当前版本中,WALT 算法设置了四种策略,分别通过不同的方法来计算 demand。
其中,avg = div64_u64(sum, sched_ravg_hist_size);

  • sched_window_stats_policy == WINDOW_STATS_RECENT
    demand = runtime; 直接将 demand 设置为上一个窗口的 runtime。
  • sched_window_stats_policy == WINDOW_STATS_MAX
    demand = max; 直接将 demand 设置为历史窗口中 runtime 的最大值。
  • sched_window_stats_policy == WINDOW_STATS_AVG
    demand = avg; 直接将 demnad 设置为历史窗口中 runtime 的平均值。
  • sched_window_stats_policy == WINDOW_STATS_MAX_RECENT_AVG(默认情况)
    demand = max(avg, runtime); 在上一个窗口的 runtime 和 历史窗口中 runtime 的平均值中选取最大值作为 demand。
⑷ 计算 pred_demand

根据桶算法来计算 pred_demand:pred_demand = predict_and_update_buckets(rq, p, runtime);
点击此处查看 predict_and_update_buckets() 代码详解。
⑸ 将 demand 与 pred_demand 更新到 CPU 负载中

【WALT】调度与负载计算 中详细描述了 WALT 是如何将之前计算的 demand 和 pred_demand 更新到 CPU 负载之中的。
⑹ 更新任务信息

p->ravg.demand = demand;
p->ravg.coloc_demand = div64_u64(sum, sched_ravg_hist_size);
将历史窗口中的平均值赋进 coloc_demand 中。
p->ravg.pred_demand = pred_demand;
点击此处回到 WALT 入口函数 update_task_ravg()

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

举报 回复 使用道具