Strong APA Scheduler Implementation

[Sebastian Huber]

Hello Darshit,

On 29/06/16 11:56, Darshit Shah wrote:
> Hi,
>
> For the strong APA scheduler, I have added support for storing 
> affinity sets to the Thread node structure. This code was mostly 
> borrowed from the existing code in the priority affinity SMP 
> scheduler. Currently, it was copied, but it should be possible to 
> simply reuse the entire code as well. I'm not sure what the preferred 
> method would be. I've pushed this code to my GitHub repository[1] 
> under the branch strongapa.

I doubt that we are able to re-use much of the priority affinity SMP 
scheduler.  To manage processor sets please use something more efficient 
than cpu_set_t, e.g. Processor_mask or something specialized for your 
scheduler.

>
> When implementing the scheduler, I'd like to be able to run the 
> existing tests in the testsuite, such as the smpschedaffinity* tests 
> and others.  However, most of these tests explicitly use the 
> PRIORITY_AFFINITY_SMP_SCHEDULER in the test itself. I ported one test 
> by copying it and changing the scheduler to STRONG_APA_SCHEDULER, but 
> I was wondering if there would be an easier way to run all the tests 
> without having to copy them first. A global declaration that I can use 
> somewhere to compile all the tests with a particular scheduler. That 
> would make testing very easy.

I would focus on the smpstrongapa01 test. You can add tests for each new 
feature which you add to your implementation. In addition, this makes it 
easier to integrate your stuff early, since you cannot break the other 
parts.

>
> Next, I wanted to discuss the actual implementation of the scheduler.  
> First, I'll explain my understanding of the scheduler's internal 
> working, so if there's a flaw there, it can be caught early on.
>
> When a new task is created, a new thread node is created for it. Task 
> arrival is signalled by the rtems_task_start() method which will 
> invoke the Unblock operation in the scheduler for that thread node. It 
> is during this unblock operation that we need to decide whether this 
> task can be immediately scheduled or not. And if it is scheduled, on 
> which processor should it execute. These decisions are made 
> independently. The unblock operation will invoke the enqueue_fifo 
> operation which tries to push the task to the end of the ready queue. 
> The enqueue_fifo operation tries to get the "lowest_scheduled" task, 
> which is basically the victim task that must be descheduled to allow 
> for the new task to be executed.  The 
> _Scheduler_SMP_Allocate_processor_lazy() method then tries to context 
> switch the threads on the processor on which the victim thread was 
> executing.
>
> However, none of this allows for shifting of tasks. That is, trying to 
> see if the victim thread that was descheduled, can be rescheduled on 
> another processor by replacing a lower priority task. Could this be 
> done by calling the Unblock() operation in the victim thread during 
> the allocate_processor operation?

We have

static inline Thread_Control *_Scheduler_SMP_Enqueue_ordered(
   Scheduler_Context                  *context,
   Scheduler_Node                     *node,
   Thread_Control                     *needs_help,
   Chain_Node_order                    order,
   Scheduler_SMP_Insert                insert_ready,
   Scheduler_SMP_Insert                insert_scheduled,
   Scheduler_SMP_Move                  move_from_scheduled_to_ready,
   Scheduler_SMP_Get_lowest_scheduled  get_lowest_scheduled,
   Scheduler_SMP_Allocate_processor    allocate_processor
)
{
   Scheduler_Node *lowest_scheduled =
     ( *get_lowest_scheduled )( context, node, order );

   if ( ( *order )( &node->Node, &lowest_scheduled->Node ) ) {
     needs_help = _Scheduler_SMP_Enqueue_to_scheduled(
       context,
       node,
       lowest_scheduled,
       insert_scheduled,
       move_from_scheduled_to_ready,
       allocate_processor
     );
   } else {
     ( *insert_ready )( context, node );
   }

   return needs_help;
}

In

   Scheduler_Node *lowest_scheduled =
     ( *get_lowest_scheduled )( context, node, order );

you return the lowest scheduled thread with respect to the affinity set 
of node.

In case ( *order )( &node->Node, &lowest_scheduled->Node ) is true, then 
this node is happy, and the lowest scheduled thread is unhappy. So. in 
move_from_scheduled_to_ready you can carry out forced migrations 
according to the optimization conditions.

Otherwise, the node is unhappy, you can use insert_ready to carry out 
forced migrations according to the optimization conditions.

>
> Now, the main question that I face when trying to implement the 
> scheduler. As I understand, the scheduler operations try to find the 
> victim thread and then replace it with the newly arrived task. 
> However, for the strong APA scheduler, we may need to shift a few 
> tasks around for the most optimum scheduling decision. And these 
> shifts cannot be computed iteratively. That is, we cannot simply 
> invoke the Unblock() operation on the victim thread as I suggested 
> earlier. The entire mapping of tasks to processors will be generated 
> together. So, where exactly should I implement this algorithm? Because 
> it doesn't seem like it can be easily split into the logical sections 
> of get_lowest_scheduled and allocate_processor that the existing 
> algorithms use.
>
> [1]: https://github.com/darnir/rtems
>
>
>
> _______________________________________________
> devel mailing list
> devel at rtems.org
> http://lists.rtems.org/mailman/listinfo/devel

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