<div dir="ltr">Hi,<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">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" </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">In this case, shouldn't the filter_node remain unscheduled?</blockquote><div>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 <a href="https://git.rtems.org/rtems/tree/cpukit/include/rtems/score/schedulersmpimpl.h?id=6014fadb5a5ef44c609e9e482ff837f1ff060d93#n892">sets</a> needs_help as true because the order function returns false. </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"> 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. </blockquote><div>Yes, exactly.</div><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">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.</blockquote><div>I did not check the priority values on the backtrack path anywhere bw line <a href="https://github.com/richidubey/rtems/blob/9cc11fb283114f032c34602552c59fe51c1b0a58/cpukit/score/src/schedulerstrongapa.c#L314">314</a> to <a href="https://github.com/richidubey/rtems/blob/9cc11fb283114f032c34602552c59fe51c1b0a58/cpukit/score/src/schedulerstrongapa.c#L347">347</a>. 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. </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">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 </blockquote><div>On it. </div><div><br></div><div>Thanks a lot for the review.</div><div><br></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Aug 6, 2020 at 11:24 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">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>