RTOS Explained: Preemptive Scheduling

The RTXC Quadros multistack RTOS supports three scheduling methods that may be used in whatever combination the developer requires.

  • Preemptive
  • Round Robin
  • Time-Sliced

Today we will discuss the topic of preemptive scheduling.

To achieve efficient CPU utilization a multitasking RTOS uses an orderly transfer of control from one code entity to another. To accomplish this the RTOS must monitor system resources and the execution state of each code entity, and it must ensure that each entity receives control of the CPU in a timely manner.

The key word here is timely. A real-time system that does not perform a required operation at the correct time has failed. That failure can have consequences that range from benign to catastrophic. Response time for a request for kernel services and the execution time of these services must be fast and predictable. With such an RTOS, application program code can be designed to ensure that all needs are detected and processed.

Real-time applications usually consist of several tasks (also can be called processes or threads) that require control of system resources at varying times due to external or internal events. Each task must compete with all other task for control of system resources such as memory, execution time, or peripheral devices. The developer uses the scheduling models in the RTOS to manage this “competition” between these tasks.

Program code can be compute-bound (heavily dependent on CPU resources) or I/O-bound (heavily dependent on access to external devices). Program code that is I/O bound or compute bound cannot be allowed to monopolize a system resource if a more important task requires the same resource. There must be a way of interrupting the operation of the lesser task and granting the resource to the more important one.

One method for achieving this is to assign a priority to each task. The kernel then uses this priority to determine a task’s place within the sequence of execution of other tasks. In a prioritized system the highest priority task that is ready is given control of the processor. Tasks of lower priority must wait and, even when running, may have their execution preempted by a task of higher priority. When a task completes its operation or blocks (waits for something to happen before it can continue) it releases the CPU. The scheduler in the RTOS then looks for the next highest priority code entity that is ready to run and assigns it control of the CPU.

In this preemptive scheduling model a task must be in one of four states:

  1. Running – the task is in control of the CPU
  2. Ready – the task is not blocked and is ready to receive control of the CPU when the scheduling policy indicates it is the highest priority task in the system that is not blocked
  3. Inactive – the task is blocked and requires initialization in order to become ready.
  4. Blocked – the task is waiting for something to happen or for a resource to become available.

Preemptive Scheduling in Summary

  • Each Task has a priority relative to all other tasks
  • The most critical Task is assigned the highest priority
  • The highest priority Task that is ready to run gets control of the processor
  • A Task runs until it yields, terminates, or blocks
  • Each Task has its own memory stack
  • Before a Task can run it must load its context from its memory stack (this can take many cycles)
  • If a Task is preempted it must save its current state/context; this context is  restored when the Task is given control of the processor

Further reading

Read our previous blog post on Run-to-Completion Threads

Download the whitepaper: 10 Questions to Ask Your RTOS Vendor

Visit the RTXC Quadros RTOS information page

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>