Thursday, December 4, 2014

Cooperative task scheduling for Arduino


The current old code is here.  It is not yet in library form but is usable as is.

The updated library code is here.  Just place this directory in your ArduinoSchetches/library directory in the directory Scheduler.  Remember to close the Arduino IDE down and restart it to see a new library you drop into place.

Why write a scheduler?

The LED blinking program for Arduino illustrates the basic problem that you quickly run into when coding on Arduino.

void loop() {
  digitalWrite(led, HIGH);   // turn the LED on (HIGH is the voltage level)
  delay(1000);               // wait for a second
  digitalWrite(led, LOW);    // turn the LED off by making the voltage LOW
  delay(1000);               // wait for a second
}

This is all fine and dandy when you just want to turn one led on and off.  The big problem is that while the chip is delayed, it is not doing anything else. But what if you want to turn 8 different LEDs on and off at different rates?  While you read a couple of different sensors, each at a different rate.  And you want to de-bounce a few buttons and write some status info out to the serial port or to an LCD at a regular interval.  Which is just a typical set of things to do when you are hacking an Arduino based design.

Doing something more complicated like a scheduler is overkill to just blink one LED. You can code a bunch of complicated timing functions that are fragile and difficult to modify when you add one more switch or one more sensor, or you can bite the bullet and just write a scheduler.  Or better yet, you can just use my library once it is ready.  right now. :D

What is a scheduler?

What a scheduler does is decide when to execute code on a hardware platform.  Think of it as a rudimentary operating system for the micro-controller. You can set up various threads of execution and build state machines that can perform some interesting data processing using these threads.

Of course, you don't actually have real multitasking on the Arduino hardware, but by using cooperative multitasking you can let functions take turns running at various intervals and because this little chip runs so quickly the code all appears to be running in parallel.

The equivalent code for blinking 8 different LED's at different rates using the scheduler would look like this:  (This is one of the examples in the library, haven't tried it, but it should be close).

  #include <Scheduler.h>

  int rate[8][2];

  int
  blinkled(struct _task_entry_type * task, int led, int mesgid){

    switch (mesgid) {
      
      // Handle an on.
      case 1:
           digitalWrite(led, HIGH);   // turn the LED on
           AddTaskMilli (task, rate[led-3][0], &blinkled, 2, led);
                  // see how we rescedule with mesgid set to 2
                  // this ensures that the off case will be called next
           break;
      
      // Handle an off.
      case 2:
           digitalWrite(led, LOW);    // turn the LED off
           AddTaskMilli (task, rate[led-3][1], &blinkled, 1, led);  
                  // see how we rescedule with mesgid set to 1
                  // this ensures that the on case will be called next
break; } return 0; } void setup() {
    // setup random to always generate the same values for testing.
    randomSeed(1);
    // Setup 8 timers to randomly blink leds on pins 2-11. 
    for (int i = 0; i<8; i++) {
      rate[i][0] = random(300, 1000);  // set the on  time.
      rate[i][1] = random(300, 1000);  // set the off time.
      pinMode(i+3, OUTPUT); 
      AddTaskMilli (CreateTask(), rate[i][1], &blinkled, 1, i+3); 
    }
  }


  void loop() {
    DoTasks();
  }



Yes, it is more complicated than the single LED blinking example, but try to implement something similar in the main loop and you will quickly find yourself making things much more complicated than this relatively strait forward code.

And if later I want to debounce a set of buttons I just have to write the function and set up a thread to do the work.  I won't have to worry about messing up the timings between the two different threads like I would if I were trying to write complicated timing code in the main loop.

Let's go over what is going on.  The setup runs once, this is where the task list is created by the CreateList() function.  Then the random seed is populated so that it will repeat the same values each time it is ran.  A for loop executes 8 times, creating a set of random values for each led's on and off times, setting the output mode of the pin so it can light up an led and finally creating and adding the task to the tasklist.

AddTaskMilli() is one of 4 functions that can be used to create a new thread of execution.  There is really only a single function, the other three are just aliases that take different time arguments and translate them to the main function.

