Strong APA Scheduler Implementation

[Darshit Shah]

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.

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.

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?

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

-- 
Thanking You,
Darshit Shah
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 843 bytes
Desc: not available
URL: <http://lists.rtems.org/pipermail/devel/attachments/20160629/ed1a293c/attachment.bin>