Author Topic: Scheduling cooperative tasks waiting on a delay.  (Read 933 times)

0 Members and 1 Guest are viewing this topic.

Offline obiwanjacobiTopic starter

  • Full Member
  • ***
  • Posts: 57
  • Helpful? 0
  • You can PIC any micro controller - what AVR!
Scheduling cooperative tasks waiting on a delay.
« on: May 05, 2013, 08:07:03 AM »
Hi,

I am experimenting with a lightweight cooperative multitasking 'system' and am currently researching how to do (logical) delays inside a task.

My Tasks are able to yield and resume at the same spot. It is easy to let a task wait for a certain time. But with many other tasks present the accuracy of the time waited diminishes with a simple round-robin calling pattern.

So I am looking for inspiration on how (and/or if) to schedule these tasks in such a way that the delay-deviation is minimized. An important aspect is that I want to use as few RAM bytes as possible. For now I assume that these delays are not dynamic - so these const values could be made to go into prog-memory (C++/AVR) and are known in advance.

I have some ideas myself but perhaps there is an algorithm that is perfect for this...

Offline waltr

  • Supreme Robot
  • *****
  • Posts: 1,920
  • Helpful? 97
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #1 on: May 05, 2013, 11:34:06 AM »
The way I do this on PIC processors is to setup a Hardware timer that triggers an interrupt at a periodic rate. In the ISR do either one or both of two things: set a flag bit and/or increment a software counter.

Then in the main loop, poll the flag bit if you need to run a task at the Timer period, and/or compare the software counter value for tasks that need to run at a multiple of the Timer period.

There are some variations of this but this is the basics of how to setup multi-tasking in a micro-controller.

Offline obiwanjacobiTopic starter

  • Full Member
  • ***
  • Posts: 57
  • Helpful? 0
  • You can PIC any micro controller - what AVR!
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #2 on: May 05, 2013, 11:55:18 AM »
I do not have 'a' timer task. Any task can do a delay/wait. Some small waits I will do synchronously but a couple of hundred millisecond wait will be asynchronous. So I need to keep track of all Tasks that are waiting for their delay and prioritize those tasks that will expire the quickest.

Think of it like blinking a couple of LEDs and each LED is driven by its own task (instance) but their on/off times all differ. The scheduler will call each BlinkLedTask instance and each task will determine if its time to change the state of the LED.

The problem is that I do not want the BlinkLedTask instance with very small delays (fast blinking) to wait for the other tasks to do their thing and end up being 'over time'. So if I could detect that that fast BlinkLedTask should have be called earlier, then its actual delay would be closer to the intended time.

I just realized that this is a can of worms. If I do something like I described, I should also have logic in place to keep Tasks from starving (not getting any time at all)...  :-[

Offline paulstreats

  • Supreme Robot
  • *****
  • Posts: 1,381
  • Helpful? 21
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #3 on: May 05, 2013, 03:26:38 PM »
Hiya:)

I made a multitasking system on PIC's too, but dont use it often. I gave each task a return stack of 6 stored in ram so its not really capable of doing too many things at once, it was definately fun to develop though... I never got around to dynamic delays but this is probably how i would have approached it.

 Have a seperate function in the ISR (the place the program pointer goes to when your timer interrupts that calls up the next task on the list) then give that the ability to set a second timer (Timer 1 etc..) and recall the task when that secondary timer interrupts the runtime. If set up correctly, the seperate function could have an array stack with secondary interrupt requests from tasks that are on delay and set the second timer according to which was to resume soonest.

 As much as it seems a simple enough thing, there are other things that you need to consider like when you set up your round robin, you had to decide how much runtime each task got before switching to another, so when a task calls for a dynamic delay and then is recalled, do you give it just its remaining allocation of original runtime or do you give it the full amount of time again... I get totally wrapped up in those situations, but i'd probably just give it the remaining allocated time.

 I do agree that devoting processor time to delayed tasks is wasteful. If you come up with another way to do it or get something working at all, I would be grateful if you could post your results :)

