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_strategy_monotonic.h
Go to the documentation of this file.
1/*
2 * SuperTinyKernel(TM) RTOS: Lightweight High-Performance Deterministic C++ RTOS for Embedded Systems.
3 *
4 * Source: https://github.com/SuperTinyKernel-RTOS
5 *
6 * Copyright (c) 2022-2026 Neutron Code Limited <stk@neutroncode.com>. All Rights Reserved.
7 * License: MIT License, see LICENSE for a full text.
8 */
9
10#ifndef STK_STRATEGY_MONOTONIC_H_
11#define STK_STRATEGY_MONOTONIC_H_
12
18
19#include "stk_common.h"
20
21namespace stk {
22namespace sched {
23
33
70template <EMonotonicSwitchStrategyType TStrategyType>
72{
73public:
86
90 {}
91
96
113 void AddTask(IKernelTask *task) override
114 {
115 STK_ASSERT(task != nullptr);
116 STK_ASSERT(task->GetHead() == nullptr);
117
118 if (m_tasks.IsEmpty())
119 {
120 m_tasks.LinkFront(task);
121 }
122 else
123 {
124 IKernelTask *itr = (*m_tasks.GetFirst()), *const start = itr;
125
126 for (;;)
127 {
128 bool higher_priority = false;
129 switch (TStrategyType)
130 {
131 case MSS_TYPE_RATE:
132 higher_priority = (task->GetHrtPeriodicity() < itr->GetHrtPeriodicity());
133 break;
135 higher_priority = (task->GetHrtDeadline() < itr->GetHrtDeadline());
136 break;
137 default:
138 STK_ASSERT(false);
139 break;
140 }
141
142 if (higher_priority)
143 {
144 if (itr == start)
145 {
146 m_tasks.LinkFront(task);
147 break;
148 }
149
150 m_tasks.Link(task, itr, itr->GetPrev());
151 break;
152 }
153
154 // end of the list
155 itr = (*itr->GetNext());
156 if (itr == start)
157 {
158 m_tasks.LinkBack(task);
159 break;
160 }
161 }
162 }
163 }
164
171 void RemoveTask(IKernelTask *task) override
172 {
173 STK_ASSERT(task != nullptr);
174 STK_ASSERT(GetSize() != 0U);
175 STK_ASSERT(task->GetHead() == &m_tasks);
176
177 m_tasks.Unlink(task);
178 }
179
190 {
191 IKernelTask *next = nullptr;
192
193 if (!m_tasks.IsEmpty())
194 {
195 IKernelTask *itr = (*m_tasks.GetFirst()), *const start = itr;
196
197 // scan from head (highest priority); skip tasks that are sleeping between
198 // periodic activations; return the first task ready to run
199 do
200 {
201 if (!itr->IsSleeping())
202 {
203 next = itr;
204 break; // list is sorted by priority; no need to continue
205 }
206
207 itr = (*itr->GetNext());
208 }
209 while (itr != start);
210 }
211
212 // nullptr means all tasks are sleeping, return idle signal to kernel
213 return next;
214 }
215
224 {
225 STK_ASSERT(m_tasks.GetSize() != 0U);
226
227 return (*m_tasks.GetFirst());
228 }
229
234 size_t GetSize() const override
235 {
236 return m_tasks.GetSize();
237 }
238
244 void OnTaskSleep(IKernelTask */*task*/) override
245 {
246 // Sleep API unsupported: RM/DM keeps a single sorted non-volatile list.
247 STK_ASSERT(false);
248 }
249
253 void OnTaskWake(IKernelTask */*task*/) override
254 {
255 // Sleep API unsupported: RM/DM keeps a single sorted non-volatile list.
256 STK_ASSERT(false);
257 }
258
259private:
261
263};
264
280{
281public:
296 {
297 uint32_t duration;
298 uint32_t period;
299 };
300
305 {
306 uint16_t task;
307 uint16_t total;
308 };
309
313 struct TaskInfo
314 {
316 uint32_t wcrt;
317 };
318
334 template <uint32_t TTaskCount>
336 {
338 TaskInfo info[TTaskCount];
339
343 operator bool() const { return schedulable; }
344 };
345
361 template <uint32_t TTaskCount>
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 }
403
434 static inline bool CalculateWCRT(const TaskTiming tasks[], const uint32_t count, TaskInfo info[])
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 }
480
490 static inline void GetTaskCpuLoad(const TaskTiming tasks[], const uint32_t count, TaskInfo info[])
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 }
510
511private:
517 static inline uint32_t idiv_ceil(uint32_t x, uint32_t y)
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 }
533};
534
541
548
549} // namespace sched
550
551// ----------------------------------------------------------------------------
552// Backward compatibility: the strategies live in stk::sched, the names below keep existing
553// code that refers to them as stk::<Name> compiling. Migrate to stk::sched::<Name>.
554// ----------------------------------------------------------------------------
555
557template <sched::EMonotonicSwitchStrategyType TStrategyType>
559
561typedef sched::SwitchStrategyRM SwitchStrategyRM __stk_attr_deprecated_type("Use stk::sched::SwitchStrategyRM");
563typedef sched::SwitchStrategyDM SwitchStrategyDM __stk_attr_deprecated_type("Use stk::sched::SwitchStrategyDM");
564
566typedef sched::SchedulabilityCheck SchedulabilityCheck __stk_attr_deprecated_type("Use stk::sched::SchedulabilityCheck");
567
568} // namespace stk
569
570#endif /* STK_STRATEGY_MONOTONIC_H_ */
Contains interface definitions of the library.
#define STK_ASSERT(e)
Runtime assertion. Halts execution if the expression e evaluates to false.
Definition stk_defs.h:532
#define STK_VIRT_DTOR
Expands to nothing if STK_STRICT_COMPLIANCY=0 (non-virtual destructors, smaller objects),...
Definition stk_defs.h:254
Namespace of STK package.
sched::SwitchStrategyEDF SwitchStrategyEDF __stk_attr_deprecated_type("Use stk::sched::SwitchStrategyEDF")
Task-switching strategies (stk::sched::SwitchStrategy*) and their helpers (priority bitmaps,...
SwitchStrategyMonotonic< MSS_TYPE_DEADLINE > SwitchStrategyDM
Shorthand alias for SwitchStrategyMonotonic<MSS_TYPE_DEADLINE>: Deadline-Monotonic scheduling (shorte...
SwitchStrategyMonotonic< MSS_TYPE_RATE > SwitchStrategyRM
Shorthand alias for SwitchStrategyMonotonic<MSS_TYPE_RATE>: Rate-Monotonic scheduling (shorter schedu...
EMonotonicSwitchStrategyType
Policy selector for SwitchStrategyMonotonic: determines the timing attribute used to assign fixed pri...
@ MSS_TYPE_RATE
Rate-Monotonic (RM): shorter scheduling period -> higher priority. Priority is derived from GetHrtPer...
@ MSS_TYPE_DEADLINE
Deadline-Monotonic (DM): shorter execution deadline -> higher priority. Priority is derived from GetH...
Scheduling-strategy-facing interface for a kernel task slot.
virtual Timeout GetHrtDeadline() const =0
Get HRT task deadline (max allowed task execution time).
DLHeadType ListHeadType
List head type for IKernelTask elements.
virtual bool IsSleeping() const =0
Check whether the task is currently sleeping.
virtual Timeout GetHrtPeriodicity() const =0
Get HRT task execution periodicity.
Interface for a task switching strategy implementation.
size_t GetSize() const
Get the number of entries currently in the list.
DLEntryType * GetFirst()
Get the first (front) entry without removing it.
DLHeadType * GetHead()
Get the list head this entry currently belongs to.
DLEntryType * GetPrev()
Get the previous entry in the list.
DLEntryType * GetNext()
Get the next entry in the list.
Monotonic scheduling strategy: Rate-Monotonic (RM) or Deadline-Monotonic (DM), selected at compile ti...
size_t GetSize() const override
Get the total number of tasks managed by this strategy.
STK_NONCOPYABLE_CLASS(SwitchStrategyMonotonic)
IKernelTask * GetNext() override
Select and return the highest-priority non-sleeping task.
void OnTaskWake(IKernelTask *) override
Not supported, asserts unconditionally.
void RemoveTask(IKernelTask *task) override
Remove a task from the list.
STK_VIRT_DTOR ~SwitchStrategyMonotonic()=default
Destructor.
IKernelTask * GetFirst() override
Get the first task in the managed set (reference task for the kernel, used when it starts and when al...
SwitchStrategyMonotonic()
Construct an empty strategy with no tasks.
EConfig
Compile-time capability flags reported to the kernel.
void OnTaskSleep(IKernelTask *) override
Not supported, asserts unconditionally.
void AddTask(IKernelTask *task) override
Add a task to the priority-sorted runnable list.
Utility class providing static methods for Worst-Case Response Time (WCRT) schedulability analysis of...
static uint32_t idiv_ceil(uint32_t x, uint32_t y)
Compute the ceiling of an integer division: ceil(x / y).
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.
static SchedulabilityCheckResult< TTaskCount > IsSchedulableWCRT(const ITaskSwitchStrategy *strategy)
Perform WCRT schedulability analysis on the task set registered with strategy.
Execution deadline and scheduling period for a single periodic HRT task, used as input to CalculateWC...
uint32_t period
Scheduling period T of the task (ticks), from GetHrtPeriodicity(). Used as the interference divisor T...
uint32_t duration
Worst-Case Execution Time C of the task (ticks), from GetHrtDeadline(). Used as the base cost and int...
CPU utilisation values for a single task, in whole percent.
uint16_t total
Cumulative CPU load of this task plus all higher-priority tasks, in percent (running sum from index 0...
uint16_t task
CPU load contributed by this task alone, in percent: floor(C / T * 100) = floor(duration * 100 / peri...
Analysis results for a single task: CPU load and computed WCRT.
uint32_t wcrt
Worst-Case Response Time in ticks. Task is schedulable if wcrt <= period (T).
TaskCpuLoad cpu_load
Per-task and cumulative CPU utilisation (see TaskCpuLoad).
Result of a WCRT schedulability test: overall verdict plus per-task details.
TaskInfo info[TTaskCount]
Per-task analysis results, ordered highest priority first (index 0 = highest priority task).
bool schedulable
true if every task's WCRT <= its period (T); false if any task misses its deadline.