Lines Matching full:deadline
3 * Deadline Scheduling Class (SCHED_DEADLINE)
5 * Earliest Deadline First (EDF) + Constant Bandwidth Server (CBS).
366 * A flag in the deadline scheduling entity (dl_non_contending)
415 * If this is a non-deadline task that has been boosted, in task_non_contending()
426 zerolag_time = dl_se->deadline - in task_non_contending()
476 * If this is a non-deadline task that has been boosted, in task_contending()
532 /* zero means no -deadline tasks */ in init_dl_rq()
592 * The list of pushable -deadline task is not a plist, like in
593 * sched_rt.c, it is an rb-tree with tasks ordered by deadline.
605 rq->dl.earliest_dl.next = p->dl.deadline; in enqueue_pushable_dl_task()
624 dl_rq->earliest_dl.next = __node_2_pdl(leftmost)->dl.deadline; in dequeue_pushable_dl_task()
773 dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline; in replenish_dl_new_period()
780 * - the absolute deadline of the entity has to be placed at
781 * current time + relative deadline;
784 * The capability of specifying such event is useful whenever a -deadline
795 WARN_ON(dl_time_before(rq_clock(rq), dl_se->deadline)); in setup_new_dl_entity()
798 * We are racing with the deadline timer. So, do nothing because in setup_new_dl_entity()
799 * the deadline timer handler will take care of properly recharging in setup_new_dl_entity()
800 * the runtime and postponing the deadline in setup_new_dl_entity()
814 * Pure Earliest Deadline First (EDF) scheduling does not deal with the
825 * of a entity is replenished, its deadline is also postponed. That ensures
849 * We keep moving the deadline away until we get some in replenish_dl_entity()
855 dl_se->deadline += pi_of(dl_se)->dl_period; in replenish_dl_entity()
860 * At this point, the deadline really should be "in in replenish_dl_entity()
865 * resetting the deadline and the budget of the in replenish_dl_entity()
868 if (dl_time_before(dl_se->deadline, rq_clock(rq))) { in replenish_dl_entity()
882 * and its current deadline _without_ exceeding the bandwidth it is
885 * over residual deadline fits within the allocated bandwidth, then we
886 * can keep the current (absolute) deadline and residual budget without
888 * refill the runtime and set the deadline a period in the future,
889 * because keeping the current (absolute) deadline of the task would
891 * Documentation/scheduler/sched-deadline.rst for more information).
895 * runtime / (deadline - t) > dl_runtime / dl_deadline ,
899 * Notice that the bandwidth check is done against the deadline. For
900 * task with deadline equal to period this is the same of using
914 * are the relative deadline and the maximum runtime of each in dl_entity_overflow()
916 * and (deadline - t), since t is rq->clock, is the time left in dl_entity_overflow()
917 * to the (absolute) deadline. Even if overflowing the u64 type in dl_entity_overflow()
926 right = ((dl_se->deadline - t) >> DL_SCALE) * in dl_entity_overflow()
934 * re-initializing task's runtime and deadline, the revised wakeup
939 * runtime / (deadline - t) > dl_runtime / dl_deadline
942 * runtime = (dl_runtime / dl_deadline) * (deadline - t)
953 u64 laxity = dl_se->deadline - rq_clock(rq); in update_dl_revised_wakeup()
956 * If the task has deadline < period, and the deadline is in the past, in update_dl_revised_wakeup()
961 WARN_ON(dl_time_before(dl_se->deadline, rq_clock(rq))); in update_dl_revised_wakeup()
967 * Regarding the deadline, a task with implicit deadline has a relative
968 * deadline == relative period. A task with constrained deadline has a
969 * relative deadline <= relative period.
971 * We support constrained deadline tasks. However, there are some restrictions
972 * applied only for tasks which do not have an implicit deadline. See
975 * The dl_is_implicit() returns true if the task has an implicit deadline.
983 * When a deadline entity is placed in the runqueue, its runtime and deadline
988 * case, the runtime is replenished and a new absolute deadline is set.
991 * remaining runtime and deadline could make the entity to overflow, see
993 * is detected, the runtime and deadline need to be updated.
995 * If the task has an implicit deadline, i.e., deadline == period, the Original
996 * CBS is applied. the runtime is replenished and a new absolute deadline is
1000 * deadline < period, which are said to have a constrained deadline. By
1001 * applying the Original CBS, a constrained deadline task would be able to run
1002 * runtime/deadline in a period. With deadline < period, the task would
1006 * constrained deadline tasks when a runtime overflow is detected. In the
1007 * Revisited CBS, rather than replenishing & setting a new absolute deadline,
1016 if (dl_time_before(dl_se->deadline, rq_clock(rq)) || in update_dl_entity()
1020 !dl_time_before(dl_se->deadline, rq_clock(rq)) && in update_dl_entity()
1032 return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period; in dl_next_period()
1056 * We want the timer to fire at the deadline, but considering in start_dl_timer()
1067 * chosen as the deadline is too small, don't even try to in start_dl_timer()
1119 * do nothing but clearing dl_throttled, so that runtime and deadline
1250 * runtime and period. If the deadline of the task is in the past, CBS
1252 * works fine for implicit deadline tasks (deadline == period), and the
1253 * CBS was designed for implicit deadline tasks. However, a task with
1254 * constrained deadline (deadline < period) might be awakened after the
1255 * deadline, but before the next period. In this case, replenishing the
1256 * task would allow it to run for runtime / deadline. As in this case
1257 * deadline < period, CBS enables a task to run for more than the
1261 * To avoid this problem, in the activation of a constrained deadline
1262 * task after the deadline but before the next period, throttle the
1270 if (dl_time_before(dl_se->deadline, rq_clock(rq)) && in dl_check_constrained_dl()
1393 * using deadline servers -- however there's a few nasties to figure in update_curr_dl_se()
1441 * a -deadline task and has not been removed from the dl_rq).
1535 static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) in inc_dl_deadline() argument
1540 dl_time_before(deadline, dl_rq->earliest_dl.curr)) { in inc_dl_deadline()
1543 dl_rq->earliest_dl.curr = deadline; in inc_dl_deadline()
1544 cpudl_set(&rq->rd->cpudl, rq->cpu, deadline); in inc_dl_deadline()
1548 static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) in dec_dl_deadline() argument
1565 dl_rq->earliest_dl.curr = entry->deadline; in dec_dl_deadline()
1566 cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline); in dec_dl_deadline()
1572 static inline void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {} in inc_dl_deadline() argument
1573 static inline void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {} in dec_dl_deadline() argument
1580 u64 deadline = dl_se->deadline; in inc_dl_tasks() local
1585 inc_dl_deadline(dl_rq, deadline); in inc_dl_tasks()
1595 dec_dl_deadline(dl_rq, dl_se->deadline); in dec_dl_tasks()
1600 return dl_time_before(__node_2_dle(a)->deadline, __node_2_dle(b)->deadline); in __dl_less()
1712 * Check if a constrained deadline task was activated in enqueue_dl_entity()
1713 * after the deadline but before the next period. in enqueue_dl_entity()
1757 dl_time_before(dl_se->deadline, rq_clock(rq_of_dl_se(dl_se)))) { in enqueue_dl_entity()
1858 * Yield task semantic for -deadline tasks is:
1870 * We make the task go to sleep until its current deadline by in yield_task_dl()
1893 dl_time_before(p->dl.deadline, in dl_task_is_earliest_deadline()
1915 * If we are dealing with a -deadline task, we must in select_task_rq_dl()
1917 * If it has a later deadline and the current task in select_task_rq_dl()
1920 * other hand, if it has a shorter deadline, we in select_task_rq_dl()
2021 * Only called when both the current and waking task are -deadline
2034 * In the unlikely case current and p have the same deadline in wakeup_preempt_dl()
2037 if ((p->dl.deadline == rq->curr->dl.deadline) && in wakeup_preempt_dl()
2324 * Target rq has tasks of equal or earlier deadline, in find_lock_later_rq()
2347 * If the rq we found has no -deadline task, or in find_lock_later_rq()
2348 * its earliest one has a later deadline than our in find_lock_later_rq()
2382 * See if the non running -deadline tasks on this rq
2403 dl_time_before(next_task->dl.deadline, rq->curr->dl.deadline) && in push_dl_task()
2463 /* push_dl_task() will return true if it moved a -deadline task */ in push_dl_tasks()
2518 if (p && dl_time_before(p->dl.deadline, dmin) && in pull_dl_task()
2525 * deadline than the current task of its runqueue. in pull_dl_task()
2527 if (dl_time_before(p->dl.deadline, in pull_dl_task()
2528 src_rq->curr->dl.deadline)) in pull_dl_task()
2537 dmin = p->dl.deadline; in pull_dl_task()
2680 * runtime using its current deadline. If it stays outside of in switched_from_dl()
2695 * Inactive timer is armed. However, p is leaving DEADLINE and in switched_from_dl()
2714 * Since this might be the only -deadline task on the rq, in switched_from_dl()
2725 * When switching to -deadline, we may overload the rq, then
2761 * If the scheduling parameters of a -deadline task changed,
2773 * we don't have the old deadline value, and in prio_changed_dl()
2782 * If we now have a earlier deadline task than p, in prio_changed_dl()
2786 if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline)) in prio_changed_dl()
2790 * Current may not be deadline in case p was throttled but we in prio_changed_dl()
2793 * Otherwise, if p was given an earlier deadline, reschedule. in prio_changed_dl()
2796 dl_time_before(p->dl.deadline, rq->curr->dl.deadline)) in prio_changed_dl()
2801 * We don't know if p has a earlier or later deadline, so let's blindly in prio_changed_dl()
2958 /* !deadline task may carry old deadline bandwidth */ in sched_dl_overflow()
2963 * Either if a task, enters, leave, or stays -deadline but changes in sched_dl_overflow()
2992 * Do not decrease the total deadline utilization here, in sched_dl_overflow()
3008 * absolute deadline will be properly calculated when the task is enqueued
3036 * This function validates the new parameters of a -deadline task.
3037 * We ask for the deadline not being zero, and greater or equal
3039 * greater than deadline. Furthermore, we have to be sure that
3053 /* deadline != 0 */ in __checkparam_dl()
3076 /* runtime <= deadline <= period (if period != 0) */ in __checkparam_dl()