Offline jwatte

  • Supreme Robot
  • *****
  • Posts: 1,281
  • Helpful? 79
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #4 on: May 05, 2013, 10:00:16 PM »
In hard real-time systems, it's not uncommon to see a maximum runtime allowed for any one particular task before yielding.
Any task that exceeds the designated time is terminated, and a fault is logged. Better debug all of those before you release to real life :-)
Then you set the maximum runtime of any task, so that it is smaller than the acceptable jitter for tasks that wake up from delays.
If you have multiple tasks that can want to wake up, then the maximum runtime of any one task PLUS the runtime of all the woken-up tasks except the longest-delayed task, must be less than the acceptable jitter for the longest-delay task.

If you want the convenience of writing a task (or tasks) that can "run for as long as they want" and still get particular events to happen at particular times, then you need to use pre-emption. This means that tasks may be suspended/switched out whenever they are executing, rather than just at well-defined suspend points. This generally uses more RAM, for stack space, and for saving all the registers when pre-empting.

Sometimes, you can map all the tasks that NEED a particular wake-up time to interrupt handlers, and just run them from interrupt context. There are some things you cannot do in interrupt context (like, wait for a long time, or block waiting for another task) so you'd have to make sure that's taken into account when writing the code.
You'd still have timing requirements, where the runtime of all your interrupt handlers must be less than the smallest acceptable wakeup jitter. This isn't so bad -- it's basically the same as saying that your hardware actually needs to be capable of doing all the things you want it to do :-)

Offline obiwanjacobiTopic starter

  • Full Member
  • ***
  • Posts: 57
  • Helpful? 0
  • You can PIC any micro controller - what AVR!
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #5 on: May 05, 2013, 11:40:05 PM »
Thank you very much for your answers but I get the distinct impression you are meaning something else with the term 'mulit-tasking' than I do. So lets call a separate execution flow that is managed by a scheduler a Thread and a logical piece of code (usually a class) that performs a specific operation or set of operations a Task. A multi-tasking system is NOT the same as a multi-threading system.

In a cooperative multi-tasking system all active tasks share the CPU time with each other and I cannot stop a Task from the outside. A Task can yield execution but does so willingly (hard-coded). So the cooperative nature is that all Tasks has to play nice together and there is no higher authority that can police the Tasks into behaving.

In such a scenario I don't see how a Timer/ISR would help, other than perhaps doing some background bookkeeping on what Task has the first upcoming delay time expiration. But that can also be done easy enough in the main loop.

So please tell me if I'm just not getting what you are trying to tell me or are we having some terms mixed up...?

