From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mta21.hihonor.com (mta21.honor.com [81.70.160.142]) (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 80B932FD7D0 for ; Fri, 5 Dec 2025 08:00:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=81.70.160.142 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764921665; cv=none; b=FhJ0+YJ/uRQ0yYSGw8Nnxm/xWv9yHzwxhf7xulvgPP5JWleCqwt84eW16Szbbz/PBrrFjpVc0gdu1bILgwmmvOWUYmPyeffI8Oj/JufwCKFGBY3JwSiDNoXbQoaboqX8l61+2iEchVi9r0v1CPW9nr4TQv8/BI5Hr5wR45ff1TE= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1764921665; c=relaxed/simple; bh=DMzsMSCHXQ8Tj/IZUFoMGDABXkKNNTYq4IiDbxzswYc=; h=From:To:CC:Subject:Date:Message-ID:References:In-Reply-To: Content-Type:MIME-Version; b=un25ows0BRB28pKryu20o7V4HEvTSNeEEFyUOkPBDdwd6+Te6N2K4f5kcrFzr2CHdsEGmKs8Xu7YsJxnWExSKVAK/XcFI47SR6iwACiuMN+1xjGq8FGytcmlGNd5RQKWHmJROTRch/ZLebYcAhNYjbW1XMCpprFataooK3BpNms= 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.160.142 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 w011.hihonor.com (unknown [10.68.20.122]) by mta21.hihonor.com (SkyGuard) with ESMTPS id 4dN3dz68DSzYnjLK; Fri, 5 Dec 2025 15:58:15 +0800 (CST) Received: from a008.hihonor.com (10.68.30.56) by w011.hihonor.com (10.68.20.122) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.2562.27; Fri, 5 Dec 2025 16:00:43 +0800 Received: from a011.hihonor.com (10.68.31.243) by a008.hihonor.com (10.68.30.56) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.2562.27; Fri, 5 Dec 2025 16:00:43 +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; Fri, 5 Dec 2025 16:00:43 +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: AQHcYD7CRlSxrKgAvUCneCj7ZjASSbUHTFyAgAVePrCAAUxbAIABqCPg Date: Fri, 5 Dec 2025 08:00:42 +0000 Message-ID: <56e5a5e79bc84d5a924835f83f16f162@honor.com> References: <20251128081118.20025-1-tao.wangtao@honor.com> <20251128092923.GC3245006@noisy.programming.kicks-ass.net> <84787b6343fd4ac595a185645ced1de5@honor.com> <20251202151732.GD2458571@noisy.programming.kicks-ass.net> In-Reply-To: <20251202151732.GD2458571@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 >=20 > Not unclear, still not sure how its a fairness issue. Yes it increases co= ntext > switches, but fairness is about the amount of time distributed, not about > when time is given. >=20 > It is entirely reasonable for a task that wakes up to run now if it has p= ositive > lag. >=20 Tasks with larger lag should run first. If a task with smaller lag runs earlier, it is unfair in those time slices, or you can say it is not reason= able. It may be easier to explain this by separating inqueue_lag (lag), join_lag (jlag), and leave_lag (llag). For all tasks in the queue, \Sum lag_i is 0, but \Sum jlag_i is not always = 0. Suppose the current V =3D V0, all weights are 1, and we add four tasks with jlag values 0, 10, 80, and -12. Considering preserve-lag handling with vlag_i =3D (W + w_i) * vlag_i' / W: ----------------------------- event | jlag | v | W | V ----------------------------- add T1 | 0 | V0 | 1 | V0 add T2 | 20 | V0-20 | 2 | V0-10 add T3 | 120 | V0-130 | 3 | V0-50 add T4 | -16 | V0-34 | 4 | V0-46 Because V becomes smaller after adding T2 and T3, even though lag_T4 < 0, we still have v_T3 < v_T4 < v_T2 < v_T1. So the schedule order is T3, T4, T2, T1. A similar issue exists even without preserve-lag. If tasks are added in order T2, T3, T1, T4, the schedule order becomes T3, T1, T4, T2, which shows instability. >=20 > Which is creating a new clock that absorbs a non-zero lag sum? >=20 > 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. > Earlier I did not clearly separate jlag/lag/llag. Intuitively one may think sum_jlag =3D \Sum jlag_j - \Sum llag_l. But \Sum llag_l may approach 0, while \Sum jlag_j may not have a clear boundary. For example, if all jlag>0 go to cfs_rq0 and all jlag<0 go to cfs_rq1, then \Sum jlag_j of cfs_rq0 is unbounded. =20 >From deriving the leave process, we find that jlag_l and llag_l are not alw= ays equal. We define A to stay unchanged when tasks join or leave, and we have: v =3D V - vlag =3D A - vjlag J =3D A - V J * W =3D sum_jlag =3D (\Sum jlag_j - \Sum jlag_l) 1) A task leaves and later re-joins. We know its previous llag. Set jlag_j =3D llag. Then v_j =3D A - vjlag_j keeps A unchanged: A_j =3D (A * W + v_j * w_j + vjlag_j * w_j) / (W + w_j) =3D A 2) For any task i running in the queue, v_i and V change. Then vlag_i =3D V - v_i also changes, but vjlag_i does not change. 3) When a task leaves, from v_l we get vllag_l =3D V - v_l and vjlag_l =3D A - v_l. vjlag_l =3D vllag_l + A - V =3D vllag_l + J Because J may not be 0, vjlag_l and vllag_l are not always equal. Now we analyze the boundary of sum_jlag: When a task is added: sum_jlag_j =3D sum_jlag + jlag_j Here jlag_j is the llag from the last leave. Its upper bound is the same as the lag limit q. Adding n tasks means sum_jlag does not exceed q * n. When a task leaves: sum_jlag_l =3D sum_jlag - jlag_l =3D sum_jlag - vjlag_l * w_l sum_jlag_l =3D sum_jlag - (vllag_l + J) * w_l sum_jlag_l =3D sum_jlag - llag_l - sum_jlag * w_l / W sum_jlag_l =3D sum_jlag * (W - w_l) / W - llag_l This means sum_jlag is reduced proportionally by weight. When all tasks leave, sum_jlag becomes the last llag. If n tasks are added and m tasks leave, the upper bound of sum_jlag is still no more than q * (n - m). Using v_j =3D A - vjlag_j makes scheduling more stable when tasks join or leave. It is equal to preserve vlag =3D vjlag - J. Using the same example with jlag values 0, 10, 80, -12: ------------------------------------------ event | jlag | v | W | V | J ------------------------------------------ add T1 | 0 | V0 | 1 | V0 | 0 add T2 | 10 | V0-10 | 2 | V0-5 | 5 add T3 | 80 | V0-80 | 3 | V0-30 | 30 add T4 | -12 | V0+12 | 4 | V0-19.5 | 19.5 As long as the four tasks are added at the same time, no matter the order, the schedule order will be T3, T2, T1, T4. Thank, Tao