<div dir="ltr">Thank you for the feedback.<div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">* put different contributors' copyrights on different lines</blockquote><div>Okay. </div><div><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">* it may be worth adding some high-level comment blocks about each<br>piece of _Scheduler_strong_APA_Get_lowest_scheduled() .  I also<br>suggest that you try to refactor this function into a few subroutines.<br>The long function is hard to follow. Refactoring it should help you to<br>think more clearly how the pieces of it fit together, and to document<br>what it is doing. You probably have snippets you can copy-paste from<br>your blog posts.</blockquote><div>I understand. I'd do this.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">* from L#318-322 you write to the same variables twice, is it redundant code?</blockquote><div>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.</div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">* The do-while loop is not well-written. You have some messy<br>preamble/epilog code surrounding it. Think whether you can make the<br>loop cleaner to avoid some redundant parts of the loop body being<br>copied outside the loop.<br>* It is unusual to see direct calls to _Scheduler_SMP_Preempt(), you<br>may want to be sure that is the correct thing to do here.</blockquote><div>I understand. This would be changed.</div></div><div><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I don't think the approach you are taking to start preempting from the<br>cpu_to_preempt is sound. The problem you'll face is that you haven't<br>yet preempted the node you want to schedule in place of the victim.<br>What will happen when you schedule a node that is already<br>scheduled/executing elsewhere?</blockquote><div>Yes, this thought occurred yesterday, since the node isn't in the BLOCKED state, preempt is unlikely to work.  </div><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">You should try to follow the same idea as the original algorithm.<br>Schedule new_task, and then schedule its victim, then its victim,<br>etc., until finally you schedule some task whose victim is the<br>cpu_to_preempt, and you're done.</blockquote></div><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">* Have you been testing your code at all as you go?</blockquote><div>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: <a href="https://lists.rtems.org/pipermail/devel/2020-July/060945.html">https://lists.rtems.org/pipermail/devel/2020-July/060945.html</a>, 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.</div><div><br></div><div>Thanks again for the review.  </div></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Aug 7, 2020 at 7:14 PM Gedare Bloom <<a href="mailto:gedare@rtems.org">gedare@rtems.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Fri, Aug 7, 2020 at 3:51 AM Richi Dubey <<a href="mailto:richidubey@gmail.com" target="_blank">richidubey@gmail.com</a>> wrote:<br>
><br>
> Hi,<br>
><br>
>> I have a question about: "scenario where all the nodes that we go<br>
>> through have a higher priority (less priority number) than our<br>
>> filter_node(the node to schedule) in which case, we would be returning<br>
>> ret: the minimum priority node encountered but there would be no<br>
>> preemptions and filter_node would remain unassigned"<br>
>><br>
>><br>
>><br>
>> In this case, shouldn't the filter_node remain unscheduled?<br>
><br>
> 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.<br>
><br>
><br>
>>  I understand the backtracking aims to follow the bipartite graph<br>
>> backward, pushing tasks to cpus that were traversed. so one way to<br>
>> achieve this is like you are trying, maintain a queue of the traversed<br>
>> tasks/cpus, and just walk them both in reverse order (LIFO) offset by<br>
>> one.<br>
><br>
> Yes, exactly.<br>
><br>
>><br>
>> I don't see why it is necessary for you to be checking the priority<br>
>> values on the backtrack path. You should build these LIFO queues in<br>
>> such a way that they are correctly ordered.<br>
><br>
> 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.<br>
><br>
<br>
I see. I was reading the blog explanation but not looking closely at the code.<br>
<br>
I took a quick look at your code (only schedulerstrongapa.c), and have<br>
some comments:<br>
* put different contributors' copyrights on different lines<br>
* it may be worth adding some high-level comment blocks about each<br>
piece of _Scheduler_strong_APA_Get_lowest_scheduled() .  I also<br>
suggest that you try to refactor this function into a few subroutines.<br>
The long function is hard to follow. Refactoring it should help you to<br>
think more clearly how the pieces of it fit together, and to document<br>
what it is doing. You probably have snippets you can copy-paste from<br>
your blog posts.<br>
* from L#318-322 you write to the same variables twice, is it redundant code?<br>
* The do-while loop is not well-written. You have some messy<br>
preamble/epilog code surrounding it. Think whether you can make the<br>
loop cleaner to avoid some redundant parts of the loop body being<br>
copied outside the loop.<br>
* It is unusual to see direct calls to _Scheduler_SMP_Preempt(), you<br>
may want to be sure that is the correct thing to do here.<br>
* Have you been testing your code at all as you go?<br>
<br>
I don't think the approach you are taking to start preempting from the<br>
cpu_to_preempt is sound. The problem you'll face is that you haven't<br>
yet preempted the node you want to schedule in place of the victim.<br>
What will happen when you schedule a node that is already<br>
scheduled/executing elsewhere?<br>
<br>
You should try to follow the same idea as the original algorithm.<br>
Schedule new_task, and then schedule its victim, then its victim,<br>
etc., until finally you schedule some task whose victim is the<br>
cpu_to_preempt, and you're done.<br>
<br>
>> At this point, you might want to see if you can find an implementation<br>
>> of this algorithm (in LitmusRT or Linux) to gain some insights<br>
><br>
> On it.<br>
><br>
As we found out, it seems no one has implemented this exactly. But you<br>
can study some similar algorithms such as<br>
<a href="https://people.mpi-sws.org/~bbb/papers/ae/ecrts16/laminar-apa.html" rel="noreferrer" target="_blank">https://people.mpi-sws.org/~bbb/papers/ae/ecrts16/laminar-apa.html</a><br>
<br>
-Gedare<br>
<br>
> Thanks a lot for the review.<br>
><br>
><br>
> On Thu, Aug 6, 2020 at 11:24 PM Gedare Bloom <<a href="mailto:gedare@rtems.org" target="_blank">gedare@rtems.org</a>> wrote:<br>
>><br>
>> Hi Richi,<br>
>><br>
>> I have a question about: "scenario where all the nodes that we go<br>
>> through have a higher priority (less priority number) than our<br>
>> filter_node(the node to schedule) in which case, we would be returning<br>
>> ret: the minimum priority node encountered but there would be no<br>
>> preemptions and filter_node would remain unassigned"<br>
>><br>
>> In this case, shouldn't the filter_node remain unscheduled?<br>
>><br>
>> On Thu, Aug 6, 2020 at 9:19 AM Richi Dubey <<a href="mailto:richidubey@gmail.com" target="_blank">richidubey@gmail.com</a>> wrote:<br>
>> ><br>
>> > 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.<br>
>> ><br>
>><br>
>> I understand the backtracking aims to follow the bipartite graph<br>
>> backward, pushing tasks to cpus that were traversed. so one way to<br>
>> achieve this is like you are trying, maintain a queue of the traversed<br>
>> tasks/cpus, and just walk them both in reverse order (LIFO) offset by<br>
>> one. Thinking like a stack, it is kind of like....<br>
>><br>
>> while (!done):<br>
>>   c = pop(qCPU)<br>
>>   assign(c, t)<br>
>>   t = pop(qTasks)<br>
>> suspend(t)<br>
>> assign(cpu_to_preempt, new_task)<br>
>><br>
>> I don't see why it is necessary for you to be checking the priority<br>
>> values on the backtrack path. You should build these LIFO queues in<br>
>> such a way that they are correctly ordered.<br>
>><br>
>> At this point, you might want to see if you can find an implementation<br>
>> of this algorithm (in LitmusRT or Linux) to gain some insights.<br>
>><br>
>> Gedare<br>
>><br>
>> ><br>
>> > On Thu, Aug 6, 2020 at 8:45 PM Richi Dubey <<a href="mailto:richidubey@gmail.com" target="_blank">richidubey@gmail.com</a>> wrote:<br>
>> >><br>
>> >> Hi,<br>
>> >><br>
>> >> Please find the blog post- <a href="https://rtemswithrichi.wordpress.com/strong-apa-low-level-design-in-rtems/" rel="noreferrer" target="_blank">https://rtemswithrichi.wordpress.com/strong-apa-low-level-design-in-rtems/</a> that explains the low-level design for get_lowest_function, importance of which was explained in the earlier high-level design description mail.<br>
>> >><br>
>> >> I really need your help in figuring out part 3 of the explanation corresponding to backtracking part of the algorithm in the blog post.<br>
>> >><br>
>> >> If it helps, Please find the latest pull request here and the edited files schedulerstrongapa.c, schedulerstrongapa.h and scheduler.h.<br>
>> >><br>
>> >> Thanks!<br>
>> >> Richi.<br>
>> ><br>
>> > _______________________________________________<br>
>> > devel mailing list<br>
>> > <a href="mailto:devel@rtems.org" target="_blank">devel@rtems.org</a><br>
>> > <a href="http://lists.rtems.org/mailman/listinfo/devel" rel="noreferrer" target="_blank">http://lists.rtems.org/mailman/listinfo/devel</a><br>
</blockquote></div>