Search for mapping various planning algorithms for a finite state machine

Question

Are there any good resources (books, websites) that give a very good comparison of different planning 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 various methods are used to plan the processing of various events that occur in the system.

For example, if two events came at the same time, what are the priorities of the events? If I assign different priorities to events, how can I ensure that an event with a higher priority is handled first? If an event with a higher priority occurs during event processing, how can you be sure that this event will be processed immediately?

I plan to use FSM to check various conditions when an event arrives, and then to plan the event correctly for processing. Since the embedded web server does not have an OS, I am considering using a circular execution approach. But I would like to see a comparison of the pros and cons of various algorithms that could be used in this approach.

Answer 1

You declare: "I mean, for example, scheduling schedules is similar if the two tasks started at the same time that the task should be prioritized and similar to other situations in the embedded web server."

Which I interpret as: "What is the set of rules used to determine which task is performed first (on a schedule) while performing several tasks at the same time."

I used your terminology, the "task", to illustrate the similarities. But Clifford is right. The correct term should be “event” or “message”.

And when you say "planning condition", I think you mean "a set of rules that determine the schedule of events."

Algorithm Definition: A process or set of rules that must be performed in computing or other problem solving operations, especially. using a computer.

From a document entitled Schedule Algorithms :

Consider the computer’s central processor, which must process a sequence of jobs that arrive over time. In what order should tasks be carried out to be processed in order to minimize, on average, the time when work in the system from arrival to completion?

Which again sounds like what you call "planning conditions."

I talk about this 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 when you explore further on your own.

If my interpretation of your question is still not what you mean, let me know that, in particular, I said this is wrong, and I will try again. Maybe a few more examples will help me better understand.

Some additional reading about planning (what you asked for):

• A good starting point, of course, is the Wikipedia article on Discipline Planning.
• A bit lower than you are looking for, but still contains detailed planning information. Planning algorithms for high-level synthesis ( NOTE: for some reason, the PDF has pages in the reverse order, so start from the bottom)

Example of a priority interrupt scheduler:

Take architecture where priority 0 is highest. Two events occur simultaneously. One with priority 2 and the other with priority 3. The planning algorithm starts to process the one with priority 2 because it has a higher priority.

While an event with priority 2 is being executed, another event with priority 0 comes in. The scheduler interrupts the event with priority 2 and processes the event with priority 0.

When he finishes processing the Priority 0 event, he will return to processing the Priority 2 event. When he finishes processing the Priority 2 event, he processes the Priority 3 event.

Finally, when it processes all priority interrupts, it returns control to the main processing task, which processes events whose priority does not matter.

Illustration:

In the above image, the “task” is the super loop mentioned by DipSwitch, or the infinite loop in main() , which occurs in the loop executor that you talked about. "Events" are various procedures that are executed in a super-loop or interrupt, as shown above, if they require prioritization.

Search Conditions: Priority Interrupt and Control Flow . Some good reading material is the Toppers Kernel Spec (where I got the image), the “ARM Interrupt Architecture” and document 80196 Interrupt Architecture .

I mention the Toppers Kernel specification only because I received the image. But at the heart of any real-time OS is the scheduling algorithm and interrupt architecture.

The "on event" processing you are asking for will be handled by the microprocessor / microcontroller interrupt subsystem. How you structure the priority levels and how you handle non-priority events is what constitutes the totality of your planning algorithm.

An example of a collaborative 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 takes a blog post called Simple Collaborative Planning .

A collaborative scheduler is a combination of a super-cycle and a timer interrupt. From section 2.4 to CONTINUOUS EQUIPMENT CODING FOR EMBEDDED SYSTEMS :

A cooperative planner is essentially a combination of the two previously discussed planners. One timer is set to interrupt at a regular interval, which will be the minimum time resolution for different tasks. Then, each task is assigned a period that is a multiple of the minimum resolution of the interrupt interval. the function is constantly called to update the number of interrupts for each task and run tasks that have reached the interrupt period. This leads to a scheduler with Superloop scalability with reliable synchronization of the Time Triggered scheduler. It is a widely used scheduler for touch systems. However, this type of scheduler is not without limitations. It is still important that the task call in the collaborative scheduler is short. If one task blocks longer than one timer interrupt period, a critical task may be skipped.

And for a deeper analysis, here is an article from the International Journal of Electrical Engineering and Computer Science .

Preventive and cooperative:

A collaborative scheduler cannot handle asynchronous events without any preemption algorithm running on top of it. An example of this is the layered architecture of a queue. Some discussion of this can be found in this article on CPU planning. Of course, for everyone there are pros and cons. Some of them are described in this short article on RTKernel-32.

As for “any priority-type planning planning process that can satisfy priority-based task planning (for example, on a graph),” any priority interrupt controller is inherently proactive. If you plan on one interrupt task, it will run as shown in the graph.

Answer 2

If I knew the question meant the answer would probably be Miro Samek Practical UML state diagrams in C / C ++, second edition: event-driven programming for embedded systems