PDA

View Full Version : [Question(s)] Writing a task scheduler



badcommandorfilename
01-28-2010, 01:35 AM
I want to write an embedded system (AVR) task scheduler in C to handle the operation of a variety of non-critical tasks which my robot (http://buildtherobot.blogspot.com) needs to perform. I'm looking for some advice on how to implement it so that it adds the lowest amount of overhead while giving it the most flexibility.

I'm also not trying to write a real time OS or anything - it just needs to be simple enough to keep a few core functions balanced. None of the tasks are time critical (I'm using interrupts for those), but I need a way to make sure that nothing is neglected for too long.

1) It needs to be able to schedule tasks for execution at a specific time.

This is mainly for scripted actions (it's a humanoid robot) like walking, etc as well as recharging the battery (which is trickle charged). Right now, I'm thinking of using an array of counters, which are decremented periodically, combined with a state machine in the main loop. This will simply switch the state to the overdue task when the current state expires.

2) It would be nice to have a method of forcing the execution of WAAAY overdue tasks.

Although it's no biggie if some actions are a few tens of milliseconds late, it would be nice if I could guarantee that a task would be executed in a reasonable time. I'm thinking of adding a watchdog interrupt which will perform the task if it's overdue.

3) Some tasks might take a long time to finish.

I'm trying to make this an extensible system, which allows for many tasks. However, if I use the state-machine system above I risk having long running tasks (like path planning/IK) postponing shorter and perhaps more critical tasks (like movement). Including the watchdog override would require the entire task to be run inside the interrupt, which is even worse.

4) A priority system would also be desirable.

In the case that a long task finishes and there are several overdue tasks to perform, the program should run the most critical ones first. Creative use of priorities could also help solve the problem of having a mix of long and short running functions.

5) I'd like a way to pass arguments to functions when the task is scheduled (not executed).

This is the one I really need help with. I'm almost certainly going to end up using function pointers, but unless all the functions take the same arguments I will have to have different data-types and handler functions. Also, how can I copy the argument(s) in their current state for execution later (in the generic case). I think I could do this in C using a sort of pseudo-stack if I can guarantee that each function will only end up in the task queue once, but I'm hoping a generic solution can be implemented if I am creative with assembly.

Has anyone had to do something like this before? I'm looking for a balance between execution overhead, complexity and versatility, so it's OK if there's no good way to get all these features working together. Also, I'm using C now but C++ is also an option.

Any input is appreciated.

MikeG
01-28-2010, 07:31 AM
I'm not too clear on what you're trying to do exactly. How about stacking a task#, current time (timer), state and priority (or pointers). From time to time poll the stack, pop off the old tasks, and execute.

Scheduling a job at a specific time might be hard with an AVR unless the AVR knows what time it is?

Is some of this stuff running on a PC or is it all embedded?

billyzelsnack
01-28-2010, 12:58 PM
Not embedded, but maybe something to have a look at when you design yours.

http://en.wikipedia.org/wiki/Grand_Central_Dispatch

This is Apple's answer to the multi-core future. In the usual Apple fashion they take the work of everyone else and simplify it down to its most basic functionality. It's much simpler than every other similar implementation. So if you're not scared off by Obj-C it might be a good resource.

Noog
01-28-2010, 04:24 PM
I want to write an embedded system (AVR) task scheduler in C to handle the operation of a variety of non-critical tasks which my robot needs to perform. I'm looking for some advice on how to implement it so that it adds the lowest amount of overhead while giving it the most flexibility.

1) It needs to be able to schedule tasks for execution at a specific time.

2) It would be nice to have a method of forcing the execution of WAAAY overdue tasks.

3) Some tasks might take a long time to finish.

4) A priority system would also be desirable.

5) I'd like a way to pass arguments to functions when the task is scheduled (not executed).

Has anyone had to do something like this before? I'm looking for a balance between execution overhead, complexity and versatility, so it's OK if there's no good way to get all these features working together. Also, I'm using C now but C++ is also an option.

Any input is appreciated.

Hiya Badcommandorfilename,

I've been thinking about the same thing lately. I have been assembling the hardware to start prototyping a system like this. Here is the core hardware I have to support the scheduler so far:

AVR microcontroller ('328)
SD card storage (2G card)
Real-time clock

I don't believe the SD card and the RTC are requirements to get a system like this going, but from my perspective they make it easier. I prefer to have the time automatically fetched after this system powers up, and I believe it will be a bit easier to use the room on the SD card to store scheduled events and any parameters that are needed for execution. (Plus the SD card gives lots of room for logging and anything else you can dream of.)

I have a few simple software requirements so far:

1) Be able to schedule events for an absolute time (e.g. Feb 2, 2010 - Run FindGroundhog() )
2) Be able to schedule events for a relative time (e.g. in 1 min - Run readGPS() )
3) Be able to schedule reoccurring absolute time events (e.g. *1st day of every month - Run compressLogs() )
4) Be able to schedule reoccurring relative events (e.g. Every 2 hours - Run scanWifiNetworks() )


For simplicity, I will start by only allowing 1 second resolution on my tasks. This will give me room to optimize things in the future. I will start with the first type of event as it seems to be the easiest to code and control.

In my main program loop I will have two routines that look something like this:

fetchNextEvents() - This will return a list of events that are scheduled to run in the current second and place them into AVR memory. This way I can control how many events are currently in memory, and keep the rest on the SD card. I could manually scale back how often this routine is called (to say every 30 seconds) depending on how many events are normally scheduled.

