Software > Software

Scheduling cooperative tasks waiting on a delay.

(1/4) > >>

obiwanjacobi:
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...

waltr:
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.

obiwanjacobi:
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)...  :-[

paulstreats:
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 :)

jwatte:
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 :-)

Navigation

[0] Message Index

[#] Next page

Go to full version