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?

Figure 1 shows a preemptive scheduler resource with multiple tasks. Here we have considered three different tasksProcess 1, Process 2 and Process 3started 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.

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 1: Preemptive scheduler resource model.

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 will start executing at 4.0 secs because of higher priority. Once Process 3 processing is completed in Scheduler resource, the next highest priority task in queue is Process 2, which will complete its processing. One more important thing to notice is that even though Process 2 and Process 1 are being interrupted, the total execution time is still 3.0 seconds for both, even though the total completion time is much longer.

Preemptive multi-tasking allows the system to more reliably guarantee each process a regular 'slice' of operating time. It also allows the system to rapidly deal with important external events like incoming data, which might require the immediate attention of one or another process.

Another common scheduling algorithm used is Round Robin, which is used especially 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 ongoing cycle, which is the round robin. A run-time counter tracks the time slice for each task, incrementing on every clock tick. When one task's time slice completes, the counter is cleared, and the task is placed at the end of the cycle. Newly added tasks of the same priority are placed at the end of the cycle, with their run-time counters initialized to 0.

If a 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 task is again eligible for execution.

?First Page?Previous Page 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