寻找有限状态机的不同调度算法的比较 [英] Looking for a comparison of different scheduling algorithms for a Finite State Machine

问题描述

在没有操作系统的嵌入式系统中，有没有什么好的资源（书籍，网站）可以很好的比较有限状态机（FSM）的不同调度算法？

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

例如，如果两个事件相同时间事件如何优先？如果我为事件分配不同的优先级，那我该如何确保优先级较高的事件先被处理？如果在处理事件时出现了更高优先级的事件，那么如何确保事件被立即处理？

我计划使用FSM在事件到达后检查各种条件，然后正确安排事件进行处理。由于嵌入式Web服务器没有操作系统，所以我正在考虑使用或 main中的无限循环（ ）发生在您提到的循环执行中。 事件是在超级循环中运行的各种例程，如果需要确定优先级，则中断。

要搜索的条款是优先级中断和控制流程。一些很好的阅读材料是 Toppers Kernel Spec （我从中获得图像）， ARM Interrupt Architecture ，以及一篇关于 80196中断架构。

我提到了Toppers内核规范，因为这是我从中获得图像的地方。但是任何实时操作系统的核心是调度算法和中断架构。

您询问的on事件处理将由微处理器/微控制器中断子系统。如何构建优先级级别以及如何处理非优先级事件是什么构成您的调度算法的整体。

协作调度程序的示例：

  typedef struct {
 void（* task）（void）; //指向任务功能的指针。 
 uint32_t period; //执行时间。 
 uint32_t delay; //第一次通话前延迟
} task_type; 
 
 volatile uint32_t elapsed_ticks = 0; 
 task_type tasks [NUM_TASKS]; 
 
 void Dispatch_Tasks（void）
 {
 Disable_Interrupts（）; 
 while（elapsed_ticks> 0）{//仅当ISR运行时为TRUE。 （uint32_t i = 0; i< NUM_TASKS; i ++）{
 if（--tasks [i] .delay == 0）{
 tasks [i] .delay = tasks [I] .period; 
 
 Enable_Interrupts（）; 
 tasks [i] .task（）; //执行任务！ 
 Disable_Interrupts（）; 
} 
} 
 --elapsed_ticks; 
} 
 Enable_Interrupts（）; 
} 
 
 //计算尚待处理的刻度数。 
 void Timer_ISR（void）
 {
 ++ elapsed_ticks; 
} 
  

上面的例子是从一个标题为简单的合作调度。

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

协作调度器本质上是两个
以前讨论的调度程序的组合。一个定时器设置为以
定期间隔中断，这将是
不同任务的最小时间分辨率。然后每个任务被分配一个周期，它是中断间隔的最小分辨率的
倍数。然后不断调用
函数来更新每个任务
的中断计数，并运行已达到其中断周期的任务。 $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $这是一个
常用的传感器系统调度程序。但是，这种类型的
调度器并不是没有限制的。
协调调度程序中的任务调用很短。如果一个任务
阻塞一个以上的定时器中断周期，则可能会错过一个时间紧迫的任务
。

为了进一步深入分析，这里是国际电气与电子学报计算机科学。

抢先与合作：

调度程序无法处理异步事件，而没有某种抢先算法运行在其上。一个例子就是多层次的队列架构。有关这方面的讨论可以在CPU上找到这篇文章调度。当然，每个人都有利弊。其中一些描述在这个短文在RTKernel-32上。

至于可以满足的任何特定类型的抢占式调度调度过程基于优先级的任务调度（如图所示），任何基于优先级的中断控制器都是固有的优先级。如果您每个中断计划一个任务，它将按图所示执行。

Are there any good resources (books, websites) that give very good comparison of different scheduling algorithms for a Finite State Machine (FSM) in an embedded system without an OS?

I am designing a simple embedded web server without an OS. I would like to know what are the various methods used to schedule the processing of the different events that occur in the system.

For example,if two events arrived at the same time how are the events prioritized? If I assign different priorities to events, how do I ensure that the higher priority event gets processed first? If an even higher priority event comes in while an event is being processed, how can make sure that that event is processed immediately?

I'm planning on using a FSM to check various conditions upon an event's arrival and then to properly schedule the event for processing. Because the embedded web server does not have an OS, I am considering using a cyclic executive approach. But I would like to see a comparison of the pros and cons of different algorithms that could be used in this approach.

解决方案

You state: "I mean for example scheduling condion in like ,if two task arrived at the same time which task need to be prioritized and simillar other situations in embedded webserver."