By keeping some events in memory you could make some simple functions that will return information about the events that are on deck.

runNextEvent() - Will run the next event on the top of the list. Only the highest priority event on the list, and then return.



5) I'd like a way to pass arguments to functions when the task is scheduled (not executed).

This is the one I really need help with. I'm almost certainly going to end up using function pointers, but unless all the functions take the same arguments I will have to have different data-types and handler functions. Also, how can I copy the argument(s) in their current state for execution later (in the generic case). I think I could do this in C using a sort of pseudo-stack if I can guarantee that each function will only end up in the task queue once, but I'm hoping a generic solution can be implemented if I am creative with assembly.

I have a few thoughts on this, but the easiest to get going would be functions that don't require arguments. I know this isn't what you are shooting for, but you have to start somewhere.

If you did want arguments, you could try and pass them into the function when you schedule the event. In my case, I would just store them as strings into the SD card and then parse them into something useful when the function is being called.

There are other possibilities but they wouldn't be as flexible and may be more complicated than what is needed.

This method does not gracefully handle any preempting of tasks because of priority. Task order could be resorted every time you call fetchNextEvents(). Because your program is calling runNextEvent() you could run your own required routines in between each of these calls.

How many events do you expect to try and run in a given period of time? That may help you solidify your requirements.

Noog

ScuD
01-28-2010, 04:24 PM
I know you don't want a "true" OS, but have you looked at Femto OS (http://www.femtoos.org/)?
I don't have any personal experience with it but it might fit your bill..

badcommandorfilename
01-28-2010, 07:10 PM
Thanks for your help everyone.

I thought I might try to dummy up what a typical task list might look like to help solidify the problem:

# | Function | Description | Timeout | Priority | Approx Length
1 | pose(WALK1) | Set servos to animation | 225ms | 1 | 1ms
2 | pose(WALK2) | Set servos to animation | 300ms | 1 | 1ms
3 | analyseWebCam() | detect obstacles | 1000ms | 5 | 2000ms
4 | pathPlanning() | navigate around obstacle| 2000ms | 6 | 4000ms
5 | rechargeOn() | toggle battery recharge | 400ms | 0 | 0.1ms
6 | rechargeOff() | toggle battery recharge | 600ms | 0 | 0.1ms
7 | pose(WALK3) | Set servos to animation | 1200ms | 1 | 1ms


I've used the unix task scheduling priority system - ie, lower is more urgent. As you can see, when I same "time scheduling", I am talking about fractions of seconds into the future, not "Febuary 12, 2012".

The problem with this list is that if each of these is simply swapped to when the previous task is finished, many tasks will be long overdue.

For example, the first two walk animations will happen, and then the battery will start charging and stop 200ms later. So far so good.

The next task is then to take an image from a camera and analyse it. This is a complicated task which takes a very long time (in processor terms). As this task is executing, the timer for WALK3 expires, leaving the robot balancing on one foot! It is stuck there until the image analysis is finished.

Keep in mind that the approximate running times can't be known ahead of time - i'm just estimating them here.

lnxfergy
01-28-2010, 09:50 PM
If we're talking times on the order of several milliseconds, you could probably adapt code similar to the Arduino clock, plus a list of scheduled tasks and the ability to switch between tasks (probably the hardest part):


Use a hardware timer plus an overflow interrupt to update a clock variable.
When the ISR runs, check to see if the current task is of lower priority than an overdue task in the list of scheduled tasks.
If so, switch to the higher priority task.

Obviously, the hardest part is probably the switching -- you'll have to save the context of the current task, which could take a decent amount of time, possibly causing clock stretching (since you're still in the ISR). You'll also need a bit of assembly code to jump into the new task during the ISR return.

-Fergs

MikeG
01-28-2010, 10:19 PM
Like lnxfergy said you would need to figure out a way to switch between tasks while saving state of the current task. IMO, this is more architecture then software. You might consider a multi-core processor or multiple single core processors?

badcommandorfilename
01-29-2010, 08:13 PM
Thanks guys.

If I allow running tasks to be put on hold while higher priority tasks are given processor time, I'm basically writing a multithreaded OS - which is more work than I am looking for.

Granted, it would completely solve the problem - I think I will give femtoOS a look, since apparently it only has about a 1% execution overhead.

If that proves too hard, I might just have to accept that it probably won't be perfect ALL the time. I think that if I allow SOME tasks to run in an interrupt, but forbid particularly long ones from doing that it should be OK most of the time.

Are there any other real time OS's out there which I should look at?

MikeG
01-29-2010, 08:20 PM
Take a look at the Parallax Propeller.
http://www.parallax.com/tabid/407/Default.aspx

bonmot
03-08-2010, 12:51 PM
I have used FREE RTOS, which is pretty good.
What CPU you are using and the frequency? You can always have a fast task for your highest priority task using hardware timer avaliable. I guess balancing is the priority. In the timer you can even halt the RTOS, but you lose a few ticks in the RTOS, but it is manageable.

badcommandorfilename
03-09-2010, 04:38 AM
Yeah, after exploring the available options, I've decided to go with one of the open source RTOSs. Something ultralight, like femtoOS.

In the meantime, I'm just using a funky task-switching main loop which allows me to service tasks at the right time, but doesn't allow me to interrupt and resume them. It's a high latency solution, but I'm still able to get my FFT (http://buildtherobot.blogspot.com/2010/02/robobob-life-of-party.html) happening about 10 times a second.

kyt
03-14-2010, 09:17 PM
Try this: http://courses.cit.cornell.edu/ee476/TinyRealTime/index.html