Changeset b9990b8d in rtems

Timestamp:

10/27/21 06:48:47 (2 years 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:

• cpukit/score/src/scheduleredfsmp.c (modified) (8 diffs)

cpukit/score/src/scheduleredfsmp.c

@@ -68 +68 @@
 }
 
+static inline bool _Scheduler_EDF_SMP_Overall_less_equal(
+  const void       *key,
+  const Chain_Node *to_insert,
+  const Chain_Node *next
+)
+{
+  Priority_Control              insert_priority;
+  Priority_Control              next_priority;
+  const Scheduler_EDF_SMP_Node *node_to_insert;
+  const Scheduler_EDF_SMP_Node *node_next;
+
+  insert_priority = *(const Priority_Control *) key;
+  insert_priority = SCHEDULER_PRIORITY_PURIFY( insert_priority );
+  node_to_insert = (const Scheduler_EDF_SMP_Node *) to_insert;
+  node_next = (const Scheduler_EDF_SMP_Node *) next;
+  next_priority = node_next->Base.priority;
+
+  return insert_priority < next_priority ||
+    ( insert_priority == next_priority &&
+      node_to_insert->generation <= node_next->generation );
+}
+
 void _Scheduler_EDF_SMP_Initialize( const Scheduler_Control *scheduler )
 {
@@ -242 +264 @@
 }
 
+static inline void _Scheduler_EDF_SMP_Update_generation(
+  Scheduler_Context *context,
+  Scheduler_Node    *node_base,
+  Priority_Control   insert_priority
+)
+{
+  Scheduler_EDF_SMP_Context *self;
+  Scheduler_EDF_SMP_Node    *node;
+  int                        generation_index;
+  int                        increment;
+  int64_t                    generation;
+
+  self = _Scheduler_EDF_SMP_Get_self( context );
+  node = _Scheduler_EDF_SMP_Node_downcast( node_base );
+  generation_index = SCHEDULER_PRIORITY_IS_APPEND( insert_priority );
+  increment = ( generation_index << 1 ) - 1;
+
+  generation = self->generations[ generation_index ];
+  node->generation = generation;
+  self->generations[ generation_index ] = generation + increment;
+}
+
 static inline void _Scheduler_EDF_SMP_Insert_scheduled(
   Scheduler_Context *context,
@@ -258 +302 @@
   ready_queue = &self->Ready[ rqi ];
 
-  _Scheduler_SMP_Insert_scheduled( context, node_base, priority_to_insert );
+  _Chain_Insert_ordered_unprotected(
+    &self->Base.Scheduled,
+    &node_base->Node.Chain,
+    &priority_to_insert,
+    _Scheduler_EDF_SMP_Overall_less_equal
+  );
 
   if ( rqi != 0 ) {
@@ -294 +343 @@
   uint8_t                        rqi;
   Scheduler_EDF_SMP_Ready_queue *ready_queue;
-  int                            generation_index;
-  int                            increment;
-  int64_t                        generation;
 
   self = _Scheduler_EDF_SMP_Get_self( context );
   node = _Scheduler_EDF_SMP_Node_downcast( node_base );
   rqi = node->ready_queue_index;
-  generation_index = SCHEDULER_PRIORITY_IS_APPEND( insert_priority );
-  increment = ( generation_index << 1 ) - 1;
   ready_queue = &self->Ready[ rqi ];
-
-  generation = self->generations[ generation_index ];
-  node->generation = generation;
-  self->generations[ generation_index ] = generation + increment;
 
   _Scheduler_EDF_SMP_Activate_ready_queue_if_necessary( self, rqi, ready_queue );
@@ -510 +550 @@
 )
 {
+  _Scheduler_EDF_SMP_Update_generation( context, node, insert_priority );
+
   return _Scheduler_SMP_Enqueue(
     context,
     node,
     insert_priority,
-    _Scheduler_SMP_Priority_less_equal,
+    _Scheduler_EDF_SMP_Overall_less_equal,
     _Scheduler_EDF_SMP_Insert_ready,
     _Scheduler_EDF_SMP_Insert_scheduled,
@@ -532 +574 @@
 )
 {
+  _Scheduler_EDF_SMP_Update_generation( context, node, insert_priority );
   _Scheduler_SMP_Enqueue_scheduled(
     context,
     node,
     insert_priority,
-    _Scheduler_SMP_Priority_less_equal,
+    _Scheduler_EDF_SMP_Overall_less_equal,
     _Scheduler_EDF_SMP_Extract_from_ready,
     _Scheduler_EDF_SMP_Get_highest_ready,
@@ -576 +619 @@
     the_thread,
     node,
-    _Scheduler_SMP_Priority_less_equal,
+    _Scheduler_EDF_SMP_Overall_less_equal,
     _Scheduler_EDF_SMP_Insert_ready,
     _Scheduler_EDF_SMP_Insert_scheduled,
@@ -705 +748 @@
   idle = _Scheduler_EDF_SMP_Node_downcast( idle_base );
   _Scheduler_EDF_SMP_Set_allocated( self, idle, cpu );
+  _Scheduler_EDF_SMP_Update_generation(
+    context,
+    idle_base,
+    PRIORITY_GROUP_LAST
+  );
 }