Which I interpret as: "What is the set of rules used to determine which task gets executed first (scheduled) when multiple tasks arrive at the same time."

I used your terminology, "task" to illustrate the similarity. But Clifford is correct. The proper term should be "event" or "message".

And when you say "scheduling condition" I think you mean "set of rules that determines a schedule of events".

The definition of algorithm is: A process or set of rules to be followed in calculations or other problem-solving operations, esp. by a computer.

From a paper entitled Scheduling Algorithms:

Consider the central processing unit of a computer that must process a sequence of jobs that arrive over time. In what order should the jobs be processed in order to minimize, on average, the time that a job is in the system from arrival to completion?

Which again, sounds like what you're calling "scheduling conditions".

I bring this up because using the right words to describe what you are looking for will help us (the SO community) give you better answers. And will help you as you research further on your own.

If my interpretation of your question still isn't what you have in mind, please let me know what, in particular, I've said is wrong and I will try again. Maybe some more examples would help me better understand.

Some further reading on scheduling (which is what you asked for):

1. A good starting point of course is the Wikipedia article on Scheduling Disciplines
2. A bit lower level than you are looking for but still full of detailed information on scheduling is Scheduling Algorithms for High-Level Synthesis (NOTE: for whatever reason the PDF has the pages in reverse order, so start at the bottom)

An example of a priority interrupt scheduler:

Take an architecture where Priority Level 0 is the highest. Two events come in simultaneously. One with Priority 2 and another with Priority 3. The scheduling algorithm starts processing the one with Priority 2 because it has a higher priority.

While the event with Priority 2 is being processed, another event with Priority 0 comes in. The scheduler interrupts the event with Priority 2 and processes the event with Priority 0.

When it's finished processing the Priority 0 event, it returns to processing the Priority 2 event. When it's finished processing the Priority 2 event, it processes the Priority 3 event.

Finally, when it's done with processing all of the priority interrupts, it returns control to the main processing task which handles events where priority doesn't matter.

An illustration:

In the above image, the "task" is the super loop which DipSwitch mentioned or the infinite loop in main() that occurs in a cyclic executive which you mentioned. The "events" are the various routines that are run in the super loop or interrupts as seen above if they require prioritization.

Terms to search for are Priority Interrupt and Control Flow. Some good reading material is the Toppers Kernel Spec (where I got the image from), the ARM Interrupt Architecture, and a paper on the 80196 Interrupt Architecture.

I mention the Toppers Kernel Spec just because that's where I got the image from. But at the heart of any real-time OS is it's scheduling algorithm and interrupt architecture.

The "on event" processing you ask about would be handled by the microprocessor/microcontroller interrupt subsystem. How you structure the priority levels and how you handle non-priority events is what makes up the totality of your scheduling algorithm.

An example of a cooperative scheduler:

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;
}

The above example was take from a blog post entitled "Simple Co-Operative Scheduling".

A cooperative scheduler is a combination of a super loop and a timer interrupt. From Section 2.4 in NON-BLOCKING HARDWARE CODING FOR EMBEDDED SYSTEMS:

A Cooperative scheduler is essentially a combination of the two previously discussed schedulers. One timer is set to interrupt at a regular interval, which will be the minimum time resolution for the different tasks. Each task is then assigned a period that is a multiple of the minimum resolution of the interrupt interval. A function is then constantly called to update the interrupt count for each task and run tasks that have reached their interrupt period. This results in a scheduler that has the scalability of the Superloop with the timing reliability of the Time Triggered scheduler. This is a commonly used scheduler for sensor systems. However, this type of scheduler is not without its limitations. It is still important that the task calls in a cooperative scheduler are short. If one task blocks longer than one timer interrupt period, a time-critical task might be missed.

And for a more in depth analysis, here is a paper from the International Journal of Electrical & Computer Sciences.

Preemptive versus Cooperative:

A cooperative scheduler cannot handle asynchronous events without some sort of a preemption algorithm running on top of it. An example of this would be a multilevel queue architecture. Some discussion on this can be found in this paper on CPU Scheduling. There are, of course, pros and cons to each. A few of which are described in this short article on the RTKernel-32.

As for "any specific type preemptive scheduling scheduling process that can satisfy priority based task scheduling (like in the graph)", any priority based interrupt controller is inherently preemptive. If you schedule one task per interrupt, it will execute as shown in the graph.

这篇关于寻找有限状态机的不同调度算法的比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！