Partitioned/clustered scheduling

[Chris Johns]

On 20/11/2013 12:39 am, Sebastian Huber wrote:
> Hello,
>
> we would like to implement partitioned/clustered scheduling for SMP
> RTEMS.  The reasons for this are highlighted in
>

What time frame are you looking at for this ?

> Björn B. Brandenburg, Scheduling and Locking in Multiprocessor Real-Time
> Operating Systems, 2011

http://www.cs.unc.edu/~bbb/diss/brandenburg-diss.pdf ?

> Partitioned/clustered scheduling means that the set of processors of a
> system can be partitioned into pairwise disjoint subsets.  Each subset
> of processors will be owned by one scheduler instance.

Nice.

>
> The following proposal covers the processor configuration, high-level
> scheduler implementation and RTEMS API changes.
>
> ==== Scheduler Configuration ====
>
> There are two options for the scheduler instance configuration
>
> # static configuration by means of global data structures, and
> # configuration at run-time via function calls.
>
> For a configuration at run-time the system must start with a default
> scheduler.
> The global constructors are called in this environment.  The order of
> global
> constructor invocation is unpredictable so it is difficult to create
> threads in
> this context since the run-time scheduler configuration may not exist yet.
> Since scheduler data structures are allocated from the workspace the
> configuration must take a later run-time setup of schedulers into
> account for
> the workspace size estimate.  In case the default scheduler is not
> appropriate
> it must be replaced which gives raise to some implementation difficulties.

I am not sure static constructors is a good example. If a user is 
wanting runtime configuration and is doing this inside static 
constructors they need to manage the dependences. A C++ programmer needs 
to know this.

> Since the processor availability is determined by hardware constraints
> it is
> unclear which benefits a run-time configuration has.  For now run-time
> configuration of scheduler instances will be not implemented.

It may not be clear at this point in time and concentrating on a static 
configuration may be ok however I would hope the design is such it could 
be possible if a suitable use case appears. Will this be possible ?

>
> The focus is now on static configuration.  Every scheduler needs a control
> context.  The scheduler API must provide a macro which creates a global
> scheduler instance specific data structure with a designator name as a
> mandatory parameter.  The scheduler instance creation macro may require
> additional scheduler specific configuration options.  For example a
> fixed-priority scheduler instance must know the maximum priority level to
> allocate the ready chain control table.
>
> Once the scheduler instances are configured it must be specified for each
> processor in the system which scheduler instance owns this processor.
>
> For each processor except the initialization processor a scheduler
> instance is
> optional so that other operating systems can run independent of this RTEMS
> system on this processor.

I am not sure I follow. You say a scheduler instance must be specified 
for each processor then you say for each processor a scheduler instance 
is optional.

What other operating systems are you referring to ?

>  It is a fatal error to omit a scheduler
> instance for
> the initialization processor.  The initialization processor is the
> processor
> which executes the boot_card() function.

Will RTEMS manage the starting of other cores ? At the moment this is 
not the way it works and it places an unneeded dependency on the boot 
monitor. I would like to see code in RTEMS to manage this and plan to 
add Zynq support to do this.

>
>   /**
>    * @brief Processor configuration.
>    *
>    * Use RTEMS_CPU_CONFIG_INIT() to initialize this structure.
>    */
>   typedef struct {
>     /**
>      * @brief Scheduler instance for this processor.
>      *
>      * It is possible to omit a scheduler instance for this processor by
> using
>      * the @c NULL pointer.  In this case RTEMS will not use this
> processor and
>      * other operating systems may claim it.
>      */
>     Scheduler_Control *scheduler;
>   } rtems_cpu_config;
>
>   /**
>    * @brief Processor configuration initializer.
>    *
>    * @param scheduler The reference to a scheduler instance or @c NULL.
>    *
>    * @see rtems_cpu_config.
>    */
>   #define RTEMS_CPU_CONFIG_INIT(scheduler) \
>     { ( scheduler ) }
>
> Scheduler and processor configuration example:
>
>   RTEMS_SCHED_DEFINE_FP_SMP(sched_fp0, 256);
>   RTEMS_SCHED_DEFINE_FP_SMP(sched_fp1, 64);
>   RTEMS_SCHED_DEFINE_EDF_SMP(sched_edf0);
>
>   const rtems_cpu_config rtems_cpu_config_table[] = {
>     RTEMS_CPU_CONFIG_INIT(RTEMS_SCHED_REF_FP_SMP(sched_fp0)),
>     RTEMS_CPU_CONFIG_INIT(RTEMS_SCHED_REF_FP_SMP(sched_fp1)),
>     RTEMS_CPU_CONFIG_INIT(RTEMS_SCHED_REF_FP_SMP(sched_fp1)),
>     RTEMS_CPU_CONFIG_INIT(RTEMS_SCHED_REF_FP_SMP(sched_fp1)),
>     RTEMS_CPU_CONFIG_INIT(NULL),
>     RTEMS_CPU_CONFIG_INIT(NULL),
>     RTEMS_CPU_CONFIG_INIT(RTEMS_SCHED_REF_EDF_SMP(sched_edf0)),
>     RTEMS_CPU_CONFIG_INIT(RTEMS_SCHED_REF_EDF_SMP(sched_edf0)
>   };
>
>   const size_t rtems_cpu_config_count =
>     RTEMS_ARRAY_SIZE(rtems_cpu_config_table);
>
> An alternative to the processor configuration table would be to specify
> in the
> scheduler instance which processors are owned by the instance.  This would
> require a static initialization of CPU sets which is difficult.  Also the
> schedulers have to be registered somewhere, so some sort of table is needed
> anyway.  Since a processor can be owned by at most one scheduler
> instance this
> configuration approach enables an additional error source which is
> avoided by
> the processor configuration table.

Is there support to add and remove processors and provide any form of 
dynamic control ?

Chris

>
> ==== Scheduler Implementation Changes ====
>
> Currently the scheduler operations have no control context and use global
> variables instead.  Thus the scheduler operations signatures must change
> to use
> a scheduler control context as the first parameter, e.g.
>
>   typedef struct Scheduler_Control Scheduler_Control;
>
>   typedef struct {
>     [...]
>     void ( *set_affinity )(
>       Scheduler_Control *self,
>       Thread_Control *thread,
>       size_t affinity_set_size,
>       const cpu_set_t *affinity_set
>     );
>     [...]
>   } Scheduler_Operations;
>
>   /**
>    * @brief General scheduler control.
>    */
>   struct Scheduler_Control {
>     /**
>      * @brief The scheduler operations.
>      */
>     Scheduler_Operations Operations;
>
>     /**
>      * @brief Size of the owned processor set in bytes.
>      */
>     size_t owned_cpu_set_size
>
>     /**
>      * @brief Reference to the owned processor set.
>      *
>      * A set bit means this processor is owned by this scheduler
> instance, an
>      * unset bit means the opposite.
>      */
>     cpu_set_t *owned_cpu_set;
>   };
>
> Single processor configurations benefit also from this change since it
> makes
> all dependencies explicit and easier to access (allows more efficient
> machine
> code).
>
> ==== RTEMS API Changes ====
>
> Each thread needs a processor affinity set in the RTEMS SMP
> configuration.  The
> rtems_task_create() function will use the processor affinity set of the
> executing thread to initialize the processor affinity set of the created
> task.  This enables backward compatibility for existing software.
>
> Two new functions should be added to alter and retrieve the processor
> affinity
> sets of threads.
>
>   /**
>    * @brief Sets the processor affinity set of a task.
>    *
>    * @param[in] task_id Identifier of the task.  Use @ref RTEMS_SELF to
> select
>    * the executing task.
>    * @param[in] affinity_set_size Size of the specified affinity set in
> bytes.
>    * This value must be positive.
>    * @param[in] affinity_set The processor affinity set for the task.  This
>    * pointer must not be @c NULL.  A set bit in the affinity set means
> that the
>    * task can execute on this processor and an unset bit means the
> opposite.
>    *
>    * @retval RTEMS_SUCCESSFUL Successful operation.
>    * @retval RTEMS_INVALID_ID Invalid task identifier.
>    * @retval RTEMS_INVALID_CPU_SET Invalid processor affinity set.
>    */
>   rtems_status_code rtems_task_set_affinity(
>     rtems_id task_id,
>     size_t affinity_set_size,
>     const cpu_set_t *affinity_set
>   );
>
>   /**
>    * @brief Gets the processor affinity set of a task.
>    *
>    * @param[in] task_id Identifier of the task.  Use @ref RTEMS_SELF to
> select
>    * the executing task.
>    * @param[in] affinity_set_size Size of the specified affinity set in
> bytes.
>    * This value must be positive.
>    * @param[out] affinity_set The processor affinity set of the task.  This
>    * pointer must not be @c NULL.  A set bit in the affinity set means
> that the
>    * task can execute on this processor and an unset bit means the
> opposite.
>    *
>    * @retval RTEMS_SUCCESSFUL Successful operation.
>    * @retval RTEMS_INVALID_ID Invalid task identifier.
>    * @retval RTEMS_INVALID_CPU_SET The affinity set is too small for the
>    * processor affinity set of the task.
>    */
>   rtems_status_code rtems_task_get_affinity(
>     rtems_id task_id,
>     size_t affinity_set_size,
>     cpu_set_t *affinity_set
>   );
>