网站建设项目创业计划书,团员个人信息查询官网,购物网站建设机构,网络科技官网网站建设简介
deadline调度是比rt调度更高优先级的调度#xff0c;它没有依赖于优先级的概念#xff0c;而是给了每个实时任务一定的调度时间#xff0c;这样的好处是#xff1a;使多个实时任务场景的时间分配更合理#xff0c;不让一些实时任务因为优先级低而饿死。deadline调度…简介
deadline调度是比rt调度更高优先级的调度它没有依赖于优先级的概念而是给了每个实时任务一定的调度时间这样的好处是使多个实时任务场景的时间分配更合理不让一些实时任务因为优先级低而饿死。deadline调度不是说必须在这个deadline时间点前跑完任务而是在一个调度周期内期望在deadline之前调度一次这个任务。理论上这个任务跑的时间是有可能超过deadline时间点甚至period时间点。
deadline调度策略
三个参数
关于rt调度中优先级是怎么起作用的可以参考之前的一个文章https://blog.csdn.net/qq_37517281/article/details/134080158
deadline调度用三个额定参数来控制调度dl_runtime允许跑的时间 / dl_deadline期望在一个调度周期内等待不超过dl_deadline的时间内被调度一次 / dl_period调度周期。其中dl_runtime dl_deadline dl_period。它期望在一个dl_period时长内任务只能跑dl_runtime的时长如果没有跑完这个时长且在同一时间周期内的下次再调度时只能跑此时到deadline还剩的时间中dl_runtime/dl_deadline的时长如果下次唤醒已经跳到下一个周期则可以重新跑dl_runtime的时长但如果上次跑的时间超过额定的dl_runtime导致runtime0则从下一周期中可跑时长应减去超出的时长new_runtime dl_runtimeruntime其中runtime0。一个例外是有太多deadline任务导致某个不幸的deadline任务长时间没被调度则下几个周期后他能跑的时长还是重置为dl_runtime。
一个cpu上的task按deadline先到的顺序组织为一个红黑树dl_rq-root其中支持迁移的task还会额外组织成一个红黑树dl_rq-pushable_dl_tasks_root。
一个周期内实际可运行的时长用runtime表示与dl_runtime都表示时长但到达的时间点用deadline表示是一个时间点与dl_deadline表示一个周期内的时长相区别。
每个cpu运行队列的最早deadline组成了一个大顶堆顶上的cpu的最早deadline最晚到达当一个任务需要迁移时在没有idle cpu的情况下优先选最早deadline最晚到达的cpu做迁移find_later_rq
当一个任务执行了runtime后会有timer让它不再执行(dl_throttled)它的下一次可重新被调度的时间点为deadline(dl_period - dl_deadline)。start_dl_timer
bandwidth与density
有两个概念不易理解bandwidth runtime/perioddensity runtime/deadline。
可以简单认为bandwidth是cpu与cpu负载之间的关系density是一个cpu上任务与任务之间的关系。
bandwidth
bandwidth与utilizationruntime占整个周期的比例的概念可以等同每个cpu默认有global_rt_runtime(0.95e9) / global_rt_period(1e9) 0.95 的bandwidthinit_dl_rq_bw_ratio。当一个cpu的总bandwith(sum(runtime)/period)小时有可能在运行deadline任务之后将剩余的dl_period-dl_deadline的时长用于运行一些非deadline的任务比如低级别的cfs任务但grub_reclaim函数会尽可能减少这种可能尽量让deadline任务先做。
total_bw一个cpu调度域中所有cpu的deadline task的bandwidth。其中包含所有从其它调度类提升优先级而来的task。bw常量一个cpu调度域的每个cpu的最大bandwidth等于global_rt_runtime(0.95e9) / global_rt_period(1e9)0.95extra_bw一个cpu运行队列上可分摊到其它域内cpu的空闲bandwidth最初没有任务时extra_bwmax_bw。this_bw一个cpu运行队列上active 与非active的task的bandwidth和。max_bw常量一个cpu运行队列上的最大bandwidth等于global_rt_runtime(0.95e9) / global_rt_period(1e9)0.95。running_bw一个cpu运行队列上非inactive任务的bandwidth它的更新有延迟。wakeup任务时就可add但任务block 要sub这个bandwidth要等到快到deadline时间点称为zerolag_time更准确的讲是等到deadline前这个时长的时间点(runtime/dl_runtime)×dl_period。可以参考下面的图图中有三种状态 active contending唤醒状态进入运行队列non contending挂起任务移出运行队列但还没有到zerolag_time时间点inactive挂起任务移出运行队列且本周期已结束另外还有一个状态 throttled当一个任务执行runtime后没执行完要先睡至下个周期开始。或者任务主动yield也是throttled状态。两种情况都要移出运行队列。但其bw依然认为是在队列上且running的。可以认为还在active contending状态。 ** ------------------* wakeup | ACTIVE |* ------------------ contending |* | add_running_bw | |* | ----------------* | | ^* | dequeue | |* --------------- | |* | | t 0-lag | | wakeup* | INACTIVE |--------------- |* | | sub_running_bw | |* --------------- | |* ^ | |* | t 0-lag | |* | | |* | V |* | ----------------* | sub_running_bw | ACTIVE |* ------------------- |* inactive timer | non contending |* fired ------------------*
当向一个调度域中加入一个task时调度域的total_bw会增加但要先校验是否overflow即total_bw new bw * total_capacitytotal_capacity指域内所有cpu的算力。然后在每个cpu上均摊减掉extra_bw。
density
density是一个cpu上各deadline任务之间的一个平衡概念期望每个deadline任务的density都不超过额定的dl_runtime/dl_deadlineCBS rule当有任务在一个调度周期内睡眠一定时间又被唤醒时这个突发的唤醒可能导致它的density过高因为这个周期的时间已经只剩一部分了剩余runtime还按完整周期来算当然会高需要尝试减少它可执行时长来平衡与其它任务的关系Revised CBS rule即 runtime (deadline - now) * density。update_dl_revised_wakeup
其它名词
dl.overloaded与pushable_queueoverload不是说真的任务忙而是说这个队列有可在其它cpu执行的任务记在pushable_queue红黑树上。当这个任务没有在运行时允许其它队列与任务比较deadline的先后如果比队列的所有任务deadline都早就尝试steal这个任务去执行特殊情况是这个任务比队列的deadline都早但任务又在一些关键区而被设置了无法迁移migrate_disable这时的策略是给队列一个信号让它去检查是否可以把在运行的任务迁移出去从而给这个不能迁移的任务一个运行机会。 task生命周期
通用调度过程
调度的大体过程为
1、选下一个任务__schedule-pick_next_task这里会先pull一些其它队列的任务过来dl_sched_class-balance-pull_dl_task然后将前一个任务放下dl_sched_class-put_prev_task选下一个任务dl_sched_class-pick_next_task将它set到队列的next上pick_next_taskset_next_task同时注册push的callbackset_next_task-deadline_queue_push_tasks
、切换上下文context_switch-switch_to
、切换之后尝试调push callback将一些可迁移任务给其它cpu队列finish_task_switch-finish_lock_switch-__balance_callbacks-push_dl_tasks
deadline任务生命周期
一个任务被选中的开始是第一步中的set_next_task_dl在这里开启一个计时器至可运行时长runtime结束start_hrtick_dl切换运行前会将任务从迁移队列移出dequeue_pushable_dl_task然后运行一段时间后可预见两种情况其它情况比如优先级提升主要re
、runtime用完高精计时器到达触发task_tick_dl
、主要yield让出cpu触发yield_task_dl
这两种都会调用update_curr_dl更新剩余runtime。如果runtime用完了队则任务退出运行列和可迁移队列__dequeue_task_dl标记throtled并启动计时至下个周期开始start_dl_timer才重新回到队列。如果runtime没有用完比如set_next_task_dl-start_hrtick_dl开始计时后被其它进程抢占又回到这个进程执行则runtime没有用完这时如果它还是最先到deadline的task则会对剩余的runtime重新调start_hrtick_dl计时。如果是主动sleep的情况虽然退出队列了但不会马上将bandwidth去掉而是开启inactive_task_timer计时到deadline时间点才将bandwidth去掉实际是deadline - dl_period*(runtime/dl_runtime)的时间点task_non_contending。
在中断恢复时触发一次系统的schedule()它会走pick_next_task的流程根据deadline是否还是最先到达来决定是否换到其它任务。它可能会选中其它任务这时将原任务放回可迁移队列put_prev_task_dl-enqueue_pushable_dl_task
当throtled到的下一个周期到达时会将task重新加回运行队列dl_task_timer-enqueue_task_dl(ENQUEUE_REPLENISH)并标记resched_curr()来让调度器发现这个任务重新做抉择。
剩余runtime的扣除
上面提到的更新剩余runtime的方法在grubGreedy Reclamation of Unused Bandwidth算法中不是直接减去运行时长而是 这个公式在扣除runtime时考虑了总体空闲的情况将总体的非active的时长(not running 和 extra的时长)分一部分给这个task让他能再多跑一会可以看到runtime减去的时间一定小于真实duration从而减少一个周期内deadline任务都被延迟到下一周期而本周期中没有deadline任务可跑的情况。参考的这个pdf:http://retis.santannapisa.it/luca/ospm-summit/2017/Downloads/deadline_reclaiming.pdf不确定我的理解对不对
代码注释
enqueue_task_dl
enqueue_task_dl():// 如果task是从其它优先级提升到deadline的// 则不需要throttled到下个周期因为它只是个临时行为//比如一个cfs进程1拿了一个锁而一个deadline进程2在等这个锁// 则进程1会临时提升为deadline调度级别if (is_dl_boosted() || !dl_prio(p-normal_prio)) {p-dl.dl_throttled 0;}// 如果一个task还没有throttled且超过了deadline则标记throttled// 并启动计时期至下个周期才解除throttleddeadline (dl_period - dl_deadline)// 和重新装填runtime 和 deadline并在deadline前合适的时候调度if (!p-dl.dl_throttled !dl_is_implicit(p-dl))dl_check_constrained_dl(p-dl);enqueue_dl_entity():if (flags ENQUEUE_WAKEUP) {// 如果是一个从suspend状态激活的任务且当前时间还没有超过deadline// 由于这个周期的时间已经只剩一部分了而原来的runtime是按完整周期来算// 算出的density(runtime/deadline)会比额定的(dl_runtime/dl_period)要大。// 所以要对可运行时间做修剪:// runtime (dl_runtime / dl_deadline) * (deadline - now())//// 对于超过deadline说明这个周期内都没有调度机会// 或已经用完了这个周期的运行时间后睡眠了dl_period-dl_deadline时长// 这时可以直接重置 runtime dl_runtime, deadline now dl_deadlineupdate_dl_entity();} else if (flags ENQUEUE_REPLENISH) {// 通过优先级提升来的task或主要释放cpu的task// 或时间已经超过一个周期的task可以重置runtime 与 deadline// 而因为上个周期执行太久或cpu主频变化导致的执行时间超过可运行时间的场景// runtime是负的需要在下个周期中将多的可运行时间减掉 (runtime dl_runtime)replenish_dl_entity(dl_se);} else if (flags ENQUEUE_RESTORE) {// 因修改task参数(比如修改优先级或可运行的cpu集合)// 导致的dequeue和重新enqueue强制重置runtime与deadlinesetup_new_dl_entity()}__enqueue_dl_entity():// task 加入 deadline 运行队列rb_add_cached(dl_se-rb_node, dl_rq-root, __dl_less);// 更新cpu队列上最早的deadline值// 并更新这个cpu的最早deadline值在整个调度域中的排名//按从deadline晚到早排序用堆结构来组织// 可用于为一个任务选择下个周期在哪个cpu上执行优选deadline晚的执行inc_dl_tasks(dl_se, dl_rq);// 如果这个任务支持在其它cpu上跑则可以被别人拿走执行// 按deadline先后进入pushable排序队列enqueue_pushable_dl_task()
dequeue_task_dl
dequeue_task_dl()// 更新任务的runtime如果runtime用完则要throtle退出队列并在下个周期开始时回到队列 update_curr_dl();__dequeue_task_dl():// 除去运行队列中的项更新cpu的最先到达deadline// 和在所有cpu最先到达deadline大顶堆中的位置dequeue_dl_entity();// 从可迁移队列移出如果没有可迁移task则清除overload标记dequeue_pushable_dl_task();// 对于 sleep 导致的出队需要开启计时inactive_timer到deadline的时间点再更新bandwidthtask_non_contending();
update_curr_dl
按grub算法扣除可运行时长如果没有可运行时长了则throttle至下个周期
// 在运行一段时间后中断中调用。
update_curr_dl()// 更新执行时间 update_current_exec_runtime();// 扣除时长为 dq -(max{u, (Umax - Uinact - Uextra)} / Umax) dtdl_se-runtime - grub_reclaim();// 如果剩余runtime小于0或主动让出cpu则标记throttled但这不会改变其bandwidthif (dl_runtime_exceeded(dl_se) || dl_se-dl_yielded) {dl_se-dl_throttled 1;// 将它移出队列__dequeue_task_dl();// 如果它是其它调度类通过优先级提升而来的任务(这种临时任务不用睡眠等待)// 或dl任务启动计时失败则再加回来if (unlikely(is_dl_boosted(dl_se) || !start_dl_timer(curr)))enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH);// 大概率它不在运行队列上了所以标记重调度if (!is_leftmost(curr, rq-dl))resched_curr(rq);
pull_dl_task
从其它cpu的可迁移队列拉任务过来。
比如从deadline类型转为其它类型发现没有deadline任务可以调度了switched_from_dl
pull_dl_task():// 遍历每个有可迁移任务的cpufor_each_cpu(cpu, this_rq-rd-dlo_mask) {// 找到比当前cpu的deadline先到的task从这些task中找到最早到deadline的..// 如果可在本cpu运行则拿来。deactivate_task(src_rq);set_task_cpu(this_cpu);activate_task(this_rq);// 如果因为一些临时原因不能迁移则尝试在它所在cpu上换掉正运行的// (前提是正运行的task可迁移为它找合适的迁移队列)stop_one_cpu_nowait(push_cpu_stop);}
push_dl_tasks
将可迁移任务主动推到其它cpu执行
比如下一个task不能抢占当前task且下一个可以迁移task_woken_dl
这里代码为纯逻辑顺序没按原代码组织原代码版本linux v6.6
push_dl_tasks():// 尝试迁移每个pushable task直到有一个迁移失败。while (push_dl_task(rq)):next_task pick_next_pushable_dl_task(rq);find_lock_later_rq(next_task):// 为这个任务找合适的队列迁移过去find_later_rq();// 如果找到了下一个队列则入那个队并resched_curr那个队列。deactivate_task(rq, next_task, 0);set_task_cpu(next_task, later_rq-cpu);activate_task(later_rq, next_task, 0);resched_curr(later_rq);// 如果没找到下一个队列且没有新的pushable task加入则不再尝试if (!dl_task_is_earliest_deadline(task, later_rq)) break;// 如果pushable task变了则有可能有新task重试最多三次。..find_later_rq():// 找调度域中idle的cpu中bandwidth能满足这个task的cpu集合// 如果bandwidth都不满足则找算力最大的cpu// 如果没有 free 的 cpu则找最早deadline大顶堆中最晚到达deadline的那个cpu,// 确认这个任务的deadline在那个cpu的最早deadline之前并选中它// 找到的cpu或cpu集合标记为cpudl_find(task_rq(task)-rd-cpudl, task, later_mask);// 从原cpu的domain里一层层向上找,与上面备选集合A的交集// 如果有cpu要求在唤醒过程中考虑亲和性SD_WAKE_AFFINE标记则优先考虑for_each_domain(cpu, sd) {// 如果当前cpu在这个集合中则用当前cpu是最好的不做迁移// 否则用round-robin方式在cpu集合B中找一个cpucpumask_any_and_distribute(later_mask, sd);}如果所有备选cpu都没有SD_WAKE_AFFINE标记则用round-robin方式在备选集合中找一个cpucpumask_any_distribute(later_mask);
set_next_task_dl
标记即将运行的任务是这个任务
set_next_task_dl():// 将要在本cpu运行的task不再支持被其它cpu倫过去执行dequeue_pushable_dl_task();// 启动定时到可运行时长runtime耗尽start_hrtick_dl();// 更新load值// 参考https://blog.csdn.net/qq_37517281/article/details/134039766update_dl_rq_load_avg非deadline调度类load sum 累加0load avg 累加1,// 在切换至这个task后尝试将下一个到deadline的进程迁移到其它cpu执行deadline_queue_push_tasks(push_dl_tasks);
wakeup_preempt_dl
判断是否可抢占当前task
wakeup_preempt_dl():// 两任务deadline不同选deadline先到的// 两任务deadline相同原则是尽可能不抢占可抢占的条件// 运行中任务可移动且超过了deadline且要换入的任务不可移动且deadline没到。
put_prev_task_dl
将前一个任务从运行队列移除
put_prev_task_dl():// 扣除运行时长update_curr_dl();// 累积load_sum/avgupdate_dl_rq_load_avg();// 如果任务可在其它cpu执行则加入可迁移队列并在下次调度时尝试迁移enqueue_pushable_dl_task();
switched_to_dl
从其它调度类型切至deadline调度
switched_to_dl():// 如果这个任务在一个周期时间内迁走又迁回则将计时器去掉if (hrtimer_try_to_cancel(p-dl.inactive_timer) 1)put_task_struct(p);// 任务不是当前队列的任务if (rq-curr ! p) {// 如果它可迁移加入pushable队列deadline_queue_push_tasks();// 尝试抢当前在跑的taskwakeup_preempt_dl();}// 如果提升优先级变为deadline任务或用户指定它调度类型变更// 它的cpu没有变还是之前运行的cpu需要更新下loadupdate_dl_rq_load_avg();
