April 26, 2007

Real-Time Operating Systems for DSP, part 2

Part 2 of this 8-part series introduces the concept of multitasking, and explains how an RTOS schedules tasks for execution.

By Robert Oshana

[Part 1 introduces the RTOS, and explains the special features a DSP-oriented RTOS. Part 3 introduces the RTOS kernel and shows how it prioritizes tasks. It also explains dynamic memory allocation, system calls, and hardware interrupts.]

Concepts of RTOS
Real-time operating systems require a set of functionality to effectively perform their function, which is to be able to execute all of their tasks without violating specified timing constraints. This section describes the major functions that real-time operating systems perform.

Task-Based
A task is a basic unit of programming that an operating system controls. Each different operating system may define a task slightly differently. A task implements a computation job and is the basic unit of work handled by the scheduler. The kernel creates the task, allocates memory space to the task and brings the code to be executed by the task into memory. A structure called a task control block (TCB) is created and used to manage the schedule of the task. A task is placeholder information associated with a single use of a program that can handle multiple concurrent users. From the program's point-of-view, a task is the information needed to serve one individual user or a particular service request.

Types of real-time tasks:

• Periodic – Executes regularly according to a precomputed schedule.
• Sporadic – Triggered by external events or conditions, with a predetermined maximum execution frequency.
• Spontaneous – Optional real-time tasks that are executed in response to external events (or opportunities), if resources are available.
• Ongoing tasks – Fair-share threads.

Multitasking
Today's microprocessors can only execute one program instruction at a time. But because they operate so fast, they can be made to appear to run many programs and serve many users simultaneously. This illusion is created by rapidly multiplexing the processor over the set of active tasks. The processor operates at speeds that make it seem as though all of the user's tasks are being performed at the same time.

While all multitasking depends on some time of processor multiplexing, there are many strategies for "scheduling" the processor. In systems with priority-based scheduling, each task is assigned a priority depending on its relative importance, the amount of resources it is consuming, and other factors. The operating system preempts tasks having a lower priority value so that a higher priority task is given a chance to run. I'll have much more to say about scheduling later in this series.

Forms of Multitasking
There are three important multitasking algorithms:

• Preemptive – With this algorithm, if a high-priority task becomes ready for execution it can immediately pre-empt the execution of a lower-priority task and acquire the processor without having to wait for the next regular rescheduling. In this context, "immediately" means after the scheduling latency period. This latency is one of the most important characteristics of a real-time kernel and largely defines the system responsiveness to external stimuli.
  
  
• Cooperative – With this algorithm, if a task is not ready to execute it voluntarily relinquishes the control of the processor so that other tasks can run. This algorithm does not require much scheduling and generally is not suited for real-time applications.
  
  
• Time-sharing – A pure time sharing algorithm has obvious low responsiveness (limited by the length of scheduling interval). Nevertheless, a time sharing algorithm is always implemented in real-time operating systems. The reason for this is that there is almost always more than one nonreal-time task in the real-time system (interaction with user, logging of accounting information, various other bookkeeping tasks). These tasks have low priority and are scheduled with a timesharing policy in the time when no tasks of higher priority are ready for execution.
  

Rapid Response to Interrupts
An interrupt is a signal from a device attached to a computer or from a program within the computer that causes the RTOS to stop and figure out what to do next. Almost all DSPs and general-purpose processors are interrupt-driven. The processor will begin executing a list of computer instructions in one program and keep executing the instructions until either the task is complete or cannot go any further (waiting on a system resource for example) or an interrupt signal is sensed. After the interrupt signal is sensed, the processor either resumes running the program it was running or begins running another program.

An RTOS has code that is called an interrupt handler. The interrupt handler prioritizes the interrupts and saves them in a queue if more than one is waiting to be handled. The scheduler program in the RTOS then determines which program to give control to next.

An interrupt request (IRQ) will have a value associated with it that identifies it as a particular device. The IRQ value is an assigned location where the processor can expect a particular device to interrupt it when the device sends the processor signals about its operation. The signal momentarily interrupts the processor so that it can decide what processing to do next. Since multiple signals to the processor on the same interrupt line might not be understood by the processor, a unique value must be specified for each device and its path to the processor.

In many ways, interrupts provide the "energy" for embedded real-time systems. The energy is consumed by the tasks executing in the system. Typically, in DSP systems, interrupts are generated on buffer boundaries by the DMA or other equivalent hardware. In this way, every interrupt occurrence will ready a DSP RTOS task that iterated on full/empty buffers. Interrupts come from many sources (Figure 1) and the DSP RTOS must effectively manage multiple interruptions from both inside and outside the DSP system.

Figure 1. An RTOS must respond to and manage multiple interruptions from inside and outside the application.

A RTOS for DSP requires a specific set of attributes to be effective. The task scheduling should be priority based. A task scheduler for DSP RTOS has multiple levels of interrupt priorities where the higher priority tasks run first. The task scheduler for DSP RTOS is also preemptive. If a higher priority task becomes ready to run, it will immediately pre-empt a lower priority running task. This is required for real-time applications. Finally, the DSP RTOS is event driven. The RTOS has the capability to respond to external events such as interrupts from the environment. DSP RTOS can also respond to internal events if required.

