Executing Thread Migrating Due to Affinity Change

Fri May 30 15:32:48 UTC 2014

On 05/30/2014 04:43 PM, Joel Sherrill wrote:
> On 5/30/2014 8:33 AM, Sebastian Huber wrote:
>> >On 05/29/2014 09:28 PM, Joel Sherrill wrote:
>>> >>Hi
>>> >>
>>> >>The priority affinity algorithm appears to be behaving as
>>> >>we expect from a decision making standpoint. However,
>>> >>Jennifer and I think that when a scheduled thread must
>>> >>be migrated to another core, we have a case for a new
>>> >>state in the Thread Life Cycle.
>> >I hope we can avoid this.  Which problem do you want to address with
>> >this new state?
> We have some tests that are not behaving on grsim as we expect.
> I was wondering if migrating the executing thread to another core
> would result in some unexpected weirdness. Because of [1], we
> were in desk check and thinking mode to find the problem.
>
> [1] grsim+gdb on multi-core configurations results in an assert
> in RTEMS if you run with a breakpoint set.   You don't have to
> continue -- just "tar remote :2222; load; b XXX; cont" and you
> get an assert. Daniel H. is looking into an example for us.
> But for now, we have no real visibility on leon3. We are in
> the process of switching to the realview on qemu to debug.

What are these for tests and which assertions fail?  Some of the 
smptests work only on real SMP machines.

>>> >>I am thinking that the thread needs to have a blocking state
>>> >>set, have its context saved and be taken out of the scheduled
>>> >>set. Then a life cycle state change handler van run as an
>>> >>extension to unblock it so it can be potentially scheduled to
>>> >>execute on another processor.
>> >The scheduler is not responsible for the thread context.  This is
>> >_Thread_Dispatch().  A post-switch handler can only do actions for the
>> >executing thread.  It would be extremely difficult to perform actions on
>> >behalf of another thread.
> I was thinking that. I couldn't see how it would even work reliably.
> Plus we are
> already technically blocking and unblocking the thread so it should be
> moving
> from scheduled to ready and back.
>> >  We have to keep also fine grained locking
>> >into account.  The _Thread_Dispatch() function is on the critical path
>> >for average and worst-case performance, so we should keep it as simple
>> >as possible.
> I agree.
>> >As I wrote already in another thread you can use something like this to
>> >allocate an exact processor for a thread:
> I suppose I should have posted the patch for review by now but I was hoping
> to have it completely working with tests when posted.  Anyway, it is
> attached. The key is that I modified the priority SMP to let
> let get_lowest_scheduled() and get_highest_ready() both be passed in
> from higher levels.
>
> The selection of get_lowest_scheduled() and get_highest_ready()
> include the option of a filter thread.  The filter thread is used
> as to check that the victim's CPU is in the potential heir's affinity
> set.

Looks good, apart from the extra NULL pointer check.

>
> I think the logic works out so that the normal calls to
> _Scheduler_SMP_Allocate_processor() have selected the
> correct thread/CPU.
>
> I don't see the extra logic in _Scheduler_SMP_Allocate_processor()
> having a negative impact. What do you see that I might be missing?

The current _Scheduler_SMP_Allocate_processor() tries to keep a thread 
on its executing processor.  The thread dispatch is asynchronous on 
SMP.  So for example if you block/unblock a thread extremely fast, then 
this helps to avoid a thread migration.  I think this optimization 
conflicts with the affinity scheduler.

>> >static inline void _Scheduler_SMP_Allocate_processor_exact(
>> >    Scheduler_SMP_Context *self,
>> >    Thread_Control *scheduled,
>> >    Thread_Control *victim
>> >)
>> >{
>> >    Scheduler_SMP_Node *scheduled_node = _Scheduler_SMP_Node_get(
>> >scheduled );
>> >    Per_CPU_Control *cpu_of_scheduled = _Thread_Get_CPU( scheduled );
>> >    Per_CPU_Control *cpu_of_victim = _Thread_Get_CPU( victim );
>> >    Per_CPU_Control *cpu_self = _Per_CPU_Get();
>> >
>> >    _Scheduler_SMP_Node_change_state(
>> >      scheduled_node,
>> >      SCHEDULER_SMP_NODE_SCHEDULED
>> >    );
>> >
>> >    _Thread_Set_CPU( scheduled, cpu_of_victim );
>> >    _Scheduler_SMP_Update_heir( cpu_self, cpu_of_victim, scheduled );
>> >}
>> >
>> >You can even use this function to do things like this:
>> >
>> >_Scheduler_SMP_Allocate_processor_exact(self, executing, other);
>> >_Scheduler_SMP_Allocate_processor_exact(self, other, executing);
>> >
>> >This works because the is executing indicator moved to the thread
>> >context and is maintained at the lowest context switch level.  For
>> >proper migration the scheduler must ensure that,
>> >
>> >1. an heir thread other than the migrating thread exists on the source
>> >processor, and
>> >
>> >2. the migrating thread is the heir thread on the destination processor.
>> >
> Hmmm... If I am using the normal _Scheduler_SMP_Allocate_processor()
> aren't these ensured?

