Low level design description for _Scheduler_strong_APA_Get_lowest_scheduled

[Richi Dubey]

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
<https://git.rtems.org/rtems/tree/cpukit/include/rtems/score/schedulersmpimpl.h?id=6014fadb5a5ef44c609e9e482ff837f1ff060d93#n892>
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
<https://github.com/richidubey/rtems/blob/9cc11fb283114f032c34602552c59fe51c1b0a58/cpukit/score/src/schedulerstrongapa.c#L314>
to
347
<https://github.com/richidubey/rtems/blob/9cc11fb283114f032c34602552c59fe51c1b0a58/cpukit/score/src/schedulerstrongapa.c#L347>.
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.

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.

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/20200807/f9bd95f5/attachment.html>