# Simple and fair scheduler for function calls on Arduino

because Arduino platforms are fairly limited in its capacities, I wrote a small process scheduler. I append a function to an array and define a tickrate. After this tickrate elapses, the function should be called. Additionally I set a small delay. If several function share the same tickrate, this delays hinders them to get called very shortly together. In case, that the serial bus is used, this could avoid write/read blocks. I never wrote something similiar and wouldn't say that my approach with the delay is elegant. Maybe someone has ideas to enhance this story.

Ads: - CAPITALS are #defines

Sample:

Emitter emitMain(&main_loop, MAIN_LOOP_T_MS);
// Prepare scheduler for the main loop ..
_SCHED.addEmitter(&emitMain,  0);
_SCHED.run();


Code *.h:

class Emitter {
public:
Emitter(void (*pf_foo)(), uint16_t delay = 0);

bool emit();
void reset();
uint16_t getDelay(uint16_t iNum);

private:
bool bSend;
uint16_t iDelay;
void (*pfEmitter)();
};
///////////////////////////////////////////////////////////
// Container for emitter objects
///////////////////////////////////////////////////////////
class Emitters {
private:
const AP_HAL::HAL *m_pHAL;

uint8_t   m_iItems; // Current number of items in the arrays below
uint32_t  m_timerList   [MAX_NO_PROC_IN_SCHED];
Emitter  *m_functionList[MAX_NO_PROC_IN_SCHED];
uint16_t  m_tickrateList[MAX_NO_PROC_IN_SCHED];

protected:

///////////////////////////////////////////////////////////
// pEmitters: Array of iSize_N elements
// iTickRates: The times in ms until the emitter in the array will emit again
// iTimerList: Array holding the timers for each element
// iSize_N: The number of emitters in the array
///////////////////////////////////////////////////////////
void scheduler(Emitter **pEmitters, uint16_t *iTickRates, uint32_t *iTimerList, const uint8_t iSize_N);

public:
Emitters(const AP_HAL::HAL *);

void addEmitter(Emitter *, uint16_t iTickRate);
void run();
};


Code *.cpp:

#include "emitter.h"

Emitter::Emitter(void (*pf_foo)(), uint16_t delay) {
bSend = false;
iDelay = delay;
pfEmitter = pf_foo;
}

bool Emitter::emit() {
if(!bSend && pfEmitter != NULL) {
pfEmitter();
bSend = true;
return true;
}
return false;
}

void Emitter::reset() {
bSend = false;
}

