Messages in this thread | | | Date | Wed, 29 Mar 2023 10:22:35 +0200 | From | Peter Zijlstra <> | Subject | Re: [PATCH 08/17] sched/fair: Implement an EEVDF like policy |
| |
On Wed, Mar 29, 2023 at 10:06:46AM +0200, Peter Zijlstra wrote: > On Tue, Mar 28, 2023 at 06:26:51PM -0700, Josh Don 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; > > > > Isn't it possible to have a child with less vruntime (ie. rb->left) > > but with the same deadline? Wouldn't it be preferable to choose the > > child instead since the deadlines are equivalent but the child has > > received less service time? > > Possible, yes I suppose. But given this is ns granular virtual time, > somewhat unlikely. You can modify the last (validation) patch and have > it detect the case, see if you can trigger it. > > Doing that will make the pick always do a full decent of the tree > through, which is a little more expensive. Not sure it's worth the > effort.
Hmm, maybe not, if there is no smaller-or-equal deadline then the min_deadline of the child will be greater and we can terminate the decent right there.
| |