Offline paulstreats

  • Supreme Robot
  • *****
  • Posts: 1,381
  • Helpful? 21
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #6 on: May 06, 2013, 05:21:52 AM »
The reason I used timers and an ISR was so that tasks only run for a certain amount of time, they then yield for the next task and so on, until it comes back to the first task that resumes. It means that individual tasks dont need to be hardcoded to yield at any time, the processor timing unit and ISR handles it for you ensuring that each task gets the same amount of runtime and sharing the processors time equally.

 The only issue I have is the lack of ram to develop mine further, and the "book keeping" in the task scheduler becomes more and more complicated and is a fully time laden task in itself Popping and restoring the return stack, setting the program pointer etc... as well as building in fail safe stack checking to make sure errors and blank spaces are eliminated (if i remember, if a task is running and using the standard delay code, and its runtime has to yield, a blank space can occasionally appear where the program pointer should be so i just had to waste the time with loops. I would like to be able to setup a delay server to handle delays and allow other tasks to run instead of just wasting it though :))

 If you dont need such a complicated system, then a simple schedule list in the main function should work just aswell (mine was developed to handle dynamic tasks but if you know what tasks you need to run then theres no need for the complication).

 One way of handling the delays in the simp[lified system could still be done with the timer and an ISR, set the timer for the length of delay you require, store the position of the program counter and when the timer interrupt happens and the pointer jumps to the ISR, put the stored position on the top of the stack and return;

Offline obiwanjacobiTopic starter

  • Full Member
  • ***
  • Posts: 57
  • Helpful? 0
  • You can PIC any micro controller - what AVR!
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #7 on: May 06, 2013, 05:41:29 AM »
I explicitly do not want to go pre-emptive because I feel that it is overkill in the small MCU's my lib is targeting. The fact that you run out of RAM to develop it further is a sure sign (to me) that you're not on the the 'correct' (correct is a matter of setting goals) path.

I just posted the link to the mechanism I use for cooperative mult-tasking here: http://www.societyofrobots.com/robotforum/index.php?topic=16906.0

It consists of some macros that build up a switch statement that keeps track of where the Task was with executing its code.

I am currently experimenting with a simple (static) scheduler that keeps track of tasks in two lists (arrays): tasks that are running and tasks that are waiting. If I can get that to work - just wrote the pseudo code for it - it will do just fine.

Offline paulstreats

  • Supreme Robot
  • *****
  • Posts: 1,381
  • Helpful? 21
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #8 on: May 06, 2013, 05:59:33 AM »
Definately, dont go too heavy with it. The simpler you can make it to do the job, the better. The more you incorporate into it, the more memory its going to need and also more time is needed to devote to housekeeping on the stacks, I developed mine for fun really and for the challenge rather than to be used in a specific application and I got a lot out of it in terms of understanding more about the program pointer, return stack, memory heap etc... as well as having all of the register loaded up on the simulator and watching pointers moving backwards and forwards. It really was just a learning experience and to be honest I would still like to develop it further but not until I have an ARM setup that I'm confident with and get on with the toolchain. There really is a limit to what can be done on small mcu's or especially those with limited clock speeds since housekeeping external ram would take up too much runtime to further develop the system (something that i did consider :D)

 But no carry on as you are, I'd love to see how you do eventually handle the efficient delays :)

Offline obiwanjacobiTopic starter

  • Full Member
  • ***
  • Posts: 57
  • Helpful? 0
  • You can PIC any micro controller - what AVR!
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #9 on: May 06, 2013, 06:20:06 AM »
[..] I'd love to see how you do eventually handle the efficient delays :)

Me too!  :o   :P

Offline jwatte

  • Supreme Robot
  • *****
  • Posts: 1,281
  • Helpful? 79
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #10 on: May 06, 2013, 12:28:52 PM »
In a cooperative multi-tasking system all active tasks share the CPU time with each other and I cannot stop a Task from the outside. A Task can yield execution but does so willingly (hard-coded). So the cooperative nature is that all Tasks has to play nice together and there is no higher authority that can police the Tasks into behaving.

...

So please tell me if I'm just not getting what you are trying to tell me or are we having some terms mixed up...?

There are four levels of multi-tasking:

1) A top-level scheduler calls into some context (object, function pointer, whatever) and lets it do its thing; when it returns, the top-level scheduler calls into the next context. Optionally, contexts may return/set some amount of time that the scheduler can wait before re-calling the context. I think this is what you're talking about. Personally, I structure almost all my AVR code like this; it's a fine way to do it.
The main draw-back is that if a particular task wants to run at a particular time, the worst-case wake-up jitter is the same as the worst-case runtime of any task that might run, no matter whether it's important or not. Also, a task has to be written in "callback style" -- it has to return back to the caller to yield. This can be tricky if you are trying to convert algorithms that are not inherently state-machine-like.
In computer science, this mechanism is generally referred to as "continuation passing style" or sometimes "co-routines" (although that's an overloaded term, see below.)

2) Still use explicit (cooperative) yielding, but let the task yield wherever it wants in the code by simply calling "yield()." The scheduler will then either copy the stack/registers to a saving area, or reset the stack pointer to somewhere else, and call another task. This still has most of the draw-backs of cooperative scheduling in step 1, except it allows you to yield from anywhere within your code. Thus, if you have a complex algorithm that can't be easily broken into a bunch of separate calls, you can insert a yield() inside some loop, and the CPU will be yielded to other tasks more often -- the worst case runtime before yield is easier to control. This mechanism is typically referred to as "fibers" or "cooperative threading" or "co-routines" (see, overloading!)
Also, the "yield" function is often built into blocking operations like "wait for I/O" or "acquire semaphore" or whatever synchronization you have.

