Low level design description for _Scheduler_strong_APA_Get_lowest_scheduled

Fri Aug 7 13:44:37 UTC 2020

On Fri, Aug 7, 2020 at 3:51 AM Richi Dubey <richidubey at gmail.com> wrote:
>
> Hi,
>
>> I have a question about: "scenario where all the nodes that we go
>> through have a higher priority (less priority number) than our
>> filter_node(the node to schedule) in which case, we would be returning
>> ret: the minimum priority node encountered but there would be no
>> preemptions and filter_node would remain unassigned"
>>
>>
>>
>> In this case, shouldn't the filter_node remain unscheduled?
>
> Yes, it does remain unscheduled since the priority of ret is more (less in number), the conditional expression for part 3 fails, so there is no task shifting/backtracking and the schedulersmpimpl.h sets needs_help as true because the order function returns false.
>
>
>>  I understand the backtracking aims to follow the bipartite graph
>> backward, pushing tasks to cpus that were traversed. so one way to
>> achieve this is like you are trying, maintain a queue of the traversed
>> tasks/cpus, and just walk them both in reverse order (LIFO) offset by
>> one.
>
> Yes, exactly.
>
>>
>> I don't see why it is necessary for you to be checking the priority
>> values on the backtrack path. You should build these LIFO queues in
>> such a way that they are correctly ordered.
>
> I did not check the priority values on the backtrack path anywhere bw line 314 to 347. All I am doing is starting with the last cpu (offset by 1) and preempting it by it's caller task (the task that added this cpu in the queue). Did I miss something? It's hard to explain (and understand) code like this and I hope what I'm trying to do is clear.
>

I see. I was reading the blog explanation but not looking closely at the code.

I took a quick look at your code (only schedulerstrongapa.c), and have
some comments:
* put different contributors' copyrights on different lines
* it may be worth adding some high-level comment blocks about each
piece of _Scheduler_strong_APA_Get_lowest_scheduled() .  I also
suggest that you try to refactor this function into a few subroutines.
The long function is hard to follow. Refactoring it should help you to
think more clearly how the pieces of it fit together, and to document
what it is doing. You probably have snippets you can copy-paste from
your blog posts.
* from L#318-322 you write to the same variables twice, is it redundant code?
* The do-while loop is not well-written. You have some messy
preamble/epilog code surrounding it. Think whether you can make the
loop cleaner to avoid some redundant parts of the loop body being
copied outside the loop.
* It is unusual to see direct calls to _Scheduler_SMP_Preempt(), you
may want to be sure that is the correct thing to do here.
* Have you been testing your code at all as you go?

I don't think the approach you are taking to start preempting from the
cpu_to_preempt is sound. The problem you'll face is that you haven't
yet preempted the node you want to schedule in place of the victim.
What will happen when you schedule a node that is already
scheduled/executing elsewhere?

You should try to follow the same idea as the original algorithm.
Schedule new_task, and then schedule its victim, then its victim,
etc., until finally you schedule some task whose victim is the
cpu_to_preempt, and you're done.

>> At this point, you might want to see if you can find an implementation
>> of this algorithm (in LitmusRT or Linux) to gain some insights
>
> On it.
>
As we found out, it seems no one has implemented this exactly. But you
can study some similar algorithms such as
https://people.mpi-sws.org/~bbb/papers/ae/ecrts16/laminar-apa.html

-Gedare

> Thanks a lot for the review.
>
>
> On Thu, Aug 6, 2020 at 11:24 PM Gedare Bloom <gedare at rtems.org> wrote:
>>
>> Hi Richi,
>>
>> I have a question about: "scenario where all the nodes that we go
>> through have a higher priority (less priority number) than our
>> filter_node(the node to schedule) in which case, we would be returning
>> ret: the minimum priority node encountered but there would be no
>> preemptions and filter_node would remain unassigned"
>>
>> In this case, shouldn't the filter_node remain unscheduled?
>>
>> On Thu, Aug 6, 2020 at 9:19 AM Richi Dubey <richidubey at gmail.com> wrote:
>> >
>> > The part 3 corresponding to the backtracking changes the filter_node pointer (the original node pointer passed to the function) and calls the Scheduler_SMP_Preempt, all of which is documented in the blog post. I feel like this might mean that the file is taking a higher-level role that it is supposed to and I cannot progress further without your views on this.
>> >
>>
>> I understand the backtracking aims to follow the bipartite graph
>> backward, pushing tasks to cpus that were traversed. so one way to
>> achieve this is like you are trying, maintain a queue of the traversed
>> tasks/cpus, and just walk them both in reverse order (LIFO) offset by
>> one. Thinking like a stack, it is kind of like....
>>
>> while (!done):
>>   c = pop(qCPU)
>>   assign(c, t)
>>   t = pop(qTasks)
>> suspend(t)
>> assign(cpu_to_preempt, new_task)
>>
>> I don't see why it is necessary for you to be checking the priority
>> values on the backtrack path. You should build these LIFO queues in
>> such a way that they are correctly ordered.
>>
>> At this point, you might want to see if you can find an implementation
>> of this algorithm (in LitmusRT or Linux) to gain some insights.
>>
>> Gedare
>>
>> >
>> > On Thu, Aug 6, 2020 at 8:45 PM Richi Dubey <richidubey at gmail.com> wrote:
>> >>
>> >> Hi,
>> >>
>> >> Please find the blog post- https://rtemswithrichi.wordpress.com/strong-apa-low-level-design-in-rtems/ that explains the low-level design for get_lowest_function, importance of which was explained in the earlier high-level design description mail.
>> >>
>> >> I really need your help in figuring out part 3 of the explanation corresponding to backtracking part of the algorithm in the blog post.
>> >>
>> >> If it helps, Please find the latest pull request here and the edited files schedulerstrongapa.c, schedulerstrongapa.h and scheduler.h.
>> >>
>> >> Thanks!
>> >> Richi.
>> >
>> > _______________________________________________
>> > devel mailing list
>> > devel at rtems.org
>> > http://lists.rtems.org/mailman/listinfo/devel