Scheduler:Traffic Light With Walk

Since the scheduler example for a traffic light of a week or two ago had nothing to do in the background, this next example uses the idle time to watch for a button push. The program is Figure 13.5, flowcharted in Figure 13.4. I add two buttons to be used by pedestrians to request a walk cycle. The scheduling of the light cycle will still happen in the real-time interrupt as before. I set up two flags (bits in walk) to keep track of anyone pushing the button (which comes in as a logic 0). By ORing the port with the variable, if the button was pushed previously, the logical OR will simply keep a 1 in that bit position. No matter how many people push the button, there will be just one walk cycle, and the bit can be cleared when the walk is actually provided. It is cleared by & ~0x02, which is a more understandable way of getting the 0xfd to clear that bit from a 1 to a 0. When a walk bit is detected, the switch expression substitutes a different pointer to give a walk instead of a normal light cycle. [This is very crude, and you would want a DON’T WALK light and perhaps a flashing period before the walk cycle ends. Also you would want to coordinate with turning cars, and so on. A true traffic light program is significantly more complicated than this.]

There are at least three options for keeping track of users pushing the walk buttons:

1. Polling in the main routine is the easiest way to recognize walk requests. This is the solution I have chosen to show here.
2. The buttons could be scanned in the scheduler interrupt itself—add another counter and once every 40th interrupt, perhaps, read the buttons. If there were much else for the processor to do, this would be the preferred solution because long background tasks (in main()) would not alter the button scanning.
3. The buttons could be tied to external interrupts. There are at least two of them, and they could be made edge-triggered so the software would interrupt whenever a button is pushed. This is a bit wasteful of hardware and has limited expansion capability—there aren’t many external interrupts. Besides, it is a waste of hardware when it can be done easily by the earlier methods.

Flowchart: Traffic Light With Walk

Traffic Light With Walk Buttons
#include<C8051F020.h>
#define uchar unsigned char
#define uint unsigned int
#define LEDS P1
#define WLKBTNS P3
uint countdown; uchar index,walk;
code struct{uint delay;uchar pattern;}cycle[]=
{{1000,0×12},{3000,0×41},{1000,0×21},
//(0)=—R,–Y-; (1)=-G–,—R; (2)=–Y-,—R;
{5000,0×14}, {3000,0xc1},{5000,0x1c}};
//(3)=—R,-G–; (4)=WG–,—R; (5)=—R,WG–;

void initialize(void){
WDTCN = 0x07; WDTCN = 0xDE;//Disable WDT WDTCN = 0xAD;
XBR2 = 0x40;//enable crossbar
P1MDOUT = 0xFF;//P3 push-pull out
OSCICN = 0x04;//enable int oscillator
countdown=1;//start at once
walk=0;//none pending
index=3;//lead to first state
TMOD=0x10;//tmr1 16-bit
TH1=~(1000/256);
TL1=-(1000%256);
TR1=1;//enable timer 1
IE=0x88;//enable timer1 int
}

void msecint (void) interrupt 3 using 1{
uchar i;
TH1=~(1000/256);TL1=-(1000%256);
if(–countdown==0){ //end of delay
++index;index%=4;i=index;
switch(index){//override for walk
case 1:if((walk&0x02)==0){
walk&=~0x02; i=4;
}
break;
case 3:if((walk&0x01)==0){
walk&=~0x01; i=5;
}
break;
}
LEDS=cycle[i].pattern;
countdown=cycle[i].delay;
}}

void main(void){
initialize();
while(1){
walk=walk | WLKBTNS;
}}

Communication by Shared Variable With the first solution I must get the value of walk to the scheduler from the main (background) program; in a formal sense you can say the two tasks communicate. In effect communication is by shared variable—walk is global and can be accessed by both the interrupt and the main program. Later chapters will go into other communication methods.

For the pattern going to the LEDs I arbitrarily chose to position the walk lights as the most significant bits of the nibbles.

Although the interrupt in this stoplight example has grown more complicated, the basic approach has not changed. The program flow never waits in the interrupt function. Rather, it moves through and returns to the main as quickly as possible.

A scheduler may seem too simple and too efficient to qualify as a multitasking operating system. You write all the code, there are no operating system commands to learn, and you can achieve full real-time performance. In one sense a scheduler just makes good use of a real-time clock. Yet the concept is so powerful it rates its own chapter [this post is from chapter13].

