Real-time operating systems are built around a multi-tasking kernel which controls the allocation of time slices to tasks. A time slice is the period of time a given task has for execution before it is stopped and replaced by another task. This process, also known as context switching, repeats continuously. When context switching occurs, the executing task is stopped, the processor registers are saved in memory, the processor registers of the next available task are loaded into the CPU, and the new task begins execution. An RTOS also provides task-to-task message passing, synchronization of tasks, and allocation of shared resources to tasks.
The basic parts of an RTOS are:
• Scheduler
• RTOS services
• Synchronization and messaging tools
A scheduler is at the heart of every RTOS, as it provides the algorithms to select the tasks for execution. Three of the more common scheduling algorithms are:
• Cooperative scheduling
• Round-robin scheduling
• Preemptive scheduling
Cooperative scheduling is perhaps the simplest scheduling algorithm available. Each task runs until it is complete and gives up the CPU voluntarily. Cooperative scheduling cannot satisfy real-time system needs, since it cannot support the prioritization of tasks according to importance. Also, a single task may use the CPU too long, leaving too little time for other tasks. And the scheduler has no control of the various tasks’ execution time. A state machine construct is a simple form of a cooperative scheduling technique.
In round-robin scheduling, each task is assigned an equal share of CPU time (see Figure 10.4). A counter tracks the time slice for each task. 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 are placed at the end of the cycle with their counters cleared to 0. This, like cooperative scheduling, is not very useful in a real-time system, since very often some tasks take only a few milliseconds while others require hundreds of milliseconds or more.
Preemptive scheduling is considered a real-time scheduling algorithm. It is priority- based, and each task is given a priority (see Figure 10.5). The task with the highest priority gets the CPU time. Real-time systems generally support priority levels ranging from 0 to 255, where 0 is the highest priority and 255 is the lowest.
In some real-time systems where more than one task can be at the same priority level, preemptive scheduling is mixed with round-robin scheduling. In such cases, tasks at higher priority levels run before lower priority ones, and tasks at the same priority level run by round-robin scheduling. If a task is preempted by a higher priority task, its run time counter is saved and then restored when it regains control of the CPU.
In some systems a strict real-time priority class is defined where tasks above this class may run to completion (or run until a resource is not available) even if there are other tasks at the same priority level.
In a real-time system a task can be in any one of the following states (see Figure 10.6):
• Ready to run
• Running
• Blocked
When a task is first created, it is usually ready to run and is entered in the task list. From this state, subject to the scheduling algorithm, the task can become a running task. According to the conditions of preemptive scheduling, the task will run if it is the highest priority task in the system and is not waiting for a resource.
A running task becomes a blocked task if it needs a resource that is not available. For example, a task may need data from an A/D converter and is blocked until it is
available. Once the resource can be accessed, the blocked task becomes a running task if it is the highest priority task in the system, otherwise it moves to the ready state. Only a running task can be blocked. A ready task cannot be blocked.
When a task moves from one state to another, the processor saves the running task’s context in memory, loads the new task’s context from memory, and then executes the new instructions as required.
The kernel usually provides an interface to manipulate task operations. Typical task operations are:
• Creating a task
• Deleting a task
• Changing the priority of a task
• Changing the state of a task
RTOS services are utilities provided by the kernel that help developers create real-time tasks efficiently. For example, a task can use time services to obtain the current date and time. Some of these services are:
• Interrupt handling services
• Time services
• Device management services
• Memory management services
• Input-output services
Synchronization and messaging tools are kernel constructs that help developers create real-time applications. Some of these services are:
• Semaphores
• Event flags
• Mailboxes
• Pipes
• Message queues
Semaphores are used to synchronize access to shared resources, such as common data areas. Event flags are used to synchronize the intertask activities. Mailboxes, pipes, and message queues are used to send messages among tasks.