Selecting the right RTOS scheduling algorithms using system modelling

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 anddefinition 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.Similarly, before completion of Process 2 Processing, Process 3 willstart executing at 4.0 secs because of higher priority. Once Process 3processing is completed in Scheduler resource, the next highest prioritytask in queue is Process 2, which will complete its processing. Onemore important thing to notice is that even though Process 2 and Process1 are being interrupted, the total execution time is still 3.0 secondsfor both, even though the total completion time is much longer.

Preemptivemultitasking allows the system to more reliably guarantee each process aregular ‘slice’ of operating time. It also allows the system to rapidlydeal with important external events like incoming data, which mightrequire the immediate attention of one or another process.

Anothercommon scheduling algorithm used is Round Robin, which is usedespecially for time-sharing systems. It is similar to FCFS scheduling,but preemption is added to switch between processes. With time slicing,each task executes for a defined interval, or time slice, in an ongoingcycle, which is the round robin. A run-time counter tracks the timeslice for each task, incrementing on every clock tick. When one task’stime slice completes, the counter is cleared, and the task is placed atthe end of the cycle. Newly added tasks of the same priority are placedat the end of the cycle, with their run-time counters initialized to 0.

Ifa task in a Round Robin cycle is preempted by a higher-priority task,its run-time count is saved and then restored when the interrupted taskis again eligible for execution.

Figure 4: Round Robin

Figure 4 represents the simulation task plot, Task ID vs Simulation time. Herewe have considered three different tasks, Task 1, Task 2, and Task 3.Task 1 starts at 0.0 ms, Task 2 starts at 2.0 ms, and Task 3 starts at4.0 ms. The Round Robin time slice we have given is 2.0 ms. Accordinglyeach task is provided with 2.0 ms of equal proportion of time slice. Wehave provided Task processing time for all tasks as 3.0 ms.

Asyou can see in Figure 4, Task 1 has divided into 2 sections, the firsthalf is provided with time slice of 2.0 ms and the remaining 1.0 ms isperformed at a later time after completion of Task 2 time slice of 2.0ms. Task 3 is supposed to start at 4.0 ms but is pushed to 5.0 becauseof Task 1. If we look at the Task 2, the first part of the processing iscarried out from 2.0 to 4.0 ms, and the remaining 1.0 ms will beperformed during 7.0 to 8.0 simulation time.

VisualSim Architectprovided us a package that included scheduling algorithms, analysistools, and traffic generators. These allowed us to set up the systemquickly and conduct hundreds of such experiments with different valuesof variables, and a number of additional variables. Some of the otherscheduling mechanisms include First Come First Served, First Come FirstServe + Preemption, Round Robin, Priority Based, Credit Policy, WeightedRound Robin, and a framework for proprietary scheduling algorithms.

As noted in the online web version ,using VisualSim Architect we assembled the model that included systemtraffic; hardware elements like processor, DSP, Memories, DMA and Bus;and probes to capture all the relevant design metrics. VisualSim’slibraries of standard hardware and software components, flow chartsdefining the behavior, traffic models, and prebuilt analysis probesallowed us to focus on the analysis. That allowed us to leave themathematics to the underlying engine to define and analyze unpredictablebehavior.

Modelling an embedded system to choose the rightscheduling algorithm at the higher abstraction level model ensuresgreater flexibility in evaluation, can identify error conditions thatwould be hard to find downstream, and determine what is feasible withthe available resources.

The selection ofthe right RTOS scheduling depends on the application and activities ofthe tasks to be scheduled. There are many scheduling algorithms fromwhich to choose. But in our analysis we found that having many smallertasks without preemption provided the best overall performance. Thisalso allowed us to provide a higher priority for some tasks and allowpreemption for only extremely rare tasks.

System modelling andsimulation were critical in our analysis of the timing and was a keydriver in selecting the right scheduling algorithm. Using thissystem-level analysis, we found that a full-blown RTOS was not arequirement and we could get better performance at a lower cost with afocused scheduler. A discussion on this topic is available on YouTube .

Editor’s note: The author provides an executable web version of the project where users can visualize the setup of the software processes anddefinition of the hardware platform. Users can also modify attributes,run simulations, and view the resulting analysis.

Ranjith Adiga (KR) is an EDA Application engineer, specializing in VisualSimsystem-level products at CMR Design Automation in Bengaluru, India. Hehas many years of expertise in system level modeling, simulation, anddevelopment. Mr. Ranjith has been involved in various system-level modeldevelopment projects with the defense sector, aerospace corporations,and multinational semiconductor companies in India. He completed his MSin Electronics from Kuvempu University and a Diploma in FPGA design andverification.

4 thoughts on “Selecting the right RTOS scheduling algorithms using system modelling

  1. “… smaller tasks without preemption provided the best overall performance. … allow preemption for only extremely rare tasks. ”

    So does your system have preemption, or not? Are you just implementing a polling loop, or do you really have an OS that's

    Log in to Reply
  2. I was pointed to this article again by one of my colleagues who seems to think it says “nobody ever needs an RTOS”, and anything more complicated than a top level polling loop is unnecessary.

    If we had a complete system-level understanding of our system b

    Log in to Reply
  3. I am also a firm believer that , though it may seem to be a lot of unnecessary things , the basic RTOS is the fool proof answer for any Embedded system developer – Preemptive scheduling being one of the essential features. Any shortcuts in this can prove t

    Log in to Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.