|
SuperTinyKernel™ RTOS 1.08.x
Lightweight, high-performance, deterministic, bare-metal C++ RTOS for resource-constrained embedded systems. MIT Open Source License.
|
Earliest Deadline First (EDF) scheduling strategy: always selects the runnable task with the least time remaining before its deadline expires. More...
#include <stk_strategy_edf.h>
Public Types | |
| enum | EConfig { WEIGHT_API = 0 , SLEEP_EVENT_API = 1 , DEADLINE_MISSED_API = 0 , PRIORITY_INHERITANCE_API = 0 , NOSLEEP_YIELD_API = 0 , TIMESLICE_API = 0 } |
| Compile-time capability flags reported to the kernel. More... | |
Public Member Functions | |
| SwitchStrategyEDF () | |
| Construct an empty strategy with no tasks. | |
| STK_VIRT_DTOR | ~SwitchStrategyEDF ()=default |
| Destructor. | |
| void | AddTask (IKernelTask *task) override |
| Add task to the runnable set. | |
| void | RemoveTask (IKernelTask *task) override |
| Remove task from whichever list it currently occupies. | |
| IKernelTask * | GetNext () override |
| Select and return the task with the earliest (minimum) relative deadline. | |
| IKernelTask * | GetFirst () override |
| Get first task in the managed set (reference task for the kernel). | |
| size_t | GetSize () const override |
| Get total number of tasks managed by this strategy. | |
| void | OnTaskSleep (IKernelTask *task) override |
| Notification that a task has entered the sleeping state. | |
| void | OnTaskWake (IKernelTask *task) override |
| Notification that a task has become runnable again. | |
| virtual bool | OnTaskYield (IKernelTask *task) |
| Notification that the running task called Yield() (non-HRT kernel modes only). | |
| virtual bool | OnTaskTimeSlice (IKernelTask *task) |
| Notification that the running task's time slice expired (KERNEL_TIMESLICE only). | |
| virtual bool | OnTaskDeadlineMissed (IKernelTask *task) |
| Notification that a task has exceeded its HRT deadline; returns whether the strategy can recover without a hard fault. | |
| virtual void | OnTaskWeightChange (IKernelTask *task, Weight old_weight) |
| Notification that a runnable task's scheduling weight has changed. | |
Protected Member Functions | |
| STK_NONCOPYABLE_CLASS (SwitchStrategyEDF) | |
Protected Attributes | |
| IKernelTask::ListHeadType | m_tasks |
| Runnable tasks eligible for scheduling. Scanned in full by GetNext() each tick to find the minimum relative deadline. | |
| IKernelTask::ListHeadType | m_sleep |
| Sleeping (blocked) tasks not eligible for scheduling, e.g. HRT tasks waiting for their next activation. | |
Earliest Deadline First (EDF) scheduling strategy: always selects the runnable task with the least time remaining before its deadline expires.
IKernelTask::GetHrtRelativeDeadline() = deadline - duration (ticks remaining before the task must complete and call Yield()). The task with the minimum relative deadline, i.e. the one closest to missing its deadline is selected.KERNEL_HRT mode. In HRT mode the kernel tracks duration (active ticks elapsed) per task, making GetHrtRelativeDeadline() produce meaningful, monotonically decreasing values. Outside HRT mode GetHrtRelativeDeadline() asserts (debug builds) and returns 0 for every task, so every comparison ties and the first runnable task in m_tasks always wins: the other tasks do not run until it sleeps.m_tasks wins, i.e. the one nearest the list head. List order therefore determines tie priority: tasks keep the order in which they were added, except that a task which sleeps and wakes is re-appended at the back (see OnTaskWake()). This behaviour is implementation-defined and not guaranteed to remain stable across kernel versions.KERNEL_HRT mode, tasks do not need to override ITask::GetWeight(). Definition at line 66 of file stk_strategy_edf.h.
Compile-time capability flags reported to the kernel.
| Enumerator | |
|---|---|
| WEIGHT_API | This strategy does not use per-task weights. Deadline tracking is handled by the kernel in KERNEL_HRT mode via GetHrtRelativeDeadline(). |
| SLEEP_EVENT_API | This strategy requires OnTaskSleep() / OnTaskWake() events to move tasks between the runnable and sleeping lists. |
| DEADLINE_MISSED_API | This strategy does not use OnTaskDeadlineMissed() events. |
| PRIORITY_INHERITANCE_API | This strategy does not require Priority Inheritance and OnTaskWeightChange() events. |
| NOSLEEP_YIELD_API | This strategy does not handle Yield() itself (OnTaskYield() is not used); the kernel puts the yielding task to sleep for a tick. |
| TIMESLICE_API | This strategy does not support KERNEL_TIMESLICE mode. |
Definition at line 72 of file stk_strategy_edf.h.
|
inlineexplicit |
Construct an empty strategy with no tasks.
Definition at line 84 of file stk_strategy_edf.h.
References m_sleep, and m_tasks.
Referenced by STK_NONCOPYABLE_CLASS().
|
default |
|
inlineoverridevirtual |
Add task to the runnable set.
| [in] | task | Task to add. Must not be NULL and must not already be in any list. |
m_tasks. Unlike RR and FP strategies, no cursor or bitmap state is updated here — all scheduling decisions are deferred to GetNext(), which scans m_tasks at selection time. Implements stk::ITaskSwitchStrategy.
Definition at line 101 of file stk_strategy_edf.h.
References stk::detail::DListEntry< T, TClosedLoop >::GetHead(), m_tasks, and STK_ASSERT.
|
inlineoverridevirtual |
Get first task in the managed set (reference task for the kernel).
m_tasks if any task is runnable; otherwise the first task in m_sleep. Asserts if the combined set is empty (GetSize() == 0). Implements stk::ITaskSwitchStrategy.
Definition at line 182 of file stk_strategy_edf.h.
References GetSize(), m_sleep, m_tasks, and STK_ASSERT.
|
inlineoverridevirtual |
Select and return the task with the earliest (minimum) relative deadline.
GetHrtRelativeDeadline() is smallest, or NULL if m_tasks is empty (no runnable tasks — kernel will sleep). m_tasks is empty, return NULL immediately.next to the first task in m_tasks and cache its relative deadline as the initial minimum (avoids the need for a special INT32_MAX guard).next whenever a task has a strictly smaller GetHrtRelativeDeadline() value.next. m_tasks is returned (see the class documentation). GetHrtRelativeDeadline() calls per tick. Implements stk::ITaskSwitchStrategy.
Definition at line 146 of file stk_strategy_edf.h.
References stk::IKernelTask::GetHrtRelativeDeadline(), stk::detail::DListEntry< T, TClosedLoop >::GetNext(), and m_tasks.
|
inlineoverridevirtual |
Get total number of tasks managed by this strategy.
m_tasks (runnable) and m_sleep (sleeping). Implements stk::ITaskSwitchStrategy.
Definition at line 192 of file stk_strategy_edf.h.
References m_sleep, and m_tasks.
Referenced by GetFirst(), and RemoveTask().
|
inlinevirtualinherited |
Notification that a task has exceeded its HRT deadline; returns whether the strategy can recover without a hard fault.
| [in] | task | The task whose deadline was missed. Must not be nullptr. |
true — the strategy has absorbed the overrun (e.g. by escalating its scheduling mode): the kernel must not call HrtHardFailDeadline() for this tick. false — the strategy cannot recover: the kernel must call HrtHardFailDeadline() as normal. DEADLINE_MISSED_API == 1 in the concrete strategy's EConfig. Strategies that set DEADLINE_MISSED_API = 0 do not need to implement this method; the kernel will not call it and will proceed directly to HrtHardFailDeadline(). true carries no implicit side-effects on task sleep state or duration counters — normal tick-driven scheduling remains responsible for those. This call only communicates "do not hard-fault this tick." false (unrecoverable), which is the correct default for strategies that do not implement overrun recovery. Definition at line 1501 of file stk_common.h.
References STK_UNUSED.
|
inlineoverridevirtual |
Notification that a task has entered the sleeping state.
| [in] | task | The task that is now sleeping. Must be in m_tasks (asserted). |
m_tasks and appends to m_sleep. No cursor or bitmap state is affected — EDF maintains no per-task cursor, so this is a simpler operation than the equivalent in RR or FP strategies. Implements stk::ITaskSwitchStrategy.
Definition at line 203 of file stk_strategy_edf.h.
References stk::detail::DListEntry< T, TClosedLoop >::GetHead(), stk::IKernelTask::IsSleeping(), m_sleep, m_tasks, and STK_ASSERT.
|
inlinevirtualinherited |
Notification that the running task's time slice expired (KERNEL_TIMESLICE only).
| [in] | task | Pointer to the running task, currently in the runnable set. |
true if the strategy rotated to a same-priority peer (the following GetNext() returns it); false to keep running the task (no peer, or the task is not eligible for time-slicing). TIMESLICE_API == 1. Reimplemented in stk::sched::SwitchStrategyPreemptionThreshold< MAX_PRIORITIES, TIMESLICE, ReadyBitmap >, stk::sched::SwitchStrategyPreemptionThreshold< 32 >, stk::sched::SwitchStrategyPreemptionThreshold< 32 >, stk::sched::SwitchStrategyPreemptionThreshold< 32, true >, stk::sched::SwitchStrategyPreemptionThreshold< 32, true >, stk::sched::SwitchStrategyPreemptionThreshold< 64 >, stk::sched::SwitchStrategyPreemptionThreshold< 64 >, stk::sched::SwitchStrategyPreemptionThreshold< 64, true >, stk::sched::SwitchStrategyPreemptionThreshold< 64, true >, and stk::SwitchStrategyPreemptionThreshold< MAX_PRIORITIES, TIMESLICE, ReadyBitmap >.
Definition at line 1475 of file stk_common.h.
References STK_UNUSED.
|
inlineoverridevirtual |
Notification that a task has become runnable again.
| [in] | task | The task that woke up. Must be in m_sleep (asserted). |
m_sleep and appends to the back of m_tasks. No priority boost is applied (unlike SwitchStrategySmoothWeightedRoundRobin) and no bitmap is updated (unlike SwitchStrategyFixedPriority). The waking task's deadline urgency is determined naturally by GetHrtRelativeDeadline() on the next GetNext() call. Implements stk::ITaskSwitchStrategy.
Definition at line 221 of file stk_strategy_edf.h.
References stk::detail::DListEntry< T, TClosedLoop >::GetHead(), stk::IKernelTask::IsSleeping(), m_sleep, m_tasks, and STK_ASSERT.
|
inlinevirtualinherited |
Notification that a runnable task's scheduling weight has changed.
| [in] | task | The task whose weight was just updated via SetWeight(). |
| [in] | old_weight | The previous weight of this task (required to remove it from the priority list belonging to that weight). |
Reimplemented in stk::sched::SwitchStrategyFixedPriority< MAX_PRIORITIES, NoSleepYield, ReadyBitmap >, stk::sched::SwitchStrategyFixedPriority< 32 >, stk::sched::SwitchStrategyFixedPriority< 32 >, stk::sched::SwitchStrategyFixedPriority< 32, true >, stk::sched::SwitchStrategyFixedPriority< 32, true >, stk::sched::SwitchStrategyFixedPriority< 64 >, stk::sched::SwitchStrategyFixedPriority< 64 >, stk::sched::SwitchStrategyFixedPriority< 64, true >, stk::sched::SwitchStrategyFixedPriority< 64, true >, stk::sched::SwitchStrategyPreemptionThreshold< MAX_PRIORITIES, TIMESLICE, ReadyBitmap >, stk::sched::SwitchStrategyPreemptionThreshold< 32 >, stk::sched::SwitchStrategyPreemptionThreshold< 32 >, stk::sched::SwitchStrategyPreemptionThreshold< 32, true >, stk::sched::SwitchStrategyPreemptionThreshold< 32, true >, stk::sched::SwitchStrategyPreemptionThreshold< 64 >, stk::sched::SwitchStrategyPreemptionThreshold< 64 >, stk::sched::SwitchStrategyPreemptionThreshold< 64, true >, stk::sched::SwitchStrategyPreemptionThreshold< 64, true >, stk::SwitchStrategyFixedPriority< MAX_PRIORITIES, NoSleepYield, ReadyBitmap >, and stk::SwitchStrategyPreemptionThreshold< MAX_PRIORITIES, TIMESLICE, ReadyBitmap >.
Definition at line 1518 of file stk_common.h.
References STK_UNUSED.
|
inlinevirtualinherited |
Notification that the running task called Yield() (non-HRT kernel modes only).
| [in] | task | Pointer to the yielding task, currently in the runnable set. |
true if the strategy handled the yield itself: the task stays runnable (it is NOT put to sleep) and the strategy must arrange for the following GetNext() to return another task according to its own policy; false (default) if the kernel shall perform the legacy yield, i.e. sleep the task for YIELD_TICKS. Reimplemented in stk::sched::SwitchStrategyFixedPriority< MAX_PRIORITIES, NoSleepYield, ReadyBitmap >, stk::sched::SwitchStrategyFixedPriority< 32 >, stk::sched::SwitchStrategyFixedPriority< 32 >, stk::sched::SwitchStrategyFixedPriority< 32, true >, stk::sched::SwitchStrategyFixedPriority< 32, true >, stk::sched::SwitchStrategyFixedPriority< 64 >, stk::sched::SwitchStrategyFixedPriority< 64 >, stk::sched::SwitchStrategyFixedPriority< 64, true >, stk::sched::SwitchStrategyFixedPriority< 64, true >, stk::sched::SwitchStrategyPreemptionThreshold< MAX_PRIORITIES, TIMESLICE, ReadyBitmap >, stk::sched::SwitchStrategyPreemptionThreshold< 32 >, stk::sched::SwitchStrategyPreemptionThreshold< 32 >, stk::sched::SwitchStrategyPreemptionThreshold< 32, true >, stk::sched::SwitchStrategyPreemptionThreshold< 32, true >, stk::sched::SwitchStrategyPreemptionThreshold< 64 >, stk::sched::SwitchStrategyPreemptionThreshold< 64 >, stk::sched::SwitchStrategyPreemptionThreshold< 64, true >, stk::sched::SwitchStrategyPreemptionThreshold< 64, true >, stk::sched::SwitchStrategyRoundRobinT< NoSleepYield >, stk::sched::SwitchStrategyRoundRobinT< false >, stk::sched::SwitchStrategyRoundRobinT< false >, stk::sched::SwitchStrategyRoundRobinT< true >, stk::sched::SwitchStrategyRoundRobinT< true >, stk::sched::SwitchStrategySmoothWeightedRoundRobinT< NoSleepYield >, stk::sched::SwitchStrategySmoothWeightedRoundRobinT< false >, stk::sched::SwitchStrategySmoothWeightedRoundRobinT< false >, stk::sched::SwitchStrategySmoothWeightedRoundRobinT< true >, stk::sched::SwitchStrategySmoothWeightedRoundRobinT< true >, stk::SwitchStrategyFixedPriority< MAX_PRIORITIES, NoSleepYield, ReadyBitmap >, stk::SwitchStrategyPreemptionThreshold< MAX_PRIORITIES, TIMESLICE, ReadyBitmap >, stk::SwitchStrategyRoundRobinT< NoSleepYield >, and stk::SwitchStrategySmoothWeightedRoundRobinT< NoSleepYield >.
Definition at line 1460 of file stk_common.h.
References STK_UNUSED.
|
inlineoverridevirtual |
Remove task from whichever list it currently occupies.
| [in] | task | Task to remove. Must not be NULL and must belong to either m_tasks or m_sleep (asserted). |
Implements stk::ITaskSwitchStrategy.
Definition at line 115 of file stk_strategy_edf.h.
References stk::detail::DListEntry< T, TClosedLoop >::GetHead(), GetSize(), m_sleep, m_tasks, and STK_ASSERT.
|
protected |
|
protected |
Sleeping (blocked) tasks not eligible for scheduling, e.g. HRT tasks waiting for their next activation.
Definition at line 235 of file stk_strategy_edf.h.
Referenced by GetFirst(), GetSize(), OnTaskSleep(), OnTaskWake(), RemoveTask(), and SwitchStrategyEDF().
|
protected |
Runnable tasks eligible for scheduling. Scanned in full by GetNext() each tick to find the minimum relative deadline.
Definition at line 234 of file stk_strategy_edf.h.
Referenced by AddTask(), GetFirst(), GetNext(), GetSize(), OnTaskSleep(), OnTaskWake(), RemoveTask(), and SwitchStrategyEDF().