[V4,07/16] block, bfq: reduce I/O latency for soft real-time applications

To guarantee a low latency also to the I/O requests issued by soft
real-time applications, this patch introduces a further heuristic,
which weight-raises (in the sense explained in the previous patch)
also the queues associated to applications deemed as soft real-time.

To be deemed as soft real-time, an application must meet two
requirements.  First, the application must not require an average
bandwidth higher than the approximate bandwidth required to playback
or record a compressed high-definition video. Second, the request
pattern of the application must be isochronous, i.e., after issuing a
request or a batch of requests, the application must stop issuing new
requests until all its pending requests have been completed. After
that, the application may issue a new batch, and so on.

As for the second requirement, it is critical to require also that,
after all the pending requests of the application have been completed,
an adequate minimum amount of time elapses before the application
starts issuing new requests. This prevents also greedy (i.e.,
I/O-bound) applications from being incorrectly deemed, occasionally,
as soft real-time. In fact, if *any amount of time* is fine, then even
a greedy application may, paradoxically, meet both the above
requirements, if: (1) the application performs random I/O and/or the
device is slow, and (2) the CPU load is high. The reason is the
following.  First, if condition (1) is true, then, during the service
of the application, the throughput may be low enough to let the
application meet the bandwidth requirement.  Second, if condition (2)
is true as well, then the application may occasionally behave in an
apparently isochronous way, because it may simply stop issuing
requests while the CPUs are busy serving other processes.

To address this issue, the heuristic leverages the simple fact that
greedy applications issue *all* their requests as quickly as they can,
whereas soft real-time applications spend some time processing data
after each batch of requests is completed. In particular, the
heuristic works as follows. First, according to the above isochrony
requirement, the heuristic checks whether an application may be soft
real-time, thereby giving to the application the opportunity to be
deemed as such, only when both the following two conditions happen to
hold: 1) the queue associated with the application has expired and is
empty, 2) there is no outstanding request of the application.

Suppose that both conditions hold at time, say, t_c and that the
application issues its next request at time, say, t_i. At time t_c the
heuristic computes the next time instant, called soft_rt_next_start in
the code, such that, only if t_i >= soft_rt_next_start, then both the
next conditions will hold when the application issues its next
request: 1) the application will meet the above bandwidth requirement,
2) a given minimum time interval, say Delta, will have elapsed from
time t_c (so as to filter out greedy application).

The current value of Delta is a little bit higher than the value that
we have found, experimentally, to be adequate on a real,
general-purpose machine. In particular we had to increase Delta to
make the filter quite precise also in slower, embedded systems, and in
KVM/QEMU virtual machines (details in the comments on the code).

If the application actually issues its next request after time
soft_rt_next_start, then its associated queue will be weight-raised
for a relatively short time interval. If, during this time interval,
the application proves again to meet the bandwidth and isochrony
requirements, then the end of the weight-raising period for the queue
is moved forward, and so on. Note that an application whose associated
queue never happens to be empty when it expires will never have the
opportunity to be deemed as soft real-time.

Signed-off-by: Paolo Valente <paolo.valente@linaro.org>

Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>

---
 block/bfq-iosched.c | 342 +++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 323 insertions(+), 19 deletions(-)

-- 
2.10.0

Message ID	20170412162322.11139-8-paolo.valente@linaro.org
State	Accepted
Commit	77b7dcead36d15d7af9159f2a5f91149c5887634
Headers	show Delivered-To: patch@linaro.org Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; From: Paolo Valente <paolo.valente@linaro.org> To: Jens Axboe <axboe@kernel.dk>, Tejun Heo <tj@kernel.org> Cc: Fabio Checconi <fchecconi@gmail.com>, Arianna Avanzini <avanzini.arianna@gmail.com>, linux-block@vger.kernel.org, linux-kernel@vger.kernel.org, ulf.hansson@linaro.org, linus.walleij@linaro.org, broonie@kernel.org, Paolo Valente <paolo.valente@linaro.org> Subject: [PATCH V4 07/16] block, bfq: reduce I/O latency for soft real-time applications Date: Wed, 12 Apr 2017 18:23:13 +0200 Message-Id: <20170412162322.11139-8-paolo.valente@linaro.org> In-Reply-To: <20170412162322.11139-1-paolo.valente@linaro.org> References: <20170412162322.11139-1-paolo.valente@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk
Series	Introduce the BFQ I/O scheduler \| expand [V4,00/16] Introduce the BFQ I/O scheduler [V4,01/16] block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler [V4,02/16] block, bfq: add full hierarchical scheduling and cgroups support [V4,03/16] block, bfq: improve throughput boosting [V4,04/16] block, bfq: modify the peak-rate estimator [V4,05/16] block, bfq: add more fairness with writes and slow processes [V4,06/16] block, bfq: improve responsiveness [V4,07/16] block, bfq: reduce I/O latency for soft real-time applications [V4,08/16] block, bfq: preserve a low latency also with NCQ-capable drives [V4,09/16] block, bfq: reduce latency during request-pool saturation [V4,10/16] block, bfq: add Early Queue Merge (EQM) [V4,11/16] block, bfq: reduce idling only in symmetric scenarios [V4,12/16] block, bfq: boost the throughput on NCQ-capable flash-based devices [V4,13/16] block, bfq: boost the throughput with random I/O on NCQ-capable HDDs [V4,14/16] block, bfq: handle bursts of queue activations [V4,15/16] block, bfq: remove all get and put of I/O contexts [V4,16/16] block, bfq: split bfq-iosched.c into multiple source files

[V4,07/16] block, bfq: reduce I/O latency for soft real-time applications

Commit Message

Patch