From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from casper.infradead.org (casper.infradead.org [90.155.50.34]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7C07613D891 for ; Tue, 2 Dec 2025 15:17:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=90.155.50.34 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764688670; cv=none; b=X2yaA93qGkUjz5H9tFlaybrUAWyD98QyxbRYONxC8GglVNHl8RkM8hwJDS7Tp1CuzsoH5y4Ep4MamShEArZNBjnldngRYQrtLw5C5XfYL+jX2SwbO7OvTPTSY62XnX8Qsv6ihfKUlce9Zqbw2oPLPnkEc/ehvTiYQb+XDQdfzPo= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764688670; c=relaxed/simple; bh=0zwrhoo8vr1uKc45dcD66I0t+72OKZ+VEwPpTvoL1DY=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=J1B8NxNSMsdZJY9hY2VvLFAvYlLwgaVuAnZ6pFzcr8WjyUMBU6WixcEYJTPDe/F2wUtiOJ40nhzGkVoJSYqOMm0dcZGYsqUJ+XYWhAslbxI9MFuANOeRLT77eouTKDl2yYPKpHPfAuHQui8d2TmBe0La3PkCfW8QJrcb37SJdPY= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=none smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=R0q5DQNh; arc=none smtp.client-ip=90.155.50.34 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="R0q5DQNh" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=casper.20170209; h=In-Reply-To:Content-Type:MIME-Version: References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description; bh=g0TnYNwp/+cTHJh9bP2jzk0WciqpXzncvvpHCdD5jfc=; b=R0q5DQNh9og49CVf2xJsNfE8Bd j6lfDtHRNyeBDXLq95lKGfRFXtrv7ei04EoH7x3ZvcFVKa636+Z76BymVUzvN+pk0kQRCj38Abdv4 yT+I0dKedUN66xx0b3WA2062IPZG7OTLdMU/St6rAa6MZf68Uzed7p3RRC+ubIsa71mz0GP4uNil0 ln5ISkzFCCgp2Cxn+nI3iEDhnmOpAwJrWDmjrA/cujzdx2Q6GRqW3W2FmFv/wSe69/wcdROzIZpXA fDj4NYHUlyFk2W8XyYVdVUYvYunRefa2PE7NchD9d+9d65FkLKPk3x83AHFxY99cDTOazc/5mJLvJ B8uSFe5Q==; Received: from 77-249-17-252.cable.dynamic.v4.ziggo.nl ([77.249.17.252] helo=noisy.programming.kicks-ass.net) by casper.infradead.org with esmtpsa (Exim 4.98.2 #2 (Red Hat Linux)) id 1vQS8E-00000001M1p-2Npb; Tue, 02 Dec 2025 15:17:34 +0000 Received: by noisy.programming.kicks-ass.net (Postfix, from userid 1000) id 389E730027B; Tue, 02 Dec 2025 16:17:32 +0100 (CET) Date: Tue, 2 Dec 2025 16:17:32 +0100 From: Peter Zijlstra To: wangtao Cc: "mingo@redhat.com" , "juri.lelli@redhat.com" , "vincent.guittot@linaro.org" , "dietmar.eggemann@arm.com" , "rostedt@goodmis.org" , "bsegall@google.com" , "mgorman@suse.de" , "vschneid@redhat.com" , "linux-kernel@vger.kernel.org" , liulu 00013167 , "wangbintian(BintianWang)" , wangzicheng Subject: Re: [PATCH] sched: fair: make V move forward only Message-ID: <20251202151732.GD2458571@noisy.programming.kicks-ass.net> References: <20251128081118.20025-1-tao.wangtao@honor.com> <20251128092923.GC3245006@noisy.programming.kicks-ass.net> <84787b6343fd4ac595a185645ced1de5@honor.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <84787b6343fd4ac595a185645ced1de5@honor.com> On Tue, Dec 02, 2025 at 12:43:15PM +0000, wangtao wrote: > > > -----Original Message----- > > From: Peter Zijlstra > > Sent: Friday, November 28, 2025 5:29 PM > > To: wangtao > > Cc: mingo@redhat.com; juri.lelli@redhat.com; vincent.guittot@linaro.org; > > dietmar.eggemann@arm.com; rostedt@goodmis.org; bsegall@google.com; > > mgorman@suse.de; vschneid@redhat.com; linux-kernel@vger.kernel.org; > > liulu.liu@honor.com; bintian.wang@honor.com > > Subject: Re: [PATCH] sched: fair: make V move forward only > > > > On Fri, Nov 28, 2025 at 04:11:18PM +0800, wangtao wrote: > > > V is the weighted average of entities. Adding tasks with positive lag > > > or removing tasks with negative lag may cause V to move backward. This > > > will result in unfair task scheduling, > > > > Have you actually read the paper? Why do you think this breaks fairness? > > > > > causing previously eligible tasks to become ineligible, shorter > > > runtimes, and more task switches. > > > > None of that is a fairness issue. Those are issues related to when, rather than > > how much time is given. > > > Maybe my earlier explanation was unclear, so here is a detailed example. Not unclear, still not sure how its a fairness issue. Yes it increases context switches, but fairness is about the amount of time distributed, not about when time is given. It is entirely reasonable for a task that wakes up to run now if it has positive lag. > > > Making V move forward only resolves such issues and simplifies the > > > code for adding tasks with positive lag. > > > > It breaks a metric ton of math. Which you don't provide updates for. > > > > Yes, the paper is light on dynamic behaviour, but please don't disregard the > > math like this. Either stay inside the constraints laid out, or provide coherent > > alternatives. Notably EEVDF is in the same class of scheduling functions as > > WF2Q and both provide better lag bounds than the simpler WFQ class of > > schedulers. > > > > The 'zero-lag point is the weighted average of the entities' is a fairly core > > tenet of EEVDF. Mucking with this *will* mess with the lag bounds. > > > You are right. The reasoning should be based on math. I will submit a new > patch based on the derivation below. > > When deriving V, we previously assumed \Sum lag_i = 0, but in many cases > \Sum lag_i is not zero. Sure, which is where the V adjustments come from. > The simplest case is when the run queue is empty and we add a task with > lag not zero, Then \Sum lag_i is clearly not zero. Well, all of this is only valid under contention. If there is only a single task, there is no lag. Note how we ignore lag when placing the first entry. Still the point remains, you can leave/join with non-zero lag, and in those cases we have to adjust V. > Our goal is \Sum lag_i = 0. This is equivalent to the statement that the zero-lag point is the weighted average of vruntime. These two things are interchangeable. > So when task i finishes running and is removed > from the queue, its lag is: > > lag_i = S - s_i = w_i * (V - v_i) Yes, but taking it out also affects V. > After some time, when task i is added back, Note how you state we're adding _i_ back. > the other tasks' v have > changed, and V has changed. Let A be V at that moment: > > \Sum lag_i = \Sum w_i * (A - v_i) You need to introduce more indices, i was our removed task, but now you're re-using i to sum over the remaining tasks? And if indeed you did mean: \Sun_j!=i lag_j = \Sum_j!=i w_j * (A - v_j) \Sum v_j * w_j Then yes, because A, or rather V = -------------- \Sum w_j Making both left- and right-hand expressions 0. > We can compute A from v_i and lag_i: > > A = \Sum (w_i * v_i + lag_i) / \Sum w_i = \Sum (w_i * v_i + lag_i) / W You're doing: lag_j = w_j * (A - v_j) lag_j ----- = A - v_j w_j lag_j ----- + v_j = A w_j lag_j v_j * w_j ----- + --------- = A w_j w_j lag_j + v_j * w_j ----------------- = A w_j Which is creating a new clock that absorbs a non-zero lag sum? I don't think there's a bound on the difference between A and V. You can extract unbounded lag from the system. We recently had someone showcase exactly that, they managed to wrap V backwards far enough to make the old min_vruntime thing wrap the s64 space and things went sideways real fast. > Use A to compute v for the newly added task k. But you were adding task i, per [*] > After adding k: > > A' = (\Sum (w_i * v_i + lag_i) + w_k * v_k + lag_k) / (W + w_k) > > To preserve lag_k, set v_k = A' - lag_k / w_k, then: > > A' = (\Sum (w_i * v_i + lag_i) + w_k * A') / (W + w_k) > A' * (W + w_k) = \Sum (w_i * v_i + lag_i) + w_k * A' > A' = \Sum (w_i * v_i + lag_i) / W = A > > This shows that adding task k does not change A. > Similarly, removing task k does not change A. > > It is easy to get: > > A = V + (\Sum lag_i) / W > > \Sum lag_i stays around 0 when tasks are added or removed. > > The roles of V and A are: > 1) Use V to judge whether task is eligible. > 2) Use V to compute lag when a task is removed. > 3) Use A to compute v when a task is added. So I don't think A can work. As mentioned, they can drift unbounded, and per that they would also break the lag bounds as outlined in lemmas 3 and onwards. Now, there is a clue in the WF2Q paper, that it is possible to change the V function. This is mentioned in the future work section of the paper. I've never gotten around to figuring out which paper that is and getting a copy.