From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.6 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,NICE_REPLY_A,SPF_HELO_NONE,SPF_PASS,USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 93FF0C433B4 for ; Fri, 21 May 2021 13:00:57 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7E480613D8 for ; Fri, 21 May 2021 13:00:57 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232018AbhEUNCP (ORCPT ); Fri, 21 May 2021 09:02:15 -0400 Received: from us-smtp-delivery-124.mimecast.com ([216.205.24.124]:23900 "EHLO us-smtp-delivery-124.mimecast.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229512AbhEUNCN (ORCPT ); Fri, 21 May 2021 09:02:13 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1621602049; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=SP1j3lBexDWEssgurMXzVe6QbtETBwWqUZ3KB+CEW78=; b=LcPeGajnNGbSlDfLkngojnOh8Y3KQcRrV4OfSwh4eKwpUFcCTyWEOUZRJcoCLR7DgtQIV2 wBHk4plCdpBABVxb6ZU+rnAQXtZafdV+rGYL6Aq66KjPN69LYch4p1/2FepIuejcStnNYJ +BsEymbaOk00m+CGdExcz5EUejkJgOc= Received: from mail-lf1-f70.google.com (mail-lf1-f70.google.com [209.85.167.70]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-553-G1_aX_7nMbyO7vvxHB8Wgw-1; Fri, 21 May 2021 09:00:46 -0400 X-MC-Unique: G1_aX_7nMbyO7vvxHB8Wgw-1 Received: by mail-lf1-f70.google.com with SMTP id o4-20020a0565120524b02901fc3210717eso5139870lfc.19 for ; Fri, 21 May 2021 06:00:46 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=SP1j3lBexDWEssgurMXzVe6QbtETBwWqUZ3KB+CEW78=; b=g/7yoCoFG+UhIkY57+YGuOg0Cw9jCiBlOBt3qEKXC3O4Wjhrg9z32p5P0RQiNwtJXb SRIptTXTzNlzYQQGfrS4UIXW7KgdwGw3OfQGN0KbMVlSIvaQNOoncDReoFxio0h7uPYF pHR83Y8ZuYPu+Vbc445TwD4MySMG+xVGnurwCEWeIOUmhzNjDiGEOh86pcznCoPIesN6 K8GdBNMJgztR1T5CgVr57mw7ZjNDoEkhG/1x7lUHECabUnWw1KhG+s286H1vg0AuTJke Dr+ctJ8JQlU9xn9Wo67tiRMDcj0xD1QtFRuO8sLXNOaROPwnHpUyS3aG3I8VlD6j+T0d /8Lw== X-Gm-Message-State: AOAM530toWX4oTmOHO2OKu6U22/qdegcVVtktAN7Ka0mfPDONE+GIOSP x4m2AZv2yCYuEkw3qBfUhPXelrfbl/+P2OVhe18/yKJo0LRUd9mYLs/nUmcGGRncLX9AsLBzi6K svgJEBSrbbSwirV23XSMiwYqG X-Received: by 2002:a2e:5842:: with SMTP id x2mr6722155ljd.228.1621602044866; Fri, 21 May 2021 06:00:44 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwUAgJJeugJDvgzv58Unyyv+sMfrnrZRt7zMDFjI81QGSvDbxDDn0PxzWyb4Ax/MVpyYscj6A== X-Received: by 2002:a2e:5842:: with SMTP id x2mr6722105ljd.228.1621602044422; Fri, 21 May 2021 06:00:44 -0700 (PDT) Received: from x1.bristot.me (host-87-19-51-73.retail.telecomitalia.it. [87.19.51.73]) by smtp.gmail.com with ESMTPSA id g4sm4024868edw.8.2021.05.21.06.00.43 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 21 May 2021 06:00:44 -0700 (PDT) Subject: Re: [PATCH v6 13/21] sched: Admit forcefully-affined tasks into SCHED_DEADLINE To: Will Deacon , Juri Lelli Cc: Quentin Perret , linux-arm-kernel@lists.infradead.org, linux-arch@vger.kernel.org, linux-kernel@vger.kernel.org, Catalin Marinas , Marc Zyngier , Greg Kroah-Hartman , Peter Zijlstra , Morten Rasmussen , Qais Yousef , Suren Baghdasaryan , Tejun Heo , Johannes Weiner , Ingo Molnar , Vincent Guittot , "Rafael J. Wysocki" , kernel-team@android.com References: <20210518105951.GC7770@willie-the-truck> <20210520101640.GA10065@willie-the-truck> <20210520180138.GA10523@willie-the-truck> <20210521103724.GA11680@willie-the-truck> From: Daniel Bristot de Oliveira Message-ID: Date: Fri, 21 May 2021 15:00:42 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.10.1 MIME-Version: 1.0 In-Reply-To: <20210521103724.GA11680@willie-the-truck> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 5/21/21 12:37 PM, Will Deacon wrote: > Interesting, thanks. Thinking about this some more, it strikes me that with > these silly asymmetric systems there could be an interesting additional > problem with hotplug and deadline tasks. Imagine the following sequence of > events: > > 1. All online CPUs are 32-bit-capable > 2. sched_setattr() admits a 32-bit deadline task > 3. A 64-bit-only CPU is onlined At the point 3, the global scheduler assumption is broken. For instance, in a system with four CPUs and five ready 32-bit-capable tasks, when the fifth CPU as added, the working conserving rule is violated because the five highest priority thread are not running (only four are) :-(. So, at this point, for us to keep to the current behavior, the addition should be.. blocked? :-(( > 4. Some of the 32-bit-capable CPUs are offlined Assuming that point 3 does not exist (i.e., all CPUs are 32-bit-capable). At this point, we will have an increase in the pressure on the 32-bit-capable CPUs. This can also create bad effects for 64-bit tasks, as the "contended" 32-bit tasks will still be "queued" in a future time where they were supposed to be done (leaving time for the 64-bit tasks). > I wonder if we can get into a situation where we think we have enough > bandwidth available, but in reality the 32-bit task is in trouble because > it can't make use of the 64-bit-only CPU. I would have to think more, but there might be a case where this contended 32-bit tasks could cause deadline misses for the 64-bit too. > If so, then it seems to me that admission control is really just > "best-effort" for 32-bit deadline tasks on these systems because it's based > on a snapshot in time of the available resources. The admission test as is now is "best-effort" in the sense that it allows a workload higher than it could handle (it is necessary, but not sufficient AC). But it should not be considered "best-effort" because of violations in the working conserving property as a result of arbitrary affinities among tasks. Overall, we have been trying to close any "exception left" to this later case. I know, it is a complex situation, I am just trying to illustrate our concerns, because, in the near future we might have a scheduler that handles arbitrary affinity correctly. But that might require us to stick to an AC. The AC is something precious for us. (yeah, SP would not face this problem... now that I made progress on RV I can get back to it). -- Daniel From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-5.6 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, NICE_REPLY_A,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_SANE_1 autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id B623BC433ED for ; Fri, 21 May 2021 13:04:30 +0000 (UTC) Received: from desiato.infradead.org (desiato.infradead.org [90.155.92.199]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 3D2F6613D8 for ; Fri, 21 May 2021 13:04:30 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 3D2F6613D8 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=desiato.20200630; h=Sender:Content-Transfer-Encoding :Content-Type:List-Subscribe:List-Help:List-Post:List-Archive: List-Unsubscribe:List-Id:In-Reply-To:MIME-Version:Date:Message-ID:From: References:Cc:To:Subject:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=412TZ/w42U7SHl/aW0ehDL68S0DPC0Jrc1hbJQ3Ga0k=; b=cVLCuaYOOJ8BzlF81Q41CwrgzV UM1YuHYWgRbMLJSlSWd29G6MpVYtFOjJvOUS01FPGXlId7kRU5Nw3YJLvy3xEruPY4tZPbRZzVaG5 oR995j5eIGpRWV5ECA3PXCEjMsTRKPUXJbNSpDNctxqmSPkXf2+DyOJslcGg1ocsSs+iTqKkJaIwK 9PJnl4l+Pr3IJKR3dilTd8Sp9m7eZJRvgFsftqSAaiJIcKmMkdnQ5fYu9A2OFHXDoWG1lHDB/rg8r F8Soubp8HEWyCN29rLVzV8gy1V+V/HswZ6yLeO879pROrRG8Q+WYaBGj4p+EiDxuQvYXRNd7tgHsO pw6j5dZQ==; Received: from localhost ([::1] helo=desiato.infradead.org) by desiato.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1lk4lz-005P64-7t; Fri, 21 May 2021 13:01:03 +0000 Received: from bombadil.infradead.org ([2607:7c80:54:e::133]) by desiato.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1lk4lv-005P4x-7x for linux-arm-kernel@desiato.infradead.org; Fri, 21 May 2021 13:00:59 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=Content-Transfer-Encoding: Content-Type:In-Reply-To:MIME-Version:Date:Message-ID:From:References:Cc:To: Subject:Sender:Reply-To:Content-ID:Content-Description; bh=SP1j3lBexDWEssgurMXzVe6QbtETBwWqUZ3KB+CEW78=; b=jD9OonMrCRabwtMRNNpF8DVSo0 Qok1RcrRvj1v3BnY+FvgSVDRq8ClUx1hfvQgtzld+bKk8nxvhPtEEih1K2otGXQb506+aS8iG+G+J RFNlboRBVMTbEmjHU4NKdOJ9jMS/mUKmcXzY1uJteOO2u4p8orgVXaQ93gNzPXx6MAJ7B5m7JzoDF jsviKv79jftTAWutlw6w596Cvu1RJJ9A1KW+51d/eHs3D76Aii6N+Dzn3Xn42K1ejSciW3k0bUTIl 4B+OffFgH0pPo0hY4uJ+r0CMOaET+q3ggKh2XYOAYBbhFURl7Kj1GNOmwVgE3G05P2GCgwvRbN4sv A3jvdxpw==; Received: from us-smtp-delivery-124.mimecast.com ([216.205.24.124]) by bombadil.infradead.org with esmtps (Exim 4.94 #2 (Red Hat Linux)) id 1lk4lr-00H7JD-Ka for linux-arm-kernel@lists.infradead.org; Fri, 21 May 2021 13:00:58 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1621602051; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=SP1j3lBexDWEssgurMXzVe6QbtETBwWqUZ3KB+CEW78=; b=Ntcd36tJQEJxuTSAuhfyA3krwS+a4Xi7fHudMuibgiHXseNE/BERZofuI0x7DlXVGahJpp k/m29WdWIS/Cu0NX+5IOlz3DKNk8JgquKEiV7b+O63/v5oPBDEML0GbqGZTzAtwfM7KkNq AfE4lAlKAcruFo5MoQSrYgH+onLD2c4= Received: from mail-lf1-f71.google.com (mail-lf1-f71.google.com [209.85.167.71]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-313-pgQWMqbYP72Op4pPXK6bwQ-1; Fri, 21 May 2021 09:00:47 -0400 X-MC-Unique: pgQWMqbYP72Op4pPXK6bwQ-1 Received: by mail-lf1-f71.google.com with SMTP id m17-20020a1943510000b0290240943e037bso3816502lfj.4 for ; Fri, 21 May 2021 06:00:47 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=SP1j3lBexDWEssgurMXzVe6QbtETBwWqUZ3KB+CEW78=; b=J1Jdm3fA/gFv8G4OsP2KhAFHODKsEbN4xs7FCtVhZUzciefuiNcLlDSuJTENrTDq44 BgIuZFJjstZLYdaimbHRgHqH1Yo46c/F+y6f7EN31kVL96mny+f7qOrUXvVJpsW3w+oP VAf/opICXXVXbw91cD8le1uE2a3C5jJEtNg7GaY47WsC/GogPEdQ2GVYMzsIjOc9eACG +qYWMQfMZpgYKtvdG0L6ZNnJfVE5KByBFgw+NLmeLey6XbkY33ep/hAWvPFF4LbXrzFg 8ddh5VvZV85tA27TowQN0Oxe9ggH7pIMeEvMrKf6ScDpxh06XYa9zUY/410epx4lydQj dyEg== X-Gm-Message-State: AOAM531xzJrHxJd2RlsXogopDu56HlUaNlt/px+dRGVxytgH4IDeanEV Lw1kvQnwcQhUv8kcFPN0rcJuAdVEVDO4BVaxYa8nSR9qHNcP/tRv0rPmItHJjAlKUAQ8c7kju6B BvJDaECX6W8VTX5YwyIvSN7JTYB7Ha1xPB/0= X-Received: by 2002:a2e:5842:: with SMTP id x2mr6722145ljd.228.1621602044837; Fri, 21 May 2021 06:00:44 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwUAgJJeugJDvgzv58Unyyv+sMfrnrZRt7zMDFjI81QGSvDbxDDn0PxzWyb4Ax/MVpyYscj6A== X-Received: by 2002:a2e:5842:: with SMTP id x2mr6722105ljd.228.1621602044422; Fri, 21 May 2021 06:00:44 -0700 (PDT) Received: from x1.bristot.me (host-87-19-51-73.retail.telecomitalia.it. [87.19.51.73]) by smtp.gmail.com with ESMTPSA id g4sm4024868edw.8.2021.05.21.06.00.43 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 21 May 2021 06:00:44 -0700 (PDT) Subject: Re: [PATCH v6 13/21] sched: Admit forcefully-affined tasks into SCHED_DEADLINE To: Will Deacon , Juri Lelli Cc: Quentin Perret , linux-arm-kernel@lists.infradead.org, linux-arch@vger.kernel.org, linux-kernel@vger.kernel.org, Catalin Marinas , Marc Zyngier , Greg Kroah-Hartman , Peter Zijlstra , Morten Rasmussen , Qais Yousef , Suren Baghdasaryan , Tejun Heo , Johannes Weiner , Ingo Molnar , Vincent Guittot , "Rafael J. Wysocki" , kernel-team@android.com References: <20210518105951.GC7770@willie-the-truck> <20210520101640.GA10065@willie-the-truck> <20210520180138.GA10523@willie-the-truck> <20210521103724.GA11680@willie-the-truck> From: Daniel Bristot de Oliveira Message-ID: Date: Fri, 21 May 2021 15:00:42 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.10.1 MIME-Version: 1.0 In-Reply-To: <20210521103724.GA11680@willie-the-truck> Authentication-Results: relay.mimecast.com; auth=pass smtp.auth=CUSA124A263 smtp.mailfrom=bristot@redhat.com X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20210521_060055_976068_0AEF549C X-CRM114-Status: GOOD ( 23.15 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org On 5/21/21 12:37 PM, Will Deacon wrote: > Interesting, thanks. Thinking about this some more, it strikes me that with > these silly asymmetric systems there could be an interesting additional > problem with hotplug and deadline tasks. Imagine the following sequence of > events: > > 1. All online CPUs are 32-bit-capable > 2. sched_setattr() admits a 32-bit deadline task > 3. A 64-bit-only CPU is onlined At the point 3, the global scheduler assumption is broken. For instance, in a system with four CPUs and five ready 32-bit-capable tasks, when the fifth CPU as added, the working conserving rule is violated because the five highest priority thread are not running (only four are) :-(. So, at this point, for us to keep to the current behavior, the addition should be.. blocked? :-(( > 4. Some of the 32-bit-capable CPUs are offlined Assuming that point 3 does not exist (i.e., all CPUs are 32-bit-capable). At this point, we will have an increase in the pressure on the 32-bit-capable CPUs. This can also create bad effects for 64-bit tasks, as the "contended" 32-bit tasks will still be "queued" in a future time where they were supposed to be done (leaving time for the 64-bit tasks). > I wonder if we can get into a situation where we think we have enough > bandwidth available, but in reality the 32-bit task is in trouble because > it can't make use of the 64-bit-only CPU. I would have to think more, but there might be a case where this contended 32-bit tasks could cause deadline misses for the 64-bit too. > If so, then it seems to me that admission control is really just > "best-effort" for 32-bit deadline tasks on these systems because it's based > on a snapshot in time of the available resources. The admission test as is now is "best-effort" in the sense that it allows a workload higher than it could handle (it is necessary, but not sufficient AC). But it should not be considered "best-effort" because of violations in the working conserving property as a result of arbitrary affinities among tasks. Overall, we have been trying to close any "exception left" to this later case. I know, it is a complex situation, I am just trying to illustrate our concerns, because, in the near future we might have a scheduler that handles arbitrary affinity correctly. But that might require us to stick to an AC. The AC is something precious for us. (yeah, SP would not face this problem... now that I made progress on RV I can get back to it). -- Daniel _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel