Selecting the right RTOS scheduling algorithms using system modelling

Ranjit Adiga, CMR Design Automation

August 26, 2013

Ranjit Adiga, CMR Design AutomationAugust 26, 2013

Editor’s Note: Ranjit Adiga describes how his company did away with the need for a full RTOS implementation by using a hardware/software system modelling tool to build a dedicated scheduler. Also provided is an executable web version of the project where users can visualize the setup of the software processes and definition of the hardware platform.

Most high-performance embedded systems do not need 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 neighboring 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).

Figure 1 shows a preemptive scheduler resource with multiple tasks. Here we have considered three different tasks - Process 1, Process 2 and Process 3 - started at time intervals of 3, 6, and 9 seconds respectively. The processing time provided for each task is 3 seconds. Process 1 will start at 0.0 secs with an allotted time slice of 3 seconds, Process 2 will start at 2.0 seconds with an allotted time slice of 3.0 seconds, and Process 3 starts at 4.0 seconds with a time slice of 3.0 seconds.

Figure 1: Preemptive Scheduler Resource Model

The resource (Scheduler block) is a dispatch unit; the actual deployment can be a processor, DSP, FPGA, or ASIC. Here we abstracted the hardware resources with an execution delay. The model will evaluate the response time for the different tasks with preemptive scheduling schemes with different levels of priority, different arrival rates, and different processing times. The assigned priorities range from 1 to 3, with the higher number being higher priority.

Figure 2 is the task completion graph for the above sequence without considering pre-emption.
If you look at the plot, Process 1 will complete its processing on scheduler resource with the given time slice of  3 seconds. Process 2 should have started processing on the scheduler at 2.0 secs but it is delayed because of Process 1, which will complete at 3.0 seconds. Similarly, Process 3 will start processing in Scheduler resource with a delayed time of 2.0 seconds because of occupancy of Process 2 in Scheduler resource.

Figure 2: Non-preemptive

Figure 3: Preemptive

Figure 3 is the task plot when the scheduler resource is preemptive. Here Process 1 will start processing in scheduler at 0.0 with the task time of 3.0 secs. Before completion of Process 1 processing, Process 2 will start processing at 2.0 seconds in scheduler because of higher priority. In this case Process 1 processing is interrupted temporarily and Process 2 processing begins.

< Previous
Page 1 of 2
Next >

Loading comments...