3) Once you have the ability to switch out the stack of a running function and schedule another function, you realize that you can do this at any time, without the running function needing to call yield explicitly. This is how pre-emptive multithreading is born. Set up a timer interrupt that makes the scheduler switch in another runnable task. This way, existing algorithms can run unchanged without having to insert calls to yield(). If you then have a way of assigning priorities to tasks, you can have the pre-emptive system make sure that the highest-priority task wakes up exactly when it needs to, by setting a timer interrupt and compensating for the scheduling latency (which is fairly predictable.)

4) In any of these systems, you will have hardware events that require immediate attention. In a larger system, it might be something as low-level as a page fault. In smaller systems, something like a data byte coming in on a UART would require immediately de-queuing it and putting it in a receive buffer to avoid losing the next byte. These kinds of operations are typically supported through hardware; the hardware will generate an interrupt, which will (in hardware) save the running task context on the stack, and jump to a specific interrupt handler. The interrupt handler can then run within a slightly limited environment (because it doesn't know exactly what else was going on at the time on the CPU) and when it returns, the original task is resumed.
Now, for really important high-priority tasks, you may choose to just use interrupts for this, because of the light-weight context switch, and the ability to make them happen with very precise timing. The draw-back is the more limited execution environment during interrupt time, and a very long execution will prevent possibly other interrupts from running.

It sounds like what you're describing is an instance of 1), and you're talking about the main problem with that approach: the long worst-case latency for scheduling time-critical tasks. Because these models are well studied (back in the '60s and '70s, even) and available in any computer science textbook, I chose to make reference to this context when suggesting ways that industry generally solves the problem you were asking about: minimize the delay (jitter) of tasks that need to run at a particular point in time.

There are lots of good books on these subjects if you're really interested, although a basic college-level textbook like Tannenbaum's "dinosaur book" would be a great start if you have it available. (If not, it's likely available at your local library.)


Offline obiwanjacobiTopic starter

  • Full Member
  • ***
  • Posts: 57
  • Helpful? 0
  • You can PIC any micro controller - what AVR!
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #11 on: May 06, 2013, 01:48:59 PM »
Wow thanks for the detailed descriptions.

Yes, I'm doing 1 but in a very sexy way8)

I have written a central/static Delay class a Task can use to 'schedule' a delay wait. It's not really scheduling but it does do the timekeeping for the tasks. Each iteration of the main loop, the time is updated and waiting tasks that have their delay elapsed, are run - currently at a random (empty) spot in the task array.

I have spend a couple of hours trying to get a scheduler, but I was not pleased with the amount of overhead versus the gain it provided to the developer. I went back to letting the developer write the 'scheduler' in the main loop and determine the flow of Tasks.

Here is a Task class for blinking a LED. Refer to the link for the Task_Begin, Task_Yield and Task_End macros.

Code: [Select]
template<const int rate, const byte pin>
class BlinkLedTask
{
public:
BlinkLedTask()
{
pinMode(pin, OUTPUT);
digitalWrite(pin, false);
_state = false;
}

Task_Begin(Execute)
{
while(true)
{
Task_YieldUntil(Delay::Wait((int)this, rate));

// toggle led
_state = !_state;
digitalWrite(pin, _state);
}
}
Task_End

private:
bool _state;
int _task;
};

The Delay class is used to do the timekeeping on Task waiting times.

Code: [Select]
#define MAXTASKS 4

class Delay
{
public:
static void Init(Time* time)
{
_time = time;
for(int i = 0; i < MAXTASKS; i++)
{
_ids[i] = 0;
_delays[i] = 0;
}
}

static unsigned long Update()
{
_delta = _time->Update();
return _delta;
}

static bool Wait(int id, int milliseconds)
{
for(int i = 0; i < MAXTASKS; i++)
{
if (_ids[i] == id)
{
if (_delta >= _delays[i])
{
_ids[i] = 0;
return true;
}

_delays[i] -= _delta;
return false;
}
}

for(int i = 0; i < MAXTASKS; i++)
{
if (_ids[i] == 0)
{
_ids[i] = id;
_delays[i] = milliseconds;

break;
}
}

return false;
}

private:
static unsigned long _delta;
static Time* _time;
static int _ids[MAXTASKS];
static int _delays[MAXTASKS];

Delay(){}
};

I use the Arduino to test this and have 3 leds blinking away at me.

Code: [Select]
Time time;
BlinkLedTask<1000, 13> ledTask1;
BlinkLedTask<2000, 12> ledTask2;
BlinkLedTask<500, 11> ledTask3;

void setup()
{
Delay::Init(&time);
}

void loop()
{
Delay::Update();

ledTask1.Execute();
ledTask2.Execute();
ledTask3.Execute();
}

I'm pretty happy with the result.
« Last Edit: May 06, 2013, 11:06:30 PM by obiwanjacobi »

Offline jwatte

  • Supreme Robot
  • *****
  • Posts: 1,281
  • Helpful? 79
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #12 on: May 06, 2013, 08:52:48 PM »
For comparison, here's the way I would blink three LEDs at different intervals, using my own version of 1):

Code: [Select]
struct blinking {
    unsigned char volatile *port;
    unsigned char bit;
    unsigned short delay;
};

void blinking_task(void *ptr) {
    blinking &b = *(blinking *)ptr;
    after(b.delay, blinking_task, ptr);
    *port ^= b.bit;
}

blinking a = { &PORTB, 0x08, 400 };
blinking b = { &PORTB, 0x10, 500 };
blinking c = { &PORTB, 0x20, 600 };

void setup() {
    blinking_task(&a);
    blinking_task(&b);
    blinking_task(&c);
}

I don't have a main() at all -- my library (scheduler) owns main. The scheduler has a timer and knows when the "next" task is ready to run. If you want a task to keep running as much as possible, yet fairly give up time to other tasks that become available, use a 0-time delay each time it re-enqueues itself.

And, yes, I could totally re-write this as a C++-style interface, but I kind-of like the C-like syntax. Call me weird :-)

Offline obiwanjacobiTopic starter

  • Full Member
  • ***
  • Posts: 57
  • Helpful? 0
  • You can PIC any micro controller - what AVR!
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #13 on: May 06, 2013, 11:29:37 PM »
You're weird!  :P

I don't see how the task is repeated. What does after() do, exactly?

Thanx.

Offline jwatte

  • Supreme Robot
  • *****
  • Posts: 1,281
  • Helpful? 79
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #14 on: May 07, 2013, 03:57:35 PM »
after() tells the scheduler to call the given function pointer with the given void pointer argument after a certain number of milliseconds. It's a bit like "setTimeout()" in Javascript. Importantly, it only enters a single-shot callback. It can also be called from interrupt handlers, which is nice for scheduling follow-up work (a bit like DPCs in Windows.)
Because the blinking_task function calls after() on itself, it will repeat itself forever.
I keep all the scheduled timeouts/tasks in a queue in the scheduler, ordered by "next task to run" (lowest time-to-wake-up.)

Offline obiwanjacobiTopic starter

  • Full Member
  • ***
  • Posts: 57
  • Helpful? 0
  • You can PIC any micro controller - what AVR!
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #15 on: May 08, 2013, 12:07:14 AM »
 :o  but how is the "*port ^= b.bit;" code called? Shouldn't that code be before calling after()?

And how do you keep the stack from growing? Doesn't the return address stay on the stack each time you call after()?


Offline jwatte

  • Supreme Robot
  • *****
  • Posts: 1,281
  • Helpful? 79
Re: Scheduling cooperative tasks waiting on a delay.
« Reply #16 on: May 08, 2013, 09:41:30 AM »
No, after() just remembers the callback function/pointer, and doesn't save any other context. It's a really simple system, with very minimal overhead! The draw-back is that I have to make sure to return out to the beginning of the task function each time.
More convenient code structure could be built on top of longjmp(), but I didn't need that complexity.

 


Get Your Ad Here

data_list