stk::SwitchStrategyEDF Class Reference

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>

Inheritance diagram for stk::SwitchStrategyEDF:

Collaboration diagram for stk::SwitchStrategyEDF:

Public Types
enum	EConfig {   WEIGHT_API = 0 ,   SLEEP_EVENT_API = 1 ,   DEADLINE_MISSED_API = 0 ,   PRIORITY_INHERITANCE_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 (used by the kernel for initial scheduling).
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	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. Deadline tracking continues in the kernel while tasks are in this list.

Detailed Description

Earliest Deadline First (EDF) scheduling strategy: always selects the runnable task with the least time remaining before its deadline expires.

Selection metric

GetNext() compares each runnable task's relative deadline, obtained via 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.

HRT mode requirement

This strategy is only meaningful when used with 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() returns 0 for every task, making selection order arbitrary.

Tie-breaking

When two or more tasks share the same relative deadline the first such task encountered during the linear scan of m_tasks wins. Insertion order therefore determines tie priority. This behaviour is implementation-defined and not guaranteed to remain stable across kernel versions.

Complexity

GetNext() performs an O(n) linear scan over all runnable tasks on every call (once per kernel tick). This is inherent to EDF: unlike fixed-priority strategies there is no O(1) data structure that maintains a sorted deadline order under arbitrary insertions and removals without additional memory cost.

Note

This strategy does not use per-task weights (WEIGHT_API = 0). The EDF deadline is tracked internally by the kernel in KERNEL_HRT mode, tasks do not need to override ITask::GetWeight().

Requires the kernel Sleep API (SLEEP_EVENT_API = 1): the kernel must call OnTaskSleep() and OnTaskWake() to maintain the runnable/sleeping list split.

Unlike SwitchStrategyRoundRobin and SwitchStrategyFixedPriority, EDF maintains no per-task cursor. Task insertion and removal do not update any scheduling state beyond the list membership, all scheduling decisions are deferred to GetNext().

See also

ITaskSwitchStrategy, IKernelTask::GetHrtRelativeDeadline

Definition at line 60 of file stk_strategy_edf.h.

Member Enumeration Documentation

EConfig

enum stk::SwitchStrategyEDF::EConfig

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 OnTaskPriorityChange() events.

Definition at line 66 of file stk_strategy_edf.h.

    {
        WEIGHT_API               = 0, 
        SLEEP_EVENT_API          = 1, 
        DEADLINE_MISSED_API      = 0, 
        PRIORITY_INHERITANCE_API = 0  
    };

Constructor & Destructor Documentation

SwitchStrategyEDF()

stk::SwitchStrategyEDF::SwitchStrategyEDF ( )

inlineexplicit

Construct an empty strategy with no tasks.

Definition at line 76 of file stk_strategy_edf.h.

                                 : m_tasks(), m_sleep()
    {}

References m_sleep, and m_tasks.

Referenced by STK_NONCOPYABLE_CLASS().

Here is the caller graph for this function:

~SwitchStrategyEDF()

STK_VIRT_DTOR stk::SwitchStrategyEDF::~SwitchStrategyEDF ( )

default

Destructor.

Note

MISRA deviation: [STK-DEV-005] Rule 10-3-2.

References STK_VIRT_DTOR.

Member Function Documentation

AddTask()

void stk::SwitchStrategyEDF::AddTask ( IKernelTask * task )

inlineoverridevirtual

Add task to the runnable set.

Parameters

[in]

task

Task to add. Must not be NULL and must not already be in any list.

Note

The task is appended to the back of 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.

Insertion order determines tie-breaking: when two tasks share the same relative deadline, the one added earlier (closer to the list head) wins.

Implements stk::ITaskSwitchStrategy.

Definition at line 92 of file stk_strategy_edf.h.

    {
        STK_ASSERT(task != nullptr);
        STK_ASSERT(task->GetHead() == nullptr);
 
        m_tasks.LinkBack(task);
    }

References stk::util::DListEntry< T, TClosedLoop >::GetHead(), m_tasks, and STK_ASSERT.

Here is the call graph for this function:

GetFirst()

IKernelTask * stk::SwitchStrategyEDF::GetFirst ( )

inlineoverridevirtual

Get first task in the managed set (used by the kernel for initial scheduling).

Returns

The first task in m_tasks if any task is runnable; otherwise the first task in m_sleep. Asserts if the combined set is empty (GetSize() == 0).

Note

Returns the list-head task regardless of its deadline. This is called once at kernel start to seed the initial context; EDF ordering begins with the first GetNext() call.

Implements stk::ITaskSwitchStrategy.

Definition at line 171 of file stk_strategy_edf.h.

