Executing Thread Migrating Due to Affinity Change
Joel Sherrill
joel.sherrill at OARcorp.com
Fri May 30 15:41:41 UTC 2014
On 5/30/2014 10:32 AM, Sebastian Huber wrote:
> 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.
New tests from Jennifer. The Daniel's have them so we should get some
feedback. Maybe Jennifer should just posts the tests as is to the list
in case someone else has an idea.
I think this is a grsim/gdb issue. Hopefully the realview/SMP will let
us debug.
>>>>>> 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.
The NULL is used in one case. Which NULL check are you referring to?
_Scheduler_priority_affinity_SMP_Get_lowest_scheduled() can return
NULL if based on the affinity of the thread being considered, it shouldn't
replace any of the scheduled threads.
NULL indicates nothing to do.
>> 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.
Does your _Scheduler_SMP_Allocate_processor_exact() address this? If so,
how?
>>>> 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.
Ahh... let me think about this over the weekend.
Would you mind if _Scheduler_SMP_Allocate_processor() went from inline
to a passed in method? Otherwise, I think there will be a lot of
duplication.
This would seem to be in keeping with the current style.
>> -- 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.
>
--
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
More information about the devel
mailing list