Messages in this thread | | | Date | Mon, 2 Oct 2023 19:39:04 +0200 | From | Peter Zijlstra <> | Subject | Re: [PATCH 05/15] sched/fair: Implement an EEVDF like policy |
| |
On Fri, Sep 29, 2023 at 02:40:31PM -0700, Benjamin Segall wrote:
> > +static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) > > +{ > > + struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node; > > + struct sched_entity *curr = cfs_rq->curr; > > + struct sched_entity *best = NULL; > > + > > + if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr))) > > + curr = NULL; > > + > > + while (node) { > > + struct sched_entity *se = __node_2_se(node); > > + > > + /* > > + * If this entity is not eligible, try the left subtree. > > + */ > > + if (!entity_eligible(cfs_rq, se)) { > > + node = node->rb_left; > > + continue; > > + } > > + > > + /* > > + * If this entity has an earlier deadline than the previous > > + * best, take this one. If it also has the earliest deadline > > + * of its subtree, we're done. > > + */ > > + if (!best || deadline_gt(deadline, best, se)) { > > + best = se; > > + if (best->deadline == best->min_deadline) > > + break; > > + } > > + > > + /* > > + * If the earlest deadline in this subtree is in the fully > > + * eligible left half of our space, go there. > > + */ > > + if (node->rb_left && > > + __node_2_se(node->rb_left)->min_deadline == se->min_deadline) { > > + node = node->rb_left; > > + continue; > > + } > > + > > + node = node->rb_right; > > + } > > I believe that this can fail to actually find the earliest eligible > deadline, because the earliest deadline (min_deadline) can be in the > right branch, but that se isn't eligible, and the actual target se is in > the left branch. A trivial 3-se example with the nodes represented by > (vruntime, deadline, min_deadline): > > (5,9,7) > / \ > (4,8,8) (6,7,7) > > AIUI, here the EEVDF pick should be (4,8,8), but pick_eevdf() will > instead pick (5,9,7), because it goes into the right branch and then > fails eligibility. > > I'm not sure how much of a problem this is in practice, either in > frequency or severity, but it probably should be mentioned if it's > an intentional tradeoff.
Well, that is embarrassing :-(
You're quite right -- and I *SHOULD* have double checked my decade old patches, but alas.
Re-reading the paper, your proposal is fairly close to what they have. Let me go stare at your patch in more detail.
| |