On Fri, May 15, 2020 at 6:39 AM Peter Zijlstra <[email protected]> wrote: > > It's complicated ;-) > > So this sync is basically a relative reset of S to 0. > > So with 2 queues, when one goes idle, we drop them both to 0 and one > then increases due to not being idle, and the idle one builds up lag to > get re-elected. So far so simple, right? > > When there's 3, we can have the situation where 2 run and one is idle, > we sync to 0 and let the idle one build up lag to get re-election. Now > suppose another one also drops idle. At this point dropping all to 0 > again would destroy the built-up lag from the queue that was already > idle, not good. > Thanks for the clarification :-).
I was suggesting an idea of corewide force_idle. We sync the core_vruntime on first force_idle of a sibling in the core and start using core_vruntime for priority comparison from then on. That way, we don't reset the lag on every force_idle and the lag builds up from the first sibling that was forced_idle. I think this would work with infeasible weights as well, but needs to think more to see if it would break. A sample check to enter this core wide force_idle state is: (cpumask_weight(cpu_smt_mask(cpu)) == old_active && new_active < old_active) And we exit the core wide force_idle state when the last sibling goes out of force_idle and can start using min_vruntime for priority comparison from then on. When there is a cookie match on all siblings, we don't do priority comparison now. But I think we need to do priority comparison for cookie matches also, so that we update 'max' in the loop. And for this comparison during a no forced_idle scenario, I hope it should be fine to use the min_vruntime. Updating 'max' in the loop when cookie matches is not really needed for SMT2, but would be needed for SMTn. This is just a wild idea on top of your patches. Might not be accurate in all cases and need to think more about the corner cases. I thought I would think it loud here :-) > So instead of syncing everything, we can: > > less := !((s64)(s_a - s_b) <= 0) > > (v_a - S_a) - (v_b - S_b) == v_a - v_b - S_a + S_b > == v_a - (v_b - S_a + S_b) > > IOW, we can recast the (lag) comparison to a one-sided difference. > So if then, instead of syncing the whole queue, sync the idle queue > against the active queue with S_a + S_b at the point where we sync. > > (XXX consider the implication of living in a cyclic group: N / 2^n N) > > This gives us means of syncing single queues against the active queue, > and for already idle queues to preseve their build-up lag. > > Of course, then we get the situation where there's 2 active and one > going idle, who do we pick to sync against? Theory would have us sync > against the combined S, but as we've already demonstated, there is no > such thing in infeasible weight scenarios. > > One thing I've considered; and this is where that core_active rudiment > came from, is having active queues sync up between themselves after > every tick. This limits the observed divergence due to the work > conservance. > > On top of that, we can improve upon things by moving away from our > horrible (10) hack and moving to (9) and employing (13) here. > > Anyway, I got partway through that in the past days, but then my head > hurt. I'll consider it some more :-) This sounds much better and a more accurate approach then the one I mentioned above. Please share the code when you have it in some form :-) > > > > + new_active++; > > I think we need to reset new_active on restarting the selection. > > But this loop is after selection has been done; we don't modify > new_active during selection. My bad, sorry about this false alarm! > > > + > > > + vruntime_a = se_a->vruntime - cfs_rq_a->core_vruntime; > > > + vruntime_b = se_b->vruntime - cfs_rq_b->core_vruntime; > > Should we be using core_vruntime conditionally? should it be min_vruntime > > for > > default comparisons and core_vruntime during force_idle? > > At the very least it should be min_vruntime when cfs_rq_a == cfs_rq_b, > ie. when we're on the same CPU. > yes, this makes sense. The issue that I was thinking about is, when there is no force_idle and all siblings run compatible tasks for a while, min_vruntime progresses, but core_vruntime lags behind. And when a new task gets enqueued, it gets the min_vruntime. But now during comparison it might be treated unfairly. Consider a small example of two rqs rq1 and rq2. rq1->cfs->min_vruntime = 1000 rq2->cfs->min_vruntime = 2000 During a force_idle, core_vruntime gets synced and rq1->cfs->core_vruntime = 1000 rq2->cfs->core_vruntime = 2000 Now, suppose the core is out of force_idle and runs two compatible tasks for a while, where the task on rq1 has more weight. min_vruntime progresses on both, but slowly on rq1. Say the progress looks like: rq1->cfs->min_vruntime = 1200, se1->vruntime = 1200 rq2->cfs->min_vruntime = 2500, se2->vruntime = 2500 If a new incompatible task(se3) gets enqueued to rq2, it's vruntime would be based on rq2's min_vruntime, say: se3->vruntime = 2500 During our priority comparison, lag would be: l_se1 = 200 l_se3 = 500 So se1, will get selected and run with se2 until its lag catches up with se3's lag(even if se3 has more weight than se1). This is a hypothetical situation, but can happen I think. And if we use min_vruntime for comparison during no force_idle scenario, we could avoid this. What do you think? I didn't clearly understand the tick based active sync and probably would better fix this problem I guess. Thanks, Vineeth