uint16_t Emitter::getDelay(uint16_t iNum) {
return iDelay * (iNum+1);
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
Emitters::Emitters(const AP_HAL::HAL *p) {
m_pHAL = p;

memset(m_functionList, NULL, sizeof(m_functionList));
memset(m_tickrateList, 0, sizeof(m_tickrateList));

m_iItems = 0;
uint32_t timer = m_pHAL->scheduler->millis();
for(uint8_t i = 0; i < MAX_NO_PROC_IN_SCHED; i++) {
m_timerList[i] = timer;
}
}

void Emitters::addEmitter(Emitter *p, uint16_t iTickRate) {
if(m_iItems < sizeof(m_functionList)-1 && p != NULL) {
m_functionList[m_iItems] = p;
m_tickrateList[m_iItems] = iTickRate;
m_iItems++;
}
}

void Emitters::scheduler(Emitter **pEmitters, uint16_t *iTickRates, uint32_t *iTimerList, const uint8_t iSize_N) {
if(m_pHAL == NULL)
return;

for(uint8_t i = 0; i < iSize_N; i++) {
uint32_t time = m_pHAL->scheduler->millis() - iTimerList[i];
if(time > iTickRates[i] + pEmitters[i]->getDelay(i) ) {
if(pEmitters[i]->emit() ) {
if(i == (iSize_N - 1) ) { // Reset everything if last emitter successfully emitted
for(uint16_t i = 0; i < iSize_N; i++) {
pEmitters[i]->reset();
}
iTimerList[i] = m_pHAL->scheduler->millis();
}
}
}
}
}

void Emitters::run() {
scheduler(m_functionList, m_tickrateList, m_timerList, m_iItems);
}


EDIT after first answer: Initially my scheduler had a completely other design. I was not testing the current code so far. But with the help of palacsint I made a few changes in comparison to the example above. If there are further suggestion I will change the code after this section.

SAMPLE:

// function, delay, multiplier of the delay
Emitter emitAtti(&send_atti, 3,  0);
Emitter emitRC  (&send_rc,   37, 0);
Emitter emitComp(&send_comp, 44, 0);
Emitter emitBaro(&send_baro, 66, 0);
Emitter emitGPS (&send_gps,  66, 1);
Emitter emitBat (&send_bat,  75, 0);
Emitter emitPID (&send_pids, 75, 1);


IMPLEMENTATION:

Emitter::Emitter(void (*pf_foo)(), uint16_t delay, uint8_t mult) {
m_bSend           = false;
m_iDelay          = delay;
pfEmitter         = pf_foo;
m_iDelayMultplr   = mult;

uint32_t m_iTimer = 0;
}

bool Emitter::emit() {
if(!m_bSend && pfEmitter != NULL) {
pfEmitter();
m_bSend = true;
return true;
}
return false;
}

void Emitter::reset() {
m_bSend = false;
}

uint32_t Emitter::getTimer() {
return m_iTimer;
}

void Emitter::setTimer(const uint32_t iTimer) {
m_iTimer = iTimer;
}

uint16_t Emitter::getDelay() {
return m_iDelay * m_iDelayMultplr;
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
Emitters::Emitters(const AP_HAL::HAL *p) {
m_pHAL = p;

memset(m_functionList, NULL, sizeof(m_functionList));
memset(m_tickrateList, 0, sizeof(m_tickrateList));

m_iItems = 0;
}

void Emitters::addEmitter(Emitter *p, uint16_t iTickRate) {
if(m_iItems < NO_PRC_SCHED && p != NULL) {
m_functionList[m_iItems] = p;
m_tickrateList[m_iItems] = iTickRate;
m_iItems++;
}
}

bool Emitters::isEmitted(const uint8_t i) {
Emitter *pCurEmit = m_functionList[i];
uint32_t time = m_pHAL->scheduler->millis() - pCurEmit->getTimer();

// Time yet to start the current emitter?
if(time <= m_tickrateList[i] + pCurEmit->getDelay() ) {
return false;
} else {
// Release the block for the transmitter
pCurEmit->reset();
}

if(pCurEmit->emit() ) {
// Set timer to the current time
pCurEmit->setTimer(m_pHAL->scheduler->millis() );
} else {
return false;
}

return true;
}

void Emitters::resetAll() {
// Reset everything if last emitter successfully emitted
for(uint16_t i = 0; i < m_iItems; i++) {
m_functionList[i]->reset();
}
}

void Emitters::run() {
if(m_pHAL == NULL)
return;

for(uint8_t i = 0; i < m_iItems; i++) {
// Run all emitters
if(!isEmitted(i) ) {
continue;
}
}
}

-
Thanks for the accept! :) Anyway I think you should wait at least a few days before accept an answer to give other people time to answer, and then make a selection. Selecting an answer so soon may also ward off some answers that you may have received had you not accepted an answer so early. (You can unaccept by clicking on the thick I guess.) –  palacsint Feb 18 '14 at 12:37

## 2 Answers

Your application looks like a typical periodic real-time task scheduler. There are many known and good algorithms for this, the two most widely used are Earliest Deadline First(EDF) and Rate Monotonic (RM). By the looks of your example you do not seem to have a pre-emptive scheduling model, which is fine if you don't want to deal with processes and context switches.

A Task is a periodic processing that has to be done. We call each period of a Task for a job. The task releases jobs to be executed periodically, and each job has a deadline. The deadline is equal to the time_of_release + period, which coincidentally is the time of the next job release. Jobs are executed in order of earliest deadline first after they have been released. Each job has a designed "worst case execution time" (WCET), which you can determine experimentally or preferably by analysis. Or if you don't care about hard real-time constraints, you can simply set it to 0. It only affects schedulability analysis, and has no impact on actual scheduling.

The following implements a rudimentary (not-tested) non-preemptive EDF scheduler.

Please note: I have written this from the top of my head, and this is not suitable for use in any real-time system without a thorough code review and testing. This is provided for demonstrative purposes only!

class EdfScheduler;

class Task{
public:
// period: The period the task must be executed with.
// wcet: The worst case execution time of the task.
Task(int period, int wcet, int start_time)
: m_period(period), m_wcet(wcet), m_next_deadline(start_time)
{}
virtual ~Task();
virtual void run() = 0;
private:

bool canRun(int time){
int job_start = m_next_deadline - m_period;
return job_start >= time;
}
int nextRun(){
return m_next_deadline;
}
const int m_period;
const int m_wcet;

int m_next_deadline; // And coincidental job-release
friend class EdfScheduler;
};

class EdfScheduler{
static const int MAX_TASKS = 8;
static const int MAX_SLEEP = 200;
public:
EdfScheduler(){
for(int i = 0; i < MAX_TASKS; ++i){
m_tasks[i] = NULL;
}
m_processor_load = 0.0f;
}

bool addTask(Task* t){
bool added = false;
for(int i = 0; i < MAX_TASKS; ++i){
if(m_tasks[i] == NULL){
m_tasks[i] = t;
added = true;
break;
}
}
if(!added)
return false;

t->m_next_deadline += t->m_period;

float wcet_max = 0;
for(int i = 0; i < MAX_TASKS; ++i){
if(m_tasks[i] != NULL){
wcet_max = max(wcet_max, m_tasks[i]->m_wcet);
}
}
float load = 0;
for(int i = 0; i < MAX_TASKS; ++i){
if(m_tasks[i] != NULL){
load += (m_tasks[i]->m_wcet + wcet_max) / m_tasks[i]->m_period;
}
}

if(load > 1.0f)
warning("System is overloaded and may not meet deadlines.");
return true;
}

void runScheduler(){
while(1){
Task* edf = NULL;

int next_run = MAX_SLEEP;
for(int i = 0; i < MAX_TASKS; ++i){
if(m_tasks[i] != NULL){
if(m_tasks[i]->canRun()){
if(edf == NULL){
edf = m_tasks[i];
}else if( m_tasks[i]->m_next_deadline < edf->m_next_deadline){
edf = m_tasks[i];
}
}
next_run = min(next_run, m_tasks[i]->nextRun());
}
}

if(!edf){
sleep(next_run);
continue;
}

edf->run();
edf->m_next_deadline += edf->m_period; // Perpare it for running the next time.
}
}

private:
Task* m_tasks[MAX_TASKS];
float m_processor_load;
};


I realize I might have gone over-board with this but I hope you find it helpful or at least interesting in some way :rollseyes:

-
Interesting. I think I will make some performance comparisons for different situations in future. –  dgrat Feb 19 '14 at 9:08
In general, scheduling is difficult to get right. Especially for real-time systems. And although you didn't state it, your problem looks like a real-time system. Attempting to schedule real-time tasks without a properly implemented real-time scheduling algorithm will cause problems. I would advise to read up on existing algorithms and choose a suitable one. For your case you'd be looking at non-preemptive scheduling. Disclaimer: I have done academic research on real-time scheduling algorithms. –  Emily L. Feb 19 '14 at 9:51
I write my own quadrocopter firmware. Things started easy at the beginning. Just one loop with maximum performance for inertial readout and reading a control command. Then I added support for other devices and sensors, functions for serial output, everything at once was too much for the serial ports and/or the ATMega. Then I used timers, which started to mess up the code. This is why I started to write a preliminary "something like a" scheduler. Ideally the scheduler should privilege the control task. But there are exceptions as well. I think there are always optimizations possible. –  dgrat Feb 19 '14 at 10:31
By the sound of it, you definitely have a real-time system on your hands. The beauty of a real-time scheduler is that it will guarantee that all your tasks will get the WCET amount of execution time within their period. As long as the feasibility test succeeds (the last few rows in addTask). So you don't need to think about privilege or priorities that much. –  Emily L. Feb 19 '14 at 12:16

Just a few minor notes: guard clauses (inverting a few conditions and using continue) would make the code flatten and easier to read:

for(uint8_t i = 0; i < iSize_N; i++) {
uint32_t time = m_pHAL->scheduler->millis() - iTimerList[i];
if(time <= iTickRates[i] + pEmitters[i]->getDelay(i) ) {
continue;
}
if(!pEmitters[i]->emit()) {
continue;
}
if(i != (iSize_N - 1) ) {
continue;
}

// Reset everything if last emitter successfully emitted
for(uint16_t i = 0; i < iSize_N; i++) {
pEmitters[i]->reset();
}
iTimerList[i] = m_pHAL->scheduler->millis();
}


Accessing pEmitters[i] happens three two times. You could create a named local variable for that. The third one is easy to misread (as I did) since both for loops use the same loop variable. It would be more readable if they used different variables or the inner loop was extracted out to a named function.

The function could be called resetEverything (something more conrete would be better). This eliminates the first part of the comment. The second part of the comment could be also a function, isLastEmitterSuccessfullyEmitted which contains the conditions.

for(uint8_t i = 0; i < iSize_N; i++) {
if (!isLastEmitterSuccessfullyEmitted(...)) {
continue;
}
resetEverything(...);
}

boolean isLastEmitterSuccessfullyEmitted(...) {
uint32_t time = m_pHAL->scheduler->millis() - iTimerList[i];
if(time <= iTickRates[i] + pEmitters[i]->getDelay(i) ) {
return false;
}
if(!pEmitters[i]->emit()) {
return false;
}
if(i != (iSize_N - 1) ) {
return false;
}
}

void resetEverything(...) {
// Reset everything if last emitter successfully emitted
for(uint16_t i = 0; i < iSize_N; i++) {
pEmitters[i]->reset();
}
iTimerList[i] = m_pHAL->scheduler->millis();
}


It increases the abstraction level of the code and gives a high level overview for readers/maintainers while the details are hidden in the functions.

-
It really is better to read, if I turn the comparisons. Was not thinking about this! –  dgrat Feb 18 '14 at 12:37