Low level design description for _Scheduler_strong_APA_Get_lowest_scheduled

Sat Aug 8 04:41:47 UTC 2020

Thank you for the feedback.

* put different contributors' copyrights on different lines

Okay.

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

I understand. I'd do this.

> * from L#318-322 you write to the same variables twice, is it redundant
> code?

It is being used to offset by one cpu. First time the variable gets
initialized with caller to cpu_to_preempt, and the second time the caller
to the cpu that was initialized first time.

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

I understand. This would be changed.

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?

Yes, this thought occurred yesterday, since the node isn't in the BLOCKED
state, preempt is unlikely to work.

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.

* Have you been testing your code at all as you go?

Great advice. This is what will be done now. The next time I ask for
review, it would be on a code that would be completely tested and after
making sure that it works perfectly fine as a scheduler based on this test:
https://lists.rtems.org/pipermail/devel/2020-July/060945.html, I'd be using
gdb and qemu for arm realview to step through each function and print
variable names to make sure what I intend to do is what is actually
happening. Please let me know if there's a better way to go about than
doing this.

Thanks again for the review.

On Fri, Aug 7, 2020 at 7:14 PM Gedare Bloom <gedare at rtems.org> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20200808/f99d958c/attachment-0001.html>