Scheduling cooperative tasks waiting on a delay.

Projects General Guidance
1

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 and are known in advance.

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

2

I have no advice to offer but your simple yield and resume system might be useful for a project I am tinkering with. Would you be prepared to share your code, or even a description of the process you are using?

Thanks

...R

3

The code is open source and can be found here:
https://atl.codeplex.com/SourceControl/changeset/view/102681#2066544

4

Somebody has already implemented a timer library which manages callbacks at defined intervals or after defined one-off delays. Obviously, since there is only a single physical processor core, where there are conflicting timer requirements one has to be given precedence. Without any explicit prioritisation scheme, it might just be 'first come, first served'.

My view is that these microcontrollers do not have sufficient resources available to warrant the overheads of these scheduling systems. Emulating multi-threaded execution requires a stack per thread and the memory requirements grow substantially - in such a memory-constrained system, that's a recipe for disaster. Then you probably also need some sort of synchronisation mechanism, adding further code space, processing and memory overhead. Put another way - if your system is complex enough to justify the overhead of an emulated multi-threaded environment, it's unlikely that Arduino is a suitable platform to run it on.

The need for multi-threading can be eliminated simply and easily by designing the code to be non-blocking, and IMO that's a far more sensible approach in this environment.

5

I have not mentioned nor do I mean a (preemptive) multi-threading system. I mean a cooperative multi-tasking system. No extra stacks, no overhead - as I said - lightweight - and as you call it - non-blocking. I totally agree with you on the idea that a resource constrained processor (MCU) is no place for fancy multi-threading stuff. In fact my library is geared toward consuming as few RAM bytes as possible. That makes perhaps for some odd constructions (for those who have not seen them before) but optimum and flexible nonetheless.

The only concern I am trying to address is the timing accuracy of delays that are part of a Task. I was thinking along the lines of a central time keeping class that is used for deciding which waiting (queued) Task is to get priority and be called next.

PeterH:
Somebody has already implemented a timer library which manages callbacks at defined intervals or after defined one-off delays. Obviously, since there is only a single physical processor core, where there are conflicting timer requirements one has to be given precedence. Without any explicit prioritisation scheme, it might just be 'first come, first served'.

Any specifics on who that somebody might be?

6

obiwanjacobi:
Any specifics on who that somebody might be?

I don't remember the author's name, but I expect that searching the playground or just googling something like "Arduino timer library" would turn it up.

7

There are maybe 2-3 simple schedulers around I think.

Rob

8

This library replicates the task scheduler from Bitlash for Arduino C functions:

Simple non-pre-emptive round-robin scheduling seems to be tunable to more or less work in most of the cases I've seen.

But I wouldn't expect to run a lot of 5-20 ms tasks. In Bitlash, the keyboard response stays pretty lively until the fastest intertask interval goes below about 50ms. Simple tasks (in Bitlash) run fine down into the 10-20 ms range, at which point you're basically running the task every time through the scheduler.

-br

9

If you enter "multitasking" into the Forum Search window, you'll find dozens
of previous discussions.

There was a guy named Morris Dovey, who had a lot of good ideas about a year
ago, eg see
http://arduino.cc/forum/index.php/topic,91874.0.html

10

Using this method: [Code Share] Simple lightweight cooperative multi-tasking code - Libraries - Arduino Forum

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.

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.

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.

#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.

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.

Thanx for all the feedback.

11

I would appreciate it if you could post the complete code for your Arduino demo as I don't immediately see how the parts hang together.

...R

12

Robin2:
I would appreciate it if you could post the complete code for your Arduino demo as I don't immediately see how the parts hang together.

All that is missing is the Time class which is basically a call to millis(). The Time class just remembers the last value returned by millis(). Its Update method calls millis() and returns the delta bewteen the last time and the current time.

Other than that, everything is there.

The Delay class manages a group of delay times for different tasks. Each cycle through loop() the time is updated and all tasks are called. Each tasks calls the Delay::Wait() method again which will return true when the delay wait is done. Then the task continues executing (toggle led) and does it again (while loop): wait for the delay etc.

I suggest you read the article so you get a notion on how the Task_Xxxx macros work. It's basically a switch statement.

Otherwise, can ask a concrete question so I can help you understand?

13

Thanks.

I think I have figured out how it works. What I don't know is how to package a complete sketch so that it will work on an Arduino - hence my request for a copy of the whole thing as a single file (plus any extra files such as .h files if they are necessary.)

It does seem that this concept is a trick that can be played with the C++ compiler. JRuby is 'too clever' to allow it :slight_smile:

...R

14

I have each class in its own .h (and sometime .cpp) file. Just include those in the .pde/.ino and you're good to go. The last code block, with setup() and loop() is the .pde file.

It is indeed a quirk in C++ that is exploited here. It seems to work fine and is very optimal/light weight.

15

Do you mean include as 'cut and paste' or as #include? If the latter where should the .h files be saved?

Also, in reply #9 you have 3 pieces of code - are those all the pieces? What should each be called?

As part of figuring out how "your" system works I replaced the macros in your example with the code the macros would produce (I haven't tried to run it) and it seems to me it is conceptually identical to the State system that PeterH suggested in the other Topic. Except that I would prefer to be debugging PeterH's system if things go wrong.

...R

16

Save all the code of the the Delay class in a separate file called Delay.h. You will need to add #include statements to the Delay.h file to resolve dependencies the Delay class needs.
Same goes for the BlinkLedTask.

Then #include these files in the main sketch. Compile, upload and blink away XD

17

There seems to be a need for a Time class but I can't figure out where that comes from?

...R

18

Like I said, basically a wrapper around millis().

class Time
{
public:
	Time() : _ticks(0)
	{
		Update();
	}

	unsigned long Update()
	{
		unsigned long previous = _ticks;

		_ticks = millis();

		return _ticks - previous;
	}

private:
	unsigned long _ticks;
};
19

I've put that in a file called Time.h and referred to it with #include<Time.h> and it still says "‘Time’ does not name a type"

Rather than this piecemeal approach could you please put ALL the necessary parts into a zip file that I can extract and "it just works".

Thanks

...R

20

Robin2:
[..] and it seems to me it is conceptually identical to the State system that PeterH suggested in the other Topic. Except that I would prefer to be debugging PeterH's system if things go wrong.

I suggest you use his code...