On Fri, Mar 21, 2014 at 9:32 AM, Sebastian Huber
<sebastian.hu...@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.hu...@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@rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel
_______________________________________________
rtems-devel mailing list
rtems-devel@rtems.org
http://www.rtems.org/mailman/listinfo/rtems-devel
