[PATCH] Add SMP Priority Scheduler with Affinity

Sebastian Huber sebastian.huber at embedded-brains.de
Tue Jun 10 07:06:46 UTC 2014


On 2014-06-09 22:42, Joel Sherrill wrote:
> This scheduler attempts to account for needed thread migrations caused
> as a side-effect of a thread state, affinity, or priority change operation.
>
> This scheduler has its own allocate_processor handler named
> _Scheduler_SMP_Allocate_processor_exact() because
> _Scheduler_SMP_Allocate_processor() attempts to prevent an executing
> thread from moving off its current CPU without considering affinity.
> Without this, the scheduler makes all the right decisions and then
> they are discarded at the end.
>
> ==Side Effects of Adding This Scheduler==
>
> Added Thread_Control * parameter to Scheduler_SMP_Get_highest_ready type
> so methods looking for the highest ready thread can filter by the processor
> on which the thread blocking resides. This allows affinity to be considered.
> Simple Priority SMP and Priority SMP ignore this parameter.
>
> + Added get_lowest_scheduled argument to _Scheduler_SMP_Enqueue_ordered().
>
> + Added allocate_processor argument to _Scheduler_SMP_Enqueue_ordered().
>
> + Added allocate_processor argument to
>    _Scheduler_SMP_Enqueue_scheduled_ordered().
>
> + schedulerprioritysmpimpl.h is a new file with prototypes for methods
>    which were formerly static in schedulerprioritysmp.c but now need to
>    be public to be shared with this scheduler.
>
> NOTE:
>    _Scheduler_SMP_Get_lowest_ready() appears to have a path which would
>    allow it to return a NULL.  Previously, _Scheduler_SMP_Enqueue_ordered()
>    would have asserted on it. If it cannot return a NULL,
>    _Scheduler_SMP_Get_lowest_ready() should have an assertions.
> ---
>   cpukit/score/Makefile.am                           |    1 +
>   .../rtems/score/schedulerpriorityaffinitysmp.h     |   68 +++-
>   .../include/rtems/score/schedulerprioritysmpimpl.h |   84 ++++
>   .../score/include/rtems/score/schedulersmpimpl.h   |  102 +++--
>   cpukit/score/preinstall.am                         |    4 +
>   cpukit/score/src/schedulerpriorityaffinitysmp.c    |  495 +++++++++++++++++++-
>   cpukit/score/src/schedulerprioritysmp.c            |   32 +-
>   cpukit/score/src/schedulersimplesmp.c              |   12 +-
>   8 files changed, 727 insertions(+), 71 deletions(-)
>   create mode 100644 cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h
>
[...]
> diff --git a/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h b/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h
> new file mode 100644
> index 0000000..2d8d1a5
> --- /dev/null
> +++ b/cpukit/score/include/rtems/score/schedulerprioritysmpimpl.h
> @@ -0,0 +1,84 @@
> +/**
> + * @file
> + *
> + * @ingroup ScoreSchedulerPrioritySMP
> + *
> + * @brief Deterministic Priority SMP Scheduler API
> + */
> +
> +/*
> + * Copyright (c) 2013-2014 embedded brains GmbH.  All rights reserved.
> + *
> + *  embedded brains GmbH
> + *  Dornierstr. 4
> + *  82178 Puchheim
> + *  Germany
> + *  <rtems at 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.
> + */
> +
> +#ifndef _RTEMS_SCORE_SCHEDULERPRIORITYSMPIMPL_H
> +#define _RTEMS_SCORE_SCHEDULERPRIORITYSMPIMPL_H
> +
> +#include <rtems/score/scheduler.h>
> +#include <rtems/score/schedulerpriority.h>
> +#include <rtems/score/schedulersmp.h>
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif /* __cplusplus */
> +
> +/**
> + * @ingroup ScoreSchedulerPrioritySMP
> + * @{
> + */
> +
> +Scheduler_priority_SMP_Context *_Scheduler_priority_SMP_Get_self(
> +  Scheduler_Context *context
> +);
> +
> +Scheduler_priority_SMP_Node *_Scheduler_priority_SMP_Node_get(
> +  Thread_Control *thread
> +);
> +
> +void _Scheduler_priority_SMP_Insert_ready_fifo(
> +  Scheduler_Context *context,
> +  Thread_Control *thread
> +);
> +
> +void _Scheduler_priority_SMP_Insert_ready_lifo(
> +  Scheduler_Context *context,
> +  Thread_Control *thread
> +);
> +
> +void _Scheduler_priority_SMP_Move_from_scheduled_to_ready(
> +  Scheduler_Context *context,
> +  Thread_Control *scheduled_to_ready
> +);
> +
> +void _Scheduler_priority_SMP_Move_from_ready_to_scheduled(
> +  Scheduler_Context *context,
> +  Thread_Control *ready_to_scheduled
> +);
> +
> +void _Scheduler_priority_SMP_Extract_from_ready(
> +  Scheduler_Context *context,
> +  Thread_Control *thread
> +);
> +
> +void _Scheduler_priority_SMP_Do_update(
> +  Scheduler_Context *context,
> +  Scheduler_Node *base_node,
> +  Priority_Control new_priority
> +);

Functions used only via the function pointers should be provided as static 
inline so that the compiler can optimize more easily.

