Partitioned/clustered scheduling

[Sebastian Huber]

On 2013-11-19 21:17, Gedare Bloom wrote:
> 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?

I just wanted to give examples why a run-time only configuration is problematic.

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

Its a bit harder to get right since you now have multiple schedulers to estimate.

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

I have no budget or customer demand to implement dynamic run-time scheduler 
re-configuration explicitly, but I have it in mind and will do nothing which 
prevents it in the future.  I also think it will be very easy to implement if 
needed.  The blocking point for this is currently that we don't know when a 
thread stops execution on a particular processor, but this issue has to be 
solved for other purposes as well.

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