Understanding How Tasks Work - Part 2

This is part 2 of a two part article that discusses in technical detail how tasks (threads) work with respect to task switching, instance data, inter-task communication, scheduling, and priority. For a general overview of threads, see a previous article. This article discusses task scheduling and priority.

Task Scheduling

There are various ways in which a task can be scheduled. This article deals only with techniques for implementing priority based preemptive scheduling. For information about other scheduling policies, see the reference. Priority based preemptive scheduling can be accomplished in a variety of ways, however, in this article we will examine only one in detail, as described below.

The Ready Queue

The ready queue is a doubly linked list of tasks waiting to run, ordered by task priority, the highest priority waiting task being at the front of the queue, (referred to as the ready task), and the lowest at the rear of the queue. The kernel schedules a task to run by inserting it into the queue according to its priority. Each element of the list contains a reference to a tcb. Implicit is the fact that the active task is of a higher priority than the highest priority waiting task.

Determining Which Task Runs

The kernel begins multi-tasking by removing the task at the front of the ready queue and executing it via a context switch. The task will run until it voluntarily relinquishes control or is preempted, at which time a context switch to the ready task is performed.

How Tasks Voluntarily Relinquish Control

A task can voluntarily relinquish control explicitly with a yield, pause, or suspend; or implicitly with waitMsg, waitMail, etc. When the active task relinquishes control, the task referenced by the node at the front of the ready queue becomes the new active task.

How Tasks Involuntarily Relinquish Control

Tasks can involuntarily relinquish control when a message is passed as described below, or via time-slicing, which is not described in this article.

Message Passing and Scheduling

When a message is sent, the destination task is scheduled to run, which has some interesting implications. One implication is that when a lower priority task sends a message to a higher priority task, the lower priority task should suspend so that the higher priority task can run. This can be used as a mechanism for interrupt handling as described below.

Interrupts and Scheduling

Sometimes an isr should not return to the interrupted task, but rather to a higher priority task that must run as a result of the interrupt. This can be effected using the message passing rule alluded to above. So, if lower priority taskA is interrupted to run isrA and isrA sends higher priority taskB a message, then on executing the IRET instruction, taskA should remain suspended, and taskB resumed.

Idle Task

Consider a 5 task system where each task issues a 500 ms pause on entry, which will cause all 5 tasks to be suspended for 500 ms. One may ask what happens during this 500 ms period when all 5 tasks are suspended. Typically what occurs is that a special system task called the idle task runs. The idle task has the lowest possible priority and runs only when no other tasks are scheduled. The idle task is typically a "do nothing" tight loop. Its only purpose is to run when no other tasks run. It is a convenience mechanism in that no special kernel code is required to handle the case of all tasks being idle; the kernel sees the idle task like any other task. The key is that the idle task has a lower priority than any other task, and even though it is scheduled to run and occupies a place in the ready queue, it will not run until all other tasks are idle. And, conversely, when any other task is scheduled, the idle task is preempted.

Summary and Comments

The above description is only one of various scheduling mechanisms. The scheduling mechanism described above is referred to as dynamic scheduling because it allows for an unlimited number of waiting tasks; for the creation of new tasks during execution; and for task priorities to change during execution. Contrast this to a static scheduling system in which tasks are entered into a table in priority order and bound at compile-time. The result is that new tasks cannot be created during execution time, nor can task priorities be changed with static scheduling.

We welcome comments. Let us know what subjects you would like written up. Send comments to mike@Ticsrealtime.com