Global Sources
EE Times-Asia
Stay in touch with EE Times Asia
EE Times-Asia > Embedded

Choosing the right RTOS scheduling algorithms

Posted: 10 Sep 2013 ?? ?Print Version ?Bookmark and Share

Keywords:real-time operating system? RTOS? FCFS? VisualSim Architect? Preemption?

Most high-performance embedded systems do not require an expensive and full-functionality real-time operating system (RTOS). A dedicated scheduler such as those used in arbitration processes and traffic management is sufficient, extremely efficient, and has a low memory footprint. This approach is particularly preferred where memory size is limited and timing deadlines must be strictly enforced.

Typical applications are in defence, aerospace, industrial, and automotive. There are a number of standard scheduling algorithms such as First¬ Come, First ¬Served (FCFS); Shortest Job First (SJF); Preemptive; and Round Robin.

How do we select the right scheduler at the start of the project when the software is not ready and we have only the guideline specification of the hardware? There are many approaches, such as rate monotonic analysis (RMA), worst case execution time analysis, and system-level performance modelling analysis. When you combine the requirements of current software architectures such as non-periodic arrivals, pre-emption, and variable start times, deploying RMA is extremely difficult and in many cases impossible to configure.

Worst case execution analysis can be extremely pessimistic, unable to handle too many non-deterministic expressions, and this type of analysis does not provide a probability for the execution time range. In our opinion and in accordance with industry practices, we see system-level performance modelling and analysis as the only approach that can truly define ad hoc software-task execution details as well as define hardware resource impacts. For our study, we used a commercial system-level performance modelling simulator called VisualSim Architect from Mirabilis Design for our scheduling analysis.

To explain our evaluation mechanism, we used a system with three concurrent software tasks and a common scheduling resource. The variables considered are the non-periodic rate, concurrency, execution time, priority, context-switching, and the scheduling algorithm. The lists of scheduling algorithms we have short-listed are First Come, First Serve (FCFS), Preemptive FCFS, and Round Robin.

FCFS queues the incoming request from multiple concurrent requestors and schedules them on the hardware resource in the order of arrival. The queue gets reordered based on the priority of each incoming resource. Preemptive scheduling is the act of temporarily interrupting a task which is being carried out by a system without requiring task co-operation and with the intention of resuming the particular task at a later time. Preemptive FCFS uses the FCFS technique and can pre-empt an executing task with the arrival of a higher priority task. The current task will complete the execution when it gets access to the resource again, which will depend on the priority of the other tasks in the queue.

Round Robin provides equal time slices to all the requesting tasks until the task has completed. Another scheduling algorithm is Time Slots, which is similar to ARINC 653. In ARINC 653, multiple time slots are set up. Each task is assigned to a time slot in a concentric loop. The tasks must complete within their assigned time slots or wait until the next slot that is assigned to that task. We used a protected mode whereby a task cannot infringe on a neighbouring slot.

A context switching time is allocated for the hardware to reset and manage resources between task executions. To switch between tasks, we use an interrupt when the time slices expire. This effectively allows the processor's time to be shared between tasks, giving the illusion that it is dealing with these tasks concurrently.

We evaluated a scenario of priority-based, preemptive scheduling resources using VisualSim Architect, which provides a wide rage of support in the area of RTOS scheduling. The system-level model for simulation we used is focused on illustrating the methodology we deployed in our analysis. A more detailed analysis can include Deadline plus Preemption, Weighted Round Robin (WRR), Cooperative Scheduling, and Earliest Deadline First (EDF).

1???2???3?Next Page?Last Page

Article Comments - Choosing the right RTOS scheduling a...
*? You can enter [0] more charecters.
*Verify code:


Visit Asia Webinars to learn about the latest in technology and get practical design tips.

Back to Top