[ell-i-developers] Re: Fixed Priority + Round Robin Scheduler

  • From: Ivan Raul <supra.material@xxxxxxxxx>
  • To: ell-i-developers@xxxxxxxxxxxxx
  • Date: Tue, 11 Feb 2014 23:48:19 +0200

Dear All, Good Evening.

Sorry, this message turned out to be quite long...

I had have a considerable trouble about the "yield" primitive adapted to
Fixed Priority Preemptive Scheduling (or more general Priority Preemptive

In general, the yield primitive is only used for Cooperative Scheduling,
where all tasks share the same priority. In those systems, there is some
kind of trust that the threads will not be greedy, or in schemes such as
Round Robin, it is clear that the given time will benefit all the other
threads in the system.

On the opposite side, with Priority Scheduling starvation is possible. In
general, it is possible that the lower priority threads never get CPU
access during unbounded periods of time. In some way it makes sense. Such
systems are mainly designed for Real Time, where there are process that
require a very low latency, and others that are not that important. Another
property with Priority Scheduling is that in the case of overload, it is
already known that the higher priority tasks will be the last to suffer.
Another characteristic of Real Time systems is that in general tasks have
periodic behavior, thus allowing that other tasks to take the CPU while the
next event comes.

As systems generally require both characteristics, modern systems (Windows
NT family, Mac OS, Linux) schedule by priority groups. Tasks are grouped in
priorities, which follow the rules of higher priorities can preempt lower
priorities, and inside each group, they use other algorithm like RR or FCFS
to schedule the tasks.

In general, all the RTOS that I have inspected so far provide the hybrid
approach. It translates into the characteristic of "multiple tasks with the
same priority". As expected, the yield primitive is present on those
systems, but it only allows to yield the CPU to tasks of the same queue or
priority level. In other words, the yield primitive only operates on the
priority level and has no effect to trigger lower priority tasks or prevent
preemption from higher priority elements.

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.

In summary, the next options are the ones I consider as possible design

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.

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
Personally, I don't advise this option as medium or short term alternative.

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.

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?

With Best Regards, and Waiting for Your Comments,

Ivan Raul

On Sat, Feb 8, 2014 at 11:35 PM, Ivan Raul <supra.material@xxxxxxxxx> wrote:

> Dear All, Good Evening
> For the initial implementation of the scheduler, I'm planning to use only
> fixed priority scheduling. In particular, there is only one task that at
> any priority level.
> The real question goes here: I was planning to design the code in a way
> that is prepared for, later, add the possibility of multiple tasks at the
> same level scheduled by round robin (As in ChibiOS, FreeRTOS and
> uC/OS-III). The point is, will it really be needed in the future?
> From what I have seen through the implementations, it increases the
> complexity and memory required. In particular, the remake of uC/OS III from
> II made the ready list data structure far more complex. In the side of
> ChibiOS it was designed like that, and includes a flag to remove that
> option, what in theory reduces memory and execution time, but I haven't
> checked fully. About FreeRTOS I haven't checked.
> In the meanwhile, I send the current state of the analysis I've made of
> the schedulers that Pekka kinly suggested (FreeRTOS is still missing). Does
> anyone know any other good Open Source RTOS / OS / Scheduler worth
> checking?:
> N = Number of Tasks
> ChibiOS,
>      Get Highest Priority Ready Task -> O(1),
>      Insert Ready Task -> O(N)
>      Underlying Data Structure -> Doubly Linked List
> uC/OS-II,
>      Get Highest Priority Ready Task -> O(1),
>      Insert Ready Task -> O(1)
>      Underlying Data Structure -> Bitmap
> uC/OS-III,
>      Get Highest Priority Ready Task -> O(N),
>      Insert Ready Task -> O(1)
>      Underlying Data Structure -> Bitmap + Doubly Linked List
> Thank you in advance for you comments,
> With Warm Regards, Ivan Raul

Other related posts: