SuperTinyKernel™ RTOS 1.08.x
Lightweight, high-performance, deterministic, bare-metal C++ RTOS for resource-constrained embedded systems. MIT Open Source License.
Loading...
Searching...
No Matches
stk::sched::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>

Collaboration diagram for stk::sched::SchedulabilityCheck:

Classes

struct  TaskTiming
 Execution deadline and scheduling period for a single periodic HRT task, used as input to CalculateWCRT() and GetTaskCpuLoad(). More...
struct  TaskCpuLoad
 CPU utilisation values for a single task, in whole percent. More...
struct  TaskInfo
 Analysis results for a single task: CPU load and computed WCRT. More...
struct  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).
The HRT deadline is used as the execution budget C and the period as the deadline T of the analysis (implicit-deadline model).
See also
SwitchStrategyMonotonic, IsSchedulableWCRT, CalculateWCRT

Definition at line 279 of file stk_strategy_monotonic.h.

Member Function Documentation

◆ CalculateWCRT()

bool stk::sched::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).

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]tasksArray of TaskTiming in descending priority order (index 0 = highest).
[in]countNumber of tasks in tasks.
[out]infoArray 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 434 of file stk_strategy_monotonic.h.

435 {
436 bool schedulable = true;
437
438 if (count > 0U)
439 {
440 info[0].wcrt = tasks[0].duration;
441
442 for (uint32_t t = 1U; t < count; ++t)
443 {
444 const uint32_t Cx = tasks[t].duration;
445 const uint32_t Tx = tasks[t].period;
446
447 uint32_t w0 = Cx;
448 uint32_t w = Cx;
449 bool converged = false;
450
451 while (!converged)
452 {
453 w = Cx;
454 for (uint32_t i = 0U; i < t; ++i)
455 {
456 w += idiv_ceil(w0, tasks[i].period) * tasks[i].duration;
457 }
458
459 if ((w != w0) && (w <= Tx))
460 {
461 w0 = w;
462 }
463 else
464 {
465 converged = true;
466 }
467 }
468
469 if (w > Tx)
470 {
471 schedulable = false;
472 }
473
474 info[t].wcrt = w;
475 }
476 }
477
478 return schedulable;
479 }
static uint32_t idiv_ceil(uint32_t x, uint32_t y)
Compute the ceiling of an integer division: ceil(x / y).

References stk::sched::SchedulabilityCheck::TaskTiming::duration, idiv_ceil(), stk::sched::SchedulabilityCheck::TaskTiming::period, and stk::sched::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::sched::SchedulabilityCheck::GetTaskCpuLoad ( const TaskTiming tasks[],
const uint32_t count,
TaskInfo info[] )
inlinestatic

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

Parameters
[in]tasksArray of TaskTiming in descending priority order (index 0 = highest).
[in]countNumber of tasks in tasks.
[out]infoArray 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). A task with a zero period is reported as 0 %. Cumulative load is the running sum from index 0 to count - 1.

Definition at line 490 of file stk_strategy_monotonic.h.

491 {
492 uint16_t total = 0U;
493
494 for (uint32_t i = 0U; i < count; ++i)
495 {
496 uint16_t task_load = 0U;
497
498 // guard against a zero period (e.g. HRT parameters not populated)
499 if (tasks[i].period != 0U)
500 {
501 task_load = static_cast<uint16_t>(tasks[i].duration * 100U / tasks[i].period);
502 }
503
504 total += task_load;
505
506 info[i].cpu_load.task = task_load;
507 info[i].cpu_load.total = total;
508 }
509 }

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

Referenced by IsSchedulableWCRT().

Here is the caller graph for this function:

◆ idiv_ceil()

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

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

Parameters
[in]xDividend (numerator).
[in]yDivisor (denominator).
Returns
The result of the ceiling division, or 0 if y is 0.

Definition at line 517 of file stk_strategy_monotonic.h.

518 {
519 uint32_t result = 0U;
520
521 if (y != 0U)
522 {
523 result = x / y;
524
525 if ((x % y) > 0U)
526 {
527 result++;
528 }
529 }
530
531 return result;
532 }

Referenced by CalculateWCRT().

Here is the caller graph for this function:

◆ IsSchedulableWCRT()

template<uint32_t TTaskCount>
SchedulabilityCheckResult< TTaskCount > stk::sched::SchedulabilityCheck::IsSchedulableWCRT ( const ITaskSwitchStrategy * strategy)
inlinestatic

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

Template Parameters
TTaskCountNumber of tasks to analyse. Must equal the number of tasks currently registered with strategy (asserted at runtime: idx == TTaskCount).
Parameters
[in]strategyPointer 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().
If the number of registered tasks differs from TTaskCount an assertion fires; with assertions disabled at most TTaskCount tasks are analysed and entries of the result beyond the analysed tasks are zero-initialised.

Definition at line 362 of file stk_strategy_monotonic.h.

363 {
364 STK_ASSERT(strategy != nullptr);
365 STK_ASSERT(const_cast<ITaskSwitchStrategy *>(strategy)->GetFirst() != nullptr);
366
367 const IKernelTask::ListHeadType *const ktasks = const_cast<ITaskSwitchStrategy *>(strategy)->GetFirst()->GetHead();
368
369 STK_ASSERT(ktasks != nullptr);
370 STK_ASSERT(ktasks->GetSize() <= TTaskCount);
371
373 TaskTiming tasks[TTaskCount] = {};
374
375 // fill tasks timing (bounded: never write past the array even if asserts are disabled)
376 const IKernelTask *itr = (*ktasks->GetFirst()), * const start = itr;
377 uint32_t idx = 0U;
378 do
379 {
380 STK_ASSERT(idx < TTaskCount);
381
382 if (idx < TTaskCount)
383 {
384 tasks[idx].period = static_cast<uint32_t>(itr->GetHrtPeriodicity());
385 tasks[idx].duration = static_cast<uint32_t>(itr->GetHrtDeadline());
386 ++idx;
387 }
388
389 itr = (*itr->GetNext());
390 }
391 while (itr != start);
392
393 STK_ASSERT(idx == TTaskCount);
394
395 // calculate CPU load, only for the tasks actually read
396 GetTaskCpuLoad(tasks, idx, ret.info);
397
398 // run the WCRT schedulability analysis
399 ret.schedulable = CalculateWCRT(tasks, idx, ret.info);
400
401 return ret;
402 }
#define STK_ASSERT(e)
Runtime assertion. Halts execution if the expression e evaluates to false.
Definition stk_defs.h:532
DLHeadType ListHeadType
List head type for IKernelTask elements.
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 d...
static void GetTaskCpuLoad(const TaskTiming tasks[], const uint32_t count, TaskInfo info[])
Compute per-task and cumulative CPU utilization, in whole percent.
Execution deadline and scheduling period for a single periodic HRT task, used as input to CalculateWC...
Result of a WCRT schedulability test: overall verdict plus per-task details.

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