#2174 closed defect

Memory corruption with EDF scheduler and thread priority queues

Reported by: Sebastian Huber Owned by: Gedare Bloom
Priority: normal Milestone: 4.11
Component: score Version: 4.11
Severity: normal Keywords:
Cc: gedare@… Blocked By:
Blocking:

Description (last modified by Joel Sherrill)

On 2014-03-21 14:51, Gedare Bloom wrote:> On Fri, Mar 21, 2014 at 9:32 AM, Sebastian Huber

<sebastian.huber@…> 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

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

Change History (5)

comment:1 Changed on Mar 25, 2014 at 12:40:38 PM by Gedare Bloom

Cc: Gedare Bloom added

comment:2 Changed on Apr 30, 2014 at 6:15:40 PM by Joel Sherrill

Should the confdefs.h code which sets the "FIXME" flag print a warning that priority blocking and EDF is not currently supported.

comment:3 Changed on Nov 22, 2014 at 4:09:41 PM by Joel Sherrill

Description: modified (diff)
Owner: changed from Joel Sherrill to Gedare Bloom
Status: newassigned

Gedare... you are more familiar with this code than I am. Is it fixed?

comment:4 Changed on Nov 23, 2014 at 7:55:21 PM by Gedare Bloom

Resolution: fixed
Status: assignedclosed
Version: HEAD4.11

--- Comment #2 from Gedare <gedare@…> 2014-03-25 08:40:38 CDT ---
(In reply to comment #1)

I added a workaround for this problem:

http://git.rtems.org/rtems/commit/?id=1fac361fb9d4ec7f5b4ad2801ee6ff5858c82942

Thanks. I see this basically implements #1 described above about not allowing
to block w/ priority. If anyone wants to actually use this EDF scheduler in a
system with priority/deadline-based blocking, they should implement a proper
solution with #2 or #3.

comment:5 Changed on Nov 23, 2014 at 9:40:17 PM by Joel Sherrill

FWIW I also converted the thread queue priority implementation to RBtree which should also be addressing this problem.

There is a separate issue that "get priority" on an EDF thread gives an out of range priority. I think we need to discuss a reasonable approach to this with some academics.

But please let's close this PR.

Note: See TracTickets for help on using tickets.