Книга: Advanced PIC Microcontroller Projects in C

10.2.1 The Scheduler

10.2.1 The Scheduler

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.

Figure 10.4: Round-robin scheduling

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.

Figure 10.5: Preemptive scheduling

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

Figure 10.6: Task states

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

Оглавление книги