The  function CreateTask() is the first argument.  This creates a new task that is owned by the Tasks list and passes it as the first argument.  The second argument sets the delay before the function is ran, using the random value it generated for that field.  The third argument is the handle to the function that you want executed when the thread times out.  The fourth field is a message id, with 0 being used to indicate that a thread is being ended, for clean up code purposes.  Feel free to pass any values you want above or below 0. The last field is a data field that I am setting to the pin to use for that thread.

When the thread times out it calls the function with a pointer to the thread, the message id, and the data that you stored there. The thread is ended at this point, so unless you reschedule it, it will never run again.  Based on the message id when the thread first ends it will be message id 1, so the code in the switch case statement is ran for 1, which turns on the LED that is passed in from the data field, reschedules the thread to run again with the message id set to off.  The next time it comes in the message id is 2 and this turns off the led and reschedules the thread to run for the off period of time.  Each time the thread runs it swaps between states on and off, 1 and 2 on the message ids.   And each thread is ran independent of the other threads.

This type of state machine can be used to model complex protocol states, such as found in a tcp stack, or in a file protocol that is being used to write logs or images out to an SD card.

Converting structures.

I used C code that I wrote for Linux. Even though the programming language on the Arduino is similar to C, it seems that you have to specifically spell out the types used inside the structure and for function types, for the function argument lists, and inside the function itself. I'm not sure if the problem is a name scope issue or what, but I eventually worked around it.

Passing function pointers as function arguments.

I had trouble storing and calling function pointers in the structure. All the syntax is just slightly different than C. Just enough to mess up my more complex programs.  I have ported many C programs between systems before and only ever had to add a few ‪#‎ifdefs‬ here and there. Having to rewrite so many lines of code is sort of annoying.

Converting from using unix time to millis().

I was using some UNIX time functions under Linux that don't work the same under the Arduino.  So I converted to using the millis()  function, using /1000 to get the seconds and %1000 to get the milliseconds.

Current Status.

Right now I have working code that does exactly what I want.  The base code is 2.5KB out of 30KB compiled on the upload to the chip, which is very reasonable. With the LED stuff it pushes about 4KB.    Running with just the led code in the example code at the top of the page I was able to create over 70 threads that all ran simultaneously. At the 71th thread it failed gracefully and kept running the threads that it was able to create.

I had to fix a lot of things I was doing wrong in the code, amazed it worked at all on the original platform.  I should port those changes back over.

*** Update *** Library code is written, see below for more details.

Next Steps.


1. *** DONE! ***  Obviously this needs to be a library. *** DONE! ***  
I am betting that some of the name space issues will go away if I do this as a library, enabling me to make the code simpler. By making it a library it will be more convenient to use in multiple projects and any bug fixes will fix the bug everywhere the library is used.

*** UPDATE 04 Dec 2014 ****

 I made a couple of examples for the library to show how to use it and posted a link to the new code at the top of this page.

I had to pull the Tasks list into the library itself, as I didn't see any easy way to define it so that both the library and the user code could both see it without creating a duplicate variable definition, but this is fine because it makes setting up the library much easier now.
2. Add in battery conserving code. 
One of the cool features of this sort of library is that it knows when the next thing needs to run. Which means that the library could put the chip in a low power mode until it needs to run again. Adding this sort of code to your own already fragile timings can shatter them into a million bits so most people don't add it in.  I know I have avoided learning about the watchdog timers and the code to put the chip into low power mode and wake up when it should just because it seems so complicated.

By letting this library conserve power, it will simplify each project because the code will not have to be added to each project individually, speeding development of efficient battery operated modes.  You will still need to adjust the  timings of various threads to match the available timing slots in the watchdog timer for the best performance versus battery life.

This mode will make my library take up more room on the chip, so it might make sense to include a flag to disable this part of the code if not needed.
3. Fix the 50 day millisecond wrap around issue.
At 49 or 50 days the milliseconds will wrap around so I need to handle this situation so that things will work without a blip even if the chip runs for years, like in a battery backed up thermostat or the like.
3. Get feedback to make things better.
 I am not satisfied with how I am passing information into the thread functions. And how I had to define the types in the struts and parameters and functions is needlessly complicated. I may be able to just hardcode the schedule list and the run list, instead of dynamically creating them, since I only ever want 2 these two lists anyway.  Deleting running threads does not work right. Or maybe I do want more threads, with an order of priority so that the ones in the first list process first.

No comments:

Post a Comment