From 15dbc710b62084e101bd2a46b3faa1ddc7ee417e Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Thu, 29 Jun 2017 09:44:16 +0200 Subject: score: Add red-black tree node to Scheduler_Node In SMP configurations, add a red-black tree node to Scheduler_Node to enable an EDF scheduler implementation. Update #3056. --- cpukit/score/include/rtems/score/schedulernode.h | 14 ++++++++------ .../include/rtems/score/schedulerprioritysmpimpl.h | 14 +++++++------- cpukit/score/include/rtems/score/schedulersmpimpl.h | 18 +++++++++--------- 3 files changed, 24 insertions(+), 22 deletions(-) (limited to 'cpukit/score/include/rtems') diff --git a/cpukit/score/include/rtems/score/schedulernode.h b/cpukit/score/include/rtems/score/schedulernode.h index 09d03d4e59..1474b0c13c 100644 --- a/cpukit/score/include/rtems/score/schedulernode.h +++ b/cpukit/score/include/rtems/score/schedulernode.h @@ -67,14 +67,16 @@ struct Scheduler_Node { /** * @brief Chain node for usage in various scheduler data structures. * - * Strictly this is the wrong place for this field since the data structures + * Strictly, this is the wrong place for this field since the data structures * to manage scheduler nodes belong to the particular scheduler - * implementation. Currently all SMP scheduler implementations use chains. - * The node is here to simplify things, just like the object node in the - * thread control block. It may be replaced with a union to add a red-black - * tree node in the future. + * implementation. Currently, all SMP scheduler implementations use chains + * or red-black trees. The node is here to simplify things, just like the + * object node in the thread control block. */ - Chain_Node Node; + union { + Chain_Node Chain; + RBTree_Node RBTree; + } Node; /** * @brief The sticky level determines if this scheduler node should use an diff --git a/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h b/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h index 5136565bbe..f37414c7a8 100644 --- a/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h +++ b/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h @@ -75,9 +75,9 @@ static inline void _Scheduler_priority_SMP_Move_from_scheduled_to_ready( Scheduler_priority_SMP_Node *node = _Scheduler_priority_SMP_Node_downcast( scheduled_to_ready ); - _Chain_Extract_unprotected( &node->Base.Base.Node ); + _Chain_Extract_unprotected( &node->Base.Base.Node.Chain ); _Scheduler_priority_Ready_queue_enqueue_first( - &node->Base.Base.Node, + &node->Base.Base.Node.Chain, &node->Ready_queue, &self->Bit_map ); @@ -94,13 +94,13 @@ static inline void _Scheduler_priority_SMP_Move_from_ready_to_scheduled( _Scheduler_priority_SMP_Node_downcast( ready_to_scheduled ); _Scheduler_priority_Ready_queue_extract( - &node->Base.Base.Node, + &node->Base.Base.Node.Chain, &node->Ready_queue, &self->Bit_map ); _Chain_Insert_ordered_unprotected( &self->Base.Scheduled, - &node->Base.Base.Node, + &node->Base.Base.Node.Chain, _Scheduler_SMP_Insert_priority_fifo_order ); } @@ -116,7 +116,7 @@ static inline void _Scheduler_priority_SMP_Insert_ready_lifo( _Scheduler_priority_SMP_Node_downcast( thread ); _Scheduler_priority_Ready_queue_enqueue( - &node->Base.Base.Node, + &node->Base.Base.Node.Chain, &node->Ready_queue, &self->Bit_map ); @@ -133,7 +133,7 @@ static inline void _Scheduler_priority_SMP_Insert_ready_fifo( _Scheduler_priority_SMP_Node_downcast( thread ); _Scheduler_priority_Ready_queue_enqueue_first( - &node->Base.Base.Node, + &node->Base.Base.Node.Chain, &node->Ready_queue, &self->Bit_map ); @@ -150,7 +150,7 @@ static inline void _Scheduler_priority_SMP_Extract_from_ready( _Scheduler_priority_SMP_Node_downcast( thread ); _Scheduler_priority_Ready_queue_extract( - &node->Base.Base.Node, + &node->Base.Base.Node.Chain, &node->Ready_queue, &self->Bit_map ); diff --git a/cpukit/score/include/rtems/score/schedulersmpimpl.h b/cpukit/score/include/rtems/score/schedulersmpimpl.h index d91a62c3ca..b90c359d4c 100644 --- a/cpukit/score/include/rtems/score/schedulersmpimpl.h +++ b/cpukit/score/include/rtems/score/schedulersmpimpl.h @@ -608,9 +608,9 @@ static inline Scheduler_Node *_Scheduler_SMP_Get_lowest_scheduled( (void) filter; (void) order; - _Assert( &lowest_scheduled->Node != _Chain_Tail( scheduled ) ); + _Assert( &lowest_scheduled->Node.Chain != _Chain_Tail( scheduled ) ); _Assert( - _Chain_Next( &lowest_scheduled->Node ) == _Chain_Tail( scheduled ) + _Chain_Next( &lowest_scheduled->Node.Chain ) == _Chain_Tail( scheduled ) ); return lowest_scheduled; @@ -708,7 +708,7 @@ static inline bool _Scheduler_SMP_Enqueue_ordered( lowest_scheduled = ( *get_lowest_scheduled )( context, node, order ); - if ( ( *order )( &node->Node, &lowest_scheduled->Node ) ) { + if ( ( *order )( &node->Node.Chain, &lowest_scheduled->Node.Chain ) ) { _Scheduler_SMP_Enqueue_to_scheduled( context, node, @@ -769,7 +769,7 @@ static inline bool _Scheduler_SMP_Enqueue_scheduled_ordered( */ if ( node->sticky_level > 0 - && ( *order )( &node->Node, &highest_ready->Node ) + && ( *order )( &node->Node.Chain, &highest_ready->Node.Chain ) ) { ( *insert_scheduled )( context, node ); @@ -859,7 +859,7 @@ static inline void _Scheduler_SMP_Extract_from_scheduled( Scheduler_Node *node ) { - _Chain_Extract_unprotected( &node->Node ); + _Chain_Extract_unprotected( &node->Node.Chain ); } static inline void _Scheduler_SMP_Schedule_highest_ready( @@ -1109,7 +1109,7 @@ static inline void _Scheduler_SMP_Insert_scheduled_lifo( _Chain_Insert_ordered_unprotected( &self->Scheduled, - &node_to_insert->Node, + &node_to_insert->Node.Chain, _Scheduler_SMP_Insert_priority_lifo_order ); } @@ -1123,7 +1123,7 @@ static inline void _Scheduler_SMP_Insert_scheduled_fifo( _Chain_Insert_ordered_unprotected( &self->Scheduled, - &node_to_insert->Node, + &node_to_insert->Node.Chain, _Scheduler_SMP_Insert_priority_fifo_order ); } @@ -1154,7 +1154,7 @@ static inline bool _Scheduler_SMP_Ask_for_help( node_state = _Scheduler_SMP_Node_state( node ); if ( node_state == SCHEDULER_SMP_NODE_BLOCKED ) { - if ( ( *order )( &node->Node, &lowest_scheduled->Node ) ) { + if ( ( *order )( &node->Node.Chain, &lowest_scheduled->Node.Chain ) ) { _Thread_Scheduler_cancel_need_for_help( thread, _Thread_Get_CPU( thread ) @@ -1297,7 +1297,7 @@ static inline void _Scheduler_SMP_Add_processor( if ( ( *has_ready )( &self->Base ) ) { ( *enqueue_scheduled_fifo )( &self->Base, node ); } else { - _Chain_Append_unprotected( &self->Scheduled, &node->Node ); + _Chain_Append_unprotected( &self->Scheduled, &node->Node.Chain ); } } -- cgit v1.2.3