    {
        STK_ASSERT(GetSize() != 0U);
        
        return (*(!m_tasks.IsEmpty() ? m_tasks.GetFirst() : m_sleep.GetFirst()));
    }

References GetSize(), m_sleep, m_tasks, and STK_ASSERT.

Here is the call graph for this function:

GetNext()

IKernelTask * stk::SwitchStrategyEDF::GetNext ( )

inlineoverridevirtual

Select and return the task with the earliest (minimum) relative deadline.

Returns

The runnable task whose GetHrtRelativeDeadline() is smallest, or NULL if m_tasks is empty (no runnable tasks — kernel will sleep).

Note

Algorithm (O(n) linear scan over runnable tasks):

1. If m_tasks is empty, return NULL immediately.
2. Initialize earliest to the first task in m_tasks (acts as the initial minimum sentinel — avoids the need for a special INT32_MAX guard).
3. Iterate the remaining tasks; replace earliest whenever a task has a strictly smaller GetHrtRelativeDeadline() value.
4. Return earliest.

Tie-breaking: if two tasks share the same relative deadline the one closer to the head of m_tasks (i.e. added earlier) is returned. This is consistent with AddTask() insertion order.

This method is called once per kernel tick. On an n-task system it performs n−1 comparisons and n GetHrtRelativeDeadline() calls per tick.

Implements stk::ITaskSwitchStrategy.

Definition at line 138 of file stk_strategy_edf.h.

    {
        IKernelTask *next = nullptr;
 
        if (!m_tasks.IsEmpty())
        {
            IKernelTask *itr = (*m_tasks.GetFirst());
            IKernelTask *const start = itr;
            
            next = itr; // initialize earliest found task to the first one
 
            do
            {
                if (itr->GetHrtRelativeDeadline() < next->GetHrtRelativeDeadline())
                {
                    next = itr;
                }
                  
                itr = (*itr->GetNext());
            }
            while (itr != start);
        }
 
        return next;
    }

References stk::IKernelTask::GetHrtRelativeDeadline(), stk::util::DListEntry< T, TClosedLoop >::GetNext(), and m_tasks.

Here is the call graph for this function:

GetSize()

size_t stk::SwitchStrategyEDF::GetSize ( ) const

inlineoverridevirtual

Get total number of tasks managed by this strategy.

Returns

Sum of tasks in m_tasks (runnable) and m_sleep (sleeping).

Implements stk::ITaskSwitchStrategy.

Definition at line 181 of file stk_strategy_edf.h.

    {
        return m_tasks.GetSize() + m_sleep.GetSize();
    }

References m_sleep, and m_tasks.

Referenced by GetFirst(), and RemoveTask().

Here is the caller graph for this function:

OnTaskDeadlineMissed()

virtual bool stk::ITaskSwitchStrategy::OnTaskDeadlineMissed ( IKernelTask * task )

inlinevirtualinherited

Notification that a task has exceeded its HRT deadline; returns whether the strategy can recover without a hard fault.

Parameters

[in]

task

The task whose deadline was missed. Must not be nullptr.

Returns

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.

Note

Budget Overrun API. Called by the kernel from UpdateTaskState() within a tick, after GetNext() has already been called for that tick. Only invoked when 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().

Returning 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."

The base implementation returns false (unrecoverable), which is the correct default for strategies that do not implement overrun recovery.

Definition at line 1371 of file stk_common.h.

    {
        STK_UNUSED(task);
        return false;
    }

References STK_UNUSED.

OnTaskSleep()

void stk::SwitchStrategyEDF::OnTaskSleep ( IKernelTask * task )

inlineoverridevirtual

Notification that a task has entered the sleeping state.

Parameters

[in]

task

The task that is now sleeping. Must be in m_tasks (asserted).

Note

Unlinks from 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 192 of file stk_strategy_edf.h.

