Real-Time Scheduler Library For Arduino

2013-07-18 01:05 by Ian

Arduino has turned out to be a prolific microcontroller platform, and has spawned many clones. This article will give a brief tour of a C++ library I wrote to accurately schedule many processes on the CPU using a single timing source.

Things have changed a great deal since I last programmed for embedded controllers. My last embedded CPU was an HC12 at 8MHz. The CPU was 16-bit, and the only free manufacturer support was the assembler. Obviously, writing a program in assembly language is much more tedious than using a high-level language like C (let alone C++). So to be able to flex my C skills in such a tiny chip is a welcome development. It's also uplifting to see the creativity of the many new programmers being drawn-in by the sudden accessibility of these miniature 32-bit monsters that we call modern microcontrollers.

In my case, I am using the Teensy 3.0 which operates at 48MHz, has 128KiB of flash for program storage, 16KiB of RAM, and 2KiB of EEPROM for the program's use. The creator of the Teensy ported the Arduino tools and wrote a bootloader for the CPU. While I don't think much of the Arduino IDE, it *is* simple, and it's nice to leverage all of the support that has grown around the AVR microcontroller family. This code ought to work on any Arduino-esque microcontroller. It should also work as a stand-alone library independent of the Arduino code base. But both of these assertions are untested.

You can download the library from my Github page.


Basic concept:

As awesome as they are, the AVR micros on the market today are single core. And even though they are fast (relative to 10 years ago), their resource constraints are quite apparent when you start doing lots of I/O or floating-point arithmetic. If I were writing my program in assembly, certain tasks could be offloaded to interrupts, or DMA(!), but eventually, a pseudo-threading system will be required. The Scheduler library is that threading system.


Example usage:

Instantiating the scheduler is done like so (somewhere in your global namespace).... 

Scheduler scheduler;

uint32_t pid = scheduler.createSchedule(50, -1, false, callback_function);  // Make a schedule...
scheduler.disableSchedule(pid);  // A given schedule can be disabled this way.
scheduler.removeSchedule(pid);  // Remove a schedule. This frees memory, but the PID will no longer exist.

The code above will create a new schedule that executes callback_function(void) every 50 time-units, repeats forever, and does not auto-clear. Schedules are always enabled upon creation, so the next line disables the schedule.

The last line will cause the scheduler to disable and reap the schedule, thereby freeing the memory it occupied.

Now... the scheduler is itself inert. In order for it to do its job, we need to call it with some sort of a periodic timing source. The rate of this call will determine the time-unit. In my case, I am using a periodic interrupt set for 1ms. In that timer's ISR, I have.... 

/**
* Services the scheduler...
* Called once every millisecond.
*/
void timerCallbackScheduler() {
  scheduler.advanceScheduler();
}

IntervalTimer timer0;    // Scheduler
uint32_t timer_0_period  = 1000;    // Once every 1mS.
timer0.begin(timerCallbackScheduler, timer_0_period);

There is no reason that you couldn't re-purpose this library to be an event-based scheduler (versus a real-time scheduler) by calling advanceScheduler() from a pin interrupt, or even in your main loop. But using a timer (or an RTC) is the best way to get predictable timing and resolution.

Now the timing source has been established. The last thing required to make the library work is to put the call to the service function somewhere where idle cycles would otherwise be. And that probably means: In your main loop... 

void loop() {
  // The things in this block need to be scheduled from the periodic interrupt
  //  on timer0. These things are generally IO or CPU "heavy" and need to be interruptable.
  scheduler.serviceScheduledEvents();
}

Ideally, this would be the ONLY thing in the main loop, and all other processes would be called by the scheduler. But there is no reason the scheduler cannot cohabitate with other functionality.


Using delays and timing offsets:

There are a few functions that will allow you to forestall the initial execution of a schedule, or reset a schedule at any point... 

/* Reset the given schedule to its previously-specified period and enable it. */
delaySchedule(pid);

/* Will cause the schedule identified by PID to wait 45 seconds for its next execution. 
* If the schedule was disabled before, it will be enabled after this call. */
delaySchedule(pid, 45000);


Profiling your schedules:

It is often useful to know how long (exactly) a given function takes to execute. The Scheduler's profiler has the capability of capturing the following information about any given schedule.