> +
> +/** @} */
> +
> +#ifdef __cplusplus
> +}
> +#endif /* __cplusplus */
> +
> +#endif /* _RTEMS_SCORE_SCHEDULERPRIORITYSMPIMPL_H */
> diff --git a/cpukit/score/include/rtems/score/schedulersmpimpl.h b/cpukit/score/include/rtems/score/schedulersmpimpl.h
> index bb7c41e..5356de9 100644
> --- a/cpukit/score/include/rtems/score/schedulersmpimpl.h
> +++ b/cpukit/score/include/rtems/score/schedulersmpimpl.h
> @@ -275,7 +275,14 @@ extern "C" {
>    */
>
>   typedef Thread_Control *( *Scheduler_SMP_Get_highest_ready )(
> -  Scheduler_Context *context
> +  Scheduler_Context *context,
> +  Thread_Control    *blocking
> +);
> +
> +typedef Thread_Control *( *Scheduler_SMP_Get_lowest_scheduled )(
> +  Scheduler_Context *context,
> +  Thread_Control    *thread,
> +  Chain_Node_order   order
>   );
>
>   typedef void ( *Scheduler_SMP_Extract )(
> @@ -304,6 +311,12 @@ typedef void ( *Scheduler_SMP_Enqueue )(
>     Thread_Control *thread_to_enqueue
>   );
>
> +typedef void ( *Scheduler_SMP_Allocate_processor )(
> +  Scheduler_SMP_Context *self,
> +  Thread_Control *scheduled,
> +  Thread_Control *victim
> +);
> +
>   static inline Scheduler_SMP_Context *_Scheduler_SMP_Get_self(
>     Scheduler_Context *context
>   )
> @@ -382,7 +395,7 @@ static inline void _Scheduler_SMP_Update_heir(
>     }
>   }
>
> -static inline void _Scheduler_SMP_Allocate_processor(
> +static void _Scheduler_SMP_Allocate_processor(

Should be "static inline".

>     Scheduler_SMP_Context *self,
>     Thread_Control *scheduled,
>     Thread_Control *victim
> @@ -420,10 +433,13 @@ static inline void _Scheduler_SMP_Allocate_processor(
>     }
>   }
>
> -static inline Thread_Control *_Scheduler_SMP_Get_lowest_scheduled(
> -  Scheduler_SMP_Context *self
> +static Thread_Control *_Scheduler_SMP_Get_lowest_scheduled(
> +  Scheduler_Context *context,
> +  Thread_Control    *filter,
> +  Chain_Node_order   order
>   )
>   {
> +  Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context );
>     Thread_Control *lowest_ready = NULL;
>     Chain_Control *scheduled = &self->Scheduled;
>
> @@ -431,6 +447,12 @@ static inline Thread_Control *_Scheduler_SMP_Get_lowest_scheduled(
>       lowest_ready = (Thread_Control *) _Chain_Last( scheduled );
>     }
>
> +  /*
> +   * _Scheduler_SMP_Enqueue_ordered() assumes that get_lowest_scheduled
> +   * helpers may return NULL. But this method never should.
> +   */
> +  _Assert( lowest_ready != NULL );
> +
>     return lowest_ready;
>   }
>
> @@ -443,28 +465,45 @@ static inline Thread_Control *_Scheduler_SMP_Get_lowest_scheduled(
>    * @param[in] thread The thread to enqueue.
>    * @param[in] order The order function.
>    * @param[in] insert_ready Function to insert a node into the set of ready
> - * nodes.
> + *   nodes.
>    * @param[in] insert_scheduled Function to insert a node into the set of
> - * scheduled nodes.
> + *   scheduled nodes.
>    * @param[in] move_from_scheduled_to_ready Function to move a node from the set
> - * of scheduled nodes to the set of ready nodes.
> + *   of scheduled nodes to the set of ready nodes.
> + * @param[in] get_lowest_scheduled Function to select the thread from the
> + *   scheduled nodes to replace. It may not be possible to find one.
> + * @param[in] allocate_processor Function to allocate a processor to a thread
> + *   based on the rules of the scheduler.
>    */
>   static inline void _Scheduler_SMP_Enqueue_ordered(
> -  Scheduler_Context *context,
> -  Thread_Control *thread,
> -  Chain_Node_order order,
> -  Scheduler_SMP_Insert insert_ready,
> -  Scheduler_SMP_Insert insert_scheduled,
> -  Scheduler_SMP_Move move_from_scheduled_to_ready
> +  Scheduler_Context                 *context,
> +  Thread_Control                    *thread,
> +  Chain_Node_order                   order,

Its not aligned thoroughly.

> +  Scheduler_SMP_Insert                insert_ready,
> +  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_Context *self = _Scheduler_SMP_Get_self( context );
>     Thread_Control *lowest_scheduled =
> -    _Scheduler_SMP_Get_lowest_scheduled( self );
> +    ( *get_lowest_scheduled )( context, thread, order );
>
> -  _Assert( lowest_scheduled != NULL );
> +  /*
> +   *  get_lowest_scheduled can return a NULL if no scheduled threads
> +   *  should be removed from their processor based on the selection
> +   *  criteria. For example, this can occur when the affinity of the
> +   *  thread being enqueued schedules it against higher priority threads.
> +   *  A low priority thread with affinity can only consider the threads
> +   *  which are on the cores if has affinity for.
> +   *
> +   *  The get_lowest_scheduled helper should assert on not returning NULL
> +   *  if that is not possible for that scheduler.
> +   */
>
> -  if ( ( *order )( &thread->Object.Node, &lowest_scheduled->Object.Node ) ) {
> +  if ( lowest_scheduled &&
> +       ( *order )( &thread->Object.Node, &lowest_scheduled->Object.Node ) ) {

I will send a patch that moves this NULL pointer check into the order function 
once this is committed.

[...]

-- 
Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone   : +49 89 189 47 41-16
Fax     : +49 89 189 47 41-09
E-Mail  : sebastian.huber at embedded-brains.de
PGP     : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.



More information about the devel mailing list