stk::SchedulabilityCheck Class Reference

Utility class providing static methods for Worst-Case Response Time (WCRT) schedulability analysis of a monotonic HRT task set. More...

#include <stk_strategy_monotonic.h>

Classes
class	TaskTiming
	Execution deadline and scheduling period for a single periodic HRT task, used as input to CalculateWCRT() and GetTaskCpuLoad(). More...
class	TaskCpuLoad
	CPU utilisation values for a single task, in whole percent. More...
class	TaskInfo
	Analysis results for a single task: CPU load and computed WCRT. More...
class	SchedulabilityCheckResult
	Result of a WCRT schedulability test: overall verdict plus per-task details. More...

Static Public Member Functions
template<uint32_t _TaskCount>
static SchedulabilityCheckResult< _TaskCount >	IsSchedulableWCRT (const ITaskSwitchStrategy *strategy)
	Perform WCRT schedulability analysis on the task set registered with strategy.
static bool	CalculateWCRT (const TaskTiming *tasks, const uint32_t count, TaskInfo *info)
	Compute the Worst-Case Response Time (WCRT) for each task in a fixed-priority periodic task set and determine schedulability.
static void	GetTaskCpuLoad (const TaskTiming *tasks, const uint32_t count, TaskInfo *info)
	Compute per-task and cumulative CPU utilization, in whole percent.

Static Private Member Functions
static __stk_forceinline int32_t	idiv_ceil (uint32_t x, uint32_t y)

Detailed Description

Utility class providing static methods for Worst-Case Response Time (WCRT) schedulability analysis of a monotonic HRT task set.

Determines whether a set of periodic tasks can meet all their deadlines under Rate-Monotonic or Deadline-Monotonic scheduling, assuming fully preemptive execution and no resource-sharing blocking.

Note

All methods are static. This class is not instantiated, call its methods directly as SchedulabilityCheck::IsSchedulableWCRT<N>(strategy).

See also

SwitchStrategyMonotonic, IsSchedulableWCRT, CalculateWCRT

Definition at line 281 of file stk_strategy_monotonic.h.

Member Function Documentation

CalculateWCRT()

bool stk::SchedulabilityCheck::CalculateWCRT ( const TaskTiming * tasks, const uint32_t count, TaskInfo * info )

inlinestatic

Compute the Worst-Case Response Time (WCRT) for each task in a fixed-priority periodic task set and determine schedulability.

Evaluates schedulability using standard iterative WCRT recurrence. Assumptions:

• Fixed priorities, tasks ordered by descending priority (index 0 = highest priority = shortest period for RM, or shortest deadline for DM).
• Fully preemptive execution with no resource-sharing blocking.

Within this function, local variable Cx holds tasks[t].duration (WCET C) and Tx holds tasks[t].period (period T), matching standard WCRT notation directly.

For each task t the recurrence is initialised as W(0) = Cx and iterated:

W(n+1) = Cx + sum( ceil(W(n) / Tj) * Cj,  for all j < t )

where the sum runs over all higher-priority tasks j (index < t). Cj = tasks[j].duration and Tj = tasks[j].period. Iteration continues until convergence (W(n+1) == W(n)) or W(n+1) > Tx (deadline miss confirmed). A goto is used for the iteration step to avoid re-initialising loop variables inside the outer for block.

The highest-priority task (index 0) has no higher-priority interference; its WCRT is set directly to its own WCET (tasks[0].duration) without iteration.

Parameters

[in]	tasks	Array of TaskTiming in descending priority order (index 0 = highest).
[in]	count	Number of tasks in tasks.
[out]	info	Array of TaskInfo of size count. info[i].wcrt receives the computed WCRT for task i on return.

Returns

true if every task's WCRT <= its period (Tx); false if any task misses.

Definition at line 428 of file stk_strategy_monotonic.h.

    {
        bool schedulable = true;
        info[0].wcrt = tasks[0].duration;
 
        for (uint32_t t = 1; t < count; )
        {
            uint32_t w,
            Cx = tasks[t].duration,
            Tx = tasks[t].period,
            w0 = Cx;
 
        next_itr:
 
            w = Cx;
            for (uint32_t i = 0; i < t; ++i)
                w += idiv_ceil(w0, tasks[i].period) * tasks[i].duration;
 
            if ((w != w0) && (w <= Tx))
            {
                w0 = w;
                goto next_itr;
            }
            else
            {
                schedulable &= (w <= Tx);
                info[t++].wcrt = w;
            }
        }
 
        return schedulable;
    }

References stk::SchedulabilityCheck::TaskTiming::duration, idiv_ceil(), stk::SchedulabilityCheck::TaskTiming::period, and stk::SchedulabilityCheck::TaskInfo::wcrt.

Referenced by IsSchedulableWCRT().

Here is the call graph for this function:

Here is the caller graph for this function:

GetTaskCpuLoad()

void stk::SchedulabilityCheck::GetTaskCpuLoad ( const TaskTiming * tasks, const uint32_t count, TaskInfo * info )

inlinestatic

Compute per-task and cumulative CPU utilization, in whole percent.

Parameters

