stk_strategy_monotonic.h

Go to the documentation of this file.

/*
 * SuperTinyKernel(TM) RTOS: Lightweight High-Performance Deterministic C++ RTOS for Embedded Systems.
 *
 * Source: https://github.com/SuperTinyKernel-RTOS
 *
 * Copyright (c) 2022-2026 Neutron Code Limited <stk@neutroncode.com>. All Rights Reserved.
 * License: MIT License, see LICENSE for a full text.
 */
 
#ifndef STK_STRATEGY_MONOTONIC_H_
#define STK_STRATEGY_MONOTONIC_H_

 
#include "stk_common.h"
 
namespace stk {

enum EMonotonicSwitchStrategyType
{
    MSS_TYPE_RATE,    
    MSS_TYPE_DEADLINE 
};

template <EMonotonicSwitchStrategyType TStrategyType>
class SwitchStrategyMonotonic final : public ITaskSwitchStrategy
{
public:
    enum EConfig
    {
        WEIGHT_API               = 0, 
        SLEEP_EVENT_API          = 0, 
        DEADLINE_MISSED_API      = 0, 
        PRIORITY_INHERITANCE_API = 0, 
        NOSLEEP_YIELD_API        = 0, 
        TIMESLICE_API            = 0  
    };

    explicit SwitchStrategyMonotonic() : m_tasks()
    {}

    STK_VIRT_DTOR ~SwitchStrategyMonotonic() = default;

    void AddTask(IKernelTask *task) override
    {
        STK_ASSERT(task != nullptr);
        STK_ASSERT(task->GetHead() == nullptr);
 
        if (m_tasks.IsEmpty())
        {
            m_tasks.LinkFront(task);
        }
        else
        {
            IKernelTask *itr = (*m_tasks.GetFirst()), *const start = itr;
 
            for (;;)
            {
                bool higher_priority = false;
                switch (TStrategyType)
                {
                case MSS_TYPE_RATE:
                    higher_priority = (task->GetHrtPeriodicity() < itr->GetHrtPeriodicity());
                    break;
                case MSS_TYPE_DEADLINE:
                    higher_priority = (task->GetHrtDeadline() < itr->GetHrtDeadline());
                    break;
                default:
                    STK_ASSERT(false);
                    break;
                }
 
                if (higher_priority)
                {
                    if (itr == start)
                    {
                        m_tasks.LinkFront(task);
                        break;
                    }
 
                    m_tasks.Link(task, itr, itr->GetPrev());
                    break;
                }
 
                // end of the list
                itr = (*itr->GetNext());
                if (itr == start)
                {
                    m_tasks.LinkBack(task);
                    break;
                }
            }
        }
    }

    void RemoveTask(IKernelTask *task) override
    {
        STK_ASSERT(task != nullptr);
        STK_ASSERT(GetSize() != 0U);
        STK_ASSERT(task->GetHead() == &m_tasks);
 
        m_tasks.Unlink(task);
    }

    IKernelTask *GetNext() override
    {
        IKernelTask *next = nullptr;
 
        if (!m_tasks.IsEmpty())
        {
            IKernelTask *itr = (*m_tasks.GetFirst()), *const start = itr;
 
            // scan from head (highest priority); skip tasks that are sleeping between
            // periodic activations; return the first task ready to run
            do
            {
                if (!itr->IsSleeping())
                {
                    next = itr;
                    break; // list is sorted by priority; no need to continue
                }
 
                itr = (*itr->GetNext());
            }
            while (itr != start);
        }
 
        // nullptr means all tasks are sleeping, return idle signal to kernel
        return next;
    }

    IKernelTask *GetFirst() override
    {
        STK_ASSERT(m_tasks.GetSize() != 0U);
 
        return (*m_tasks.GetFirst());
    }

    size_t GetSize() const override
    {
        return m_tasks.GetSize();
    }

    void OnTaskSleep(IKernelTask */*task*/) override
    {
        // Sleep API unsupported: RM/DM keeps a single sorted non-volatile list.
        STK_ASSERT(false);
    }

    void OnTaskWake(IKernelTask */*task*/) override
    {
        // Sleep API unsupported: RM/DM keeps a single sorted non-volatile list.
        STK_ASSERT(false);
    }
 
private:
    STK_NONCOPYABLE_CLASS(SwitchStrategyMonotonic);
 
    IKernelTask::ListHeadType m_tasks; 
};

class SchedulabilityCheck
{
public:
    struct TaskTiming
    {
        uint32_t duration; 
        uint32_t period;   
    };

    struct TaskCpuLoad
    {
        uint16_t task;  
        uint16_t total; 
    };

    struct TaskInfo
    {
        TaskCpuLoad cpu_load; 
        uint32_t    wcrt;     
    };

    template <uint32_t TTaskCount>
    struct SchedulabilityCheckResult
    {
        bool     schedulable;      
        TaskInfo info[TTaskCount]; 

        operator bool() const { return schedulable; }
    };

    template <uint32_t TTaskCount>
    static inline SchedulabilityCheckResult<TTaskCount> IsSchedulableWCRT(const ITaskSwitchStrategy *strategy)
    {
        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 (bounded: never write past the array even if asserts are disabled)
        const IKernelTask *itr = (*ktasks->GetFirst()), * const start = itr;
        uint32_t idx = 0U;
        do
        {
            STK_ASSERT(idx < TTaskCount);
 
            if (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, only for the tasks actually read
        GetTaskCpuLoad(tasks, idx, ret.info);
 
        // run the WCRT schedulability analysis
        ret.schedulable = CalculateWCRT(tasks, idx, ret.info);
 
        return ret;
    }

    static inline bool CalculateWCRT(const TaskTiming tasks[], const uint32_t count, TaskInfo info[])
    {
        bool schedulable = true;
 
        if (count > 0U)
        {
            info[0].wcrt = tasks[0].duration;
 
            for (uint32_t t = 1U; t < count; ++t)
            {
                const uint32_t Cx = tasks[t].duration;
                const uint32_t Tx = tasks[t].period;
 
                uint32_t w0 = Cx;
                uint32_t w  = Cx;
                bool converged = false;
 
                while (!converged)
                {
                    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;
                    }
                    else
                    {
                        converged = true;
                    }
                }
 
                if (w > Tx)
                {
                    schedulable = false;
                }
 
                info[t].wcrt = w;
            }
        }
 
        return schedulable;
    }

    static inline void GetTaskCpuLoad(const TaskTiming tasks[], const uint32_t count, TaskInfo info[])
    {
        uint16_t total = 0U;
 
        for (uint32_t i = 0U; i < count; ++i)
        {
            uint16_t task_load = 0U;
 
            // guard against a zero period (e.g. HRT parameters not populated)
            if (tasks[i].period != 0U)
            {
                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;
        }
    }
 
private:
    static inline uint32_t idiv_ceil(uint32_t x, uint32_t y)
    {
        uint32_t result = 0U;
 
        if (y != 0U)
        {
            result = x / y;
            
            if ((x % y) > 0U)
            {
                result++;
            }
        }
 
        return result;
    }
};

typedef SwitchStrategyMonotonic<MSS_TYPE_RATE> SwitchStrategyRM;

typedef SwitchStrategyMonotonic<MSS_TYPE_DEADLINE> SwitchStrategyDM;
 
} // namespace stk
 
#endif /* STK_STRATEGY_MONOTONIC_H_ */