    {
        STK_ASSERT(task != nullptr);
        STK_ASSERT(task->IsSleeping());
        STK_ASSERT(task->GetHead() == &m_tasks);
 
        m_tasks.Unlink(task);
        m_sleep.LinkBack(task);
    }

References stk::util::DListEntry< T, TClosedLoop >::GetHead(), stk::IKernelTask::IsSleeping(), m_sleep, m_tasks, and STK_ASSERT.

Here is the call graph for this function:

OnTaskWake()

void stk::SwitchStrategyEDF::OnTaskWake ( IKernelTask * task )

inlineoverridevirtual

Notification that a task has become runnable again.

Parameters

[in]

task

The task that woke up. Must be in m_sleep (asserted).

Note

Unlinks from 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 210 of file stk_strategy_edf.h.

    {
        STK_ASSERT(task != nullptr);
        STK_ASSERT(!task->IsSleeping());
        STK_ASSERT(task->GetHead() == &m_sleep);
 
        m_sleep.Unlink(task);
        m_tasks.LinkBack(task);
    }

References stk::util::DListEntry< T, TClosedLoop >::GetHead(), stk::IKernelTask::IsSleeping(), m_sleep, m_tasks, and STK_ASSERT.

Here is the call graph for this function:

OnTaskWeightChange()

virtual void stk::ITaskSwitchStrategy::OnTaskWeightChange ( IKernelTask * task, Weight old_weight )

inlinevirtualinherited

Notification that a runnable task's scheduling weight has changed.

Parameters

[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).

Note

Called only for tasks that are currently in the runnable set (not sleeping). The strategy must relink the task to reflect its new weight. For strategies with WEIGHT_API = 0 this is a no-op. For SwitchStrategyFixedPriority it moves the task from its old priority-level list to the new one and updates m_ready_bitmap.

Called from within a ScopedCriticalSection.

Reimplemented in stk::SwitchStrategyFixedPriority< MAX_PRIORITIES >, and stk::SwitchStrategyFixedPriority< 32 >.

Definition at line 1389 of file stk_common.h.

    {
        STK_UNUSED(task);
        STK_UNUSED(old_weight);
    }

References STK_UNUSED.

RemoveTask()

void stk::SwitchStrategyEDF::RemoveTask ( IKernelTask * task )

inlineoverridevirtual

Remove task from whichever list it currently occupies.

Parameters

[in]

task

Task to remove. Must not be NULL and must belong to either m_tasks or m_sleep (asserted).

Note

Dispatch is by list membership check. No cursor or bitmap state is affected because EDF maintains no per-task scheduling state outside list membership.

Implements stk::ITaskSwitchStrategy.

Definition at line 106 of file stk_strategy_edf.h.

    {
        STK_ASSERT(task != nullptr);
        STK_ASSERT(GetSize() != 0U);
        STK_ASSERT((task->GetHead() == &m_tasks) || (task->GetHead() == &m_sleep));
 
        if (task->GetHead() == &m_tasks)
        {
            m_tasks.Unlink(task);
        }
        else
        {
            m_sleep.Unlink(task);
        }
    }

References stk::util::DListEntry< T, TClosedLoop >::GetHead(), GetSize(), m_sleep, m_tasks, and STK_ASSERT.

Here is the call graph for this function:

STK_NONCOPYABLE_CLASS()

stk::SwitchStrategyEDF::STK_NONCOPYABLE_CLASS ( SwitchStrategyEDF )

protected

References SwitchStrategyEDF().

Here is the call graph for this function:

Member Data Documentation

m_sleep

IKernelTask::ListHeadType stk::SwitchStrategyEDF::m_sleep

protected

Sleeping (blocked) tasks not eligible for scheduling. Deadline tracking continues in the kernel while tasks are in this list.

Definition at line 224 of file stk_strategy_edf.h.

Referenced by GetFirst(), GetSize(), OnTaskSleep(), OnTaskWake(), RemoveTask(), and SwitchStrategyEDF().

m_tasks

IKernelTask::ListHeadType stk::SwitchStrategyEDF::m_tasks

protected

Runnable tasks eligible for scheduling. Scanned in full by GetNext() each tick to find the minimum relative deadline.

Definition at line 223 of file stk_strategy_edf.h.

Referenced by AddTask(), GetFirst(), GetNext(), GetSize(), OnTaskSleep(), OnTaskWake(), RemoveTask(), and SwitchStrategyEDF().

---

The documentation for this class was generated from the following file:

• stk_strategy_edf.h