Partitioned/clustered scheduling

[Sebastian Huber]

On 2013-11-19 22:22, Chris Johns wrote:
> 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 ?

It has a high priority, so Q1 2014.

>
>> Björn B. Brandenburg, Scheduling and Locking in Multiprocessor Real-Time
>> Operating Systems, 2011
>
> http://www.cs.unc.edu/~bbb/diss/brandenburg-diss.pdf ?

Yes, also interesting:

A. Burns and A.J. Wellings, A Schedulability Compatible Multiprocessor Resource 
Sharing Protocol - MrsP, Proceedings of the 25th Euromicro Conference on 
Real-Time Systems (ECRTS 2013), July 2013

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

Yes, but I think it is desirable to have a working scheduler setup once 
multi-threading started.

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

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.

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

Ok, I will clarify this.  It is important that RTEMS doesn't claim all 
processors in the system automatically.

>
> What other operating systems are you referring to ?

You may use for example an RTEMS instance on two processors and Linux on 
another 22 of a 24 processor chip.

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

The low-level start is a different issue.  I have no plans to change something 
here at the moment.

>
>>
>>   /**
>>    * @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 ?

Currently no, but I don't see any problems for adding this later.

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