Received-SPF: pass (google.com: domain of linux-kernel+bounces-133876-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) client-ip=147.75.48.161;
Date: Sat, 6 Apr 2024 17:23:25 +0800
From: Chen Yu <yu.c.chen@intel.com>
To: Peter Zijlstra <peterz@infradead.org>
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>, <bristot@redhat.com>, <vschneid@redhat.com>,
	<linux-kernel@vger.kernel.org>, <kprateek.nayak@amd.com>,
	<wuyun.abel@bytedance.com>, <tglx@linutronix.de>, <efault@gmx.de>,
	<yu.chen.surf@gmail.com>
Subject: Re: [RFC][PATCH 08/10] sched/fair: Implement delayed dequeue
Message-ID: <ZhEUjX1Nw0y2eJ1o@chenyu5-mobl2>
References: <20240405102754.435410987@infradead.org>
 <20240405110010.631664251@infradead.org>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <20240405110010.631664251@infradead.org>
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?amLTLOecezdgY4rq0OfTWohYdSqabTRBGhjVFtSKZutvOZODe1p9XoulIq9/?=
 =?us-ascii?Q?pX9KDm3xpnT8PgxEWuiXVCHgrQO4nGfELuwmk7Cz/vCA9oh/baYPUHsY5gTV?=
 =?us-ascii?Q?sWqainEXMaZnYyLmt13LIj/5LgvWybsDp8vV1VLGqyS+uhbhy7fpBuMSKYUh?=
 =?us-ascii?Q?xWZ9K6FJaK3ARMpTkO922g9m2aWC/mn2fAWpsvXRl7JMA3OC6+Mdoqz4C49t?=
 =?us-ascii?Q?0r8rZwLvCyGm7BS3rTP8VE3I/QjsrfqL7fQVJTbEEr2F+33iIPHeKg6ZwsrD?=
 =?us-ascii?Q?6jyQ+EgBf5EjyAQ5pqHOVKY3dU3SDauWQv+ti9fxlmHPJT/ktOyPzEYjrwV2?=
 =?us-ascii?Q?IThkSieq9s8vOxi36Cox8zj5JYTD2lUTPLVm4B1B6E3nKN1esyXJr1IzlGTp?=
 =?us-ascii?Q?TTBSgWf9JimO+b/jq6mlU6hyBJbCtYQsD5Xn1JQgZA2tM7XdYj3IZJDB/B9g?=
 =?us-ascii?Q?bq7jouRSBsODdS2GIBthUOn6kQILR33ooRgVioy3UjTNvU6//hd/Crwll9cd?=
 =?us-ascii?Q?WVOWVVlIezGm5Q56Ut/rClqvhVC+IaQrbhozU2PKugmDCVzGq/qSqzy8HRUj?=
 =?us-ascii?Q?3KafJByK6XHuCmetOc471A6XRVDLuUbk9cdSlJgfP3AFvvoAacrR2s94SObI?=
 =?us-ascii?Q?jP8kRwCtqKT9pRy25VOfXn5+82xYMuh8nHG0AupKDrcXvTTwwSzXwV6KvvWQ?=
 =?us-ascii?Q?XqKsLBqC5IIZe7sKn7lXqV2+nmH5gHMIL3h1dsNVf4JVWGKhzQbYqojqKoGd?=
 =?us-ascii?Q?+cBu5JWntVkzKfzGYV18gDfRPdAp7+YeObzjWD6PV6I2tVaT1CtOOiZLOE0T?=
 =?us-ascii?Q?FaWq1v+1hJSRzrVMMtQeVA0IydDKn5xg4oPPQMSK2nWcw+LmJ40GEOVNKZ8R?=
 =?us-ascii?Q?dRNgw++/CwZjWXJIM3TamRJG60hncYXdySxw53iMOrn3gkqhUWyaefJ7kBaZ?=
 =?us-ascii?Q?VNnXwy8Vc7TqwOPzcVHGUwIgrlmfYtuVzZSp+0trJqDxkYcVMlSADn0+UUnf?=
 =?us-ascii?Q?beyqrfo6uXqXZv875az+af2z3ArmO/Mm23Z9QEdP3sIK9mATq2SL2jYeumFY?=
 =?us-ascii?Q?m2moBxn9N+EjwXybXsjMecJVsvSYY0lvPJ05RG+qKQAPt/ZOkVZ/NlKPWygJ?=
 =?us-ascii?Q?G1qkFPjSVU/D15GurPoXVZ7KHUFQgkQdxPpWSL7APpJjPMkLIjXJUoMyveYK?=
 =?us-ascii?Q?8rAeouqH9k6r6F7hCgs3RpfrUHh8LaYgTu1vtawY9Y5HOOm/PB0eKViBZKuj?=
 =?us-ascii?Q?O3guzsXrKl1G1kxhgypQpzvkqxR8bfobS/14o0ekn3gvKkMy3cUBy3ptC3j9?=
 =?us-ascii?Q?TxtvveKSDuV9DyA8+rjIT7D+XKmAHgyVTgZyi8IeJUQ3C2q/fFkKbLVK3JGo?=
 =?us-ascii?Q?vNLC52qyunhkgtsghYhBvHjZxh9cyUdjUYx2dYh9K7ZehhfRFSv/XjxwDQD3?=
 =?us-ascii?Q?1qz1GW85tS5aaMTl8aeOERJAGCWBJL7c9dzj+HHqOonhCvb+DETuZoHtXwm9?=
 =?us-ascii?Q?hodY3KQ89WXAhvgknB/AkF9HCyQHyJbweicxqqJhxjX5xKa70836mqGLPKH9?=
 =?us-ascii?Q?BnKuZHZahWD+eHtL44U9HtaEmieFFYfZrKpB3yMJ?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 50598d8b-1794-4121-1a59-08dc561b3f85
