3

是否有任何好的资源（书籍、网站）可以很好地比较没有操作系统的嵌入式系统中有限状态机 (FSM) 的不同调度算法？

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

例如，如果两个事件同时到达，事件的优先级如何？如果我为事件分配不同的优先级，如何确保优先级较高的事件首先得到处理？如果在处理事件时出现更高优先级的事件，如何确保立即处理该事件？

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

4

2 回答 2

8

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

于 2012-08-14T15:15:50.147 回答
7

您说：“我的意思是例如调度条件，如果两个任务同时到达，则需要优先考虑哪个任务，并且类似于嵌入式网络服务器中的其他情况。”

我将其解释为：“当多个任务同时到达时，用于确定哪个任务首先执行（计划）的规则集是什么。”

我用你的术语“任务”来说明相似性。但克利福德是正确的。正确的术语应该是“事件”或“消息”。

当您说“调度条件”时，我认为您的意思是“确定事件时间表的一组规则”。

算法的定义是：在计算或其他解决问题的操作中要遵循的过程或规则集，尤其是。通过计算机。

来自题为调度算法的论文：

考虑必须处理随时间到达的一系列作业的计算机的中央处理单元。应按什么顺序处理作业，以最小化作业从到达到完成在系统中的平均时间？

再一次，听起来像你所说的“调度条件”。

我提出这一点是因为使用正确的词语来描述您正在寻找的内容将帮助我们（SO 社区）为您提供更好的答案。并且会在您自己进一步研究时为您提供帮助。

如果我对您问题的解释仍然不是您的想法，请告诉我，尤其是我所说的错误，我会再试一次。也许更多的例子可以帮助我更好地理解。

关于日程安排的一些进一步阅读（这是你所要求的）：

  1. 一个很好的起点当然是关于调度学科的维基百科文章
  2. 比您正在寻找的级别略低但仍然包含有关调度的详细信息的是高级合成的调度算法（注意：无论出于何种原因，PDF 的页面顺序都是相反的，所以从底部开始）

优先级中断调度程序的示例：

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

在处理优先级为 2 的事件时，另一个优先级为 0 的事件进入。调度程序中断优先级为 2 的事件并处理优先级为 0 的事件。

处理完优先级 0 事件后，它会返回处理优先级 2 事件。处理完优先级 2 事件后，它会处理优先级 3 事件。

最后，当它处理完所有优先级中断时，它会将控制权返回给主处理任务，该任务处理优先级无关紧要的事件。

插图：

优先中断时序

在上图中，“任务”是DipSwitch 提到的超级循环或您提到的循环执行main()程序中发生的无限循环。“事件”是在超级循环或中断中运行的各种例程，如果它们需要优先级，则如上所示。

要搜索的术语是Priority Interrupt和Control Flow。一些很好的阅读材料是Toppers Kernel Spec（我从中得到图像）、ARM Interrupt Architecture和一篇关于80196 Interrupt Architecture的论文。

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

您询问的“事件”处理将由微处理器/微控制器中断子系统处理。如何构建优先级以及如何处理非优先级事件构成了整个调度算法。

协作调度器的示例：

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 的可扩展性和 Time Triggered 调度器的时序可靠性。这是传感器系统常用的调度程序。但是，这种类型的调度器并非没有局限性。协作调度程序中的任务调用很短仍然很重要。

要进行更深入的分析，请参阅International Journal of Electrical & Computer Sciences的一篇论文。

抢占式与合作式：

如果没有某种在其之上运行的抢占算法，协作调度程序就无法处理异步事件。这方面的一个例子是多级队列架构。关于这个问题的一些讨论可以在这篇关于 CPU 调度的论文中找到。当然，各有利弊。这篇关于 RTKernel-32 的简短文章中描述了其中的一些。

至于“任何能够满足基于优先级的任务调度的特定类型的抢占式调度调度过程（如图）”，任何基于优先级的中断控制器本质上都是抢占式的。如果您为每个中断安排一个任务，它将如图所示执行。

于 2012-08-14T17:35:26.147 回答