#2174: Memory corruption with EDF scheduler and thread priority queues
-----------------------------+-----------------------
Reporter: sebastian.huber | Owner: gedare
Type: defect | Status: assigned
Priority: normal | Milestone: 4.11
Component: cpukit | Version: HEAD
Severity: normal | Resolution:
Keywords: |
-----------------------------+-----------------------
Changes (by joel.sherrill):
* owner: joel.sherrill => gedare
* status: new => assigned
Old description:
> On 2014-03-21 14:51, Gedare Bloom wrote:> 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.
New description:
On 2014-03-21 14:51, Gedare Bloom wrote:> 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.
--
Comment:
Gedare... you are more familiar with this code than I am. Is it fixed?
--
Ticket URL: <http://devel.rtems.org/ticket/2174#comment:3>
RTEMS Project <http://www.rtems.org/>
RTEMS Project
_______________________________________________
bugs mailing list
bugs@rtems.org
http://lists.rtems.org/mailman/listinfo/bugs
