#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
- 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 03/25/14 at 12:40:38 by Gedare Bloom
Cc: | Gedare Bloom added |
---|
comment:2 Changed on 04/30/14 at 18:15:40 by Joel Sherrill
comment:3 Changed on 11/22/14 at 16:09:41 by Joel Sherrill
Description: | modified (diff) |
---|---|
Owner: | changed from Joel Sherrill to Gedare Bloom |
Status: | new → assigned |
Gedare... you are more familiar with this code than I am. Is it fixed?
comment:4 Changed on 11/23/14 at 19:55:21 by Gedare Bloom
Resolution: | → fixed |
---|---|
Status: | assigned → closed |
Version: | HEAD → 4.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 11/23/14 at 21:40:17 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.
Should the confdefs.h code which sets the "FIXME" flag print a warning that priority blocking and EDF is not currently supported.