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 TTaskCount>
static SchedulabilityCheckResult< TTaskCount >	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 uint32_t	idiv_ceil (uint32_t x, uint32_t y)
	Compute the ceiling of an integer division: ceil(x / 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 274 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 initialized 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 425 of file stk_strategy_monotonic.h.

    {
        bool schedulable = true;
        info[0].wcrt = tasks[0].duration;
 
        for (uint32_t t = 1U; t < count; )
        {
            uint32_t       w;
            const uint32_t Cx = tasks[t].duration;
            const uint32_t Tx = tasks[t].period;
            uint32_t       w0 = Cx;
 
        next_itr:
 
            w = Cx;
            for (uint32_t i = 0U; 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 468 of file stk_strategy_monotonic.h.

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

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

Referenced by IsSchedulableWCRT().

Here is the caller graph for this function:

◆ idiv_ceil()

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

inlinestaticprivate

Compute the ceiling of an integer division: ceil(x / y).

Parameters

[in]	x	Dividend (numerator).
[in]	y	Divisor (denominator).

Returns: The result of the ceiling division, or 0 if y is 0.

Definition at line 488 of file stk_strategy_monotonic.h.

    {
        uint32_t result = 0U;
 
        if (y != 0U)
        {
            result = x / y;
            
            if ((x % y) > 0U)
            {
                result++;
            }
        }
 
        return result;
    }

Referenced by CalculateWCRT().

Here is the caller graph for this function:

◆ IsSchedulableWCRT()

template<uint32_t TTaskCount>

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

inlinestatic

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

Template Parameters

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

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<TTaskCount> 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 354 of file stk_strategy_monotonic.h.

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

References CalculateWCRT(), stk::SchedulabilityCheck::TaskTiming::duration, stk::util::DListHead< T, TClosedLoop >::GetFirst(), stk::IKernelTask::GetHrtDeadline(), stk::IKernelTask::GetHrtPeriodicity(), stk::util::DListEntry< T, TClosedLoop >::GetNext(), stk::util::DListHead< T, TClosedLoop >::GetSize(), GetTaskCpuLoad(), stk::SchedulabilityCheck::SchedulabilityCheckResult< TTaskCount >::info, stk::SchedulabilityCheck::TaskTiming::period, stk::SchedulabilityCheck::SchedulabilityCheckResult< TTaskCount >::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

Classes

Static Public Member Functions

Static Private Member Functions

Detailed Description

Member Function Documentation

◆ CalculateWCRT()

◆ GetTaskCpuLoad()

◆ idiv_ceil()

◆ IsSchedulableWCRT()