diff options
28 files changed, 1399 insertions, 127 deletions
diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am index 6caefb5f10..e4c373c836 100644 --- a/cpukit/score/Makefile.am +++ b/cpukit/score/Makefile.am @@ -133,13 +133,15 @@ endif if HAS_SMP libscore_a_SOURCES += src/percpustatewait.c libscore_a_SOURCES += src/profilingsmplock.c -libscore_a_SOURCES += src/schedulersmpvalidstatechanges.c +libscore_a_SOURCES += src/schedulerchangeroot.c libscore_a_SOURCES += src/schedulerpriorityaffinitysmp.c libscore_a_SOURCES += src/schedulerprioritysmp.c libscore_a_SOURCES += src/schedulersimplesmp.c +libscore_a_SOURCES += src/schedulersmpdebug.c libscore_a_SOURCES += src/smp.c libscore_a_SOURCES += src/cpuset.c libscore_a_SOURCES += src/cpusetprintsupport.c +libscore_a_SOURCES += src/schedulerdefaultaskforhelp.c libscore_a_SOURCES += src/schedulerdefaultgetaffinity.c libscore_a_SOURCES += src/schedulerdefaultsetaffinity.c libscore_a_SOURCES += src/schedulersmpstartidle.c diff --git a/cpukit/score/include/rtems/score/mrspimpl.h b/cpukit/score/include/rtems/score/mrspimpl.h index 6aa45a8c4f..4aaa50bc01 100644 --- a/cpukit/score/include/rtems/score/mrspimpl.h +++ b/cpukit/score/include/rtems/score/mrspimpl.h @@ -42,25 +42,6 @@ extern "C" { #define MRSP_RIVAL_STATE_TIMEOUT 0x2U -RTEMS_INLINE_ROUTINE bool _MRSP_Set_root_visitor( - Resource_Node *node, - void *arg -) -{ - _Resource_Node_set_root( node, arg ); - - return false; -} - -RTEMS_INLINE_ROUTINE void _MRSP_Set_root( - Resource_Node *top, - Resource_Node *root -) -{ - _Resource_Node_set_root( top, root ); - _Resource_Iterate( top, _MRSP_Set_root_visitor, root ); -} - RTEMS_INLINE_ROUTINE void _MRSP_Elevate_priority( MRSP_Control *mrsp, Thread_Control *new_owner, @@ -197,9 +178,10 @@ RTEMS_INLINE_ROUTINE MRSP_Status _MRSP_Wait_for_ownership( _Resource_Node_set_dependency( &executing->Resource_node, &mrsp->Resource ); previous_help_state = _Scheduler_Thread_change_help_state( executing, SCHEDULER_HELP_ACTIVE_RIVAL ); - _MRSP_Set_root( - &executing->Resource_node, - _Resource_Node_get_root( owner ) + + _Scheduler_Thread_change_resource_root( + executing, + _Thread_Resource_node_to_thread( _Resource_Node_get_root( owner ) ) ); if ( timeout > 0 ) { @@ -241,7 +223,7 @@ RTEMS_INLINE_ROUTINE MRSP_Status _MRSP_Wait_for_ownership( _Resource_Node_extract( &executing->Resource_node ); _Resource_Node_set_dependency( &executing->Resource_node, NULL ); _Scheduler_Thread_change_help_state( executing, previous_help_state ); - _MRSP_Set_root( &executing->Resource_node, &executing->Resource_node ); + _Scheduler_Thread_change_resource_root( executing, executing ); _MRSP_Restore_priority( mrsp, executing, initial_priority ); status = MRSP_TIMEOUT; @@ -334,7 +316,7 @@ RTEMS_INLINE_ROUTINE MRSP_Status _MRSP_Release( _Resource_Node_add_resource( &new_owner->Resource_node, &mrsp->Resource ); _Resource_Set_owner( &mrsp->Resource, &new_owner->Resource_node ); _Scheduler_Thread_change_help_state( new_owner, SCHEDULER_HELP_ACTIVE_OWNER ); - _MRSP_Set_root( &new_owner->Resource_node, &new_owner->Resource_node ); + _Scheduler_Thread_change_resource_root( new_owner, new_owner ); _MRSP_Add_state( rival, MRSP_RIVAL_STATE_NEW_OWNER ); } diff --git a/cpukit/score/include/rtems/score/scheduler.h b/cpukit/score/include/rtems/score/scheduler.h index 993ae55b29..8da988fffd 100644 --- a/cpukit/score/include/rtems/score/scheduler.h +++ b/cpukit/score/include/rtems/score/scheduler.h @@ -90,6 +90,31 @@ typedef struct { bool ); +#if defined(RTEMS_SMP) + /** + * Ask for help operation. + * + * @param[in] scheduler The scheduler of the thread offering help. + * @param[in] offers_help The thread offering help. + * @param[in] needs_help The thread needing help. + * + * @retval needs_help It was not possible to schedule the thread needing + * help, so it is returned to continue the search for help. + * @retval next_needs_help It was possible to schedule the thread needing + * help, but this displaced another thread eligible to ask for help. So + * this thread is returned to start a new search for help. + * @retval NULL It was possible to schedule the thread needing help, and no + * other thread needs help as a result. + * + * @see _Scheduler_Ask_for_help(). + */ + Thread_Control *( *ask_for_help )( + const Scheduler_Control *scheduler, + Thread_Control *offers_help, + Thread_Control *needs_help + ); +#endif + /** @see _Scheduler_Node_initialize() */ void ( *node_initialize )( const Scheduler_Control *, Thread_Control * ); @@ -375,6 +400,28 @@ extern const Scheduler_Control _Scheduler_Table[]; extern const Scheduler_Assignment _Scheduler_Assignments[]; #endif +#if defined(RTEMS_SMP) + /** + * @brief Does nothing. + * + * @param[in] scheduler Unused. + * @param[in] offers_help Unused. + * @param[in] needs_help Unused. + * + * @retval NULL Always. + */ + Thread_Control *_Scheduler_default_Ask_for_help( + const Scheduler_Control *scheduler, + Thread_Control *offers_help, + Thread_Control *needs_help + ); + + #define SCHEDULER_OPERATION_DEFAULT_ASK_FOR_HELP \ + _Scheduler_default_Ask_for_help, +#else + #define SCHEDULER_OPERATION_DEFAULT_ASK_FOR_HELP +#endif + /** * @brief Does nothing. * diff --git a/cpukit/score/include/rtems/score/schedulercbs.h b/cpukit/score/include/rtems/score/schedulercbs.h index 008cc91261..b3381e0e43 100644 --- a/cpukit/score/include/rtems/score/schedulercbs.h +++ b/cpukit/score/include/rtems/score/schedulercbs.h @@ -53,6 +53,7 @@ extern "C" { _Scheduler_EDF_Block, /* block entry point */ \ _Scheduler_CBS_Unblock, /* unblock entry point */ \ _Scheduler_EDF_Change_priority, /* change priority entry point */ \ + SCHEDULER_OPERATION_DEFAULT_ASK_FOR_HELP \ _Scheduler_CBS_Node_initialize, /* node initialize entry point */ \ _Scheduler_default_Node_destroy, /* node destroy entry point */ \ _Scheduler_EDF_Update_priority, /* update priority entry point */ \ diff --git a/cpukit/score/include/rtems/score/scheduleredf.h b/cpukit/score/include/rtems/score/scheduleredf.h index 1dda767cf6..e69569156d 100644 --- a/cpukit/score/include/rtems/score/scheduleredf.h +++ b/cpukit/score/include/rtems/score/scheduleredf.h @@ -46,6 +46,7 @@ extern "C" { _Scheduler_EDF_Block, /* block entry point */ \ _Scheduler_EDF_Unblock, /* unblock entry point */ \ _Scheduler_EDF_Change_priority, /* change priority entry point */ \ + SCHEDULER_OPERATION_DEFAULT_ASK_FOR_HELP \ _Scheduler_EDF_Node_initialize, /* node initialize entry point */ \ _Scheduler_default_Node_destroy, /* node destroy entry point */ \ _Scheduler_EDF_Update_priority, /* update priority entry point */ \ diff --git a/cpukit/score/include/rtems/score/schedulerimpl.h b/cpukit/score/include/rtems/score/schedulerimpl.h index 5e4e5098d2..c41c3af3e6 100644 --- a/cpukit/score/include/rtems/score/schedulerimpl.h +++ b/cpukit/score/include/rtems/score/schedulerimpl.h @@ -10,6 +10,7 @@ /* * Copyright (C) 2010 Gedare Bloom. * Copyright (C) 2011 On-Line Applications Research Corporation (OAR). + * Copyright (c) 2014 embedded brains GmbH * * The license and distribution terms for this file may be * found in the file LICENSE in this distribution or at @@ -42,6 +43,13 @@ extern "C" { */ void _Scheduler_Handler_initialization( void ); +RTEMS_INLINE_ROUTINE Scheduler_Context *_Scheduler_Get_context( + const Scheduler_Control *scheduler +) +{ + return scheduler->context; +} + RTEMS_INLINE_ROUTINE const Scheduler_Control *_Scheduler_Get( const Thread_Control *the_thread ) @@ -55,6 +63,19 @@ RTEMS_INLINE_ROUTINE const Scheduler_Control *_Scheduler_Get( #endif } +RTEMS_INLINE_ROUTINE const Scheduler_Control *_Scheduler_Get_own( + const Thread_Control *the_thread +) +{ +#if defined(RTEMS_SMP) + return the_thread->Scheduler.own_control; +#else + (void) the_thread; + + return &_Scheduler_Table[ 0 ]; +#endif +} + RTEMS_INLINE_ROUTINE const Scheduler_Control *_Scheduler_Get_by_CPU_index( uint32_t cpu_index ) @@ -78,6 +99,13 @@ RTEMS_INLINE_ROUTINE const Scheduler_Control *_Scheduler_Get_by_CPU( } #if defined(RTEMS_SMP) +RTEMS_INLINE_ROUTINE Scheduler_Node *_Scheduler_Thread_get_own_node( + const Thread_Control *the_thread +) +{ + return the_thread->Scheduler.own_node; +} + RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Node_get_user( const Scheduler_Node *node ) @@ -117,6 +145,39 @@ RTEMS_INLINE_ROUTINE void _Scheduler_Schedule( Thread_Control *the_thread ) } #if defined(RTEMS_SMP) +typedef struct { + Thread_Control *needs_help; + Thread_Control *next_needs_help; +} Scheduler_Ask_for_help_context ; + +RTEMS_INLINE_ROUTINE bool _Scheduler_Ask_for_help_visitor( + Resource_Node *resource_node, + void *arg +) +{ + bool done; + Scheduler_Ask_for_help_context *help_context = arg; + Thread_Control *previous_needs_help = help_context->needs_help; + Thread_Control *next_needs_help; + Thread_Control *offers_help = + _Thread_Resource_node_to_thread( resource_node ); + const Scheduler_Control *scheduler = _Scheduler_Get_own( offers_help ); + + next_needs_help = ( *scheduler->Operations.ask_for_help )( + scheduler, + offers_help, + previous_needs_help + ); + + done = next_needs_help != previous_needs_help; + + if ( done ) { + help_context->next_needs_help = next_needs_help; + } + + return done; +} + /** * @brief Ask threads depending on resources owned by the thread for help. * @@ -124,13 +185,56 @@ RTEMS_INLINE_ROUTINE void _Scheduler_Schedule( Thread_Control *the_thread ) * pre-emption by a higher priority thread or it was not possible to assign it * a processor since its priority is to low on its current scheduler instance. * + * The run-time of this function depends on the size of the resource tree of + * the thread needing help and other resource trees in case threads in need for + * help are produced during this operation. + * * @param[in] needs_help The thread needing help. */ +RTEMS_INLINE_ROUTINE void _Scheduler_Ask_for_help( + Thread_Control *needs_help +) +{ + do { + const Scheduler_Control *scheduler = _Scheduler_Get_own( needs_help ); + + needs_help = ( *scheduler->Operations.ask_for_help )( + scheduler, + needs_help, + needs_help + ); + + if ( needs_help != NULL ) { + Scheduler_Ask_for_help_context help_context = { needs_help, NULL }; + + _Resource_Iterate( + &needs_help->Resource_node, + _Scheduler_Ask_for_help_visitor, + &help_context + ); + + needs_help = help_context.next_needs_help; + } + } while ( needs_help != NULL ); +} + RTEMS_INLINE_ROUTINE void _Scheduler_Ask_for_help_if_necessary( Thread_Control *needs_help ) { - (void) needs_help; + if ( + needs_help != NULL + && _Resource_Node_owns_resources( &needs_help->Resource_node ) + ) { + Scheduler_Node *node = _Scheduler_Thread_get_own_node( needs_help ); + + if ( + node->help_state != SCHEDULER_HELP_ACTIVE_RIVAL + || _Scheduler_Node_get_user( node ) != needs_help + ) { + _Scheduler_Ask_for_help( needs_help ); + } + } } #endif @@ -218,7 +322,7 @@ RTEMS_INLINE_ROUTINE void _Scheduler_Change_priority( bool prepend_it ) { - const Scheduler_Control *scheduler = _Scheduler_Get( the_thread ); + const Scheduler_Control *scheduler = _Scheduler_Get_own( the_thread ); #if defined(RTEMS_SMP) Thread_Control *needs_help; @@ -426,6 +530,7 @@ RTEMS_INLINE_ROUTINE void _Scheduler_Set( if ( current_scheduler != scheduler ) { _Thread_Set_state( the_thread, STATES_MIGRATING ); _Scheduler_Node_destroy( current_scheduler, the_thread ); + the_thread->Scheduler.own_control = scheduler; the_thread->Scheduler.control = scheduler; _Scheduler_Node_initialize( scheduler, the_thread ); _Scheduler_Update_priority( the_thread, the_thread->current_priority ); @@ -628,13 +733,6 @@ RTEMS_INLINE_ROUTINE void _Scheduler_Change_priority_if_higher( } } -RTEMS_INLINE_ROUTINE Scheduler_Context *_Scheduler_Get_context( - const Scheduler_Control *scheduler -) -{ - return scheduler->context; -} - RTEMS_INLINE_ROUTINE uint32_t _Scheduler_Get_processor_count( const Scheduler_Control *scheduler ) @@ -721,6 +819,29 @@ RTEMS_INLINE_ROUTINE void _Scheduler_Node_do_initialize( } #if defined(RTEMS_SMP) +/** + * @brief Gets an idle thread from the scheduler instance. + * + * @param[in] context The scheduler instance context. + * + * @retval idle An idle thread for use. This function must always return an + * idle thread. If none is available, then this is a fatal error. + */ +typedef Thread_Control *( *Scheduler_Get_idle_thread )( + Scheduler_Context *context +); + +/** + * @brief Releases an idle thread to the scheduler instance for reuse. + * + * @param[in] context The scheduler instance context. + * @param[in] idle The idle thread to release + */ +typedef void ( *Scheduler_Release_idle_thread )( + Scheduler_Context *context, + Thread_Control *idle +); + RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Node_get_owner( const Scheduler_Node *node ) @@ -735,6 +856,50 @@ RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Node_get_idle( return node->idle; } +RTEMS_INLINE_ROUTINE void _Scheduler_Node_set_user( + Scheduler_Node *node, + Thread_Control *user +) +{ + node->user = user; +} + +RTEMS_INLINE_ROUTINE void _Scheduler_Thread_set_node( + Thread_Control *the_thread, + Scheduler_Node *node +) +{ + the_thread->Scheduler.node = node; +} + +RTEMS_INLINE_ROUTINE void _Scheduler_Thread_set_scheduler_and_node( + Thread_Control *the_thread, + Scheduler_Node *node, + const Thread_Control *previous_user_of_node +) +{ + const Scheduler_Control *scheduler = + _Scheduler_Get_own( previous_user_of_node ); + + the_thread->Scheduler.control = scheduler; + _Scheduler_Thread_set_node( the_thread, node ); +} + +extern const bool _Scheduler_Thread_state_valid_state_changes[ 3 ][ 3 ]; + +RTEMS_INLINE_ROUTINE void _Scheduler_Thread_change_state( + Thread_Control *the_thread, + Thread_Scheduler_state new_state +) +{ + _Assert( + _Scheduler_Thread_state_valid_state_changes + [ the_thread->Scheduler.state ][ new_state ] + ); + + the_thread->Scheduler.state = new_state; +} + /** * @brief Changes the scheduler help state of a thread. * @@ -748,13 +913,414 @@ RTEMS_INLINE_ROUTINE Scheduler_Help_state _Scheduler_Thread_change_help_state( Scheduler_Help_state new_help_state ) { - Scheduler_Node *node = _Scheduler_Thread_get_node( the_thread ); + Scheduler_Node *node = _Scheduler_Thread_get_own_node( the_thread ); Scheduler_Help_state previous_help_state = node->help_state; node->help_state = new_help_state; return previous_help_state; } + +/** + * @brief Changes the resource tree root of a thread. + * + * For each node of the resource sub-tree specified by the top thread the + * scheduler asks for help. So the root thread gains access to all scheduler + * nodes corresponding to the resource sub-tree. In case a thread previously + * granted help is displaced by this operation, then the scheduler asks for + * help using its remaining resource tree. + * + * The run-time of this function depends on the size of the resource sub-tree + * and other resource trees in case threads in need for help are produced + * during this operation. + * + * @param[in] top The thread specifying the resource sub-tree top. + * @param[in] root The thread specifying the new resource sub-tree root. + */ +void _Scheduler_Thread_change_resource_root( + Thread_Control *top, + Thread_Control *root +); + +/** + * @brief Use an idle thread for this scheduler node. + * + * A thread in the SCHEDULER_HELP_ACTIVE_OWNER owner state may use an idle + * thread for the scheduler node owned by itself in case it executes currently + * using another scheduler node or in case it is in a blocking state. + * + * @param[in] context The scheduler instance context. + * @param[in] node The node which wants to use the idle thread. + * @param[in] get_idle_thread Function to get an idle thread. + */ +RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Use_idle_thread( + Scheduler_Context *context, + Scheduler_Node *node, + Scheduler_Get_idle_thread get_idle_thread +) +{ + Thread_Control *idle = ( *get_idle_thread )( context ); + + _Assert( node->help_state == SCHEDULER_HELP_ACTIVE_OWNER ); + _Assert( _Scheduler_Node_get_idle( node ) == NULL ); + _Assert( + _Scheduler_Node_get_owner( node ) == _Scheduler_Node_get_user( node ) + ); + + _Scheduler_Thread_set_node( idle, node ); + + _Scheduler_Node_set_user( node, idle ); + node->idle = idle; + + return idle; +} + +/** + * @brief Try to schedule this scheduler node. + * + * @param[in] context The scheduler instance context. + * @param[in] node The node which wants to get scheduled. + * @param[in] get_idle_thread Function to get an idle thread. + * + * @retval true This node can be scheduled. + * @retval false Otherwise. + */ +RTEMS_INLINE_ROUTINE bool _Scheduler_Try_to_schedule_node( + Scheduler_Context *context, + Scheduler_Node *node, + Scheduler_Get_idle_thread get_idle_thread +) +{ + bool schedule; + Thread_Control *owner; + Thread_Control *user; + + if ( node->help_state == SCHEDULER_HELP_YOURSELF ) { + return true; + } + + owner = _Scheduler_Node_get_owner( node ); + user = _Scheduler_Node_get_user( node ); + + if ( node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL) { + if ( user->Scheduler.state == THREAD_SCHEDULER_READY ) { + _Scheduler_Thread_set_scheduler_and_node( user, node, owner ); + } else { + _Scheduler_Node_set_user( node, owner ); + } + + schedule = true; + } else if ( node->help_state == SCHEDULER_HELP_ACTIVE_OWNER ) { + if ( user->Scheduler.state == THREAD_SCHEDULER_READY ) { + _Scheduler_Thread_set_scheduler_and_node( user, node, owner ); + } else { + _Scheduler_Use_idle_thread( context, node, get_idle_thread ); + } + + schedule = true; + } else { + _Assert( node->help_state == SCHEDULER_HELP_PASSIVE ); + + if ( user->Scheduler.state == THREAD_SCHEDULER_READY ) { + _Scheduler_Thread_set_scheduler_and_node( user, node, owner ); + schedule = true; + } else { + schedule = false; + } + } + + return schedule; +} + +/** + * @brief Release an idle thread using this scheduler node. + * + * @param[in] context The scheduler instance context. + * @param[in] node The node which may have an idle thread as user. + * @param[in] release_idle_thread Function to release an idle thread. + * + * @retval idle The idle thread which used this node. + * @retval NULL This node had no idle thread as an user. + */ +RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Release_idle_thread( + Scheduler_Context *context, + Scheduler_Node *node, + Scheduler_Release_idle_thread release_idle_thread +) +{ + Thread_Control *idle = _Scheduler_Node_get_idle( node ); + + if ( idle != NULL ) { + Thread_Control *owner = _Scheduler_Node_get_owner( node ); + + node->idle = NULL; + _Scheduler_Node_set_user( node, owner ); + _Scheduler_Thread_change_state( idle, THREAD_SCHEDULER_READY ); + _Scheduler_Thread_set_node( idle, idle->Scheduler.own_node ); + + ( *release_idle_thread )( context, idle ); + } + + return idle; +} + +/** + * @brief Block this scheduler node. + * + * @param[in] context The scheduler instance context. + * @param[in] node The node which wants to get blocked. + * @param[in] is_scheduled This node is scheduled. + * @param[in] get_idle_thread Function to get an idle thread. + * + * @retval true Continue with the blocking operation. + * @retval false Otherwise. + */ +RTEMS_INLINE_ROUTINE bool _Scheduler_Block_node( + Scheduler_Context *context, + Scheduler_Node *node, + bool is_scheduled, + Scheduler_Get_idle_thread get_idle_thread +) +{ + bool block; + Thread_Control *old_user = _Scheduler_Node_get_user( node ); + Thread_Control *new_user; + + _Scheduler_Thread_change_state( old_user, THREAD_SCHEDULER_BLOCKED ); + + if ( node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL ) { + new_user = _Scheduler_Node_get_owner( node ); + + _Assert( new_user != old_user ); + _Scheduler_Node_set_user( node, new_user ); + } else if ( + node->help_state == SCHEDULER_HELP_ACTIVE_OWNER + && is_scheduled + ) { + new_user = _Scheduler_Use_idle_thread( context, node, get_idle_thread ); + } else { + new_user = NULL; + } + + if ( new_user != NULL && is_scheduled ) { + Per_CPU_Control *cpu = _Thread_Get_CPU( old_user ); + + _Scheduler_Thread_change_state( new_user, THREAD_SCHEDULER_SCHEDULED ); + _Thread_Set_CPU( new_user, cpu ); + _Thread_Dispatch_update_heir( _Per_CPU_Get(), cpu, new_user ); + + block = false; + } else { + block = true; + } + + return block; +} + +/** + * @brief Unblock this scheduler node. + * + * @param[in] context The scheduler instance context. + * @param[in] the_thread The thread which wants to get unblocked. + * @param[in] node The node which wants to get unblocked. + * @param[in] is_scheduled This node is scheduled. + * @param[in] release_idle_thread Function to release an idle thread. + * + * @retval true Continue with the unblocking operation. + * @retval false Otherwise. + */ +RTEMS_INLINE_ROUTINE bool _Scheduler_Unblock_node( + Scheduler_Context *context, + Thread_Control *the_thread, + Scheduler_Node *node, + bool is_scheduled, + Scheduler_Release_idle_thread release_idle_thread +) +{ + bool unblock; + + if ( is_scheduled ) { + Thread_Control *old_user = _Scheduler_Node_get_user( node ); + Per_CPU_Control *cpu = _Thread_Get_CPU( old_user ); + + if ( node->help_state == SCHEDULER_HELP_ACTIVE_OWNER ) { + Thread_Control *idle = _Scheduler_Release_idle_thread( + context, + node, + release_idle_thread + ); + + _Assert( idle != NULL ); + (void) idle; + } else { + _Assert( node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL ); + + _Scheduler_Thread_change_state( old_user, THREAD_SCHEDULER_READY ); + _Scheduler_Node_set_user( node, the_thread ); + } + + _Scheduler_Thread_change_state( the_thread, THREAD_SCHEDULER_SCHEDULED ); + _Thread_Set_CPU( the_thread, cpu ); + _Thread_Dispatch_update_heir( _Per_CPU_Get(), cpu, the_thread ); + + unblock = false; + } else { + _Scheduler_Thread_change_state( the_thread, THREAD_SCHEDULER_READY ); + + unblock = true; + } + + return unblock; +} + +/** + * @brief Asks a ready scheduler node for help. + * + * @param[in] node The ready node offering help. + * @param[in] needs_help The thread needing help. + * + * @retval needs_help The thread needing help. + */ +RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Ask_ready_node_for_help( + Scheduler_Node *node, + Thread_Control *needs_help +) +{ + _Scheduler_Node_set_user( node, needs_help ); + + return needs_help; +} + +/** + * @brief Asks a scheduled scheduler node for help. + * + * @param[in] context The scheduler instance context. + * @param[in] node The scheduled node offering help. + * @param[in] offers_help The thread offering help. + * @param[in] needs_help The thread needing help. + * @param[in] previous_accepts_help The previous thread accepting help by this + * scheduler node. + * @param[in] release_idle_thread Function to release an idle thread. + * + * @retval needs_help The previous thread accepting help by this scheduler node + * which was displaced by the thread needing help. + * @retval NULL There are no more threads needing help. + */ +RTEMS_INLINE_ROUTINE Thread_Control *_Scheduler_Ask_scheduled_node_for_help( + Scheduler_Context *context, + Scheduler_Node *node, + Thread_Control *offers_help, + Thread_Control *needs_help, + Thread_Control *previous_accepts_help, + Scheduler_Release_idle_thread release_idle_thread +) +{ + Thread_Control *next_needs_help = NULL; + Thread_Control *old_user = NULL; + Thread_Control *new_user = NULL; + + if ( + previous_accepts_help != needs_help + && _Scheduler_Thread_get_node( previous_accepts_help ) == node + ) { + Thread_Control *idle = _Scheduler_Release_idle_thread( + context, + node, + release_idle_thread + ); + + if ( idle != NULL ) { + old_user = idle; + } else { + _Assert( _Scheduler_Node_get_user( node ) == previous_accepts_help ); + old_user = previous_accepts_help; + } + + if ( needs_help->Scheduler.state == THREAD_SCHEDULER_READY ) { + new_user = needs_help; + } else { + _Assert( node->help_state == SCHEDULER_HELP_ACTIVE_RIVAL ); + _Assert( offers_help->Scheduler.node == offers_help->Scheduler.own_node ); + + new_user = offers_help; + } + + if ( previous_accepts_help != offers_help ) { + next_needs_help = previous_accepts_help; + } + } else if ( needs_help->Scheduler.state == THREAD_SCHEDULER_READY ) { + Thread_Control *idle = _Scheduler_Release_idle_thread( + context, + node, + release_idle_thread + ); + + if ( idle != NULL ) { + old_user = idle; + } else { + old_user = _Scheduler_Node_get_user( node ); + } + + new_user = needs_help; + } else { + _Assert( needs_help->Scheduler.state == THREAD_SCHEDULER_SCHEDULED ); + } + + if ( new_user != old_user ) { + Per_CPU_Control *cpu_self = _Per_CPU_Get(); + Per_CPU_Control *cpu = _Thread_Get_CPU( old_user ); + + _Scheduler_Thread_change_state( old_user, THREAD_SCHEDULER_READY ); + _Scheduler_Thread_set_scheduler_and_node( + old_user, + _Scheduler_Thread_get_own_node( old_user ), + old_user + ); + + _Scheduler_Thread_change_state( new_user, THREAD_SCHEDULER_SCHEDULED ); + _Scheduler_Thread_set_scheduler_and_node( new_user, node, offers_help ); + + _Scheduler_Node_set_user( node, new_user ); + _Thread_Set_CPU( new_user, cpu ); + _Thread_Dispatch_update_heir( cpu_self, cpu, new_user ); + } + + return next_needs_help; +} + +/** + * @brief Asks a blocked scheduler node for help. + * + * @param[in] context The scheduler instance context. + * @param[in] node The scheduled node offering help. + * @param[in] offers_help The thread offering help. + * @param[in] needs_help The thread needing help. + * + * @retval true Enqueue this scheduler node. + * @retval false Otherwise. + */ +RTEMS_INLINE_ROUTINE bool _Scheduler_Ask_blocked_node_for_help( + Scheduler_Context *context, + Scheduler_Node *node, + Thread_Control *offers_help, + Thread_Control *needs_help +) +{ + bool enqueue; + + _Assert( node->help_state == SCHEDULER_HELP_PASSIVE ); + + if ( needs_help->Scheduler.state == THREAD_SCHEDULER_READY ) { + _Scheduler_Node_set_user( node, needs_help ); + _Scheduler_Thread_set_scheduler_and_node( needs_help, node, offers_help ); + + enqueue = true; + } else { + enqueue = false; + } + + return enqueue; +} #endif /** @} */ diff --git a/cpukit/score/include/rtems/score/schedulerpriority.h b/cpukit/score/include/rtems/score/schedulerpriority.h index 805e30257d..de051a8114 100644 --- a/cpukit/score/include/rtems/score/schedulerpriority.h +++ b/cpukit/score/include/rtems/score/schedulerpriority.h @@ -45,6 +45,7 @@ extern "C" { _Scheduler_priority_Block, /* block entry point */ \ _Scheduler_priority_Unblock, /* unblock entry point */ \ _Scheduler_priority_Change_priority, /* change priority entry point */ \ + SCHEDULER_OPERATION_DEFAULT_ASK_FOR_HELP \ _Scheduler_default_Node_initialize, /* node initialize entry point */ \ _Scheduler_default_Node_destroy, /* node destroy entry point */ \ _Scheduler_priority_Update_priority, /* update priority entry point */ \ diff --git a/cpukit/score/include/rtems/score/schedulerpriorityaffinitysmp.h b/cpukit/score/include/rtems/score/schedulerpriorityaffinitysmp.h index 3a235104cf..91ffcd28e5 100644 --- a/cpukit/score/include/rtems/score/schedulerpriorityaffinitysmp.h +++ b/cpukit/score/include/rtems/score/schedulerpriorityaffinitysmp.h @@ -55,6 +55,7 @@ extern "C" { _Scheduler_priority_affinity_SMP_Block, \ _Scheduler_priority_affinity_SMP_Unblock, \ _Scheduler_priority_affinity_SMP_Change_priority, \ + _Scheduler_priority_affinity_SMP_Ask_for_help, \ _Scheduler_priority_affinity_SMP_Node_initialize, \ _Scheduler_default_Node_destroy, \ _Scheduler_priority_SMP_Update_priority, \ @@ -139,6 +140,12 @@ Thread_Control *_Scheduler_priority_affinity_SMP_Change_priority( bool prepend_it ); +Thread_Control *_Scheduler_priority_affinity_SMP_Ask_for_help( + const Scheduler_Control *scheduler, + Thread_Control *offers_help, + Thread_Control *needs_help +); + /** * @brief Set affinity for the priority affinity SMP scheduler. * diff --git a/cpukit/score/include/rtems/score/schedulerprioritysmp.h b/cpukit/score/include/rtems/score/schedulerprioritysmp.h index a1a148173d..d8ce7dc1dd 100644 --- a/cpukit/score/include/rtems/score/schedulerprioritysmp.h +++ b/cpukit/score/include/rtems/score/schedulerprioritysmp.h @@ -84,6 +84,7 @@ typedef struct { _Scheduler_priority_SMP_Block, \ _Scheduler_priority_SMP_Unblock, \ _Scheduler_priority_SMP_Change_priority, \ + _Scheduler_priority_SMP_Ask_for_help, \ _Scheduler_priority_SMP_Node_initialize, \ _Scheduler_default_Node_destroy, \ _Scheduler_priority_SMP_Update_priority, \ @@ -118,6 +119,12 @@ Thread_Control *_Scheduler_priority_SMP_Change_priority( bool prepend_it ); +Thread_Control *_Scheduler_priority_SMP_Ask_for_help( + const Scheduler_Control *scheduler, + Thread_Control *needs_help, + Thread_Control *offers_help +); + void _Scheduler_priority_SMP_Update_priority( const Scheduler_Control *scheduler, Thread_Control *thread, diff --git a/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h b/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h index 9ae01038b6..bb200b4641 100644 --- a/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h +++ b/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h @@ -148,6 +148,28 @@ static inline void _Scheduler_priority_SMP_Extract_from_ready( ); } +static inline Thread_Control *_Scheduler_priority_SMP_Get_idle_thread( + Scheduler_Context *context +) +{ + return _Scheduler_SMP_Get_idle_thread( + context, + _Scheduler_priority_SMP_Extract_from_ready + ); +} + +static void _Scheduler_priority_SMP_Release_idle_thread( + Scheduler_Context *context, + Thread_Control *idle +) +{ + _Scheduler_SMP_Release_idle_thread( + context, + idle, + _Scheduler_priority_SMP_Insert_ready_fifo + ); +} + static inline void _Scheduler_priority_SMP_Do_update( Scheduler_Context *context, Scheduler_Node *node_to_update, diff --git a/cpukit/score/include/rtems/score/schedulersimple.h b/cpukit/score/include/rtems/score/schedulersimple.h index c97ad2f3c6..82b8c3d7b9 100644 --- a/cpukit/score/include/rtems/score/schedulersimple.h +++ b/cpukit/score/include/rtems/score/schedulersimple.h @@ -43,6 +43,7 @@ extern "C" { _Scheduler_simple_Block, /* block entry point */ \ _Scheduler_simple_Unblock, /* unblock entry point */ \ _Scheduler_simple_Change_priority, /* change priority entry point */ \ + SCHEDULER_OPERATION_DEFAULT_ASK_FOR_HELP \ _Scheduler_default_Node_initialize, /* node initialize entry point */ \ _Scheduler_default_Node_destroy, /* node destroy entry point */ \ _Scheduler_default_Update_priority, /* update priority entry point */ \ diff --git a/cpukit/score/include/rtems/score/schedulersimplesmp.h b/cpukit/score/include/rtems/score/schedulersimplesmp.h index de338ab168..11310c6898 100644 --- a/cpukit/score/include/rtems/score/schedulersimplesmp.h +++ b/cpukit/score/include/rtems/score/schedulersimplesmp.h @@ -65,6 +65,7 @@ typedef struct { _Scheduler_simple_SMP_Block, \ _Scheduler_simple_SMP_Unblock, \ _Scheduler_simple_SMP_Change_priority, \ + _Scheduler_simple_SMP_Ask_for_help, \ _Scheduler_simple_SMP_Node_initialize, \ _Scheduler_default_Node_destroy, \ _Scheduler_simple_SMP_Update_priority, \ @@ -99,6 +100,12 @@ Thread_Control *_Scheduler_simple_SMP_Change_priority( bool prepend_it ); +Thread_Control *_Scheduler_simple_SMP_Ask_for_help( + const Scheduler_Control *scheduler, + Thread_Control *offers_help, + Thread_Control *needs_help +); + void _Scheduler_simple_SMP_Update_priority( const Scheduler_Control *scheduler, Thread_Control *thread, diff --git a/cpukit/score/include/rtems/score/schedulersmp.h b/cpukit/score/include/rtems/score/schedulersmp.h index 0c51a142f6..a58417a268 100644 --- a/cpukit/score/include/rtems/score/schedulersmp.h +++ b/cpukit/score/include/rtems/score/schedulersmp.h @@ -51,6 +51,11 @@ typedef struct { * @brief The chain of scheduled nodes. */ Chain_Control Scheduled; + + /** + * @brief Chain of the available idle threads. + */ + Chain_Control Idle_threads; } Scheduler_SMP_Context; /** diff --git a/cpukit/score/include/rtems/score/schedulersmpimpl.h b/cpukit/score/include/rtems/score/schedulersmpimpl.h index 55d0697df1..3cf7861d3b 100644 --- a/cpukit/score/include/rtems/score/schedulersmpimpl.h +++ b/cpukit/score/include/rtems/score/schedulersmpimpl.h @@ -361,6 +361,7 @@ static inline void _Scheduler_SMP_Initialize( ) { _Chain_Initialize_empty( &self->Scheduled ); + _Chain_Initialize_empty( &self->Idle_threads ); } static inline Scheduler_SMP_Node *_Scheduler_SMP_Thread_get_node( @@ -370,6 +371,13 @@ static inline Scheduler_SMP_Node *_Scheduler_SMP_Thread_get_node( return (Scheduler_SMP_Node *) _Scheduler_Thread_get_node( thread ); } +static inline Scheduler_SMP_Node *_Scheduler_SMP_Thread_get_own_node( + Thread_Control *thread +) +{ + return (Scheduler_SMP_Node *) _Scheduler_Thread_get_own_node( thread ); +} + static inline Scheduler_SMP_Node *_Scheduler_SMP_Node_downcast( Scheduler_Node *node ) @@ -416,6 +424,36 @@ static inline bool _Scheduler_SMP_Is_processor_owned_by_us( return cpu->scheduler_context == context; } +static inline Thread_Control *_Scheduler_SMP_Get_idle_thread( + Scheduler_Context *context, + Scheduler_SMP_Extract extract_from_ready +) +{ + Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context ); + Thread_Control *idle = (Thread_Control *) + _Chain_Get_first_unprotected( &self->Idle_threads ); + Scheduler_Node *own_node = _Scheduler_Thread_get_own_node( idle ); + + ( *extract_from_ready )( &self->Base, own_node ); + + _Assert( &idle->Object.Node != _Chain_Tail( &self->Idle_threads ) ); + + return idle; +} + +static inline void _Scheduler_SMP_Release_idle_thread( + Scheduler_Context *context, + Thread_Control *idle, + Scheduler_SMP_Insert insert_ready +) +{ + Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context ); + Scheduler_Node *own_node = _Scheduler_Thread_get_own_node( idle ); + + _Chain_Prepend_unprotected( &self->Idle_threads, &idle->Object.Node ); + ( *insert_ready )( context, own_node ); +} + static inline void _Scheduler_SMP_Allocate_processor_lazy( Scheduler_Context *context, Thread_Control *scheduled_thread, @@ -468,6 +506,7 @@ static inline void _Scheduler_SMP_Allocate_processor( _Scheduler_SMP_Node_downcast( scheduled ), SCHEDULER_SMP_NODE_SCHEDULED ); + _Scheduler_Thread_change_state( scheduled_thread, THREAD_SCHEDULER_SCHEDULED ); ( *allocate_processor )( context, scheduled_thread, victim_thread ); } @@ -491,6 +530,57 @@ static inline Scheduler_Node *_Scheduler_SMP_Get_lowest_scheduled( return lowest_scheduled; } +static inline Thread_Control *_Scheduler_SMP_Enqueue_to_scheduled( + Scheduler_Context *context, + Scheduler_Node *node, + Scheduler_Node *lowest_scheduled, + Scheduler_SMP_Insert insert_scheduled, + Scheduler_SMP_Move move_from_scheduled_to_ready, + Scheduler_SMP_Allocate_processor allocate_processor, + Scheduler_Release_idle_thread release_idle_thread +) +{ + Thread_Control *user = _Scheduler_Node_get_user( node ); + Thread_Control *lowest_scheduled_user = + _Scheduler_Node_get_user( lowest_scheduled ); + Thread_Control *needs_help; + Thread_Control *idle; + + _Scheduler_SMP_Node_change_state( + _Scheduler_SMP_Node_downcast( lowest_scheduled ), + SCHEDULER_SMP_NODE_READY + ); + _Scheduler_Thread_change_state( + lowest_scheduled_user, + THREAD_SCHEDULER_READY + ); + + _Scheduler_Thread_set_node( user, node ); + + _Scheduler_SMP_Allocate_processor( + context, + node, + lowest_scheduled, + allocate_processor + ); + + ( *insert_scheduled )( context, node ); + ( *move_from_scheduled_to_ready )( context, lowest_scheduled ); + + idle = _Scheduler_Release_idle_thread( + context, + lowest_scheduled, + release_idle_thread + ); + if ( idle == NULL ) { + needs_help = lowest_scheduled_user; + } else { + needs_help = NULL; + } + + return needs_help; +} + /** * @brief Enqueues a node according to the specified order function. * @@ -513,6 +603,7 @@ static inline Scheduler_Node *_Scheduler_SMP_Get_lowest_scheduled( * if this pointer is passed as the second argument to the order function. * @param[in] allocate_processor Function to allocate a processor to a node * based on the rules of the scheduler. + * @param[in] release_idle_thread Function to release an idle thread. */ static inline Thread_Control *_Scheduler_SMP_Enqueue_ordered( Scheduler_Context *context, @@ -523,29 +614,23 @@ static inline Thread_Control *_Scheduler_SMP_Enqueue_ordered( Scheduler_SMP_Insert insert_scheduled, Scheduler_SMP_Move move_from_scheduled_to_ready, Scheduler_SMP_Get_lowest_scheduled get_lowest_scheduled, - Scheduler_SMP_Allocate_processor allocate_processor + Scheduler_SMP_Allocate_processor allocate_processor, + Scheduler_Release_idle_thread release_idle_thread ) { Scheduler_Node *lowest_scheduled = ( *get_lowest_scheduled )( context, node, order ); if ( ( *order )( &node->Node, &lowest_scheduled->Node ) ) { - _Scheduler_SMP_Node_change_state( - _Scheduler_SMP_Node_downcast( lowest_scheduled ), - SCHEDULER_SMP_NODE_READY - ); - - _Scheduler_SMP_Allocate_processor( + needs_help = _Scheduler_SMP_Enqueue_to_scheduled( context, node, lowest_scheduled, - allocate_processor + insert_scheduled, + move_from_scheduled_to_ready, + allocate_processor, + release_idle_thread ); - - ( *insert_scheduled )( context, node ); - ( *move_from_scheduled_to_ready )( context, lowest_scheduled ); - - needs_help = _Scheduler_Node_get_user( lowest_scheduled ); } else { ( *insert_ready )( context, node ); } @@ -560,6 +645,8 @@ static inline Thread_Control *_Scheduler_SMP_Enqueue_ordered( * @param[in] context The scheduler instance context. * @param[in] node The node to enqueue. * @param[in] order The order function. + * @param[in] extract_from_ready Function to extract a node from the set of + * ready nodes. * @param[in] get_highest_ready Function to get the highest ready node. * @param[in] insert_ready Function to insert a node into the set of ready * nodes. @@ -569,48 +656,86 @@ static inline Thread_Control *_Scheduler_SMP_Enqueue_ordered( * of ready nodes to the set of scheduled nodes. * @param[in] allocate_processor Function to allocate a processor to a node * based on the rules of the scheduler. + * @param[in] get_idle_thread Function to get an idle thread. + * @param[in] release_idle_thread Function to release an idle thread. */ static inline Thread_Control *_Scheduler_SMP_Enqueue_scheduled_ordered( Scheduler_Context *context, Scheduler_Node *node, Chain_Node_order order, + Scheduler_SMP_Extract extract_from_ready, Scheduler_SMP_Get_highest_ready get_highest_ready, Scheduler_SMP_Insert insert_ready, Scheduler_SMP_Insert insert_scheduled, Scheduler_SMP_Move move_from_ready_to_scheduled, - Scheduler_SMP_Allocate_processor allocate_processor + Scheduler_SMP_Allocate_processor allocate_processor, + Scheduler_Get_idle_thread get_idle_thread, + Scheduler_Release_idle_thread release_idle_thread ) { - Scheduler_Node *highest_ready = ( *get_highest_ready )( context, node ); Thread_Control *needs_help; - _Assert( highest_ready != NULL ); + while ( true ) { + Scheduler_Node *highest_ready = ( *get_highest_ready )( context, node ); + + _Assert( highest_ready != NULL ); + + /* + * The node has been extracted from the scheduled chain. We have to place + * it now on the scheduled or ready set. + */ + if ( ( *order )( &node->Node, &highest_ready->Node ) ) { + ( *insert_scheduled )( context, node ); + + needs_help = NULL; + + break; + } else if ( + _Scheduler_Try_to_schedule_node( + context, + highest_ready, + get_idle_thread + ) + ) { + Thread_Control *user = _Scheduler_Node_get_user( node ); + Thread_Control *idle; + + _Scheduler_SMP_Node_change_state( + _Scheduler_SMP_Node_downcast( node ), + SCHEDULER_SMP_NODE_READY + ); + _Scheduler_Thread_change_state( user, THREAD_SCHEDULER_READY ); - /* - * The node has been extracted from the scheduled chain. We have to place - * it now on the scheduled or ready set. - */ - if ( ( *order )( &node->Node, &highest_ready->Node ) ) { - ( *insert_scheduled )( context, node ); + _Scheduler_SMP_Allocate_processor( + context, + highest_ready, + node, + allocate_processor + ); - needs_help = NULL; - } else { - _Scheduler_SMP_Node_change_state( - _Scheduler_SMP_Node_downcast( node ), - SCHEDULER_SMP_NODE_READY - ); + ( *insert_ready )( context, node ); + ( *move_from_ready_to_scheduled )( context, highest_ready ); - _Scheduler_SMP_Allocate_processor( - context, - highest_ready, - node, - allocate_processor - ); + idle = _Scheduler_Release_idle_thread( + context, + node, + release_idle_thread + ); + if ( idle == NULL ) { + needs_help = user; + } else { + needs_help = NULL; + } - ( *insert_ready )( context, node ); - ( *move_from_ready_to_scheduled )( context, highest_ready ); + break; + } else { + _Scheduler_SMP_Node_change_state( + _Scheduler_SMP_Node_downcast( highest_ready ), + SCHEDULER_SMP_NODE_BLOCKED + ); - needs_help = _Scheduler_Node_get_user( node ); + ( *extract_from_ready )( context, highest_ready ); + } } return needs_help; @@ -626,21 +751,44 @@ static inline void _Scheduler_SMP_Extract_from_scheduled( static inline void _Scheduler_SMP_Schedule_highest_ready( Scheduler_Context *context, Scheduler_Node *victim, + Scheduler_SMP_Extract extract_from_ready, Scheduler_SMP_Get_highest_ready get_highest_ready, Scheduler_SMP_Move move_from_ready_to_scheduled, - Scheduler_SMP_Allocate_processor allocate_processor + Scheduler_SMP_Allocate_processor allocate_processor, + Scheduler_Get_idle_thread get_idle_thread ) { - Scheduler_Node *highest_ready = ( *get_highest_ready )( context, victim ); + while ( true ) { + Scheduler_Node *highest_ready = ( *get_highest_ready )( context, victim ); + + _Assert( highest_ready != NULL ); + + if ( + _Scheduler_Try_to_schedule_node( + context, + highest_ready, + get_idle_thread + ) + ) { + _Scheduler_SMP_Allocate_processor( + context, + highest_ready, + victim, + allocate_processor + ); - _Scheduler_SMP_Allocate_processor( - context, - highest_ready, - victim, - allocate_processor - ); + ( *move_from_ready_to_scheduled )( context, highest_ready ); + + break; + } else { + _Scheduler_SMP_Node_change_state( + _Scheduler_SMP_Node_downcast( highest_ready ), + SCHEDULER_SMP_NODE_BLOCKED + ); - ( *move_from_ready_to_scheduled )( context, highest_ready ); + ( *extract_from_ready )( context, highest_ready ); + } + } } /** @@ -649,10 +797,11 @@ static inline void _Scheduler_SMP_Schedule_highest_ready( * @param[in] context The scheduler instance context. * @param[in] thread The thread of the scheduling operation. * @param[in] extract_from_ready Function to extract a node from the set of - * ready nodes. + * ready nodes. * @param[in] get_highest_ready Function to get the highest ready node. * @param[in] move_from_ready_to_scheduled Function to move a node from the set - * of ready nodes to the set of scheduled nodes. + * of ready nodes to the set of scheduled nodes. + * @param[in] get_idle_thread Function to get an idle thread. */ static inline void _Scheduler_SMP_Block( Scheduler_Context *context, @@ -660,40 +809,67 @@ static inline void _Scheduler_SMP_Block( Scheduler_SMP_Extract extract_from_ready, Scheduler_SMP_Get_highest_ready get_highest_ready, Scheduler_SMP_Move move_from_ready_to_scheduled, - Scheduler_SMP_Allocate_processor allocate_processor + Scheduler_SMP_Allocate_processor allocate_processor, + Scheduler_Get_idle_thread get_idle_thread ) { Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_node( thread ); bool is_scheduled = node->state == SCHEDULER_SMP_NODE_SCHEDULED; + bool block = _Scheduler_Block_node( + context, + &node->Base, + is_scheduled, + get_idle_thread + ); - _Scheduler_SMP_Node_change_state( node, SCHEDULER_SMP_NODE_BLOCKED ); + if ( block ) { + _Scheduler_SMP_Node_change_state( node, SCHEDULER_SMP_NODE_BLOCKED ); - if ( is_scheduled ) { - _Scheduler_SMP_Extract_from_scheduled( &node->Base ); + if ( is_scheduled ) { + _Scheduler_SMP_Extract_from_scheduled( &node->Base ); - _Scheduler_SMP_Schedule_highest_ready( - context, - &node->Base, - get_highest_ready, - move_from_ready_to_scheduled, - allocate_processor - ); - } else { - ( *extract_from_ready )( context, &node->Base ); + _Scheduler_SMP_Schedule_highest_ready( + context, + &node->Base, + extract_from_ready, + get_highest_ready, + move_from_ready_to_scheduled, + allocate_processor, + get_idle_thread + ); + } else { + ( *extract_from_ready )( context, &node->Base ); + } } } static inline Thread_Control *_Scheduler_SMP_Unblock( - Scheduler_Context *context, - Thread_Control *thread, - Scheduler_SMP_Enqueue enqueue_fifo + Scheduler_Context *context, + Thread_Control *thread, + Scheduler_SMP_Enqueue enqueue_fifo, + Scheduler_Release_idle_thread release_idle_thread ) { Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_node( thread ); + bool is_scheduled = node->state == SCHEDULER_SMP_NODE_SCHEDULED; + bool unblock = _Scheduler_Unblock_node( + context, + thread, + &node->Base, + is_scheduled, + release_idle_thread + ); + Thread_Control *needs_help; - _Scheduler_SMP_Node_change_state( node, SCHEDULER_SMP_NODE_READY ); + if ( unblock ) { + _Scheduler_SMP_Node_change_state( node, SCHEDULER_SMP_NODE_READY ); - return ( *enqueue_fifo )( context, &node->Base, thread ); + needs_help = ( *enqueue_fifo )( context, &node->Base, thread ); + } else { + needs_help = NULL; + } + + return needs_help; } static inline Thread_Control *_Scheduler_SMP_Change_priority( @@ -709,7 +885,7 @@ static inline Thread_Control *_Scheduler_SMP_Change_priority( Scheduler_SMP_Enqueue_scheduled enqueue_scheduled_lifo ) { - Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_node( thread ); + Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_own_node( thread ); Thread_Control *needs_help; if ( node->state == SCHEDULER_SMP_NODE_SCHEDULED ) { @@ -722,7 +898,7 @@ static inline Thread_Control *_Scheduler_SMP_Change_priority( } else { needs_help = ( *enqueue_scheduled_fifo )( context, &node->Base ); } - } else { + } else if ( node->state == SCHEDULER_SMP_NODE_READY ) { ( *extract_from_ready )( context, &node->Base ); ( *update )( context, &node->Base, new_priority ); @@ -732,11 +908,68 @@ static inline Thread_Control *_Scheduler_SMP_Change_priority( } else { needs_help = ( *enqueue_fifo )( context, &node->Base, NULL ); } + } else { + ( *update )( context, &node->Base, new_priority ); + + needs_help = NULL; } return needs_help; } +static inline Thread_Control *_Scheduler_SMP_Ask_for_help( + Scheduler_Context *context, + Thread_Control *offers_help, + Thread_Control *needs_help, + Scheduler_SMP_Enqueue enqueue_fifo, + Scheduler_Release_idle_thread release_idle_thread +) +{ + Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_own_node( offers_help ); + Thread_Control *next_needs_help = NULL; + Thread_Control *previous_accepts_help; + + previous_accepts_help = node->Base.accepts_help; + node->Base.accepts_help = needs_help; + + switch ( node->state ) { + case SCHEDULER_SMP_NODE_READY: + next_needs_help = + _Scheduler_Ask_ready_node_for_help( &node->Base, needs_help ); + break; + case SCHEDULER_SMP_NODE_SCHEDULED: + next_needs_help = _Scheduler_Ask_scheduled_node_for_help( + context, + &node->Base, + offers_help, + needs_help, + previous_accepts_help, + release_idle_thread + ); + break; + case SCHEDULER_SMP_NODE_BLOCKED: + if ( + _Scheduler_Ask_blocked_node_for_help( + context, + &node->Base, + offers_help, + needs_help + ) + ) { + _Scheduler_SMP_Node_change_state( node, SCHEDULER_SMP_NODE_READY ); + + next_needs_help = ( *enqueue_fifo )( + context, + &node->Base, + needs_help + ); + } + break; + } + + return next_needs_help; +} + static inline Thread_Control *_Scheduler_SMP_Yield( Scheduler_Context *context, Thread_Control *thread, diff --git a/cpukit/score/include/rtems/score/thread.h b/cpukit/score/include/rtems/score/thread.h index 28844c3062..0d9025fdfa 100644 --- a/cpukit/score/include/rtems/score/thread.h +++ b/cpukit/score/include/rtems/score/thread.h @@ -445,19 +445,77 @@ typedef struct { Thread_Control *terminator; } Thread_Life_control; +#if defined(RTEMS_SMP) +/** + * @brief The thread state with respect to the scheduler. + */ +typedef enum { + /** + * @brief This thread is blocked with respect to the scheduler. + * + * This thread uses no scheduler nodes. + */ + THREAD_SCHEDULER_BLOCKED, + + /** + * @brief This thread is scheduled with respect to the scheduler. + * + * This thread executes using one of its scheduler nodes. This could be its + * own scheduler node or in case it owns resources taking part in the + * scheduler helping protocol a scheduler node of another thread. + */ + THREAD_SCHEDULER_SCHEDULED, + + /** + * @brief This thread is ready with respect to the scheduler. + * + * None of the scheduler nodes of this thread is scheduled. + */ + THREAD_SCHEDULER_READY +} Thread_Scheduler_state; +#endif + /** * @brief Thread scheduler control. */ typedef struct { #if defined(RTEMS_SMP) /** - * @brief The current scheduler control of this thread. + * @brief The current scheduler state of this thread. + */ + Thread_Scheduler_state state; + + /** + * @brief The own scheduler control of this thread. + * + * This field is constant after initialization. + */ + const struct Scheduler_Control *own_control; + + /** + * @brief The scheduler control of this thread. + * + * The scheduler helping protocol may change this field. */ const struct Scheduler_Control *control; + + /** + * @brief The own scheduler node of this thread. + * + * This field is constant after initialization. It is used by change + * priority and ask for help operations. + */ + struct Scheduler_Node *own_node; #endif /** - * @brief The current scheduler node of this thread. + * @brief The scheduler node of this thread. + * + * On uni-processor configurations this field is constant after + * initialization. + * + * On SMP configurations the scheduler helping protocol may change this + * field. */ struct Scheduler_Node *node; diff --git a/cpukit/score/include/rtems/score/threadimpl.h b/cpukit/score/include/rtems/score/threadimpl.h index 4971e9d274..cb7d5fe8d2 100644 --- a/cpukit/score/include/rtems/score/threadimpl.h +++ b/cpukit/score/include/rtems/score/threadimpl.h @@ -828,6 +828,16 @@ RTEMS_INLINE_ROUTINE bool _Thread_Owns_resources( return owns_resources; } +#if defined(RTEMS_SMP) +RTEMS_INLINE_ROUTINE Thread_Control *_Thread_Resource_node_to_thread( + Resource_Node *node +) +{ + return (Thread_Control *) + ( (char *) node - offsetof( Thread_Control, Resource_node ) ); +} +#endif + RTEMS_INLINE_ROUTINE void _Thread_Debug_set_real_processor( Thread_Control *the_thread, Per_CPU_Control *cpu diff --git a/cpukit/score/src/schedulercbsnodeinit.c b/cpukit/score/src/schedulercbsnodeinit.c index 1a5299a863..d16f3fa035 100644 --- a/cpukit/score/src/schedulercbsnodeinit.c +++ b/cpukit/score/src/schedulercbsnodeinit.c @@ -29,6 +29,8 @@ void _Scheduler_CBS_Node_initialize( (void) scheduler; + _Scheduler_Node_do_initialize( &node->Base.Base, the_thread ); + node->Base.thread = the_thread; node->Base.queue_state = SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN; node->cbs_server = NULL; diff --git a/cpukit/score/src/schedulerchangeroot.c b/cpukit/score/src/schedulerchangeroot.c new file mode 100644 index 0000000000..eba852ba5e --- /dev/null +++ b/cpukit/score/src/schedulerchangeroot.c @@ -0,0 +1,85 @@ +/* + * Copyright (c) 2014 embedded brains GmbH. All rights reserved. + * + * embedded brains GmbH + * Dornierstr. 4 + * 82178 Puchheim + * Germany + * <rtems@embedded-brains.de> + * + * The license and distribution terms for this file may be + * found in the file LICENSE in this distribution or at + * http://www.rtems.org/license/LICENSE. + */ + +#if HAVE_CONFIG_H + #include "config.h" +#endif + +#include <rtems/score/schedulerimpl.h> + +typedef struct { + Thread_Control *root; + Thread_Control *needs_help; +} Scheduler_Set_root_context; + +RTEMS_INLINE_ROUTINE bool _Scheduler_Set_root_visitor( + Resource_Node *resource_node, + void *arg +) +{ + Scheduler_Set_root_context *ctx = arg; + Thread_Control *root = ctx->root; + Thread_Control *needs_help = root; + Thread_Control *offers_help = + _Thread_Resource_node_to_thread( resource_node ); + const Scheduler_Control *scheduler = _Scheduler_Get_own( offers_help ); + Thread_Control *needs_help_too; + + _Resource_Node_set_root( resource_node, &root->Resource_node ); + + needs_help_too = ( *scheduler->Operations.ask_for_help )( + scheduler, + offers_help, + needs_help + ); + + if ( needs_help_too != needs_help && needs_help_too != NULL ) { + _Assert( ctx->needs_help == NULL ); + ctx->needs_help = needs_help_too; + } + + return false; +} + +void _Scheduler_Thread_change_resource_root( + Thread_Control *top, + Thread_Control *root +) +{ + Scheduler_Set_root_context ctx = { root, NULL }; + Thread_Control *offers_help = top; + Scheduler_Node *offers_help_node; + Thread_Control *offers_help_too; + ISR_Level level; + + _ISR_Disable( level ); + + offers_help_node = _Scheduler_Thread_get_node( offers_help ); + offers_help_too = _Scheduler_Node_get_owner( offers_help_node ); + + if ( offers_help != offers_help_too ) { + _Scheduler_Set_root_visitor( &offers_help_too->Resource_node, &ctx ); + _Assert( ctx.needs_help == offers_help ); + ctx.needs_help = NULL; + } + + _Scheduler_Set_root_visitor( &top->Resource_node, &ctx ); + _Resource_Iterate( &top->Resource_node, _Scheduler_Set_root_visitor, &ctx ); + + if ( ctx.needs_help != NULL ) { + _Scheduler_Ask_for_help( ctx.needs_help ); + } + + _ISR_Enable( level ); +} diff --git a/cpukit/score/src/schedulerdefaultaskforhelp.c b/cpukit/score/src/schedulerdefaultaskforhelp.c new file mode 100644 index 0000000000..b69524846b --- /dev/null +++ b/cpukit/score/src/schedulerdefaultaskforhelp.c @@ -0,0 +1,26 @@ +/* + * Copyright (c) 2014 embedded brains GmbH + * + * The license and distribution terms for this file may be + * found in the file LICENSE in this distribution or at + * http://www.rtems.org/license/LICENSE. + */ + +#if HAVE_CONFIG_H + #include "config.h" +#endif + +#include <rtems/score/scheduler.h> + +Thread_Control *_Scheduler_default_Ask_for_help( + const Scheduler_Control *scheduler, + Thread_Control *offers_help, + Thread_Control *needs_help +) +{ + (void) scheduler; + (void) offers_help; + (void) needs_help; + + return NULL; +} diff --git a/cpukit/score/src/schedulerdefaultnodeinit.c b/cpukit/score/src/schedulerdefaultnodeinit.c index ab371bd7fe..a96a528ee4 100644 --- a/cpukit/score/src/schedulerdefaultnodeinit.c +++ b/cpukit/score/src/schedulerdefaultnodeinit.c @@ -19,13 +19,16 @@ #include "config.h" #endif -#include <rtems/score/scheduler.h> +#include <rtems/score/schedulerimpl.h> void _Scheduler_default_Node_initialize( const Scheduler_Control *scheduler, Thread_Control *the_thread ) { + Scheduler_Node *node = _Scheduler_Thread_get_own_node( the_thread ); + (void) scheduler; - (void) the_thread; + + _Scheduler_Node_do_initialize( node, the_thread ); } diff --git a/cpukit/score/src/scheduleredfnodeinit.c b/cpukit/score/src/scheduleredfnodeinit.c index b23f5acda8..e7f8af70a5 100644 --- a/cpukit/score/src/scheduleredfnodeinit.c +++ b/cpukit/score/src/scheduleredfnodeinit.c @@ -29,6 +29,8 @@ void _Scheduler_EDF_Node_initialize( (void) scheduler; + _Scheduler_Node_do_initialize( &node->Base, the_thread ); + node->thread = the_thread; node->queue_state = SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN; } diff --git a/cpukit/score/src/schedulerpriorityaffinitysmp.c b/cpukit/score/src/schedulerpriorityaffinitysmp.c index 24fae3cfee..39a0a481ea 100644 --- a/cpukit/score/src/schedulerpriorityaffinitysmp.c +++ b/cpukit/score/src/schedulerpriorityaffinitysmp.c @@ -60,6 +60,15 @@ static bool _Scheduler_priority_affinity_SMP_Insert_priority_fifo_order( && _Scheduler_SMP_Insert_priority_fifo_order( to_insert, next ); } +static Scheduler_priority_affinity_SMP_Node * +_Scheduler_priority_affinity_SMP_Thread_get_own_node( + Thread_Control *thread +) +{ + return (Scheduler_priority_affinity_SMP_Node *) + _Scheduler_Thread_get_own_node( thread ); +} + /* * This method returns the scheduler node for the specified thread * as a scheduler specific type. @@ -69,7 +78,8 @@ _Scheduler_priority_affinity_SMP_Thread_get_node( Thread_Control *thread ) { - return (Scheduler_priority_affinity_SMP_Node *) _Scheduler_Thread_get_node( thread ); + return (Scheduler_priority_affinity_SMP_Node *) + _Scheduler_Thread_get_node( thread ); } static Scheduler_priority_affinity_SMP_Node * @@ -90,7 +100,7 @@ void _Scheduler_priority_affinity_SMP_Node_initialize( ) { Scheduler_priority_affinity_SMP_Node *node = - _Scheduler_priority_affinity_SMP_Thread_get_node( thread ); + _Scheduler_priority_affinity_SMP_Thread_get_own_node( thread ); (void) scheduler; @@ -221,7 +231,8 @@ void _Scheduler_priority_affinity_SMP_Block( _Scheduler_priority_SMP_Extract_from_ready, _Scheduler_priority_affinity_SMP_Get_highest_ready, _Scheduler_priority_SMP_Move_from_ready_to_scheduled, - _Scheduler_SMP_Allocate_processor_exact + _Scheduler_SMP_Allocate_processor_exact, + _Scheduler_priority_SMP_Get_idle_thread ); /* @@ -303,7 +314,8 @@ static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_fifo( _Scheduler_SMP_Insert_scheduled_fifo, _Scheduler_priority_SMP_Move_from_scheduled_to_ready, _Scheduler_priority_affinity_SMP_Get_lowest_scheduled, - _Scheduler_SMP_Allocate_processor_exact + _Scheduler_SMP_Allocate_processor_exact, + _Scheduler_priority_SMP_Release_idle_thread ); } @@ -387,7 +399,8 @@ Thread_Control *_Scheduler_priority_affinity_SMP_Unblock( needs_help = _Scheduler_SMP_Unblock( context, thread, - _Scheduler_priority_affinity_SMP_Enqueue_fifo + _Scheduler_priority_affinity_SMP_Enqueue_fifo, + _Scheduler_priority_SMP_Release_idle_thread ); /* @@ -420,7 +433,8 @@ static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_ordered( insert_scheduled, _Scheduler_priority_SMP_Move_from_scheduled_to_ready, _Scheduler_priority_affinity_SMP_Get_lowest_scheduled, - _Scheduler_SMP_Allocate_processor_exact + _Scheduler_SMP_Allocate_processor_exact, + _Scheduler_priority_SMP_Release_idle_thread ); } @@ -463,11 +477,14 @@ _Scheduler_priority_affinity_SMP_Enqueue_scheduled_ordered( context, node, order, + _Scheduler_priority_SMP_Extract_from_ready, _Scheduler_priority_affinity_SMP_Get_highest_ready, insert_ready, insert_scheduled, _Scheduler_priority_SMP_Move_from_ready_to_scheduled, - _Scheduler_SMP_Allocate_processor_exact + _Scheduler_SMP_Allocate_processor_exact, + _Scheduler_priority_SMP_Get_idle_thread, + _Scheduler_priority_SMP_Release_idle_thread ); } @@ -543,6 +560,27 @@ Thread_Control *_Scheduler_priority_affinity_SMP_Change_priority( return displaced; } +Thread_Control *_Scheduler_priority_affinity_SMP_Ask_for_help( + const Scheduler_Control *scheduler, + Thread_Control *offers_help, + Thread_Control *needs_help +) +{ + Scheduler_Context *context = _Scheduler_Get_context( scheduler ); + + needs_help = _Scheduler_SMP_Ask_for_help( + context, + offers_help, + needs_help, + _Scheduler_priority_affinity_SMP_Enqueue_fifo, + _Scheduler_priority_SMP_Release_idle_thread + ); + + _Scheduler_priority_affinity_SMP_Check_for_migrations( context ); + + return needs_help; +} + /* * This is the public scheduler specific Change Priority operation. */ diff --git a/cpukit/score/src/schedulerprioritysmp.c b/cpukit/score/src/schedulerprioritysmp.c index b642c5d6f3..93d1c76d30 100644 --- a/cpukit/score/src/schedulerprioritysmp.c +++ b/cpukit/score/src/schedulerprioritysmp.c @@ -47,7 +47,7 @@ void _Scheduler_priority_SMP_Node_initialize( Thread_Control *thread ) { - Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_node( thread ); + Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_own_node( thread ); _Scheduler_SMP_Node_initialize( node, thread ); } @@ -93,7 +93,8 @@ void _Scheduler_priority_SMP_Block( _Scheduler_priority_SMP_Extract_from_ready, _Scheduler_priority_SMP_Get_highest_ready, _Scheduler_priority_SMP_Move_from_ready_to_scheduled, - _Scheduler_SMP_Allocate_processor_lazy + _Scheduler_SMP_Allocate_processor_lazy, + _Scheduler_priority_SMP_Get_idle_thread ); } @@ -115,7 +116,8 @@ static Thread_Control *_Scheduler_priority_SMP_Enqueue_ordered( insert_scheduled, _Scheduler_priority_SMP_Move_from_scheduled_to_ready, _Scheduler_SMP_Get_lowest_scheduled, - _Scheduler_SMP_Allocate_processor_lazy + _Scheduler_SMP_Allocate_processor_lazy, + _Scheduler_priority_SMP_Release_idle_thread ); } @@ -163,11 +165,14 @@ static Thread_Control *_Scheduler_priority_SMP_Enqueue_scheduled_ordered( context, node, order, + _Scheduler_priority_SMP_Extract_from_ready, _Scheduler_priority_SMP_Get_highest_ready, insert_ready, insert_scheduled, _Scheduler_priority_SMP_Move_from_ready_to_scheduled, - _Scheduler_SMP_Allocate_processor_lazy + _Scheduler_SMP_Allocate_processor_lazy, + _Scheduler_priority_SMP_Get_idle_thread, + _Scheduler_priority_SMP_Release_idle_thread ); } @@ -209,7 +214,8 @@ Thread_Control *_Scheduler_priority_SMP_Unblock( return _Scheduler_SMP_Unblock( context, thread, - _Scheduler_priority_SMP_Enqueue_fifo + _Scheduler_priority_SMP_Enqueue_fifo, + _Scheduler_priority_SMP_Release_idle_thread ); } @@ -236,6 +242,23 @@ Thread_Control *_Scheduler_priority_SMP_Change_priority( ); } +Thread_Control *_Scheduler_priority_SMP_Ask_for_help( + const Scheduler_Control *scheduler, + Thread_Control *offers_help, + Thread_Control *needs_help +) +{ + Scheduler_Context *context = _Scheduler_Get_context( scheduler ); + + return _Scheduler_SMP_Ask_for_help( + context, + offers_help, + needs_help, + _Scheduler_priority_SMP_Enqueue_fifo, + _Scheduler_priority_SMP_Release_idle_thread + ); +} + Thread_Control *_Scheduler_priority_SMP_Yield( const Scheduler_Control *scheduler, Thread_Control *thread diff --git a/cpukit/score/src/schedulersimplesmp.c b/cpukit/score/src/schedulersimplesmp.c index ee540bebd0..084d78251f 100644 --- a/cpukit/score/src/schedulersimplesmp.c +++ b/cpukit/score/src/schedulersimplesmp.c @@ -47,7 +47,7 @@ void _Scheduler_simple_SMP_Node_initialize( Thread_Control *the_thread ) { - Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_node( the_thread ); + Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_own_node( the_thread ); _Scheduler_SMP_Node_initialize( node, the_thread ); } @@ -162,6 +162,28 @@ static void _Scheduler_simple_SMP_Extract_from_ready( _Chain_Extract_unprotected( &node_to_extract->Node ); } +static Thread_Control *_Scheduler_simple_SMP_Get_idle_thread( + Scheduler_Context *context +) +{ + return _Scheduler_SMP_Get_idle_thread( + context, + _Scheduler_simple_SMP_Extract_from_ready + ); +} + +static void _Scheduler_simple_SMP_Release_idle_thread( + Scheduler_Context *context, + Thread_Control *idle +) +{ + _Scheduler_SMP_Release_idle_thread( + context, + idle, + _Scheduler_simple_SMP_Insert_ready_fifo + ); +} + void _Scheduler_simple_SMP_Block( const Scheduler_Control *scheduler, Thread_Control *thread @@ -175,7 +197,8 @@ void _Scheduler_simple_SMP_Block( _Scheduler_simple_SMP_Extract_from_ready, _Scheduler_simple_SMP_Get_highest_ready, _Scheduler_simple_SMP_Move_from_ready_to_scheduled, - _Scheduler_SMP_Allocate_processor_lazy + _Scheduler_SMP_Allocate_processor_lazy, + _Scheduler_simple_SMP_Get_idle_thread ); } @@ -197,7 +220,8 @@ static Thread_Control *_Scheduler_simple_SMP_Enqueue_ordered( insert_scheduled, _Scheduler_simple_SMP_Move_from_scheduled_to_ready, _Scheduler_SMP_Get_lowest_scheduled, - _Scheduler_SMP_Allocate_processor_lazy + _Scheduler_SMP_Allocate_processor_lazy, + _Scheduler_simple_SMP_Release_idle_thread ); } @@ -245,11 +269,14 @@ static Thread_Control *_Scheduler_simple_SMP_Enqueue_scheduled_ordered( context, node, order, + _Scheduler_simple_SMP_Extract_from_ready, _Scheduler_simple_SMP_Get_highest_ready, insert_ready, insert_scheduled, _Scheduler_simple_SMP_Move_from_ready_to_scheduled, - _Scheduler_SMP_Allocate_processor_lazy + _Scheduler_SMP_Allocate_processor_lazy, + _Scheduler_simple_SMP_Get_idle_thread, + _Scheduler_simple_SMP_Release_idle_thread ); } @@ -291,7 +318,8 @@ Thread_Control *_Scheduler_simple_SMP_Unblock( return _Scheduler_SMP_Unblock( context, thread, - _Scheduler_simple_SMP_Enqueue_fifo + _Scheduler_simple_SMP_Enqueue_fifo, + _Scheduler_simple_SMP_Release_idle_thread ); } @@ -318,6 +346,23 @@ Thread_Control *_Scheduler_simple_SMP_Change_priority( ); } +Thread_Control *_Scheduler_simple_SMP_Ask_for_help( + const Scheduler_Control *scheduler, + Thread_Control *offers_help, + Thread_Control *needs_help +) +{ + Scheduler_Context *context = _Scheduler_Get_context( scheduler ); + + return _Scheduler_SMP_Ask_for_help( + context, + offers_help, + needs_help, + _Scheduler_simple_SMP_Enqueue_fifo, + _Scheduler_simple_SMP_Release_idle_thread + ); +} + Thread_Control *_Scheduler_simple_SMP_Yield( const Scheduler_Control *scheduler, Thread_Control *thread diff --git a/cpukit/score/src/schedulersmpvalidstatechanges.c b/cpukit/score/src/schedulersmpdebug.c index 6a5dcc6de4..4a45d2095f 100644 --- a/cpukit/score/src/schedulersmpvalidstatechanges.c +++ b/cpukit/score/src/schedulersmpdebug.c @@ -1,9 +1,9 @@ /** * @file * - * @ingroup ScoreSchedulerSMP + * @ingroup ScoreScheduler * - * @brief SMP Scheduler Implementation + * @brief Scheduler SMP Debug Implementation */ /* @@ -24,10 +24,24 @@ #include "config.h" #endif +#include <rtems/score/schedulerimpl.h> #include <rtems/score/schedulerpriorityimpl.h> +#if defined(RTEMS_DEBUG) + +/* + * Table with all valid state transitions for _Scheduler_Thread_change_state() + * in case RTEMS_DEBUG is defined. + */ +const bool _Scheduler_Thread_state_valid_state_changes[ 3 ][ 3 ] = { + /* FROM / TO BLOCKED SCHEDULED READY */ + /* BLOCKED */ { false, true, true }, + /* SCHEDULED */ { true, false, true }, + /* READY */ { true, true, true } +}; + /* - * Table with all valid state transitions. It is used in + * Table with all valid state transitions for * _Scheduler_SMP_Node_change_state() in case RTEMS_DEBUG is defined. */ const bool _Scheduler_SMP_Node_valid_state_changes[ 3 ][ 3 ] = { @@ -36,3 +50,5 @@ const bool _Scheduler_SMP_Node_valid_state_changes[ 3 ][ 3 ] = { /* SCHEDULED */ { true, false, true }, /* READY */ { true, true, false } }; + +#endif diff --git a/cpukit/score/src/schedulersmpstartidle.c b/cpukit/score/src/schedulersmpstartidle.c index 6809fd81a3..de125d3323 100644 --- a/cpukit/score/src/schedulersmpstartidle.c +++ b/cpukit/score/src/schedulersmpstartidle.c @@ -26,4 +26,5 @@ void _Scheduler_SMP_Start_idle( _Thread_Set_CPU( thread, cpu ); _Chain_Append_unprotected( &self->Scheduled, &node->Base.Node ); + _Chain_Prepend_unprotected( &self->Idle_threads, &thread->Object.Node ); } diff --git a/cpukit/score/src/threadinitialize.c b/cpukit/score/src/threadinitialize.c index e6c4985591..e56e4e6cda 100644 --- a/cpukit/score/src/threadinitialize.c +++ b/cpukit/score/src/threadinitialize.c @@ -181,7 +181,10 @@ bool _Thread_Initialize( } #if defined(RTEMS_SMP) + the_thread->Scheduler.state = THREAD_SCHEDULER_BLOCKED; + the_thread->Scheduler.own_control = scheduler; the_thread->Scheduler.control = scheduler; + the_thread->Scheduler.own_node = the_thread->Scheduler.node; _Resource_Node_initialize( &the_thread->Resource_node ); _CPU_Context_Set_is_executing( &the_thread->Registers, false ); #endif diff --git a/doc/user/smp.t b/doc/user/smp.t index dd84c37360..c21c8a0791 100644 --- a/doc/user/smp.t +++ b/doc/user/smp.t @@ -147,6 +147,84 @@ another processor. So if we enable interrupts during this transition we have to provide an alternative task independent stack for this time frame. This issue needs further investigation. +@subsection Scheduler Helping Protocol + +The scheduler provides a helping protocol to support locking protocols like +@cite{Migratory Priority Inheritance} or the @cite{Multiprocessor Resource +Sharing Protocol}. Each ready task can use at least one scheduler node at a +time to gain access to a processor. Each scheduler node has an owner, a user +and an optional idle task. The owner of a scheduler node is determined a task +creation and never changes during the life time of a scheduler node. The user +of a scheduler node may change due to the scheduler helping protocol. A +scheduler node is in one of the four scheduler help states: + +@table @dfn + +@item help yourself + +This scheduler node is solely used by the owner task. This task owns no +resources using a helping protocol and thus does not take part in the scheduler +helping protocol. No help will be provided for other tasks. + +@item help active owner + +This scheduler node is owned by a task actively owning a resource and can be +used to help out tasks. + +In case this scheduler node changes its state from ready to scheduled and the +task executes using another node, then an idle task will be provided as a user +of this node to temporarily execute on behalf of the owner task. Thus lower +priority tasks are denied access to the processors of this scheduler instance. + +In case a task actively owning a resource performs a blocking operation, then +an idle task will be used also in case this node is in the scheduled state. + +@item help active rival + +This scheduler node is owned by a task actively obtaining a resource currently +owned by another task and can be used to help out tasks. + +The task owning this node is ready and will give away its processor in case the +task owning the resource asks for help. + +@item help passive + +This scheduler node is owned by a task obtaining a resource currently owned by +another task and can be used to help out tasks. + +The task owning this node is blocked. + +@end table + +The following scheduler operations return a task in need for help + +@itemize @bullet +@item unblock, +@item change priority, +@item yield, and +@item ask for help. +@end itemize + +A task in need for help is a task that encounters a scheduler state change from +scheduled to ready (this is a pre-emption by a higher priority task) or a task +that cannot be scheduled in an unblock operation. Such a task can ask tasks +which depend on resources owned by this task for help. + +In case it is not possible to schedule a task in need for help, then the +scheduler nodes available for the task will be placed into the set of ready +scheduler nodes of the corresponding scheduler instances. Once a state change +from ready to scheduled happens for one of scheduler nodes it will be used to +schedule the task in need for help. + +The ask for help scheduler operation is used to help tasks in need for help +returned by the operations mentioned above. This operation is also used in +case the root of a resource sub-tree owned by a task changes. + +The run-time of the ask for help procedures depend on the size of the resource +tree of the task needing help and other resource trees in case tasks in need +for help are produced during this operation. Thus the worst-case latency in +the system depends on the maximum resource tree size of the application. + @subsection Critical Section Techniques and SMP As discussed earlier, SMP systems have opportunities for true parallelism |