cfq-iosched: adapt slice to number of processes doing I/O
RFC PATCH v2 1/5 cfq-iosched: adapt slice to number of processes doing I/O
When the number of processes performing I/O concurrently increases, a fixed time slice per process will cause large latencies.
This patch, if low_latency mode is enabled, will scale the time slice assigned to each process according to a 300ms target latency.
In order to keep fairness among processes:
* The number of active processes is computed using a special form of running average, that quickly follows sudden increases (to keep latency low), and decrease slowly (to have fairness in spite of rapid decreases of this value).
To safeguard sequential bandwidth, we impose a minimum time slice (computed using 2*cfq_slice_idle as base, adjusted according to priority and async-ness).
--- block/cfq-iosched.c | 46 ++++++++++++++++++++++++++++++++++++++++++++-- 1 files changed, 44 insertions(+), 2 deletions(-)
block/cfq-iosched.c +44 -2
@@ -27,6 +27,8 @@ static const int cfq_slice_sync = HZ / 10;static int cfq_slice_async =HZ /25 ;static const int cfq_slice_async_rq =2 ;static int cfq_slice_idle =HZ /125 ; +static const int cfq_target_latency =HZ *3 /10 ;/* 300 ms */ +static const int cfq_hist_divisor =4 ;/* * offset from end of service tree
@@ -134,6 +136,8 @@ struct cfq_data {struct rb_root prio_trees[CFQ_PRIO_LISTS ];unsigned int busy_queues; +unsigned int busy_rt_queues; +unsigned int busy_queues_avg[2 ];int rq_in_driver[2 ];int sync_flight;
@@ -301,10 +305,45 @@ cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)return cfq_prio_slice (cfqd,cfq_cfqq_sync (cfqq), cfqq->ioprio); } +/* +* get averaged number of queues of RT/BE priority. +* average is updated, with a formula that gives more weight to higher numbers, +* to quickly follows sudden increases and decrease slowly +*/ + +static inline unsigned +cfq_get_avg_queues (struct cfq_data *cfqd,bool rt) { +unsigned min_q, max_q; +unsigned mult = cfq_hist_divisor -1 ; +unsigned round = cfq_hist_divisor /2 ; +unsigned busy = cfqd->busy_rt_queues; + +if (!rt) + busy = cfqd->busy_queues - cfqd->busy_rt_queues; + + min_q =min (cfqd->busy_queues_avg[rt], busy); + max_q =max (cfqd->busy_queues_avg[rt], busy); + cfqd->busy_queues_avg[rt] = (mult * max_q + min_q + round) / + cfq_hist_divisor; +return cfqd->busy_queues_avg[rt]; +} +static inline void cfq_set_prio_slice (struct cfq_data *cfqd,struct cfq_queue *cfqq) { - cfqq->slice_end =cfq_prio_to_slice (cfqd, cfqq) + jiffies; +unsigned slice =cfq_prio_to_slice (cfqd, cfqq); +if (cfqd->cfq_latency) { +unsigned iq =cfq_get_avg_queues (cfqd,cfq_class_rt (cfqq)); +unsigned process_thr = cfq_target_latency / cfqd->cfq_slice[1 ]; +if (iq > process_thr) { +unsigned low_slice =2 * slice * cfqd->cfq_slice_idle + / cfqd->cfq_slice[1 ]; + slice =max (slice * cfq_target_latency / + (cfqd->cfq_slice[1 ] * iq), +min (slice, low_slice)); + } + } + cfqq->slice_end = jiffies + slice;cfq_log_cfqq (cfqd, cfqq,"set_slice=%lu" , cfqq->slice_end - jiffies); }
@@ -655,7 +694,8 @@ static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)BUG_ON (cfq_cfqq_on_rr (cfqq));cfq_mark_cfqq_on_rr (cfqq); cfqd->busy_queues++; - +if (cfq_class_rt (cfqq)) + cfqd->busy_rt_queues++;cfq_resort_rr_list (cfqd, cfqq); }
@@ -678,6 +718,8 @@ static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)BUG_ON (!cfqd->busy_queues); cfqd->busy_queues--; +if (cfq_class_rt (cfqq)) + cfqd->busy_rt_queues--; }/*
Signature · 1 line
1.6.2.5
Hi, Corrado!
Sorry if folks receive this twice, but my mailer and I had an argument about this message. ;-)
Quoted 12 lines · Corrado Zoccolo
When the number of processes performing I/O concurrently increases, a fixed time slice per process will cause large latencies.
This patch, if
low_latencymode is enabled, will scale the time slice assigned to each process according to a 300ms target latency.In order to keep fairness among processes:
* The number of active processes is computed using a special form of running average, that quickly follows sudden increases (to keep latency low), and decrease slowly (to have fairness in spite of rapid decreases of this value).
Quoted 3 lines
To safeguard sequential bandwidth, we impose a minimum time slice (computed using 2*cfq_slice_idle as base, adjusted according to priority and async-ness).
I like the idea as well, but I have a question and some nits to pick.
block/cfq-iosched.c cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq) · line 342
Quoted 13 lines
static inline void
cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq){block/cfq-iosched.c +9
-1- cfqq->slice_end =cfq_prio_to_slice (cfqd, cfqq) + jiffies; +unsigned slice =cfq_prio_to_slice (cfqd, cfqq); +if (cfqd->cfq_latency) { +unsigned iq =cfq_get_avg_queues (cfqd,cfq_class_rt (cfqq)); +unsigned process_thr = cfq_target_latency / cfqd->cfq_slice[1 ]; +if (iq > process_thr) { +unsigned low_slice =2 * slice * cfqd->cfq_slice_idle + / cfqd->cfq_slice[1 ]; + slice = max(slice * cfq_target_latency / + (cfqd->cfq_slice[1] * iq),
Couldn't you have just divided the slice by iq? And why iq? Why not nr_qs or avg_qlen or something? It's a minor nit; I can live with it.
block/cfq-iosched.c cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq) · line 347
Quoted 5 lines
block/cfq-iosched.c +4
-0+ min(slice, low_slice)); + } + } + cfqq->slice_end = jiffies + slice;cfq_log_cfqq (cfqd, cfqq,"set_slice=%lu" , cfqq->slice_end - jiffies);
Wow. That function is *dense*. I tried to write it in a more readable fashion, but please chime in if I misinterpreted anything.
static inline voidcfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
unsigned slice = cfq_prio_to_slice(cfqd, cfqq);
if (cfqd->cfq_latency) {
unsigned iq = cfq_get_avg_queues(cfqd, cfq_class_rt(cfqq));
unsigned slice_sync = cfqd->cfq_slice[1];
unsigned process_thr = cfq_target_latency / slice_sync;
if (iq > process_thr) {
/*
* Minimum slice is computed using 2*slice_idle as
* a base, and then scaling it by priority and
* async-ness.
*/
unsigned total_sync = slice_sync * iq;
unsigned slice_fraction = cfq_target_latency / total_sync;
unsigned min_slice = (2 * cfqd->cfq_slice_idle) *
(slice / slice_sync);
min_slice = min(slice, min_slice);
slice *= slice_fraction;
slice = max(slice, min_slice);
}
}
cfqq->slice_end = jiffies + slice;
cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
}Cheers,
Jeff
Hi Jeff,
Quoted 39 lines · Jeff Moyer
Hi, Corrado!
Sorry if folks receive this twice, but my mailer and I had an argument about this message. ;-)
Quoted 12 lines · Corrado Zoccolo
When the number of processes performing I/O concurrently increases, a fixed time slice per process will cause large latencies.
This patch, if
low_latencymode is enabled, will scale the time slice assigned to each process according to a 300ms target latency.In order to keep fairness among processes:
* The number of active processes is computed using a special form of running average, that quickly follows sudden increases (to keep latency low), and decrease slowly (to have fairness in spite of rapid decreases of this value).Quoted 3 lines
To safeguard sequential bandwidth, we impose a minimum time slice (computed using 2*cfq_slice_idle as base, adjusted according to priority and async-ness).
I like the idea as well, but I have a question and some nits to pick.
Quoted 5 lines
static inline void
cfq_set_prio_slice(structcfq_data*cfqd, structcfq_queue*cfqq) {
-cfqq->slice_end=cfq_prio_to_slice(cfqd, cfqq)+ jiffies;
+ unsigned slice =cfq_prio_to_slice(cfqd, cfqq);Quoted 8 lines
+ if (
cfqd->cfq_latency) {
+ unsigned iq =cfq_get_avg_queues(cfqd, cfq_class_rt(cfqq));
+ unsignedprocess_thr=cfq_target_latency/ cfqd->cfq_slice[1];
+ if (iq >process_thr) {
+ unsignedlow_slice= 2 * slice *cfqd->cfq_slice_idle
+ / cfqd->cfq_slice[1];
+ slice = max(slice *cfq_target_latency/
+ (cfqd->cfq_slice[1] * iq),
Quoted 2 lines
Couldn't you have just divided the slice by iq? And why iq? Why not
nr_qsoravg_qlenor something? It's a minor nit; I can live with it.
iq stands for interested queues, because we are restricting the count just to the same priority class, not all queues in the system.
Quoted 30 lines
Quoted 6 lines
+
min(slice, low_slice));
+ }
+ }
+cfqq->slice_end= jiffies + slice;
cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);Wow. That function is *dense*. I tried to write it in a more readable fashion, but please chime in if I misinterpreted anything.
static inline void
cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq){
unsigned slice =cfq_prio_to_slice(cfqd, cfqq);if (
cfqd->cfq_latency) {
unsigned iq =cfq_get_avg_queues(cfqd, cfq_class_rt(cfqq)); unsignedslice_sync= cfqd->cfq_slice[1]; unsignedprocess_thr=cfq_target_latency/slice_sync;if (iq >
process_thr) {
/*
* Minimum slice is computed using 2*slice_idle as
* a base, and then scaling it by priority and
* async-ness.
*/
unsignedtotal_sync=slice_sync* iq; unsignedslice_fraction=cfq_target_latency/total_sync; unsignedmin_slice= (2 *cfqd->cfq_slice_idle) * (slice /slice_sync);
Quoted 9 lines
min_slice =
min(slice, min_slice);
slice *=slice_fraction;
slice =max(slice, min_slice);
}
}
cfqq->slice_end = jiffies + slice;
cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu",cfqq->slice_end- jiffies); }
I don't think this is equivalent. You seem to compute some divisions too early, losing in precision.
slice * cfq_target_latency / (cfqd->cfq_slice[1] * iq)
is not generally equivalent to:
slice * (cfq_target_latency / (cfqd->cfq_slice[1] * iq)) that is what you are computing.
There is an other such case in your simplification.
Corrado
Quoted 4 lines
Cheers,
Jeff
Quoted 5 lines · Corrado Zoccolo
Quoted 2 lines
Couldn't you have just divided the slice by iq? And why iq? Why not
nr_qsoravg_qlenor something? It's a minor nit; I can live with it.iq stands for interested queues, because we are restricting the count just to the same priority class, not all queues in the system.
Ah, that makes sense. A comment would make that clear.
Quoted 2 lines
I don't think this is equivalent. You seem to compute some divisions too early, losing in precision.
OK, I figured as much.
Quoted 5 lines
slice *
cfq_target_latency/ (cfqd->cfq_slice[1] * iq) is not generally equivalent to:
slice * (cfq_target_latency/ (cfqd->cfq_slice[1] * iq)) that is what you are computing.
There is an other such case in your simplification.
OK. The idea was to try to make the thing a bit more digestable. Honestly, I had to re-write it to figure out what it was doing. Could you rework it so the logic is more obvious to others and still correct?
Thanks!
Jeff
Hi Jeff,
Quoted 5 lines · Jeff Moyer
Corrado Zoccolo <[email protected]> writes:
OK. The idea was to try to make the thing a bit more digestable. Honestly, I had to re-write it to figure out what it was doing. Could you rework it so the logic is more obvious to others and still correct?
What about:
/* interested queues (we consider only the ones with the same priority class) */ unsigned iq = cfq_get_avg_queues(cfqd, cfq_class_rt(cfqq)); unsigned sync_slice = cfqd->cfq_slice[1];
unsigned expected_latency = sync_slice * iq;
if (expected_latency > target_latency) {
unsigned base_low_slice = 2 * cfqd->cfq_slice_idle;
/* scale low_slice according to IO priority and sync vs async */
unsigned low_slice = min(slice, base_low_slice * slice / sync_slice);
/* the adapted slice value is scaled to fit all iqs into the target latency */
slice = max(slice * cfq_target_latency / expected_latency, low_slice);
}BTW, the other complex part of the patch, i.e. the definition of cfq_get_avg_queues, could be simplified if we hard-code the divisor, that is currently defined outside to allow for some experimentation.
Thanks for your comments
Corrado
Quoted 4 lines
Thanks!
Jeff
Signature · 5 lines
__________________________________________________________________________ dott. Corrado Zoccolo mailto:[email protected] PhD - Department of Computer Science - University of Pisa, Italy --------------------------------------------------------------------------
Quoted 13 lines · Corrado Zoccolo
Hi Jeff,
Quoted 5 lines · Jeff Moyer
Corrado Zoccolo <[email protected]> writes:
OK. The idea was to try to make the thing a bit more digestable. Honestly, I had to re-write it to figure out what it was doing. Could you rework it so the logic is more obvious to others and still correct?
What about:
/* interested queues (we consider only the ones with the same priority class) */ unsigned iq =cfq_get_avg_queues(cfqd, cfq_class_rt(cfqq)); unsignedsync_slice= cfqd->cfq_slice[1];
unsignedexpected_latency=sync_slice* iq;
Quoted 7 lines
if (expected_latency > target_latency) {
unsigned base_low_slice = 2 * cfqd->cfq_slice_idle;
/* scale low_slice according to IO priority and sync vs async */
unsigned low_slice = min(slice, base_low_slice * slice / sync_slice);
/* the adapted slice value is scaled to fit all iqs into the target latency */
slice = max(slice * cfq_target_latency / expected_latency, low_slice);
}Yeah, that looks a ton better. Thanks for doing that!
Cheers,
Jeff
Quoted 15 lines · Jeff Moyer
Quoted 13 lines · Corrado Zoccolo
What about:
/* interested queues (we consider only the ones with the same priority class) */ unsigned iq =cfq_get_avg_queues(cfqd, cfq_class_rt(cfqq));
unsignedsync_slice= cfqd->cfq_slice[1];
unsignedexpected_latency=sync_slice* iq;
if (expected_latency>target_latency) {
unsignedbase_low_slice= 2 *cfqd->cfq_slice_idle;
/* scalelow_sliceaccording to IO priority and sync vs async */ unsignedlow_slice=min(slice, base_low_slice * slice / sync_slice); /* the adapted slice value is scaled to fit all iqs into the target latency */ slice =max(slice * cfq_target_latency / expected_latency, low_slice); }
Quoted 1 line
Yeah, that looks a ton better. Thanks for doing that!
Jens, if you like the new version of the code (integrating this last change), I can rebase my patch set on top of Jeff's, since it is already queued for 2.6.33 .
Corrado
Quoted 4 lines
Cheers,
Jeff
Hi, Corrado!
Quoted 12 lines · Corrado Zoccolo
When the number of processes performing I/O concurrently increases, a fixed time slice per process will cause large latencies.
This patch, if
low_latencymode is enabled, will scale the time slice assigned to each process according to a 300ms target latency.In order to keep fairness among processes:
* The number of active processes is computed using a special form of running average, that quickly follows sudden increases (to keep latency low), and decrease slowly (to have fairness in spite of rapid decreases of this value).
Quoted 3 lines
To safeguard sequential bandwidth, we impose a minimum time slice (computed using 2*cfq_slice_idle as base, adjusted according to priority and async-ness).
I like the idea as well, but I have a question and some nits to pick.
block/cfq-iosched.c cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq) · line 342
Quoted 13 lines
static inline void
cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq){block/cfq-iosched.c +9
-1- cfqq->slice_end =cfq_prio_to_slice (cfqd, cfqq) + jiffies; +unsigned slice =cfq_prio_to_slice (cfqd, cfqq); +if (cfqd->cfq_latency) { +unsigned iq =cfq_get_avg_queues (cfqd,cfq_class_rt (cfqq)); +unsigned process_thr = cfq_target_latency / cfqd->cfq_slice[1 ]; +if (iq > process_thr) { +unsigned low_slice =2 * slice * cfqd->cfq_slice_idle + / cfqd->cfq_slice[1 ]; + slice = max(slice * cfq_target_latency / + (cfqd->cfq_slice[1] * iq),
Couldn't you have just divided the slice by iq? And why iq? Why not nr_qs or avg_qlen or something? It's a minor nit; I can live with it.
block/cfq-iosched.c cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq) · line 347
Quoted 5 lines
block/cfq-iosched.c +4
-0+ min(slice, low_slice)); + } + } + cfqq->slice_end = jiffies + slice;cfq_log_cfqq (cfqd, cfqq,"set_slice=%lu" , cfqq->slice_end - jiffies);
Wow. That function is *dense*. I tried to write it in a more readable fashion, but please chime in if I misinterpreted anything.
static inline voidcfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
unsigned slice = cfq_prio_to_slice(cfqd, cfqq);
if (cfqd->cfq_latency) {
unsigned iq = cfq_get_avg_queues(cfqd, cfq_class_rt(cfqq));
unsigned slice_sync = cfqd->cfq_slice[1];
unsigned process_thr = cfq_target_latency / slice_sync;
if (iq > process_thr) {
/*
* Minimum slice is computed using 2*slice_idle as
* a base, and then scaling it by priority and
* async-ness.
*/
unsigned total_sync = slice_sync * iq;
unsigned slice_fraction = cfq_target_latency / total_sync;
unsigned min_slice = (2 * cfqd->cfq_slice_idle) *
(slice / slice_sync);
min_slice = min(slice, min_slice);
slice *= slice_fraction;
slice = max(slice, min_slice);
}
}
cfqq->slice_end = jiffies + slice;
cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
}Cheers,
Jeff