Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Sat, 20 May 2023 11:50:13 +0200
From:   luca abeni <luca.abeni@santannapisa.it>
To:     Vineeth Remanan Pillai <vineeth@bitbyteword.org>
Cc:     Juri Lelli <juri.lelli@redhat.com>,
        Daniel Bristot de Oliveira <bristot@redhat.com>,
        Peter Zijlstra <peterz@infradead.org>,
        Ingo Molnar <mingo@redhat.com>,
        Vincent Guittot <vincent.guittot@linaro.org>,
        Steven Rostedt <rostedt@goodmis.org>,
        Joel Fernandes <joel@joelfernandes.org>,
        Dietmar Eggemann <dietmar.eggemann@arm.com>,
        Ben Segall <bsegall@google.com>, Mel Gorman <mgorman@suse.de>,
        Valentin Schneider <vschneid@redhat.com>,
        Jonathan Corbet <corbet@lwn.net>, linux-kernel@vger.kernel.org,
        linux-doc@vger.kernel.org
Subject: Re: [PATCH v3 2/5] sched/deadline: Fix reclaim inaccuracy with SMP
Message-ID: <20230520115013.55c61a00@nowhere>
In-Reply-To: <CAO7JXPhZPvzVRyL87qNT5VnaVOf=0wrRftFB-Rjx-vJc3JUMog@mail.gmail.com>
References: <20230515025716.316888-1-vineeth@bitbyteword.org>
        <20230515025716.316888-3-vineeth@bitbyteword.org>
        <20230515100616.33ba5dd9@luca64>
        <CAO7JXPgq8V5yHM6F2+iXf4XJ9cyT30Hn4ot5b2k7srjsaPc3JQ@mail.gmail.com>
        <20230516093729.0771938c@luca64>
        <CAO7JXPh5uLV4QjAEi6bJXfAGSsZ=XsnCyzrvKS8m35BGbRPYJw@mail.gmail.com>
        <20230519115621.2b3f75e2@luca64>
        <20230519121804.6c85a3ed@luca64>
        <CAO7JXPhZPvzVRyL87qNT5VnaVOf=0wrRftFB-Rjx-vJc3JUMog@mail.gmail.com>
Organization: Scuola Superiore Sant'Anna
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?wd/T//VV4+X7oQ1eCAh8KrEL9oJhd+1fdn6DkhRTB0Cgh2rl/oa1dkJ9MH5Z?=
 =?us-ascii?Q?bZyfVDAZ98PLRDMQ64nwkoAI99AnRy28YtDDCeorrlKVausPYS8nFvu2W1qj?=
 =?us-ascii?Q?r8pbBymlloIqrSqXNSTxKDExL4g4xYLN/f0WYkWu2G1LFgwlz90NYW81SWD6?=
 =?us-ascii?Q?muOUxjh3jEC/ESZFlk/YAuzo3fYNCAwCSy6Zp2mxidupEkHqwYBQyET81CQa?=
 =?us-ascii?Q?VAEn7q/Wp0UZW4wSAG5uP/9Oi4EioD/1/h+h/eJB+vtu1UcZj0u6uMN3NG0X?=
 =?us-ascii?Q?eEG0sMtbxD4WoHw6TFMu6Q/b2GjHzOdqbtDnRrwhbRiY1o5XygLiovKl02IY?=
 =?us-ascii?Q?poPobhJIazw5TpEh6uQKzdcX1bt/BHzhgC72XgrV6VbidKpmz5ByeIRuwTXk?=
 =?us-ascii?Q?POkWghVMHa0iqUkt0+GhPIdR/bynmnxqyyYyn7OhPYDakBWT5ofCsqpJsJjo?=
 =?us-ascii?Q?DkoRl+o2JI30/1jKbgkospn4OXBUjR70q5AX4tK0zB4RpkqGg5lYHT7fPXcR?=
 =?us-ascii?Q?4b2EfPgymlCoWhjPpDqwGsMrwYk5x44gI3ks6ZzQ6Bx5HoLnh1w4waTbIAp0?=
 =?us-ascii?Q?n3GBre1KKj2narP8byDLTTvSJtnx7oaAXEP0MLjiLBd/VJzlTRZOTIavYom8?=
 =?us-ascii?Q?JaOCTYeOhen040Ee0BRINsdwt0w8+/7kogDk9RxdHd1pZ+TYbiVUN5cxM7yd?=
 =?us-ascii?Q?q1wOJjfj/p+RohKeDXdmV6gfBrynv1PgEQoDA+LHso4IKTTqLx9RvxOeho/J?=
 =?us-ascii?Q?jeWf5/L+DKDgcskndZdtnqM/xG6C+cNDja1cqJe8ZLX8cat12qmPhLRT0uWr?=
 =?us-ascii?Q?cjZYu0Dutcmq3LEs4o2TXtn6lV1LiSb8w8fDpShj6ZPNGFn17cqMjiixbefu?=
 =?us-ascii?Q?8X4GH5i7lmy/cRRJr4lAPNYfoWgOZEhp1HMe4rZwFiY29cOt/BKw9Dx4LRD9?=
 =?us-ascii?Q?2BLAJgsFUHPeF/W+XMInsDyi6x2fotmYGiZCr1g4qUGVVdb9uig4AHNeNQ3H?=
 =?us-ascii?Q?zoh3Fijc5R1FqnQxyfpG3PLFH/usf71iTDrkVcQWBkwc8ACUCyziI/irp6dD?=
 =?us-ascii?Q?Ar1yd9JV/CjIMlQQwmwy/ghHR7VrkLavYSYMQcTDkgxdPICnjZ0hnUWs933P?=
 =?us-ascii?Q?L3vmDaXAubZqmbZFkjnTA6Ra+47AedMqZ/KFnOh/SuSsKqqxikK1k+0ZVv2Y?=
 =?us-ascii?Q?lXPR19b5n9jD47NU7MGVKkKrYhTD6ER1eP7mo6Q/Bu8cFr/9RaTtEDwkIEhw?=
 =?us-ascii?Q?wnvKrlFzsGPzqkhcy8K+7rSDbL00JR0ZEEoC8oA9mBX+ak4uDFI9wJfoZyMI?=
 =?us-ascii?Q?/Ne/t5H8D8LrPxPT9t5IA6sENB5y6+hc7SP63l46lNBatrHElDf5tfKXkgoS?=
 =?us-ascii?Q?fFgv7lF+JbCfFg6n1SPVlQmpGDbMj95+3mo5jKAUmOzl2KcuoTPYrXcExL7H?=
 =?us-ascii?Q?kRWN0vagpamWRfT/YBAW9M9HidifuMoyCbTVQcDfuuZtZpzDD7/mzJxJr9nE?=
 =?us-ascii?Q?jCTm+18MN8/4lGsrV1cSLKKe9taOG/1J7SZLZw26AuntnLAVzqifibHygPnK?=
 =?us-ascii?Q?5qkHkXWlTU0tCKSYrXDBRmBhmChQxzOv5QAxw4r4AeCNiGcROGYvERKCElDp?=
 =?us-ascii?Q?gw=3D=3D?=
X-OriginatorOrg: santannapisa.it
X-MS-Exchange-CrossTenant-Network-Message-Id: cae345fc-b475-46df-7382-08db59179f0a
X-MS-Exchange-CrossTenant-AuthSource: VI1PR03MB2880.eurprd03.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 20 May 2023 09:50:19.3136
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: d97360e3-138d-4b5f-956f-a646c364a01e
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: t9Metc8pVwUosvW/Y29vDhGeppKwUBhcE9AZmo4X/yBlN3yR8gC7uco96IXCJ8N8nJLXHFVPgiV3KVNgDvpjdjb8aeq/NsBsJBO5DpP6Ko4=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8PR03MB7253
X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,
        RCVD_IN_MSPIKE_H2,SPF_HELO_PASS,SPF_PASS,T_SCC_BODY_TEXT_LINE,
        URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

Hi,

On Fri, 19 May 2023 12:12:50 -0400
Vineeth Remanan Pillai <vineeth@bitbyteword.org> wrote:
[...]
> With both these equations, it doesn't solve couple of other issues we
> had discussed before:
> - tasks with different bandwidth reclaims differently even when #tasks
>   is less than #cpus.

I think I now understand this issue (see below)


> - cpu util may go to 100% when we have tasks with large bandwidth
> close to Umax

This one is still not clear to me... I'll do some more analysis.


> As an eg. for issue 1, three tasks - (7,10) (3,10) and (1,10):
> TID[590]: RECLAIM=1, (r=7ms, d=10ms, p=10ms), Util: 95.20
> TID[591]: RECLAIM=1, (r=3ms, d=10ms, p=10ms), Util: 81.94
> TID[592]: RECLAIM=1, (r=1ms, d=10ms, p=10ms), Util: 27.19

So, the issue here is that GRUB tries to assign the reclaimed
utilization proportionally to the task's utilizations... So, 591 should
execute 3 times the amount of time executed by 592, and 590 should
execute 7 times the amount of time executed by 592. Task 592 is then
supposed to execute for 95 / (1 + 3 + 7) = 95 / 11 = 8.63% of the CPU
time; task 591 is supposed to execute for 8.63 * 3 = 25.9% of the CPU
time; task 590 is supposed to execute for 8.63 * 7 = 60.64% of the CPU
time.

So, 592 executes for 8.63 * 3 = 25.9% of the time on one single CPU
(you measured 27.19, but this is nead), task 591 executes for
25.9 * 3 = 77.72% of the time on one single CPU (again, this is
close to what you measured) and task 590 should execute for...
60.64 * 3 = 181.3% of the time on one single CPU! Which is clearly not
possible... And the "max{}" rule cuts this to 95%.

So, we are wasting 181.3 - 95 = 86.3% of CPU time, which 590 cannot
reclaim (because it cannot execute simultaneously on 2 CPUs).

And this is close to the amount of CPU time not reclaimed in the test
you cite above (95 - 81 + 95 - 27)


Now that the problem is more clear to me, I am trying to understand a
possible solution (as you mention, moving some extra bandwidth from the
590's CPU will fix this problem... But I am not sure if this dynamic
extra bandwidth migration is feasible in practice without introducing
too much overhead)

I'll look better at your new proposal.


			Thanks,
				Luca