X-MS-Exchange-CrossTenant-AuthSource: DM4PR11MB6020.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 06 Apr 2024 09:23:41.3279
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: e+CSzoR4e/qulZWDv3VaOWPzsfYrwKTP+5od0O4u8bD7s/d2myzWRRWn0VSrw+LFR7tn87JFcNNym0ICZLo3uQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA2PR11MB5161
X-OriginatorOrg: intel.com

On 2024-04-05 at 12:28:02 +0200, Peter Zijlstra wrote:
> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
> noting that lag is fundamentally a temporal measure. It should not be
> carried around indefinitely.
> 
> OTOH it should also not be instantly discarded, doing so will allow a
> task to game the system by purposefully (micro) sleeping at the end of
> its time quantum.
> 
> Since lag is intimately tied to the virtual time base, a wall-time
> based decay is also insufficient, notably competition is required for
> any of this to make sense.
> 
> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
> competing until they are eligible.
> 
> Strictly speaking, we only care about keeping them until the 0-lag
> point, but that is a difficult proposition, instead carry them around
> until they get picked again, and dequeue them at that point.
> 
> Since we should have dequeued them at the 0-lag point, truncate lag
> (eg. don't let them earn positive lag).
> 
> XXX test the cfs-throttle stuff
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---

Tested schbench on xeon server, which has 240 CPUs/2 sockets.
schbench -m 2 -r 100
the result seems ok to me.

baseline:
NO_DELAY_DEQUEUE
NO_DELAY_ZERO
Wakeup Latencies percentiles (usec) runtime 100 (s) (1658446 total samples)
	  50.0th: 5          (361126 samples)
	  90.0th: 11         (654121 samples)
	* 99.0th: 25         (123032 samples)
	  99.9th: 673        (13845 samples)
	  min=1, max=8337
Request Latencies percentiles (usec) runtime 100 (s) (1662381 total samples)
	  50.0th: 14992      (524771 samples)
	  90.0th: 15344      (657370 samples)
	* 99.0th: 15568      (129769 samples)
	  99.9th: 15888      (10017 samples)
	  min=3529, max=43841
RPS percentiles (requests) runtime 100 (s) (101 total samples)
	  20.0th: 16544      (37 samples)
	* 50.0th: 16608      (30 samples)
	  90.0th: 16736      (31 samples)
	  min=16403, max=17698
average rps: 16623.81


DELAY_DEQUEUE
DELAY_ZERO
Wakeup Latencies percentiles (usec) runtime 100 (s) (1668161 total samples)
	  50.0th: 6          (394867 samples)
	  90.0th: 12         (653021 samples)
	* 99.0th: 31         (142636 samples)
	  99.9th: 755        (14547 samples)
	  min=1, max=5226
Request Latencies percentiles (usec) runtime 100 (s) (1671859 total samples)
	  50.0th: 14384      (511809 samples)
	  90.0th: 14992      (653508 samples)
	* 99.0th: 15408      (149257 samples)
	  99.9th: 15984      (12090 samples)
	  min=3546, max=38360
RPS percentiles (requests) runtime 100 (s) (101 total samples)
	  20.0th: 16672      (45 samples)
	* 50.0th: 16736      (52 samples)
	  90.0th: 16736      (0 samples)
	  min=16629, max=16800
average rps: 16718.59


The 99th wakeup latency increases a little bit, and should be in the acceptible
range(25 -> 31 us). Meanwhile the throughput increases accordingly. Here are
the possible reason I can think of:

1. wakeup latency: The time to find an eligible entity in the tree
   during wakeup might take longer - if there are more delayed-dequeue
   tasks in the tree.
2. throughput: Inhibit task dequeue can decrease the ratio to touch the
   task group's load_avg: dequeue_entity()-> { update_load_avg(), update_cfs_group()),
   which reduces the cache contention among CPUs, and improves throughput.


> +	} else {
> +		bool sleep = flags & DEQUEUE_SLEEP;
> +
> +		SCHED_WARN_ON(sleep && se->sched_delayed);
> +		update_curr(cfs_rq);
> +
> +		if (sched_feat(DELAY_DEQUEUE) && sleep &&
> +		    !entity_eligible(cfs_rq, se)) {

Regarding the elibigle check, it was found that there could be an overflow
issue, and it brings false negative of entity_eligible(), which was described here:
https://lore.kernel.org/lkml/20240226082349.302363-1-yu.c.chen@intel.com/
and also reported on another machine
https://lore.kernel.org/lkml/ZeCo7STWxq+oyN2U@gmail.com/
I don't have good idea to avoid that overflow properly, while I'm trying to
reproduce it locally, do you have any guidance on how to address it?

thanks,
Chenyu