At the time of this writing, the profiler data takes 17 bytes of memory for each schedule on which it is enabled. This memory remains allocated until one of these things happens...

uint32_t pid = scheduler.createSchedule(50, -1, false, callback_function);  // Make a schedule...

/* Allocates memory for measurements and will first measure upon next execution. */
scheduler.beginProfiling(pid); 

/* Stops the profiler from measuring this schedule, but retains the measurements already made. */
scheduler.stopProfiling(pid);

/* Stops profiling (if it is running) and frees the memory occupied by the measurements. */
scheduler.clearProfilingData(pid);  

/* Prints the profiler data for all schedules that have profiling enabled. 
   Note that the function returns a pointer to memory that was dynamically 
   allocated, and so it must be freed when we are done with it. */
char * temp = dumpProfilingData(void);
if (temp != NULL) {
  Serial.println(temp);
  free(temp);
}


Non-obvious Uses:

One-shot events.... 

/* Fires callback_function() after 790ms, and then cleans itself up. */
scheduler.createSchedule(790, 0, true, callback_function);

/* Blinks an LED for (20*9)ms. */
scheduler.createSchedule(20, 9, true, toggle_led);

/* Makes a 500Hz beep that lasts for 0.5 seconds. */
scheduler.createSchedule(1, 1000, true, toggle_speaker_pin);


Chaining schedules together: With some clever function definition, you can chain events together. This code blinks four LEDs several times in sequence. By the time the last LED schedule expires, the one schedule that runs forever comes back around and creates four new auto-clearing schedules. 

void put_leds_into_cycle() {
  // Pulse all the LEDs in sequence...
  scheduler.createSchedule(20, 7, true, toggle_02_oclock_led_r);
  scheduler.delaySchedule(scheduler.createSchedule(20, 7, true, toggle_04_oclock_led_r), 7*20);
  scheduler.delaySchedule(scheduler.createSchedule(20, 7, true, toggle_08_oclock_led_r), 7*20*2);
  scheduler.delaySchedule(scheduler.createSchedule(20, 7, true, toggle_10_oclock_led_r), 7*20*3);
}

scheduler.createSchedule(7*20*4, -1, false, put_leds_into_cycle);


Reading buttons on digital pins with ipso facto debounce... 

/* Read the buttons 10 times per-second. */
pid_poll_buttons     = scheduler.createSchedule(100, -1, false, pollButtons);


Dynamically changing the hysteresis of a sensor under varying environmental conditions... 

uint32_t pid_orientation_read;

void getOrientation() {
  /* [code omitted for brevity] Read an accelerometer.
     Based on this reading versus past readings, change the rate at which
     the accelerometer is read to acheive lower error-rates when integrating
     for position. Assign the new rate to the variable named noise_factor.*/

  /* Be sure to cast the new rate as a 4-byte int to distinguish between
     setting the period and setting the number of recurrences. */
  scheduler.alterSchedule(pid_orientation_read, (uint32_t) noise_factor);
}

/* Read the orientation every 50ms. */
pid_orientation_read = scheduler.createSchedule(50, -1, false, getOrientation);


Notes regarding construction:

The library was written using linked lists and dynamic memory allocation to support as many schedules as the program needs at any given moment. The memory footprint of the scheduler itself is very small. Adding schedules will cause the required amount of memory to be malloc'd. Adding profiling support for a schedule will cause an additional malloc for the profiler data.

When a schedule is destroyed (either manually by the calling program, or automatically by expiration), the memory associated with the schedule and its profiler data will be freed.


Notes regarding possible enhancements:

Because I wrote the library with a linked list as the underlying data structure, a priority-queue could be easily implemented by re-ordering the list elements and re-working the serviceSchedule() function to exit after servicing the first schedule. This would make the scheduler more robust in the face of high-loads. that (presently) cause IRQ lock-ups. The bug causing the lockups was resolved.

There are several functions that I have not covered here. Check Scheduler.h for a full listing and brief doc. Check Scheduler.cpp for full documentation on how each function works.

Please feel free to post bugs either here, or on the Github page. If I don't address them, I will at least reply to you and tell you why.

Previous:
Next: