Partitioned/clustered scheduling

[Gedare Bloom]

On Tue, Nov 19, 2013 at 12:36 PM, Gedare Bloom <gedare at rtems.org> wrote:
> 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.
I don't understand what constructors have to do with the scheduler
configuration. Can you explain this a little more or provide an
example?

>> 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
We already do this for the UP scheduling, right? Is the SMP scheduling
a lot harder to estimate for some reasons?

>> 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.
>
I've had some more time to think about this. Can you make it so the
static table-driven approach might be extended in the future to a
dynamic run-time configuration approach? I find it reasonable in the
future that someone might want the ability to add/remove processors to
their RTEMS system. Example scenarios where dynamic processor
management would be wanted include for fault recovery and power
management.

I'm not asking that you make the run-time configuration possible, just
that you keep it in mind as you design the static table-driven
solution. For example, could there possibly be a hook before the
initialization code reads the cpu_config_table that allows for
modifying that table?

-Gedare