A general-purpose job scheduler using a single 8-bit MCU timer in C

[groovy9]

Here's my contribution to the software forum.  I just finished up some nifty job scheduling code that's running nicely on my Atmel ATtiny461 MCU, but should work fine for any MCU with minimal mods.

The design goals were:

1) interrupt-based firing of arbitrary functions (jobs) from 1ms to several seconds in the future
2) minimal memory usage (so no function pointers, dynamic memory allocation, etc)
3) non-blocking - no delay_ms() or other blocking waits
4) efficient timer interrupt routine
5) efficient main loop code
6) must be able to schedule the same job to run at multiple points in the future

It uses about 4 bytes of memory per job slot plus 4 bytes of overhead.  The example below uses 68 bytes total.

It's written in C on the Codevision AVR compiler.  I'm lazy and use // comments, rather than /* ... */, so if you have a strict ansi compiler, it might complain. 
Any critiques or suggestions for improvement are welcome!  Here it is:

Code: [Select]

#define u8 unsigned char
#define u16 unsigned int

/////////////////////////////////////////////////////////////////////////////
//                        set up job scheduler                             //
//                                                                         //
//  assumes a timer has to configured to interrupt every 1 ms              //
/////////////////////////////////////////////////////////////////////////////
#define MAX_JOBS 16   // valid range is 1 to 254
volatile struct { // linked list of scheduled jobs in the form of a static array
u8 id; u8 next; u16 time;
} jobs[MAX_JOBS];
volatile u8 nextjob; // next job to be run (chronologically) 
volatile u8 lastjob;          // last job to be run (chronologically)
volatile u16 jobtimer; // increments on each timer interrupt, auto-wraps to 0
void initjobs(void); // run once before scheduling any jobs
void runjobs(void); // runs over and over in main loop
void runjob(u8 id); // called by runjobs based on bits set in 'runnable' */
void schedule(u8 id, u16 time); // schedule a job to run 'time' ms from now
// specific job functions - can have up to 255 of them.  unfortunately, they
// don't currently accept any arguments.  should be easy to add.
void toggle_led1(void); #define TOGGLE_LED1 1
void toggle_led2(void); #define TOGGLE_LED2 2 
void toggle_led3(void); #define TOGGLE_LED3 3 
///////////////////////////////////////////////////////////////////////////////

// Codevision-specific code for the AVR's "timer0 compare A match" interrupt
// set up your MCU similarly to interrupt every 1 ms and simply increment jobtimer on interrupt
interrupt [TIM0_COMPA] void timer0_compa_isr(void) {  jobtimer++; }


// an example main function that flashes LED1 for 250ms every second and
// LED2 for 500ms every 2 seconds and LED3 for 100ms every half second
void main(void) {       
        initjobs();

        // MCU pin configuration omitted for brevity
                 
        // schedule the first "blink" of each LED.
        // they'll then reschedule themselves as needed.       
        schedule(TOGGLE_LED1, 100); schedule(TOGGLE_LED1, 350);   
        schedule(TOGGLE_LED2, 100); schedule(TOGGLE_LED2, 600);
        schedule(TOGGLE_LED3, 100); schedule(TOGGLE_LED3, 200);
       
        while (1) { runjobs(); }                 
}                   

void toggle_led1(void) {
        PORTA.1 = ~PORTA.1;   // codevision-specific for my MCU and schematic
       
        // main function scheduled the initial led-on and led-off, resulting in a blink.
        // we reschedule ourselves every second to blink every second 
        schedule(TOGGLE_LED1, 1000);
       
}

void toggle_led2(void) {
        PORTA.2 = ~PORTA.2;
        schedule(TOGGLE_LED2, 2000);
}

void toggle_led3(void) {
        PORTA.3 = ~PORTA.3;
        schedule(TOGGLE_LED3, 500);
}                     

// initialize the job scheduler
void initjobs(void) {
u8 i;
for(i = 0; i < MAX_JOBS; i++) {
jobs[i].id=0;
jobs[i].time=0;
jobs[i].next=i;
}
nextjob = 0;
lastjob=0;     
}

// run every job due to run right now
void runjobs() {
u8 newnext;

while(jobs[nextjob].id && jobs[nextjob].time == jobtimer) {
runjob(jobs[nextjob].id);
newnext = jobs[nextjob].next;
jobs[nextjob].id = 0;
jobs[nextjob].time = 0;
jobs[nextjob].next = nextjob;
nextjob = newnext;
}
}

// run a specific job -- called by runjobs
void runjob(u8 id) {
switch(id) {
case TOGGLE_LED1: toggle_led1(); break;
case TOGGLE_LED2: toggle_led2(); break;
                case TOGGLE_LED3: toggle_led3(); break;
}
}     

// schedule a job to be run 'time' ms from now
void schedule(u8 id, u16 time) {
        u8 i;
u8 freejob = 255;
u8 prev = 255;             

/* find a free job slot.  start with nextjob and work backwards, since
   empty slots are most likely to be found there.  This also
   automatically handles the special case of an empty job list  */
i = nextjob;
for(i = nextjob; i != (u8)(nextjob + 1) % MAX_JOBS; i = (u8)(i - 1) % MAX_JOBS) {
if(! jobs[i].id) {
freejob = i;
break;
}
}                                                             

if(freejob >= MAX_JOBS) /* job list full. new job is lost. */
return;         

/* figure out where in the job list it will fit */
/* start with lastjob, since new jobs will generally be the last job */
if(jobs[lastjob].id && jobs[lastjob].time <= time + jobtimer)
prev = lastjob;
else { /* ok, then search from the beginning */
for(i = nextjob; jobs[i].id; i = jobs[i].next) {   
    // ugly expression figures out if new job happens before or after jobs[i]
if((jobs[i].time - jobtimer + 65536 * (jobtimer > jobs[i].time)) <= time)
prev = i;                   
else
    break;
if(jobs[i].next == i)
break;
}
}

/* fill in freejob slot with new job info  */
jobs[freejob].id = id;
jobs[freejob].time = jobtimer + time;
jobs[freejob].next = freejob;       

/* update next pointers */
if(prev < 255) { /* new job is not the next job */
if(jobs[prev].next != prev)
jobs[freejob].next = jobs[prev].next;
else
lastjob = freejob; /* new job is the last job */
jobs[prev].next = freejob;
} else { /* new job is the next job */
if(jobs[nextjob].id)
jobs[freejob].next = nextjob;
else
lastjob = freejob; /* new job is the only job */
nextjob = freejob;
}
}

[Admin]

im kinda confused . . .

so i think this is what it does: you command the mcu to do action A, and give it a set time T for it to do it. when this happens, it sets a timer interrupt for T and starts doing action A. when T time has passed, the interrupt is called, stoping action A.

this is useful if i am running some processor intensive application, and didnt want to do 1.4ms delays to run servos. it sets a pin high, then processor goes back to doing its own thing until time T, then sets that pin low again during the interrupt.

but i dont quite understand why there is a list of actions . . . is it just doing one action at a time until time T, then doing the next one? or can it handle all simultaneously? that would be very useful if say i had like 20 servos . . .

also, what does 'volatile' mean?

im a mechanical engineer, software is my weakspot

[groovy9]

All it does is let you schedule a function to run X milliseconds in the future.  Period.  You can have up to 16 functions in the queue at once.  A function can, if you desire, reschedule itself.  Or func A can schedule B, which can schedule C, etc.

In the LED example code, I schedule an LED toggle at time T and another at T + 250ms, then enter the while() loop. The LED toggle function reschedules itself to run again in 1 second.  End result:  250ms blinks every second. 

Say you want to blink an LED at various rates for debugging, and poll a sensor every 5 ms and poll another sensor every 2 seconds and spin in a random direction every 2 minutes and...

Unless you have 8 different hardware timers to take advantage of, you either need a job scheduler or you'll wind up with 8 state variables and a bunch of conditional code in your main loop.  This makes precise event timing easy.

[groovy9]

but i dont quite understand why there is a list of actions . . . is it just doing one action at a time until time T, then doing the next one? or can it handle all simultaneously? that would be very useful if say i had like 20 servos . . .

also, what does 'volatile' mean?

Forgot to answer all your questions... You can schedule up to 16 actions to happen at varying times in the future.  You can have one event at a time, every 100ms for 1.6 seconds, for example.  Or you can have 16 things all happen one second from now.  So yeah, you could use it to control a bunch of different servos all going different speeds.  By changing MAX_JOBS, you can handle as many jobs as you need and have the memory for.  With enough memory, you could program 20 servos (all at once, such as above the while() loop in main()) to each do a different sequence of actions spanning up to 65 seconds (it's a 16 bit counter.  2^16 milliseconds is a bit over a minute).

Volatile, at least for my compiler, means that a global variable can change while it's being accessed.  i.e.  if your main loop reads jobtimer, jobtimer could be incremented by the interrupt during the read.  volatile tells the compiler to "do the right thing" in that case.

im a mechanical engineer, software is my weakspot

I'm a programmer geek.  Hardware is my weak spot

[Hal9000]

Isn't this just a scheduler, then?

[groovy9]

Isn't this just a scheduler, then?

Not in the traditional operating system process scheduler sense.  It's not a step toward an RTOS.  It's just a simple way to use one timer to handle multiple timed events on different schedules. 

By changing the resolution from 1ms to something like 10us, you could probably even use it to implement things like SPI and I2C in software.  My MCU doesn't have a UART, so I plan to take a crack at a software UART using a modified version of this.