Yes, it is ensured, but you can probably not use this function for your 
affinity scheduler due to the _Scheduler_SMP_Is_processor_owned_by_us( 
self, cpu_of_scheduled ) check.

>
> -- Joel Sherrill, Ph.D. Director of Research & Development 
> joel.sherrill at OARcorp.com On-Line Applications Research Ask me about 
> RTEMS: a free RTOS Huntsville AL 35805 Support Available (256) 722-9985
>
> 0004-Add-SMP-Priority-Scheduler-with-Affinity.patch
>
>
> >From d83641f11d016a2cd73e2661326a5dc873ba0c3c Mon Sep 17 00:00:00 2001
> From: Joel Sherrill<joel.sherrill at oarcorp.com>
> Date: Mon, 19 May 2014 15:26:55 -0500
> Subject: [PATCH 4/4] Add SMP Priority Scheduler with Affinity
>
> Added Thread_Control * parameter to Scheduler_SMP_Get_highest_ready type
> so methods looking for the highest ready thread can filter by the processor
> on which the thread blocking resides. This allows affinity to be considered.
> Simple Priority SMP and Priority SMP ignore this parameter.
>
> This scheduler attempts to account for needed thread migrations.
>
> ==Side Effects of Adding This Scheduler==
>
> + Added get_lowest_scheduled to _Scheduler_SMP_Enqueue_ordered().
>
> + schedulerprioritysmpimpl.h is a new file with prototypes for methods
>    which were formerly static in schedulerprioritysmp.c but now need to
>    be public to be shared with this scheduler.
>
> NOTE:
>    _Scheduler_SMP_Get_lowest_ready() appears to have a path which would
>    allow it to return a NULL.  Previously, _Scheduler_SMP_Enqueue_ordered()
>    would have asserted on it. If it cannot return a NULL,
>    _Scheduler_SMP_Get_lowest_ready() should have an assertions.
[...]
> @@ -448,6 +464,8 @@ static inline Thread_Control *_Scheduler_SMP_Get_lowest_scheduled(
>    * scheduled nodes.
>    * @param[in] move_from_scheduled_to_ready Function to move a node from the set
>    * of scheduled nodes to the set of ready nodes.
> + * @param[in] get_lowest_scheduled Function to select the thread from the
> + * scheduled nodes to replace. It may not be possible to find one.
>    */
>   static inline void _Scheduler_SMP_Enqueue_ordered(
>     Scheduler_Context *context,
> @@ -455,16 +473,28 @@ static inline void _Scheduler_SMP_Enqueue_ordered(
>     Chain_Node_order order,
>     Scheduler_SMP_Insert insert_ready,
>     Scheduler_SMP_Insert insert_scheduled,
> -  Scheduler_SMP_Move move_from_scheduled_to_ready
> +  Scheduler_SMP_Move move_from_scheduled_to_ready,
> +  Scheduler_SMP_Get_lowest_scheduled get_lowest_scheduled
>   )
>   {
>     Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context );
>     Thread_Control *lowest_scheduled =
> -    _Scheduler_SMP_Get_lowest_scheduled( self );
> -
> -  _Assert( lowest_scheduled != NULL );
> +    ( *get_lowest_scheduled )( context, thread, order );
>   
> -  if ( ( *order )( &thread->Object.Node, &lowest_scheduled->Object.Node ) ) {
> +  /*
> +   *  get_lowest_scheduled can return a NULL if no scheduled threads
> +   *  should be removed from their processor based on the selection
> +   *  criteria. For example, this can occur when the affinity of the
> +   *  thread being enqueued schedules it against higher priority threads.
> +   *  A low priority thread with affinity can only consider the threads
> +   *  which are on the cores if has affinity for.
> +   *
> +   *  The get_lowest_scheduled helper should assert on not returning NULL
> +   *  if that is not possible for that scheduler.
> +   */
> +
> +  if ( lowest_scheduled &&
> +       ( *order )( &thread->Object.Node, &lowest_scheduled->Object.Node ) ) {
>       Scheduler_SMP_Node *lowest_scheduled_node =
>         _Scheduler_SMP_Node_get( lowest_scheduled );
>   

I think its possible to avoid the extra NULL pointer check here, if you 
use a special order function that returns false if the second parameter 
is NULL.  The problem is that this adds untestable code for the normal 
SMP schedulers.

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