Scheduler Jargon
Multitasking jargon is often confusing to newcomers because there are so many different strategies and techniques for multiplexing the processor. The key differences among the various strategies revolve around how a task loses control and how it gains control of the processor. While these are separate design decisions (for the RTOS designer), they are often treated as being implicitly linked in marketing literature and casual conversation.

Scheduling regimens viewed by how tasks lose control:

• Only by voluntary surrender. This style is called cooperative multitasking. For a task to lose control of the processor, the task must voluntarily call the RTOS. These systems continue to multitask only so long as all the tasks continue to share graciously.
  
  
• Only after they've finished their work. Called run to completion. To be practical, this style requires that all tasks be relatively short duration.
  
  
• Whenever the scheduler says so. Called preemptive. In this style the RTOS scheduler can interrupt a task at any time. Preemptive schedulers are generally more able to meet specific timing requirements than others. (Notice that if the scheduler "says so" at regular fixed intervals, then this style is called time slicing.)
  

• By being next in line. A simple FIFO task queue. Sometimes mistakenly called round-robin. Very uncommon.
  
  
• By waiting for its turn in a fixed-rotation. A slop cyclic scheduler. The "super loop" mentioned at the beginning of this series is this form of cyclic scheduler.If the cycle is only allowed to restart at specific fixed intervals, it's called a rate cyclic scheduler.
  
  
• By waiting a specific amount of time. A very literal form of multiplexing in which each ready to execute task is given the processor for a fixed-quantum of time. If the tasks are processed in FIFO order, this style is called a round-robin scheduler. If the tasks are selected using some other scheme it's considered a time-slicing scheduler.
  
  
• By having a higher priority than any other task wanting the processor. A priority-based or "prioritized" scheduler.
  

The scheduler is a central part of the kernel. It executes periodically and whenever the state of a thread changes. A single-task system does not really need a scheduler since there is no competition for the processor. Multitasking implies scheduling because there are multiple tasks competing for the processor. A scheduler must run often enough to monitor the usage of the CPU by the tasks. In most real-time systems, the scheduler is invoked at regular intervals. This invocation is usually the result of a periodic timer interrupt. The period in which this interrupt is invoked is called the tick size or the system "heartbeat." At each clock interrupt the RTOS updates the state of the system by analyzing task execution budgets and making decisions as to which task should have access to the system CPU. Task states
Further refinement comes when we allow tasks to have states other than ready for execution. The major states of a typical RTOS include:

• Sleeping – The thread is put into a sleeping state immediately after it is created and initialized. The thread is released and leaves this state upon the occurrence of an event of the specified type(s). Upon the completion of a thread that is to execute again it is reinitialized and put in the sleeping state.
  
  
• Ready – The thread enters the ready state after it is released or when it is pre-empted. A thread in this state is in the ready queue and eligible for execution. (The RTOS may also keep a number of ready queues. In fixed-priority scheduling, there will be a queue for each priority. The RTOS scheduler rather than simply admitting the tasks to the CPU, makes a decision based on the task state and priority.)
  
  
• Executing – A thread is in the executing state when it executes.
  
  
• Suspended (Blocked) – A thread that has been released and is yet to complete enters the suspended or blocked state when its execution cannot proceed for some reason. The kernel puts a suspended thread in the suspended queue. There are various reasons for a multitasking DSP to suspend. A task may be blocked due to resource access control. A task may be waiting to synchronize execution with some other task(s). The task may be held waiting for some reason (I/O completion and jitter control). There may be no budget or aperiodic [2] job to execute (this is a form of bandwidth control). The RTOS maintains different queues for tasks suspended or blocked for different reasons (for example, a queue for tasks waiting for each resource).
  
  
• Terminated – A thread that will not execute again enters the terminated state when it completes. A terminated thread may be destroyed.
  

  Different RTOS's will have slightly different states. Figure 2 shows the state model for a DSP RTOS called DSP/BIOS from Texas Instruments.

  
  (Click to enlarge)
  Figure 2. State model (with preemption) for the Texas Instruments DSP BIOS RTOS.

  Most RTOSs provide the user the choice of round-robin or FIFO scheduling of threads of equal priority. A time slice (execution budget) is used for round-robin scheduling. At each clock interrupt the scheduler reduces the budget of the thread by the tick size. Tasks will be pre-empted if necessary (A FIFO scheduling algorithm uses an infinite time slice.) At each clock interrupt, the RTOS scheduler updates the ready queue and either returns control to the current task or preempts the current task if it is no longer the highest priority ready task. Because of the previous actions, some threads may become ready (released upon timer expiration) and the thread executing may need to be pre-empted. The scheduler updates the ready queue accordingly and then gives control to the thread at the head of the highest priority queue.

  Part 3 introduces the RTOS kernel and shows how it prioritizes tasks. It also explains dynamic memory allocation, system calls, and hardware interrupts.

  Used with the permission of the publisher, Newnes/Elsevier, this series of eight articles is based on chapter eight of "DSP Software Development Techniques for Embedded and Real-Time Systems," by Robert Oshana.

  Footnotes
  2. Tasks are not always periodic. Tasks that are not periodic are called aperiodic. Examples of aperiodic tasks include operator requests, emergency message arrivals, threshold crossing notifications, keyboard presses, mouse movements, and detection of incoming objects.