[RTEMS Project] #4534: SMP EDF scheduler violates priority group ordering

[RTEMS trac]

#4534: SMP EDF scheduler violates priority group ordering
--------------------------------+------------------------------
 Reporter:  Sebastian Huber     |       Owner:  Sebastian Huber
     Type:  defect              |      Status:  assigned
 Priority:  normal              |   Milestone:  6.1
Component:  score               |     Version:  5
 Severity:  normal              |  Resolution:
 Keywords:  SMP, qualification  |  Blocked By:
 Blocking:                      |
--------------------------------+------------------------------
Description changed by Sebastian Huber:

Old description:

> The SMP EDF scheduler supports one-to-one and one-to-all thread to
> processor affinities.  The one-to-one thread to processor affinity
> introduces a constraint on the ordering of threads.  The implementation
> uses one ready queue for threads which have a one-to-all affinity and one
> for each one-to-one affinity group.  To order threads across the ready
> queues, a generation number is used.  However, the approach to update the
> generation number each time a thread is inserted into a ready queue is
> wrong. The generation number need to be updated only in the enqueue and
> enqueue scheduled operations where an insert priority is available. The
> scheduled chain needs to take the generation number into account.
>
> An example scenario which shows the bug is this. Let T be a high priority
> task affine to processor X. Let A be a lower priority task affine to
> processor X. Let B be a lower priority task with no affinity to a
> particular processor which executes on processor Y. Let B be in the same
> priority group than A and after A. Let A set the affinity to all
> processors. Now A (higher priority relative to B) should execute on X and
> T (high priority) should execute on Y.

New description:

 The SMP EDF scheduler supports one-to-one and one-to-all thread to
 processor affinities.  The one-to-one thread to processor affinity
 introduces a constraint on the ordering of threads.  The implementation
 uses one ready queue for threads which have a one-to-all affinity and one
 for each one-to-one affinity group.  To order threads across the ready
 queues, a generation number is used.  However, the approach to update the
 generation number each time a thread is inserted into a ready queue is
 wrong. The generation number need to be updated only in the enqueue and
 enqueue scheduled operations where an insert priority is available. The
 scheduled chain needs to take the generation number into account.

 An example scenario which shows the bug is this. Let T be a high priority
 task affine to processor X. Let A be a lower priority task affine to
 processor X. Let B be a lower priority task with no affinity to a
 particular processor which executes on processor Y. Let B be in the same
 priority group than A and after A. Let T set the affinity to all
 processors. Now A (higher priority relative to B) should execute on X and
 T (high priority) should execute on Y.

--

--
Ticket URL: <http://devel.rtems.org/ticket/4534#comment:1>
RTEMS Project <http://www.rtems.org/>
RTEMS Project