summaryrefslogtreecommitdiffstats
path: root/cpukit
diff options
context:
space:
mode:
authorSebastian Huber <sebastian.huber@embedded-brains.de>2021-10-27 08:48:47 +0200
committerSebastian Huber <sebastian.huber@embedded-brains.de>2021-11-23 11:00:28 +0100
commitb9990b8d46812766c8ca0ce5523a035be16f83a7 (patch)
tree427010b001141613531f7285449cd05f19e13ca4 /cpukit
parentscore: Add node to insert to Chain_Node_order (diff)
downloadrtems-b9990b8d46812766c8ca0ce5523a035be16f83a7.tar.bz2
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.
Diffstat (limited to 'cpukit')
-rw-r--r--cpukit/score/src/scheduleredfsmp.c74
1 files changed, 61 insertions, 13 deletions
diff --git a/cpukit/score/src/scheduleredfsmp.c b/cpukit/score/src/scheduleredfsmp.c
index 28266dd13d..7a1c3c598d 100644
--- a/cpukit/score/src/scheduleredfsmp.c
+++ b/cpukit/score/src/scheduleredfsmp.c
@@ -67,6 +67,28 @@ static inline bool _Scheduler_EDF_SMP_Priority_less_equal(
return prio_left <= prio_right;
}
+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 )
{
Scheduler_EDF_SMP_Context *self =
@@ -241,6 +263,28 @@ static inline Scheduler_Node *_Scheduler_EDF_SMP_Get_lowest_scheduled(
return _Scheduler_SMP_Get_lowest_scheduled( context, filter_base );
}
+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,
Scheduler_Node *node_base,
@@ -257,7 +301,12 @@ static inline void _Scheduler_EDF_SMP_Insert_scheduled(
rqi = node->ready_queue_index;
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 ) {
ready_queue->affine_scheduled = node;
@@ -293,21 +342,12 @@ static inline void _Scheduler_EDF_SMP_Insert_ready(
Scheduler_EDF_SMP_Node *node;
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 );
_RBTree_Initialize_node( &node->Base.Base.Node.RBTree );
_RBTree_Insert_inline(
@@ -509,11 +549,13 @@ static inline bool _Scheduler_EDF_SMP_Enqueue(
Priority_Control insert_priority
)
{
+ _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,
_Scheduler_EDF_SMP_Move_from_scheduled_to_ready,
@@ -531,11 +573,12 @@ static inline void _Scheduler_EDF_SMP_Enqueue_scheduled(
Priority_Control insert_priority
)
{
+ _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,
_Scheduler_EDF_SMP_Insert_ready,
@@ -575,7 +618,7 @@ static inline bool _Scheduler_EDF_SMP_Do_ask_for_help(
context,
the_thread,
node,
- _Scheduler_SMP_Priority_less_equal,
+ _Scheduler_EDF_SMP_Overall_less_equal,
_Scheduler_EDF_SMP_Insert_ready,
_Scheduler_EDF_SMP_Insert_scheduled,
_Scheduler_EDF_SMP_Move_from_scheduled_to_ready,
@@ -704,6 +747,11 @@ static inline void _Scheduler_EDF_SMP_Register_idle(
self = _Scheduler_EDF_SMP_Get_self( context );
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
+ );
}
void _Scheduler_EDF_SMP_Add_processor(