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

From: Peter Zijlstra
Date: Tue Aug 06 2024 - 04:27:30 EST


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.