EDF Scheduler and Priority Queues

[Gedare Bloom]

On Fri, Mar 21, 2014 at 9:32 AM, Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
> Hello,
>
> I changed the objects allocate/free to use the allocator mutex.  This change
> is very important since otherwise the thread dispatch latency depends on the
> heap fragmentation.  I noticed now a problem with the thread priority queues
> and the EDF scheduler.  The EDF scheduler uses priority values greater than
> 255.  Now we have a problem in _Thread_queue_Enqueue_priority():
>
> Thread_blocking_operation_States _Thread_queue_Enqueue_priority (
>   Thread_queue_Control *the_thread_queue,
>   Thread_Control       *the_thread,
>   ISR_Level            *level_p
> )
> {
> [...]
>   _Chain_Initialize_empty( &the_thread->Wait.Block2n );
>
>   priority     = the_thread->current_priority;
>   header_index = _Thread_queue_Header_number( priority );
>   header       = &the_thread_queue->Queues.Priority[ header_index ];
>
> The header_index is now out of range.
>
> Should the EDF scheduler work with thread priority queues?
>
This is tricky. I can see a few possibilities:
1) Do not permit blocking with priority for EDF at least for periodic
tasks.  I'm not sure how to enforce this. For non-periodic tasks, the
priority can be set to <255 but I forget if the upper-bit is used in
current_priority for distinguishing the background from periodic. If
so there needs to be a _Thread_Current_priority() function to abstract
this out.

2) Use deadline folding [hardware-implemented version described in
this paper behind pay wall: http://dl.acm.org/citation.cfm?id=829010 ]
with a max absolute deadline of 256. This permits relative deadlines
between 1 and 127 to be useable. Probably this is OK, but I am not
sure the complexity involved. Again, this requires adding some
abstraction layer to getting priority from TCB.

3) Make the thread priority queue use a more scalable solution.
Probably this can be done by front-loading the cost on the enqueue
path so that dequeue is O(1). Usually, these thread priority queues
should be quite small so the O() may not matter too much.

> --
> Sebastian Huber, embedded brains GmbH
>
> Address : Dornierstr. 4, D-82178 Puchheim, Germany
> Phone   : +49 89 189 47 41-16
> Fax     : +49 89 189 47 41-09
> E-Mail  : sebastian.huber at embedded-brains.de
> PGP     : Public key available on request.
>
> Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel