Partitioned/clustered scheduling

[Gedare Bloom]

On Tue, Nov 19, 2013 at 8:39 AM, Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
> Hello,
>
> we would like to implement partitioned/clustered scheduling for SMP RTEMS.
> The reasons for this are highlighted in
>
> Björn B. Brandenburg, Scheduling and Locking in Multiprocessor Real-Time
> Operating Systems, 2011
>
> 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.
>
Great!

> 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.
> 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.
>
That's fine. I think scheduler run-time (re)configuration is
unnecessary except in some extreme cases for debugging.

> 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.  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.
>
>  /**
>   * @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);
>
This looks good to me. I guess the user must define the table. We
should offer some logical/safe defaults, especially for
single-processor.

> 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.
>
> ==== 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;
>  };
>
For uniprocessor we don't need the owned processor set fields?

> Single processor configurations benefit also from this change since it makes
> all dependencies explicit and easier to access (allows more efficient
> machine
> code).
>
Good. This should eliminate the _Scheduler variable that is the
uniprocessor global scheduler handle? I never liked it.

> ==== 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.
>
Good. What will be the default affinity of the init task?

> 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
>  );
>
These classic API set/get affinity functions seem reasonable. They
mimic existing affinity interfaces nicely. Now users should do
rtems_task_create(), rtems_task_set_affinity(), rtems_task_start() in
order to specify the affinity of their tasks, correct?

-Gedare

> --
> 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.
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel