Re: [GIT PULL] sched_ext: Initial pull request for v6.11

[Peter Zijlstra]

On Fri, Aug 02, 2024 at 08:47:51AM -1000, Tejun Heo wrote:

> > > +static bool consume_remote_task(struct rq *rq, struct scx_dispatch_q *dsq,
> > > +				struct task_struct *p, struct rq *task_rq)
> > > +{
> > > +	bool moved = false;
> > > +
> > > +	lockdep_assert_held(&dsq->lock);	/* released on return */
> > > +
> > > +	/*
> > > +	 * @dsq is locked and @p is on a remote rq. @p is currently protected by
> > > +	 * @dsq->lock. We want to pull @p to @rq but may deadlock if we grab
> > > +	 * @task_rq while holding @dsq and @rq locks. As dequeue can't drop the
> > > +	 * rq lock or fail, do a little dancing from our side. See
> > > +	 * move_task_to_local_dsq().
> > > +	 */
> > > +	WARN_ON_ONCE(p->scx.holding_cpu >= 0);
> > > +	task_unlink_from_dsq(p, dsq);
> > > +	dsq_mod_nr(dsq, -1);
> > > +	p->scx.holding_cpu = raw_smp_processor_id();
> > > +	raw_spin_unlock(&dsq->lock);
> > > +
> > > +	double_lock_balance(rq, task_rq);
> > > +
> > > +	moved = move_task_to_local_dsq(rq, p, 0);
> > > +
> > > +	double_unlock_balance(rq, task_rq);
> > > +
> > > +	return moved;
> > > +}
> > 
> > I've gotta ask, why are you using the double_lock_balance() pattern
> > instead of the one in move_queued_task() that does:
> > 
> >   lock src
> >   dequeue src, task
> >   set_task_cpu task, dst
> >   unlock src
> > 
> >   lock dst
> >   enqueue dst, task
> >   unlock dst
> 
> When !CONFIG_PREEMPTION, double_lock_balance() seems cheaper than unlocking
> and locking unconditionally. Because SCX schedulers can do a lot more hot
> migrations, I thought it'd be better to go that way. I haven't actually
> measured anything tho, so I could be wrong.

So I think the theory is something like this.

If you take a spinlock, you wait-time W is N times the hold-time H,
where the hold-time is avg/max (depending on your analysis goals) time
you hold the lock for, and N is the contention level or number of
waiters etc.

Now, when you go nest locks, your hold-time increases with the wait-time
of the nested lock. In this case, since it's the 'same' lock, your
hold-time gets a recursive wait-time term, that is: H'=H+N*H.

This blows up your wait-time, which makes contention worse. Because what
was W=N*H then becomes W=N*(N*H).

Anyway, at the time we saw great benefits from moving away from the
double-lock thing, it might be worth looking into when/if you see
significant lock contention; because obviously if the locks are not
contended it all doesn't matter.