Cost, among other factors, determines the success of a product in the market. One way of viewing cost is the ratio of resources present in the system to the end products’ required set of features. We, the engineers, are constantly driven to provide more features at a reduced system cost. Therefore, it becomes imperative that we effectively manage each and every resource available in the system.
Flash memory, RAM and CPU throughput (processing power) are some critical microcontroller resources, especially since the cost of the microcontroller is tied to the amount of these resources that is available on it.
Additionally, firmware is expected to be portable, maintainable, and the code reusable, to reduce future engineering efforts and simplify the ability to enhance the end product in the future.It is expected of us to integrate multiple subsystems, such as USB, graphics and Ethernet, to create a feature-rich product.
This is Part 1 of a three-part article series which presents a solution to the above challenge. This first article will review the basics of multitasking, discuss what the traditional approach to multitasking is, and then study the fundamentals of a low-cost alternative using state machines by building a very simple FM player system.
Part 2 will study the design methodology for building a state machine-based multitasking system.Task design, inter task communication, and prioritizing are dealt with by building a complex MP3 Player system that integrates USB, a file system, LCD and capacitive touch sensing.
Part 3 will discuss scheduling methods for the system we just created.A time-sliced approach with design-time CPU load balancing will be introduced, and some enhancements and diagnostic methods/tools will be discussed.
Multitasking With an RTOS
The need for multitasking in low-cost systems arises mainly due to the necessity to respond to the user as quickly as possible. A product that is quick to respond to the user input appears to run faster even though that back-end job takes the same amount of time. The system is expected to simultaneously do the back end job and service the user input.
A multitasking system appears to perform multiple tasks simultaneously by sequentially running pieces of each task.Two important aspects of multitasking are regularity of time interval and reliable restoration of context while tasks are switched.
A regular RTOS achieves this via a timer interrupt.On each of these periodic interrupts, the RTOS saves the presently-running task’s context information and restores the context information of the next task on queue. These “saves” and “restores” often involve many of the CPU’s status and working registers, along with the stack and code execution pointers. All of this saved context information uses RAM.
The RTOS also requires complex methods for intertask communication, because any task can be abruptly interrupted and another scheduled.The need for mutual exclusions and semaphores arises, as RTOSs schedule asynchronous executions of tasks that access common resources. To solve these issues, the RTOS implements complex messaging and mutual-exclusion strategies.This uses precious RAM, Flash memory and CPU throughput.
While a sufficiently complex system might require all these strategies, in most low-cost systems running on 8- and 16-bit microcontrollers, multitasking can be achieved with minimal overhead.
State Machine: A Different Approach to Multitasking
A state machine is a logical collection of state handlers that transition from one state to another, depending upon the current state and transitional criteria.A state machine can be implemented in software as a function that transitions through different sections of code when called repeatedly.The transitions depend upon various factors, as designed into the system. A state machine is commonly implemented in the C programming language, using a “switch” statement. Each state is assigned a state number, and the state variable determines which portion of the state machine is executed.
Figure 1 below shows two simple C-language functions. The first is a function that services various FM radio user inputs.The input-capturing function, lets say Read_Buttons() , assigns one of the five states to the state variable “FmState ” based upon user input. The function “Service_FMRadio_Inputs() ” is repeatedly called, along with Read_Buttons() , in an infinite loop.Depending upon the activity set by the user input, the small segment of code within the state machine executes, and the desired system behavior is achieved.
Figure 1: Typical state machines.The machine on the left relies on an external input for state changes. The machine on the right steps through its states, once pushed from an idle state. ( To view larger image, click here )
The second function I2CCommStatemachine() is an I2C EEPROM driver that moves through different states.On each invocation of the function, a small portion of the EEPROM write procedure is performed.The state variable is then set to the next step, and control goes back to the calling function.We can see that an EEPROM write is broken into four steps and requires four calls to the function, to complete the EEPROM write.
Thus, a given functionality can be broken down into smaller logical units, that can be executed in a very short time.By creating multiple state machines and interweaving the execution of these states with each other, multitasking is achieved.
State Machine-Based Multitasking Fundamentals
Let us look at the fundamental concepts of this state machine-based multitasking method.
1) Each task is split into small subtasks, or states, that can be completed within a short amount of time. This time interval is typically a couple of milliseconds, at the most.
2) The responsibility of saving and restoring the context of the task lies with the task, itself.This is achieved by the state machine and state variables.Control is voluntarily relinquished by the tasks from a predetermined execution point. Hence, RAM or CPU registers are not copied.
3) Each task performs a small portion of its job and relinquishes control back to the scheduler.The system is built by many such tasks/functions, which are called repeatedly. On each invocation, the task services the current state and determines the next state, if a state change is required.The task then updates the variables accordingly, and relinquishes control back to its caller. It is quite possible for a state machine to call another state machine, internally. As long as the hierarchy of calls is completed within the predetermined time, the system will work.
4) This interleaved execution of different states of multiple tasks appears like simultaneous execution of all the state machines.Thus, multitasking is achieved.
Let us consider a very simple two-task system, e.g. FMPlayerTask and EEPROMWriteTask.Let us assume that this FM player stores preset channels in EEPROM. Let the EEPROM-write task be split into four states that need to run sequentially, as in Figure 1.The FMPlayerTask has two functions in it, a simple button press reader Read_Buttons() and Service_FMRadio_Inputs (), as shown. Service_FMRadio_Inputs () has five states that occur randomly based upon user input.
When these two state machines run together in an infinite loop, we see the behavior shown in Figure 2 below. The FM player task is ready for inputs even before EEPROM writes are completed, appearing to multitask the FM-tuning and EEPROM writes.
The scheduler is an infinite loop that repeatedly sifts through all the tasks and executes the tasks that are scheduled for the current iteration (more on this in the scheduler sections of this article series).
Simple language constructs are used as much as possible, to keep overhead to a minimum.
Figure 2: CPU Timeline of a Simple Multitasking System
Scheduling will discussed in detail in a later part of this article series.For the sake of this first article, let’s look at a simple scheme of scheduling that is sufficient for our FM player system. The simplest form of scheduling your tasks is the infinite loop, as shown below, in a C-language implementation. As shown below all the tasks are called in the correct order of execution. Once we are at the end of the list, we move back to the top.
Of course, this system has no rigid periodicity for task execution and may not be suited for complex systems where timing is critical. However, its simplicity also brings with it extremely low overhead and low resource usage. There are many low-cost systems out there that do not need a more complex scheduling method, as long as the state machines are built correctly.
Though the example presented here is simple and seems straight forward, this method is sufficient for implementing simple low-cost multitasking systems that do not have rigid timing constraints and do not have many sub systems. When we move to a sophisticated system that has multiple subsystems and rigid timing requirements we need to be more meticulous in planning and designing our tasks.
As Senior Applications Engineer for Microchip Technology’ s Advanced Microcontroller Architecture Division, Ganesh Krishna is group leader for Microchip’s graphics product portfolio, including display drivers, graphics and display libraries, manages peripheral libraries for PIC18 and PIC24F microcontrollers, and develops reference designs and performs benchmarking.Ganesh earned his Bachelor of Engineering Degree in Electronics and communication from Sri Jayachamarajendra College of Engineering, belonging to Vishveshwaraiah Technological University (VTU).