CHAPTER 18. Multi-tasking and the real-time operating system
Almost every embedded system has more than one activity that it needs to perform. A program for the Derbot AGV, for example, may need to sense its environment through bump and light sensors, measure the distance it has moved, and hence calculate and implement drive values for its motors. As a system becomes more complicated, it becomes increasingly difficult to balance the needs of the different things it does. Each will compete for CPU time and may therefore cause delays in other areas of the system. The program needs a way of dividing its time ‘fairly’ between the different demands laid upon it.
An important parallel aspect of the need to time-share the CPU is the need to ensure that things are happening in time. This is very important in almost every embedded system, and the problem just gets worse when there are multiple activities competing for CPU attention.
This chapter explores the demands of systems which have many things on their minds. It investigates the underlying challenges and comes up with a strategy for dealing with them – the real-time operating system. This leads to a completely new approach to programming – it's no longer the program sequence which determines what happens next, but the operating system that is controlling it!
Once you have worked through the chapter, you should have a good understanding of:
• The challenges posed by multi-tasking.
• The meaning and implication of ‘real time’.
• How simple multi-tasking can be achieved through sequential programming.
• The principles of the real-time operating system.
As this chapter forms a broad introduction to real-time programming, there are no actual program examples in it. However, the chapter acts as preparation for Chapter 19, which has a number of significant examples.
18.1. The main ideas – the challenges of multi-tasking and real time
Many of us in this busy modern world feel we spend our lives multi-tasking. A parent may need to get two or three children ready for school – one has lost a sock, one feels sick and the other has spilt the milk. And the dog needs feeding, the saucepan is boiling over, the mailman is at the door and the phone is ringing. Many things need to be done, but we can only do one thing at a time. The microcontroller in an embedded system can feel similarly harassed. It can be surrounded by many things, each demanding its attention. It will need to decide what to do first and what can be left till later.
Let us start this chapter by exploring the nature both of multi-tasking and of real time.
18.1.1. Multi-tasking – tasks, priorities and deadlines
Figure 18.1 shows a simplified flow diagram of a program we were looking at in Chapter 16, the Derbot light-seeking program. This program was used at the time primarily to introduce certain concepts in C, and we did not spend much time thinking about its structure.
The program is made up of a number of distinct activities, each of which appears in the figure. Let us immediately adopt the practice of calling such activities ‘tasks’. A task is a program strand or section which has a clear and distinct purpose and outcome. Multi-tasking simply describes a situation where there are many tasks which need to be performed, ideally simultaneously. Four tasks are identified in this example.
The program is structured so that each task is placed in a super loop and each is executed in turn. One task, the display (where data is sent to the hand controller for display on the LCD), executes only once every 10 cycles of the loop. The loop is ended by a delay, which determines the loop repetition rate and hence influences the program timing characteristics.
This is a very simple multi-tasking example. The program has a number of tasks. It performs them strictly in rotation, taking a little rest before it starts over again.
In reality, of course, the tasks are not all of equal importance. Going back to the harassed parent: if the phone rings, the dog probably has to wait for its dinner. Therefore, we recognise that different tasks have different priorities. A high-priority task should have the right to execute before a low-priority task. Each task also has a deadline, or could have one estimated for it. The phone has to be answered within 30 seconds, otherwise the caller rings off; the children have to be ready to leave home by 8.30 a.m., otherwise they miss the bus, and so on. The concept of priorities is linked to that of deadlines. Generally, a task with a tight deadline requires a high priority – but more of that later.
The tasks of this example program are shown in Table 18.1, together with some preliminary classification. Three levels of priority are used, with three estimated deadlines. In assigning these priorities, a microswitch being pressed is viewed as an emergency; the AGV has collided with something and the motor has probably stalled. It is therefore of high priority. In contrast, the human user will barely notice if the display function is delayed by a second or so. It can therefore be of lower priority.
|Respond to microswitches||1||20|
|Calculate and set motor speed||2||50|
18.1.2. So what is ‘real time’?
How does the Derbot light-seeking program, or indeed the harassed parent, relate to the concept of ‘real time’? The concept is widely talked about, but seems often to be surrounded by a certain mystique.
A simple but completely effective definition of operating in real time, already adopted in Ref. 1.1, is as follows:
A system operating in real time must be able to provide the correct results at the required time deadlines.
Notice that this definition carries no implication that working in real time implies high speed, although this can often help. It simply states that what is needed must be ready at the time it is needed. Therefore, if the parent gets all the children to school on time, feeds the dog before it starts to howl, opens the door to the postman before he goes away and answers the phone before the caller hangs up, then the real-time requirements of this environment have been met. Similarly, if the Derbot meets all deadlines quantified in Table 18.1, it too is operating in real time.
Underlying this simple definition, and all it implies, lies a multitude of program design challenges. The rest of this chapter forms an introduction to these, and to how they can be resolved.
18.2. Achieving multi-tasking with sequential programming
The type of programming we have engaged in to date, whether in Assembler or C, is sometimes called ‘sequential programming’. This simply implies that the program executes in the normal way, each instruction or statement following the one before, unless program branches, or subroutine or function calls, take place. Later in this chapter we will make a departure from this type of program. For now, let us explore how we can optimise it for multi-tasking applications, addressing some of the weaknesses of the program structure of Figure 18.1.
18.2.1. Evaluating the super loop
This program appears to run quite well, but that is mainly because it is not very demanding in its needs. Let us consider some of its drawbacks, all related to each other:
• Loop execution time is not constant. The time it takes to run through the loop once is equal to the sum of the times taken by each task, plus the delay time. Clearly, this could vary. If, for example, a microswitch is activated, the Derbot reverses and then turns. This results in a particularly long loop execution, which may upset some other activity in the loop.
• Tasks interfere with each other. Once a task gets the chance to execute, it will keep the CPU busy until it has completed what it needs to do. Agreed, each is written so that it shouldn't take too long. Suppose, however, that the display task starts to execute and the AGV suddenly hits a wall. The processor will continue sending data to the display and will then complete the delay routine before it finds out that an emergency has occurred.
• High-priority tasks don't get the attention they need. We have already recognised that some tasks are more important than others. They should therefore have higher priority, a concept we have already met in the context of interrupts. In this continuous loop structure, every task has the same priority.
We need to find a way of structuring programs to recognise the nature and needs of the tasks they contain, and to meet their real-time demands.
18.2.2. Time-triggered and event-triggered tasks
It is easy to recognise that some tasks are ‘time-triggered’ and others ‘event-triggered’. A time-triggered task occurs on completion of a certain period and is usually periodic. An example of this is the reading of the LDRs in this program. Event-triggered tasks occur when a certain event takes place. In this case the pressing of a microswitch is a good example.
18.2.3. Using interrupts for prioritisation – the foreground/background structure
To address the problem of lack of prioritisation among the tasks in the light-seeking program, it would be possible to transfer high-priority task(s) to interrupts. These would then gain CPU attention as soon as it was needed, particularly if only one interrupt was used. The program structure would then appear as in Figure 18.2. It is quite likely that tasks in the loop would be time-triggered, and would therefore be able to use the repetition rate of the loop as a time base. Tasks driven by interrupts are likely to be event-triggered.
With this simple program structure we have achieved a reliable repetition rate for tasks in the loop, and prioritisation for tasks that need it. This is sometimes called a ‘foreground/background program structure’. Tasks with higher priority and driven by interrupts are in the foreground (when they need to be), while the lower-priority tasks in the loop can run almost continuously in the background.
18.2.4. Introducing a ‘clock tick’ to synchronise program activity
To minimise the impact of the variable task execution times on the overall loop execution time, it is possible to trigger the whole loop from a timed interrupt, say from a timer overflow. The program would then have the structure of Figure 18.3. The main loop is now triggered by a timer overflow, so occurs at a fixed and reliable rate. Time-triggered tasks can base their own activity on this repetition rate. Event-triggered tasks, through the interrupts, can occur when needed. Task timings, of course, have to be calculated and controlled, so that the loop has adequate time to execute within the time allowed and the event-triggered tasks do not disturb too much the repetitive nature of the loop timing.
The idea of a regular timer interrupt used in this way to synchronise program activity was introduced in Chapter 9 and illustrated in Figure 9.3. As mentioned there, it is usually called a ‘clock tick’. The idea is simple, but it becomes fundamental to many program structures we are about to consider. The clock tick should not be confused with the clock oscillator itself, even though the tick is usually derived from the oscillator.
18.2.5. A general-purpose ‘operating system’
The structure which emerges in Figure 18.3 can be abstracted into a general-purpose ‘operating system’, as shown to the right in Figure 18.4. Here the main loop contains a series of low- or medium-priority tasks. It is driven by a ‘clock tick’. The general structure of each task is shown on the left. As needed, each task has an enable flag (a bit in a memory location) and each has a task counter. Tasks which need to execute every clock tick will do so. Many will only need to execute less frequently, at an interval set by the value of their task counter. Tasks can be enabled or disabled by the setting or clearing of their enable flag, by each other or by the ISRs.
This general-purpose operating system structure can be adapted to form the framework of a multi-tasking program. Its general concepts are applied in practical designs in 18.1. and 18.2.. The former describes the complete design of a multi-tasking metronome based on the PIC 16F84.
If several tasks are allocated to interrupts, then interrupt latency obviously suffers, as one ISR has to wait for another to complete. This must be analysed carefully in a very time-sensitive system. Reference 1.1 explores this topic in some depth.
18.2.6. The limits of sequential programming when multi-tasking
The approach to programming for multi-tasking just described will generally be acceptable, as long as:
• There are not too many tasks.
• Task priorities can be accommodated in the structure.
• Tasks are moderately well behaved, for example their requirement for CPU time is always reasonable and interrupt-driven tasks don't occur too often.
If these conditions are not met, it is necessary to consider a radically different programming strategy. The natural candidate is the real-time operating system.
18.3. The real-time operating system
When using a true operating system, we move away from the assumptions of normal sequential programming, as outlined in Section 18.2 above. Instead, we hand over control of the CPU and all system resources to the operating system. It is the operating system which now determines which section of the program is to run and for how long, and how it accesses system resources. The application program itself is subservient to the operating system and is written in a way that recognises the requirements of the operating system. Because we are concerned to meet real-time needs, we make use of a particular type of operating system which meets this requirement, the ‘real-time operating system’ (RTOS).
A program written for an RTOS is structured into tasks, usually (but not always) prioritised, which are controlled by the operating system. The RTOS performs three main functions:
• It decides which task should run and for how long.
• It provides communication and synchronisation between tasks.
• It controls the use of resources shared between the tasks, for example memory and hardware peripherals.
An RTOS itself is a general-purpose program utility. It is adapted for a particular application by writing tasks for it and by customising it in other ways. While you can write your own RTOS, it is generally done by specialists. There are a number of companies which develop and supply such operating systems, usually targeted towards one particular type of market and scale of processor. If you buy one of these, then you are buying a ‘COTS RTOS’ – a commercial off-the-shelf real-time operating system! We explore using such an RTOS in Chapter 19.
18.4. Scheduling and the scheduler
A central part of the RTOS is the ‘scheduler’. This determines which task is allowed to run at any particular moment. Among other things, the scheduler must be aware of what tasks are ready to run and their priorities (if any). There are a number of fundamentally different scheduling strategies, which we consider now.
18.4.1. Cyclic scheduling
Cyclic scheduling is simple. Each task is allowed to run to completion before it hands over to the next. A task cannot be discontinued as it runs. This is almost like the super loop operation we saw earlier in this chapter.
A diagrammatic example of cyclic scheduling is shown in Figure 18.5. Here the horizontal band represents CPU activity and the numbered blocks the tasks as they execute. Tasks are seen executing in turn, with Task 3 initially the longest and 2 the shortest. In the third iteration, however, Task 1 takes longer and the overall loop time is longer. Cyclic scheduling carries the disadvantages of sequential programming in a loop, as outlined above. At least it is simple.
18.4.2. Round-robin scheduling and context switching
In round-robin scheduling the operating system is driven by a regular interrupt (the ‘clock tick’). Tasks are selected in a fixed sequence for execution. On each clock tick, the current task is discontinued and the next is allowed to start execution. All tasks are treated as being of equal importance and wait in turn for their slot of CPU time. Tasks are not allowed to run to completion, but are ‘pre-empted’, i.e. their execution is discontinued mid-flight. This is an example of a ‘pre-emptive’ scheduler.
The implications of this pre-emptive task switching, and its overheads, are not insignificant and must be taken into account. When the task is allowed to run again, it must be able to pick up operation seamlessly, with no side-effect from the pre-emption. Therefore, complete context saving (all flags, registers and other memory locations) must be undertaken as the task switches. Time-critical program elements should not be interrupted, however, and this requirement will need to be written into the program.
A diagrammatic example of round-robin scheduling is shown in Figure 18.6. The numbered blocks once more represent the tasks as they execute, but there is a major difference from Figure 18.5. Now each task gets a slot of CPU time, which has a fixed length. The clock tick, which causes this task switch, is represented in the diagram by an arrow. When that time is up, the next task takes over, whether the current one has completed or not. At one stage Task 2 completes and does not need CPU time for several time slices. It then becomes ready for action again and takes its turn in the cycle.
18.4.3. Task states
It is worth pausing at this moment to consider what is happening to the tasks now they are being controlled by a scheduler. Clearly, only one task is running at any one time. Others may need to run, but at any one instant do not have the chance. Others may just need to respond to a particular set of circumstances and hence only be active at certain times during program execution.
It is important, therefore, to recognise that tasks can move between different states. A possible state diagram for this is shown in Figure 18.7. The states are described below. Note, however, that the terminology used and the way the state is affected vary to some extent from one RTOS to another. Therefore, in some cases several terms are used to describe a certain state.
• Ready (or eligible). The task is ready to run and will do so as soon as it is allocated CPU time. The task leaves this state and enters the active state when it is started by the scheduler.
• Running. The task has been allocated CPU time and is executing. A number of things can cause the task to leave this state. Maybe it simply completes and no longer needs CPU time. Alternatively, the scheduler may pre-empt it, so that another task can run. Finally, it may enter a blocked or waiting state for one of the reasons described below.
• Blocked/waiting/delayed. This state represents a task which is ready to run but for one reason or another is not allowed to. There are a number of distinct reasons why this may be the case, and indeed this single state on the diagram could be replaced by several, if greater detail was wanted. The task could be waiting for some data to arrive or for a resource that it needs that is currently being used by another task, or it could be waiting for a period to be up. The state is left when the task is released from the condition which is holding it there.
• Stopped/suspended/dormant. The task does not at present need CPU time. A task leaves this state and enters the ready state when it is activated again, for whatever reason.
• Uninitialised/destroyed. In this state the task no longer exists as far as the RTOS is concerned. An implication of this is that a task does not need to have continuous existence throughout the course of program execution. Generally, they have to be created or initialised in the program before they can run. If necessary they can later be destroyed and possibly another created instead. Removing unneeded tasks from the task list simplifies scheduler operation and reduces demands on memory.
18.4.4. Prioritised pre-emptive scheduling
We return now to our survey of scheduling strategies, armed with a greater understanding of the lifestyle of tasks. In round-robin scheduling tasks become subservient to a higher power – the operating system – as we have seen. Yet all tasks are of equal priority, so an unimportant task gets just as much access to the CPU as one of tip-top priority. We can change this by prioritising tasks.
In the ‘prioritised pre-emptive scheduler’, tasks are given priorities. High-priority tasks are now allowed to complete before any time whatsoever is given to tasks of lower priority. The scheduler is still run by a clock tick. On every tick it checks which ready task has the highest priority. Whichever that is gets access to the CPU. An executing task which still needs CPU time and is highest priority keeps the CPU. A low-priority task which is executing is replaced by one of higher priority, if it has become ready. The high-priority task becomes the ‘bully in the playground’. In almost every case it gets its way.
The way this scheduling strategy works is illustrated in the example of Figure 18.8. This contains a number of the key concepts of the RTOS and is worth understanding well. The diagram shows three tasks, each of different priority and different execution duration. At the beginning, all are ready to run. Because Task 1 has the highest priority, the scheduler selects it to run. At the next clock tick, the scheduler recognises that Task 1 still needs to run, so it is allowed to continue. The same happens at the next clock tick and the task completes during the following time slice. Task 1 does not now need CPU time and becomes suspended. At the next clock tick the scheduler therefore selects the ready task which has the highest priority, which is now Task 3. This also runs to completion.
At last Task 2 gets a chance to run! Unfortunately for it, however, during its first time slice Task 1 becomes ready again. At the next clock tick the scheduler therefore selects Task 1 to run again. Once more, this is allowed to run to completion. When it has, and only because no other task is ready, Task 2 can re-enter the arena and finally complete. Following this, for one time slice, there is no active task and hence no CPU activity. Task 1 then becomes ready one more time and starts to run again to completion.
18.4.5. Cooperative scheduling
The scheduling strategy just discussed, prioritised pre-emptive scheduling, represents classic RTOS action. It is not without disadvantage, however. The scheduler must hold all context information for all tasks that it pre-empts. This is generally done in one stack per task and is memory-intensive. The context switching can also be time-consuming. Moreover, tasks must be written in such a way that they can be switched at any time during their operation.
An alternative to pre-emptive scheduling is ‘cooperative’ scheduling. Now each task must relinquish, of its own accord, its CPU access at some time in its operation. This sounds like we're blocking out the operating system, but if each task is written correctly this need not be. The advantage is that the task relinquishes control at a moment of its choosing, so it can control its context saving and the central overhead is not required.
Cooperative scheduling is unlikely to be quite as responsive to tight deadlines as pre-emptive scheduling. It does, however, need less memory and can switch tasks quicker. This is very important in the small system, such as one based on a PIC microcontroller.
18.4.6. The role of interrupts in scheduling
So far, we have not mentioned interrupts in connection with the RTOS. Should ISRs themselves form tasks, as was done in structures like that of Figure 18.4? The answer is no. The first use of interrupts is almost always to provide the clock tick, through a timer interrupt on overflow. Beyond this, ISRs are usually used to supply urgent information to the tasks or scheduler. The interrupt could, for example, be set to signal that a certain event has occurred, thereby releasing a task from a blocked state (Figure 18.7). The ISRs themselves are not normally used as tasks.
18.5. Developing tasks
Having established the concept of tasks and how they are scheduled, let us now consider how they are written.
18.5.1. Defining tasks
It is an interesting early requirement of the programmer to actually choose which activities of the system will be defined as tasks. The number of tasks created should not be too many. More tasks generally imply more programming complexity, and for every task switch there is a time and memory overhead.
A useful starting point is to consider what the deadlines are and then to allocate one task per deadline. A set of activities which are closely related in time are likely to serve a single deadline and should therefore be grouped together into a single task. A set of activities which are closely related in function and interchange a large amount of data should also be grouped into a single task.
For example, in the Derbot light-seeking program of Figure 18.1, the super loop at one stage reads the three LDRs, then makes some calculations, then sets the motor speed. It also periodically sends data to the display. At any time, the microswitches may be activated. How many RTOS tasks should there be? The central activities are closely related in time and in function, and do share data. Writing to the display could be set as a distinct task – it occurs less often than the others and is of comparatively low priority. As the reading of the LDRs supplies data directly to the motor calculations and the motor control, all these activities could be grouped into a single task. Alternatively, the LDR reading could be separated into its own task. Finally, the microswitch response could be allocated as a further task.
18.5.2. Writing tasks and setting priority
Tasks should be written as if they are to run continuously, as self-contained and semi-autonomous programs, even though they may be discontinued by the scheduler. They cannot call on a section of another's code, but can access common code, for example C libraries. They may depend on services provided by each other and may need to be synchronised with each other. In either case, the RTOS will have special services to allow this to happen.
In all cases but the most simple, the RTOS allows the programmer to set task priorities. In the case of ‘static’ priority, priorities are fixed. In the case of ‘dynamic’ priority, priorities may be changed as the program runs. One way of looking at priority is to consider how important a task is to the operation and well-being of the system, its user and environment. Priority can then be allocated:
• Highest priority: tasks essential for system survival.
• Middle priority: tasks essential for correct system operation.
• Low priority: tasks needed for adequate system operation – these tasks might occasionally be expendable or a delay in their completion might be acceptable.
Priorities can also be considered by evaluating the task deadlines. In this case high priority is given to tasks which have very tight time deadlines. If, however, a task has a demanding deadline, but just isn't very important in the overall scheme of things, then it may still end up with a low priority.
18.6. Data and resource protection – the semaphore
Several tasks may need to access the same item of shared resource. This could be hardware (including memory or peripheral) or a common software module. This requires some care. A method for dealing with this is by the ‘semaphore’. A semaphore is allocated to each shared resource, which is used to indicate if it is in use.
In a ‘binary semaphore’, the first task needing to use the resource will find the semaphore in a GO state and will change it to WAIT before starting to use the resource. Any other task in the meantime needing to use the resource will have to enter the blocked state (Figure 18.7). When the first task has completed accessing the resource, it changes the semaphore back to GO. This leads to the concept of ‘mutual exclusion’; when one task is accessing the resource, all others are excluded.
The ‘counting semaphore’ is used for a set of identical resources, for example a group of printers. Now the semaphore is initially set to the number of units of resource. As any task uses one of the units, it decrements the semaphore by one, incrementing it again on completion of use. Thus, the counting semaphore holds the number of units that are available for use.
As an effect of setting a semaphore to the WAIT state is that another task becomes blocked, they can be used as a means of providing time synchronisation and signalling between different tasks. One task can block another by setting a semaphore and can release it at a time of its choosing by clearing the semaphore.
Remember the ‘bully in the playground’, the high-priority task mentioned in Section 18.4.4? By using a semaphore, a low-priority task can turn the tables on the bully! If a low-priority task sets a semaphore for a resource that the high-priority task needs, it can block that task. This leads to a dangerous condition known as ‘priority inversion’. This is beyond the scope of this book, but is also illustrative of the many finer details in the world of real-time programming, which are well worth further exploration. Reference 18.3 is a useful starting point for more detailed reading.
18.7. Where do we go from here?
The theory of the RTOS goes well beyond what has been discussed in this chapter and becomes specialised to different types of application. As with so many things, the theory takes on meaning when applied to a real situation. This is what happens in the chapter that follows.
• The requirement of multi-tasking, common to almost every embedded system, carries with it some valuable concepts – tasks, deadlines and priorities.
• A system operating in real time is one that is able to meet its deadlines.
• Simple multi-tasking real-time systems can be achieved using conventional sequential programming.
• More sophisticated multi-tasking real-time systems require the use of a real-time operating system.
• Use of a real-time operating system requires that programs are structured in a different way, with the programmer clearly understanding the underlying principles of the operating system.
18.1. Wilmshurst, T., Exploring real-time programming, Electronics World (2002) 54–60; January http://www.softcopy.co.uk/electronicsworld/.
18.2. A Real-Time Operating System for PICmicro Microcontrollers. (1997) Microchip Technology Inc ; Application Note 585.
18.3. Simon, D.E., An Embedded Software Primer. (1997) Addison-Wesley ; ISBN 978-0-201-61569-2.