寻找有限状态机的不同调度算法的比较

Question

是否有任何好的资源(书籍,网站)能够在没有操作系统的嵌入式系统中对有限状态机(FSM)的不同调度算法进行非常好的比较？

我正在设计一个没有操作系统的简单嵌入式Web服务器.我想知道用于安排处理系统中发生的不同事件的各种方法是什么.

例如,如果两个事件同时到达,那么事件的优先级如何？如果我为事件分配不同的优先级,我如何确保首先处理优先级较高的事件？如果在处理事件时进入更高优先级的事件,如何确保立即处理该事件？

我计划在事件到达时使用FSM检查各种条件,然后正确安排事件进行处理.由于嵌入式Web服务器没有操作系统,我正在考虑使用循环执行方法.但我希望看到可以在这种方法中使用的不同算法的优缺点的比较.

Answer 1

如果我知道这个问题意味着答案仍然可能是Miro Samek 在C/C++中的实用UML状态图,第二版:嵌入式系统的事件驱动编程

Answer 2

你说:"我的意思是例如调度条件,如果两个任务同时到达哪个任务需要优先考虑并且在嵌入式网络服务器中模拟其他情况."

我将其解释为:"当多个任务同时到达时,用于确定哪个任务首先执行(计划)的规则集是什么."

我用你的术语"任务"来说明相似之处.但克利福德是正确的.正确的术语应该是"事件"或"消息".

当你说"调度条件"时,我认为你的意思是"确定事件时间表的一套规则".

算法的定义是:在计算或其他解决问题的操作中要遵循的一个过程或一组规则,尤其是 通过电脑.

来自一篇名为调度算法的论文:

考虑一台计算机的中央处理单元,它必须处理随时间推移的一系列作业.应该以什么顺序处理作业,以便平均最小化作业在从到达到完成时在系统中的时间？

这听起来像你所谓的"调度条件".

我提出这个问题是因为使用正确的词语来描述你正在寻找的东西将有助于我们(SO社区)给你更好的答案.当您自己进一步研究时,它会帮助您.

如果我对你的问题的解释仍然不是你的想法,请让我知道,特别是,我说的是错的,我会再试一次.也许更多的例子可以帮助我更好地理解.

关于日程安排的一些进一步阅读(这是你要求的):

1. 一个很好的起点当然是维基百科关于调度学科的文章
2. 比您正在寻找的水平稍低但仍然充满了关于调度的详细信息是用于高级综合的调度算法(注意:无论出于何种原因,PDF具有相反顺序的页面,因此从底部开始)

优先中断调度程序的示例:

采用优先级0最高的架构.两个事件同时进入.一个具有优先级2,另一个具有优先级3.调度算法开始处理具有优先级2的那个,因为它具有更高的优先级.

当正在处理具有优先级2的事件时,另一个优先级为0的事件进入.调度程序使用优先级2中断事件并以优先级0处理事件.

当它处理完Prio​​rity 0事件时,它返回处理优先级2事件.处理完Prio​​rity 2事件后,它会处理优先级3事件.

最后,当处理完所有优先级中断时,它将控制返回到主处理任务,该处理任务处理优先级无关紧要的事件.

举例说明:

在上面的图像中,"任务"是DipSwitch提到的超级循环或者在你提到main()的循环执行中发生的无限循环.如果需要确定优先级,"事件"是在超级循环或中断中运行的各种例程,如上所示.

要搜索的术语是优先中断和控制流.一些好的阅读材料是Toppers Kernel Spec(我从中得到了图像),ARM中断架构和80196中断架构的论文.

我提到Toppers Kernel Spec只是因为那是我从中得到图像的地方.但任何实时操作系统的核心是它的调度算法和中断架构.

您询问的"on event"处理将由微处理器/微控制器中断子系统处理.如何构建优先级以及如何处理非优先级事件是构成整个调度算法的原因.

合作调度程序的一个示例:

typedef struct {
    void   (*task)(void); // Pointer to the task function.
    uint32_t period;      // Period to execute with.
    uint32_t delay;       // Delay before first call.
} task_type;

volatile uint32_t elapsed_ticks = 0;
task_type tasks[NUM_TASKS];

void Dispatch_Tasks(void)
{
    Disable_Interrupts();
    while (elapsed_ticks > 0) { // TRUE only if the ISR ran.
        for (uint32_t i = 0; i < NUM_TASKS; i++) {
            if (--tasks[i].delay == 0) {
                tasks[i].delay = tasks[i].period;

                Enable_Interrupts();
                tasks[i].task(); // Execute the task!
                Disable_Interrupts();
            }
        }
        --elapsed_ticks;
    }
    Enable_Interrupts();
}

// Count the number of ticks yet to be processed.
void Timer_ISR(void)
{
    ++elapsed_ticks;
}

上面的例子来自一篇名为"Simple Co-Operative Scheduling"的博客文章.

协作调度器是超级循环和定时器中断的组合.来自嵌入式系统的非阻塞硬件编码的第2.4节:

协作调度器本质上是前面讨论的两个调度器的组合.一个定时器设置为以固定间隔中断,这将是不同任务的最小时间分辨率.然后为每个任务分配一个周期,该周期是中断间隔的最小分辨率的倍数.然后不断调用函数来更新每个任务的中断计数,并运行已达到其中断周期的任务.这导致调度器具有Superloop的可伸缩性和时间触发调度器的定时可靠性.这是传感器系统常用的调度程序.但是,这种类型的调度程序并非没有限制.合作调度程序中的任务调用很短也很重要.如果一个任务阻塞超过一个定时器中断周期,则可能会错过时间关键任务.

有关更深入的分析,请参阅国际电气与计算机科学期刊.

抢先与合作:

如果没有在其上运行某种抢占算法,协作调度程序就无法处理异步事件.一个例子是多级队列架构.关于这一点的一些讨论可以在本文关于CPU调度的文章中找到.当然,每个人都有利弊.其中一些在RTKernel-32的这篇简短文章中有所描述.

对于"可以满足基于优先级的任务调度的任何特定类型抢占式调度调度过程(如图中所示)",任何基于优先级的中断控制器本质上都是抢占式的.如果您为每个中断安排一个任务,它将按图中所示执行.