What is a scheduler?

Chapter 11 Hardware: Interrupts & Timers went into detail on the production of a regular interrupt—a real-time clock running tasks at specific times is a scheduler. It is an arrangement of software that calls task functions after a specific number of system ticks. Suppose you have a system tick every millisecond. You might have a keyscan task running every 40^th tick and a stepper motor pulse task being called every 10^th tick (100 steps/S). If the step rate changed, the scheduler might call the step function every 20 ticks (for a 50steps/S rate). All the activities key off counters initialized for a desired delay and then decremented every tick interval. When the counter for a specific task reaches zero, the count is reset, and the given task function is called.

Since scheduler tasks have to fit in between system ticks, you should write the code of any task to execute as quickly as possible and return. Never write while() or for(;;) loops in a task if exiting the loop depends on an outside event. Likewise, if there is a lot of processing to do, set a flag in the scheduler interrupt. Have the main function poll and detect that flag and then handle the processing in the background. Continue reading →

Getting the computer to manage several tasks seemingly simultaneously is the heart of multitasking. You can choose to write tasks separately as though nothing else ever happens—separate modules. The ideas involved are not difficult to visualize if you compare them with everyday activities, but they differ from those of normal programming. You should develop the frame of mind that says, “If it isn’t ready yet, go on. I’ll come back to it later. Right now there may be something else to do.” Tasks may be inter-related; then you will have to plan signaling between them. Once you’ve understood the ideas of this section, it will be easy to move to complicated systems involving many calls with many parameters. Realtime systems are becoming increasingly important as the dedicated microcontroller becomes more and more prevalent. Knowing the concepts, you can have a role in the implementation. Several different approaches to multitasking are described next.

Cooperative multitasking–Round Robin

If priority is not important, no special hardware is needed for a cooperative multitasking scheme where each task politely pauses at frequent points to “go to the end of the line” or “wait ‘till the next time around” and allow other tasks to get a chance to do some work. The weakness is that if some task gets added that doesn’t cooperate, there is no protection in the operating system and all the other tasks can be blocked. This might better be called “multiple tasking.” It is a round-robin system where tasks run one after the other in turn, without the idea of preemption or priority that are essential for external realtime events. Although this approach can include interrupt service routines, attention is centered on what really should be called the background tasks. In such a scheme each task waits its turn to run. If a task has nothing to do at the time, it immediately passes control to the next task, but if it has a lot to do, it can spend all the time it needs to finish. Such a system avoids the overhead of an operating system, but requires the programmer’s close attention to avoid long latency (delay in getting back around the loop to the task needing attention). You have to be sure to break big tasks into several small tasks or scatter around intermediate pauses to be sure the running task doesn’t hog the processor.

Time slice

The time slice multitasking approach addresses some of these problems. It provides protection from hogging the processor by arbitrarily switching out long-running tasks at regular intervals. With this approach, tasks usually run round-robin unless a task takes more than an allotted amount of time. At that point the task is put on the shelf and the next task in line gets to run. The first task goes to the end of the line and is allowed to continue running when its turn comes around again. There must be a timer-driven interrupt marking off time slices so control of timing is removed from the running task. This approach is good for data processing applications and was the heart of early time-shared computing systems, before the personal computer revolution. In its basic form, though, it doesn’t allow the feature of preemption needed for non-deterministic systems—ones where urgent tasks may unexpectedly or unpredictably need immediate attention.

Scheduler

A scheduler is somewhat related to a time-slice system in that it keeps track of time for the various tasks. Typically, however, there are some tasks that are short and repetitive, such as scanning external inputs or sending regular outputs. These short tasks may come frequently or only occasionally and at irregular intervals. Any left-over processor time is used for a background task, which is often a much less urgent data-processing or decision-making activity.

Priority-based, preemptive multitasking

There are a confusing number of combinations of these types of multitasking when you begin to add in priority of tasks. More urgent tasks can go to the head of the line or preempt the running task. A common combination is a priority-based, preemptive multitasking operating system where equal priority tasks run in round-robin fashion and the system switches tasks based on both timer events and external hardware events. These events may be periodic events like the ticks of a clock for a scheduler, or dynamically changing events based on inputs from outside hardware. An event is anything that might cause the system to change tasks. It could be an external interrupt, an internal signal or message sent from another task, or the expiration of a waiting period. The primary point is, events can lead to a change in which task is running.

