Partitioned/clustered scheduling

[Sebastian Huber]

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.

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.

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);

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;
  };

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
  );

-- 
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.