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 }
	Compile-time capability flags reported to the kernel. More...

Public Member Functions
	SwitchStrategyEDF ()
	Construct an empty strategy with no tasks.
	~SwitchStrategyEDF ()
	Destructor.
void	AddTask (IKernelTask *task)
	Add task to the runnable set.
void	RemoveTask (IKernelTask *task)
	Remove task from whichever list it currently occupies.
IKernelTask *	GetNext ()
	Select and return the task with the earliest (minimum) relative deadline.
IKernelTask *	GetFirst () const
	Get first task in the managed set (used by the kernel for initial scheduling).
size_t	GetSize () const
	Get total number of tasks managed by this strategy.
void	OnTaskSleep (IKernelTask *task)
	Notification that a task has entered the sleeping state.
void	OnTaskWake (IKernelTask *task)
	Notification that a task has become runnable again.
bool	OnTaskDeadlineMissed (IKernelTask *)
	Not supported, asserts unconditionally.

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.

Definition at line 66 of file stk_strategy_edf.h.

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

Constructor & Destructor Documentation

SwitchStrategyEDF()

stk::SwitchStrategyEDF::SwitchStrategyEDF ( )

inlineexplicit

Construct an empty strategy with no tasks.

Definition at line 75 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::SwitchStrategyEDF::~SwitchStrategyEDF ( )

inline

Destructor.

Note

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

Definition at line 81 of file stk_strategy_edf.h.

    {}

Member Function Documentation

AddTask()

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

inlinevirtual

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, _ClosedLoop >::GetHead(), m_tasks, and STK_ASSERT.

Here is the call graph for this function:

GetFirst()

IKernelTask * stk::SwitchStrategyEDF::GetFirst ( ) const

inlinevirtual

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 159 of file stk_strategy_edf.h.

    {
        STK_ASSERT(GetSize() != 0U);
 
        if (!m_tasks.IsEmpty())
            return (*m_tasks.GetFirst());
        else
            return (*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 ( )

inlinevirtual

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. Initialise 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 134 of file stk_strategy_edf.h.

    {
        if (m_tasks.IsEmpty())
            return nullptr; // idle
 
        IKernelTask *itr = (*m_tasks.GetFirst()), * const start = itr;
        IKernelTask *earliest = itr;
 
        do
        {
            if (itr->GetHrtRelativeDeadline() < earliest->GetHrtRelativeDeadline())
                earliest = itr;
        }
        while ((itr = (*itr->GetNext())) != start);
 
        return earliest;
    }

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

Here is the call graph for this function:

GetSize()

size_t stk::SwitchStrategyEDF::GetSize ( ) const

inlinevirtual

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 172 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()

bool stk::SwitchStrategyEDF::OnTaskDeadlineMissed ( IKernelTask * )

inlinevirtual

Not supported, asserts unconditionally.

Note

This strategy uses DEADLINE_MISSED_API = 0. See OnTaskDeadlineMissed() for rationale.

Implements stk::ITaskSwitchStrategy.

Definition at line 214 of file stk_strategy_edf.h.

    {
        // Budget Overrun API unsupported
        STK_ASSERT(false);
        return false;
    }

References STK_ASSERT.

OnTaskSleep()

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

inlinevirtual

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 183 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, _ClosedLoop >::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 )

inlinevirtual

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 201 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, _ClosedLoop >::GetHead(), stk::IKernelTask::IsSleeping(), m_sleep, m_tasks, and STK_ASSERT.

Here is the call graph for this function:

RemoveTask()

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

inlinevirtual

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, _ClosedLoop >::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 225 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 224 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