Changeset b9990b8d in rtems


Ignore:
Timestamp:
10/27/21 06:48:47 (8 months ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
master
Children:
f767ef80
Parents:
6d20f0c5
git-author:
Sebastian Huber <sebastian.huber@…> (10/27/21 06:48:47)
git-committer:
Sebastian Huber <sebastian.huber@…> (11/23/21 10:00:28)
Message:

score: Fix SMP EDF priority group ordering

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 was wrong. The generation number needs 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.

Close #4534.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • cpukit/score/src/scheduleredfsmp.c

    r6d20f0c5 rb9990b8d  
    6868}
    6969
     70static inline bool _Scheduler_EDF_SMP_Overall_less_equal(
     71  const void       *key,
     72  const Chain_Node *to_insert,
     73  const Chain_Node *next
     74)
     75{
     76  Priority_Control              insert_priority;
     77  Priority_Control              next_priority;
     78  const Scheduler_EDF_SMP_Node *node_to_insert;
     79  const Scheduler_EDF_SMP_Node *node_next;
     80
     81  insert_priority = *(const Priority_Control *) key;
     82  insert_priority = SCHEDULER_PRIORITY_PURIFY( insert_priority );
     83  node_to_insert = (const Scheduler_EDF_SMP_Node *) to_insert;
     84  node_next = (const Scheduler_EDF_SMP_Node *) next;
     85  next_priority = node_next->Base.priority;
     86
     87  return insert_priority < next_priority ||
     88    ( insert_priority == next_priority &&
     89      node_to_insert->generation <= node_next->generation );
     90}
     91
    7092void _Scheduler_EDF_SMP_Initialize( const Scheduler_Control *scheduler )
    7193{
     
    242264}
    243265
     266static inline void _Scheduler_EDF_SMP_Update_generation(
     267  Scheduler_Context *context,
     268  Scheduler_Node    *node_base,
     269  Priority_Control   insert_priority
     270)
     271{
     272  Scheduler_EDF_SMP_Context *self;
     273  Scheduler_EDF_SMP_Node    *node;
     274  int                        generation_index;
     275  int                        increment;
     276  int64_t                    generation;
     277
     278  self = _Scheduler_EDF_SMP_Get_self( context );
     279  node = _Scheduler_EDF_SMP_Node_downcast( node_base );
     280  generation_index = SCHEDULER_PRIORITY_IS_APPEND( insert_priority );
     281  increment = ( generation_index << 1 ) - 1;
     282
     283  generation = self->generations[ generation_index ];
     284  node->generation = generation;
     285  self->generations[ generation_index ] = generation + increment;
     286}
     287
    244288static inline void _Scheduler_EDF_SMP_Insert_scheduled(
    245289  Scheduler_Context *context,
     
    258302  ready_queue = &self->Ready[ rqi ];
    259303
    260   _Scheduler_SMP_Insert_scheduled( context, node_base, priority_to_insert );
     304  _Chain_Insert_ordered_unprotected(
     305    &self->Base.Scheduled,
     306    &node_base->Node.Chain,
     307    &priority_to_insert,
     308    _Scheduler_EDF_SMP_Overall_less_equal
     309  );
    261310
    262311  if ( rqi != 0 ) {
     
    294343  uint8_t                        rqi;
    295344  Scheduler_EDF_SMP_Ready_queue *ready_queue;
    296   int                            generation_index;
    297   int                            increment;
    298   int64_t                        generation;
    299345
    300346  self = _Scheduler_EDF_SMP_Get_self( context );
    301347  node = _Scheduler_EDF_SMP_Node_downcast( node_base );
    302348  rqi = node->ready_queue_index;
    303   generation_index = SCHEDULER_PRIORITY_IS_APPEND( insert_priority );
    304   increment = ( generation_index << 1 ) - 1;
    305349  ready_queue = &self->Ready[ rqi ];
    306 
    307   generation = self->generations[ generation_index ];
    308   node->generation = generation;
    309   self->generations[ generation_index ] = generation + increment;
    310350
    311351  _Scheduler_EDF_SMP_Activate_ready_queue_if_necessary( self, rqi, ready_queue );
     
    510550)
    511551{
     552  _Scheduler_EDF_SMP_Update_generation( context, node, insert_priority );
     553
    512554  return _Scheduler_SMP_Enqueue(
    513555    context,
    514556    node,
    515557    insert_priority,
    516     _Scheduler_SMP_Priority_less_equal,
     558    _Scheduler_EDF_SMP_Overall_less_equal,
    517559    _Scheduler_EDF_SMP_Insert_ready,
    518560    _Scheduler_EDF_SMP_Insert_scheduled,
     
    532574)
    533575{
     576  _Scheduler_EDF_SMP_Update_generation( context, node, insert_priority );
    534577  _Scheduler_SMP_Enqueue_scheduled(
    535578    context,
    536579    node,
    537580    insert_priority,
    538     _Scheduler_SMP_Priority_less_equal,
     581    _Scheduler_EDF_SMP_Overall_less_equal,
    539582    _Scheduler_EDF_SMP_Extract_from_ready,
    540583    _Scheduler_EDF_SMP_Get_highest_ready,
     
    576619    the_thread,
    577620    node,
    578     _Scheduler_SMP_Priority_less_equal,
     621    _Scheduler_EDF_SMP_Overall_less_equal,
    579622    _Scheduler_EDF_SMP_Insert_ready,
    580623    _Scheduler_EDF_SMP_Insert_scheduled,
     
    705748  idle = _Scheduler_EDF_SMP_Node_downcast( idle_base );
    706749  _Scheduler_EDF_SMP_Set_allocated( self, idle, cpu );
     750  _Scheduler_EDF_SMP_Update_generation(
     751    context,
     752    idle_base,
     753    PRIORITY_GROUP_LAST
     754  );
    707755}
    708756
Note: See TracChangeset for help on using the changeset viewer.