[ell-i-developers] Re: Fixed Priority + Round Robin Scheduler
- From: Teemu Hakala <temmi@xxxxxx>
- To: "ell-i-developers@xxxxxxxxxxxxx" <ell-i-developers@xxxxxxxxxxxxx>
- Date: Wed, 12 Feb 2014 06:45:57 +0200
Good morning everyone
I’ll go on quoting the traditional way so as to keep following intra-mail
discussions easier.
On 11.2.2014, at 23:48, Ivan Raul <supra.material@xxxxxxxxx> wrote:
> Before summarizing the possible options, I should state the fact is that the
> development of the scheduler for the Runtime is not halted by the decision of
> the best scheduling algorithm, as the "port" layer and the data structures
> are independent from the scheduling algorithm.
This is very good to point out, thanks. Let the work go on and lets discuss
this scheduler for a while until jumping into the code.
> The easiest to implement (and probably also in memory and processing
> requirements) is to use simple Fixed Priority Preemptive Scheduling (FPPS).
> Then, only two main primitives are available: delay (time), and wait (sync
> event). With that choice, the selection of adequate priorities is essential.
> In general, short execution and low latency are requirements that lead to
> high priority.
As we can separate the scheduler, we can also design the system so that
scheduler is replaceable. This way we can implement one scheduler now and offer
some alternatives later. The first should in my view be the FPPS as it is
simplest and allows us a quick route to release a complete self-standing work.
> A second possibility, implies the use of Aging (increasing the priority of
> low prio. tasks as they wait for the cpu). The main advantage is that the
> possibility of starvation is reduced; the main two disadvantages are that the
> priorities are not fixed anymore (dynamic priority), and that the correct
> implementation of other protocols side to side to aging (such as priority
> inheritance for semaphores) is quite challenging. (Apparently is so relevant
> that the correct implementation of Aging and Priority Inheritance at the same
> time is marketed as an advantage of the Abassi RTOS link). Personally, I
> don't advise this option as medium or short term alternative.
This might be interesting or not interesting, but at least it is very complex
to implement and as well would be complex for application developers to
understand in an efficient manner. Thus, I think we can safely skip this one
alltogether for now and it might well be we’ll never need aging.
On the other hand, since our systems are natively connected to each other and
possibly some nodes in the network are given authoritative roles over others,
individual nodes could implement aging in scheduler while getting hints about
the weighting of processes priorities from the authoritative nodes. This is
very much dependent of the distributed application and I think mostly concerns
multifunction nodes that also have complex sleep patterns and starved
resources. I’m not worried this will come up very soon in requirements.
> A third possibility is to use the approach of priority grouping, as ChibiOS,
> FreeRTOS, uC/OS-III and others. I think this could be the next step after the
> simple FPPS is in the mature state. Although I am not completely sure if
> those characteristics will really be needed at some point. With this option,
> the yield primitive is available in the restricted sense of giving the CPU to
> other same priority tasks.
This, in my view, should be the next scheduler to offer as alternative. We
should ship the system with FPPS and offer a priority grouping scheduler as
alternative from the repository. Our target audience at this moment is more or
less the long tail of developers, who have wildly varying talent levels. The
Arduino-loving folks will not be giving any thought about scheduler and mostly
are developing a single task, so the systems are most likely to have as many
tasks as our kernel internally has plus one. The more advanced developers
should be able to change the scheduler at will if it has a makefile option,
which I think it should.
> Regarding tasks, I also wanted to ask if there is already some idea of the
> "average" number of tasks that are planned to be running on the Ellduino /
> Baselli / Flotelli?
I think the big idea is to push nodes out to the extremes, where things happen
in the real life. Every sensor in a building would eventually have its own
ELL-i node and the number of tasks would be perhaps two or three. In the
meantime, while we are waiting for world domination, a single node might have a
number of sensors and things attached and we should expect something like two
to eight tasks.
This is a very rough guess based on a "just thought about this during first
morning coffee" breakdown analysis of a few ELL-i nodes we have been thinking
about, so I might be off a bit or more.
All in all, a very good summary from Ivan, thank you.
- t
Other related posts:
