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_RM_H_
#define STK_STRATEGY_RM_H_

 
#include "stk_common.h"
#include "stk_strategy_rrobin.h"
 
namespace stk {

enum EMonotonicSwitchStrategyType
{
    MSS_TYPE_RATE,    
    MSS_TYPE_DEADLINE 
};

template <EMonotonicSwitchStrategyType _Type>
class SwitchStrategyMonotonic : public ITaskSwitchStrategy
{
public:
    enum EConfig
    {
        WEIGHT_API          = 0, 
        SLEEP_EVENT_API     = 0, 
        DEADLINE_MISSED_API = 0  
    };

    explicit SwitchStrategyMonotonic() : m_tasks()
    {}

    ~SwitchStrategyMonotonic()
    {}

    void AddTask(IKernelTask *task)
    {
        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;
                switch (_Type)
                {
                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
                if ((itr = (*itr->GetNext())) == start)
                {
                    m_tasks.LinkBack(task);
                    break;
                }
            }
        }
    }

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

    IKernelTask *GetNext()
    {
        STK_ASSERT(!m_tasks.IsEmpty());
 
        IKernelTask *itr = (*m_tasks.GetFirst()), * const start = itr;
        IKernelTask *next = nullptr;
 
        // 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
            }
        }
        while ((itr = (*itr->GetNext())) != start);
 
        // nullptr means all tasks are sleeping, return idle signal to kernel
        return next;
    }

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

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

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

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

    bool OnTaskDeadlineMissed(IKernelTask */*task*/)
    {
        // Budget Overrun API unsupported
        STK_ASSERT(false);
        return 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 _TaskCount>
    struct SchedulabilityCheckResult
    {
        bool     schedulable;      
        TaskInfo info[_TaskCount]; 

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

    template <uint32_t _TaskCount>
    static inline SchedulabilityCheckResult<_TaskCount> IsSchedulableWCRT(const ITaskSwitchStrategy *strategy)
    {
        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;
    }

    static inline bool CalculateWCRT(const TaskTiming *tasks, const uint32_t count, TaskInfo *info)
    {
        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;
    }

    static inline void GetTaskCpuLoad(const TaskTiming *tasks, const uint32_t count, TaskInfo *info)
    {
        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;
        }
    }
 
private:
    static __stk_forceinline int32_t idiv_ceil(uint32_t x, uint32_t y)
    {
        return x / y + (x % y > 0);
    }
};

typedef SwitchStrategyMonotonic<MSS_TYPE_RATE> SwitchStrategyRM;

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