From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mta20.hihonor.com (mta20.hihonor.com [81.70.206.69]) (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 E569C2FD7CA for ; Tue, 2 Dec 2025 12:43:24 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=81.70.206.69 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764679407; cv=none; b=qKNFpNdJVnqBZ+pkygUgDux6n9TS+B6ICdg5JSZzc+MilFhg6ANW92ItCf5wHq7GzBOpQ4wyJttOfgPtPsiaJAOEQUsHKZr/htDX6XWaF8FMxSK+sUWKDXNbf/2oJJ4lqHUBdlXAELK/+8eOJQ06hx+A7LUko+NTtLOIbC/daTE= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764679407; c=relaxed/simple; bh=duyzuKRMkhsrYks/qbE2saOiCVePZhDOHkUo/4txtXc=; h=From:To:CC:Subject:Date:Message-ID:References:In-Reply-To: Content-Type:MIME-Version; b=jydMVmw/ZWD2YFBIYtRqCLc7RP3NvRibjkMXxnBc7T7KZ6vh4vp46GZlsv22fZEOZs7fKYeH4hZq8cGksbtdixUfDt4L1h82ctFDL+XqHVqfXMPAyMlKyYRBt9ycaHpS7dfuurVJDjGWG2SAJvtKZSe3a2xaJ542bQyCHh8oV/k= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=honor.com; spf=pass smtp.mailfrom=honor.com; arc=none smtp.client-ip=81.70.206.69 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=honor.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=honor.com Received: from w012.hihonor.com (unknown [10.68.27.189]) by mta20.hihonor.com (SkyGuard) with ESMTPS id 4dLL3S1f7BzYl2n6; Tue, 2 Dec 2025 20:40:52 +0800 (CST) Received: from w004.hihonor.com (10.68.29.54) by w012.hihonor.com (10.68.27.189) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1544.11; Tue, 2 Dec 2025 20:43:15 +0800 Received: from a011.hihonor.com (10.68.31.243) by w004.hihonor.com (10.68.29.54) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.2562.27; Tue, 2 Dec 2025 20:43:15 +0800 Received: from a011.hihonor.com ([fe80::2ded:f949:6f48:faf]) by a011.hihonor.com ([fe80::2ded:f949:6f48:faf%7]) with mapi id 15.02.2562.027; Tue, 2 Dec 2025 20:43:15 +0800 From: wangtao To: Peter Zijlstra 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 Thread-Topic: [PATCH] sched: fair: make V move forward only Thread-Index: AQHcYD7CRlSxrKgAvUCneCj7ZjASSbUHTFyAgAVePrA= Date: Tue, 2 Dec 2025 12:43:15 +0000 Message-ID: <84787b6343fd4ac595a185645ced1de5@honor.com> References: <20251128081118.20025-1-tao.wangtao@honor.com> <20251128092923.GC3245006@noisy.programming.kicks-ass.net> In-Reply-To: <20251128092923.GC3245006@noisy.programming.kicks-ass.net> Accept-Language: zh-CN, en-US Content-Language: zh-CN X-MS-Has-Attach: X-MS-TNEF-Correlator: Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 > -----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 >=20 > 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, >=20 > Have you actually read the paper? Why do you think this breaks fairness? >=20 > > causing previously eligible tasks to become ineligible, shorter > > runtimes, and more task switches. >=20 > None of that is a fairness issue. Those are issues related to when, rathe= r than > how much time is given. >=20 Maybe my earlier explanation was unclear, so here is a detailed example. The run queue is empty. V is V_0. We add three tasks A, X, B in order. lag_A =3D 0, lag_X > 0, lag_B =3D 0. To simplify, assume the time gaps of the three additions are so small that we can treat them as zero. Add task A: v_A =3D V_0. After adding A, V does not change, V_A =3D V_0. Add task X: v_X =3D V_A =3D V_0. After adding X, V_B < V_0. Add task B: v_B =3D V_X < V_0 =3D v_A. After adding B, V_B =3D V_X < V_0. X runs first. After X runs, because v_B < v_A, we also get deadline_B < deadline_A. So the later-added task B runs before A, which is not fair. But in reality the three additions have time gaps. Suppose A runs for a short time before adding X. Let V_A' be V at that moment, and let v_A' be A's vruntime. We have v_A' =3D V_A' > V_0. v_X =3D V_A' - lag_X < V_A'. After putting X into the queue, V becomes smaller: V_X < V_A'. Since v_A' > V_X, A becomes uneligible. Even if A is in protect_slice, it will switch to X immediately, increasing context switches. Here is a trace where several tasks sleep for a while and then run briefly: v_30981 =3D 16015784959115 =3D V, schedule 30981 -0 (...) place_entity ... pid 30981 vruntime 16015784959115 vlag 0 = lag 0 sched_switch ... next_pid=3D30981 ... After adding 30983, since vlag_30983 > 0: v_30983 =3D 16015785028217 < V_30981' =3D v_30981' =3D 16015785080365 place_entity ... pid 30983 vruntime 16015785028217 vlag 26074 lag 52148 After adding 30982, even though vlag_30982 < 0, because vlag_30983 is large: v_30982 =3D 16015785061209 < V_30981' =3D 16015785080365 place_entity ... pid 30982 vruntime 16015785061209 vlag -670 lag -3793 Switch to 30983: sched_switch ... next_pid=3D30983 ... Then task 30982 with negative vlag runs before 30981: sched_switch ... next_pid=3D30982 ... sched_switch ... next_pid=3D30981 ... sched_switch ... next_pid=3D0 ... > > Making V move forward only resolves such issues and simplifies the > > code for adding tasks with positive lag. >=20 > It breaks a metric ton of math. Which you don't provide updates for. >=20 > 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 c= oherent > 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. >=20 > 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. >=20 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 =3D 0, but in many cases \Sum lag_i is not zero. 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. Our goal is \Sum lag_i =3D 0. So when task i finishes running and is remove= d from the queue, its lag is: lag_i =3D S - s_i =3D w_i * (V - v_i) After some time, when task i is added back, the other tasks' v have changed, and V has changed. Let A be V at that moment: \Sum lag_i =3D \Sum w_i * (A - v_i) We can compute A from v_i and lag_i: A =3D \Sum (w_i * v_i + lag_i) / \Sum w_i =3D \Sum (w_i * v_i + lag_i) / = W Use A to compute v for the newly added task k. After adding k: A' =3D (\Sum (w_i * v_i + lag_i) + w_k * v_k + lag_k) / (W + w_k) To preserve lag_k, set v_k =3D A' - lag_k / w_k, then: A' =3D (\Sum (w_i * v_i + lag_i) + w_k * A') / (W + w_k) A' * (W + w_k) =3D \Sum (w_i * v_i + lag_i) + w_k * A' A' =3D \Sum (w_i * v_i + lag_i) / W =3D 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 =3D 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. > The delayed dequeue feature tries to address some of these concerns by > keeping non-eligible (negative lag) tasks on the runqueue until such time > that they become eligible (approximated by getting picked again) at which > point they get removed (and any positive lag gets truncated, as if they w= ere > removed at zero-lag). As a consequence you will have much less removal of > negative lag, additionally such tasks will be eligible the moment they co= me > back. >=20 > Also, there is the small matter that your patch simply does not apply. Thanks, Tao