[in]	tasks	Array of TaskTiming in descending priority order (index 0 = highest).
[in]	count	Number of tasks in tasks.
[out]	info	Array of TaskInfo of size count. info[i].cpu_load is populated on return.

Note

Per-task load = floor(C / T * 100) = floor(duration * 100 / period), computed with integer arithmetic (truncating division). Cumulative load is the running sum from index 0 to count - 1.

Definition at line 469 of file stk_strategy_monotonic.h.

    {
        uint16_t total = 0;
 
        for (uint32_t t = 0; t < count; ++t)
        {
            uint16_t task_load = (uint16_t)(tasks[t].duration * 100 / tasks[t].period);
            total += task_load;
 
            info[t].cpu_load.task  = task_load;
            info[t].cpu_load.total = total;
        }
    }

References stk::SchedulabilityCheck::TaskInfo::cpu_load, stk::SchedulabilityCheck::TaskCpuLoad::task, and stk::SchedulabilityCheck::TaskCpuLoad::total.

Referenced by IsSchedulableWCRT().

Here is the caller graph for this function:

idiv_ceil()

__stk_forceinline int32_t stk::SchedulabilityCheck::idiv_ceil ( uint32_t x, uint32_t y )

inlinestaticprivate

Integer ceiling division: returns ceil(x / y) = x/y + (xy > 0 ? 1 : 0). Equivalent to (int32_t)ceil((float)x / y) but exact and branch-free for integers. Reference: http://stackoverflow.com/questions/2745074/fast-ceiling-of-an-integer-division-in-c-c

Definition at line 487 of file stk_strategy_monotonic.h.

    {
        return x / y + (x % y > 0);
    }

References __stk_forceinline.

Referenced by CalculateWCRT().

Here is the caller graph for this function:

IsSchedulableWCRT()

template<uint32_t _TaskCount>

SchedulabilityCheckResult< _TaskCount > stk::SchedulabilityCheck::IsSchedulableWCRT ( const ITaskSwitchStrategy * strategy )

inlinestatic

Perform WCRT schedulability analysis on the task set registered with strategy.

Template Parameters

_TaskCount

Number of tasks to analyse. Must equal the number of tasks currently registered with strategy (asserted at runtime: idx == _TaskCount).

Parameters

[in]

strategy

Pointer to the monotonic scheduling strategy whose task list is analysed. Must not be nullptr and must have at least one task registered.

Returns

A SchedulabilityCheckResult<_TaskCount> containing the schedulability verdict and per-task CPU load and WCRT values.

Note

Tasks are read from the strategy's sorted m_tasks list in priority order (index 0 = highest priority). For each task, period is populated from GetHrtPeriodicity() and duration from GetHrtDeadline() before invoking GetTaskCpuLoad() and CalculateWCRT().

Definition at line 361 of file stk_strategy_monotonic.h.

    {
        STK_ASSERT(strategy != nullptr);
        STK_ASSERT(strategy->GetFirst() != nullptr);
 
        const IKernelTask::ListHeadType *ktasks = strategy->GetFirst()->GetHead();
 
        STK_ASSERT(ktasks != nullptr);
        STK_ASSERT(ktasks->GetSize() <= _TaskCount);
 
        SchedulabilityCheckResult<_TaskCount> ret;
        TaskTiming tasks[_TaskCount];
 
        // fill tasks timing
        IKernelTask *itr = (*ktasks->GetFirst()), * const start = itr;
        uint32_t idx = 0U;
        do
        {
            STK_ASSERT(idx < _TaskCount);
            tasks[idx].period   = static_cast<uint32_t>(itr->GetHrtPeriodicity());
            tasks[idx].duration = static_cast<uint32_t>(itr->GetHrtDeadline());
            idx += 1U;
        }
        while ((itr = (*itr->GetNext())) != start);
        STK_ASSERT(idx == _TaskCount);
 
        // calculate CPU load
        GetTaskCpuLoad(tasks, _TaskCount, ret.info);
 
        // run the WCRT schedulability analysis
        ret.schedulable = CalculateWCRT(tasks, _TaskCount, ret.info);
 
        return ret;
    }

References CalculateWCRT(), stk::SchedulabilityCheck::TaskTiming::duration, stk::ITaskSwitchStrategy::GetFirst(), stk::util::DListHead< T, _ClosedLoop >::GetFirst(), stk::util::DListEntry< T, _ClosedLoop >::GetHead(), stk::IKernelTask::GetHrtDeadline(), stk::IKernelTask::GetHrtPeriodicity(), stk::util::DListEntry< T, _ClosedLoop >::GetNext(), stk::util::DListHead< T, _ClosedLoop >::GetSize(), GetTaskCpuLoad(), stk::SchedulabilityCheck::SchedulabilityCheckResult< _TaskCount >::info, stk::SchedulabilityCheck::TaskTiming::period, stk::SchedulabilityCheck::SchedulabilityCheckResult< _TaskCount >::schedulable, and STK_ASSERT.

Referenced by stk_kernel_is_schedulable().

Here is the call graph for this function:

Here is the caller graph for this function:

---

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

• stk_strategy_monotonic.h