For discussion of multitasking, we need to define a task. In its simplest form a task is any one thing to done by a controller. Think of an army with an overall mission to accomplish and many individual soldiers to carry it out. The overall mission, ”Drive out that dictator,” is the job, but the tasks might be, ”Drive this supply truck to the front lines,” or, ”Sit in this trench until ordered to advance.” For a controller, a task might be to wait for and process input from a keyboard or to keep a motor running at a set speed. A task can be as simple as a single routine having a few lines of code, or it can be an entire set of nested routines. Task divisions can be arbitrary as long as they relate to the functional parts of the overall job. Most important, tasks represent a way of thinking that logically divides the job and leads to the effective use of the microcontroller.

Priority

Should a task ‘move to the head of the line’ when other tasks have been waiting longer to run? Having different priorities in a system implies that some activities are more important or more urgent than others. We are used to degrees importance in the realm of politics and big business, and we expect to yield to fire trucks and ambulances because they have greater urgency. The same thing can be applied to individual tasks. Issuing a pulse to a stepper motor may be more urgent than the computing an average. Stepper pulses must come at regular times, whereas a computation can be done whenever time is available. The first-level processing of incoming readings is more important than subsequent processing if the new readings will be overwritten by the next readings if they aren’t processed and moved. In a realtime system the priority may be a measure of importance or urgency, or it can reflect the duration of a task–a very short task could run with higher priority because it will be over and done quickly, rather than any inherent degree of importance.

Preemption

Should a task not just move to the head of the line, but stop and replace the task that is currently running? If so, it has preempted the running task. The concept isn’t difficult but the implementation can be challenging because the preempted task could be in the middle of something that shouldn’t be interrupted and, at a minimum, the various registers must be saved so the preempted task can resume where it left off when it gets to run again.

Most courses treat multitasking as an advanced topic. I hope your perspective will change as you come to see that it is the most fundamental part of efficient programming and deserves your attention as early as possible. Once you understand it, you can have your microcontroller look like it is doing many things all at the same time—it will never seem to be unavailable and will always be checking for something to do.

Beyond single-program thinking

If you have used only traditional techniques of programming, you will find, as your applications grow more time-critical, that a single program approach becomes awkward. When you have several external hardware devices that need to be served at the same time, your challenge is to make sure each device is satisfied.

Perhaps all your software has only had one thing happens at a time…in sequence (that is why computers were called sequential machines). If a speech chip had to say something, you programmed the processor to put out the appropriate code, pulse the write line, and then wait until the phrase was done before going on to check for some new input from the keypad. Nothing could be recognized while the processor was waiting for the ‘done’ from the speech chip. To move on in your programming skills you must develop a new way of thinking about program flow…you can’t let the flow get stuck if something isn’t ready yet.

Realtime

Although the term means different things to different people, I apply realtime to any system that respond to inputs and supply outputs fast enough to meet user or external hardware requirements. For example, a keyboard entry system is realtime if it gives you some feedback quickly enough for you to feel confident that the system “heard” you. If a “beep” is fed back to you within 100mSec, you feel confident that the system recognized the input “right away.” So, a keyscan routine that repeated every 100mSec would probably meet the requirement of fast enough. Likewise, your eyes and brain cannot assimilate new digital display information more quickly than perhaps 5 times a second….numeric values that are rapidly changing might better be updated only a few times a second. On the other hand, a stepper motor ought to be sent a new step pulse at a regular time with millisecond precision, so this is a much more critical time requirement. Most serial ports have a single-character buffer, so at 9600 baud every incoming character must be picked up within about 1mSec (10 bits @9600 bits/Sec=960 char/Sec »1mSec). Outgoing (asynchronous) characters can go whenever the processor is not busy, assuming there is no other time constraint on message transfer. The same considerations would apply to collecting data via an A-D converter. Depending on how rapidly the incoming voltage is changing, the reading might need immediate retrieval or might be held for quite some time. How rapidly should a flow valve be adjusted for a process? How quickly should a motor be supplied a new speed setting? All of these are questions relating to what is fast enough.