cfq: Fix starvation of async writes in presence of heavy sync workload

In presence of heavy sync workload CFQ can starve asnc writes. If one launches multiple readers (say 16), then one can notice that CFQ can withhold dispatch of WRITEs for a very long time say 200 or 300 seconds.

Basically CFQ schedules an async queue but does not dispatch any writes because it is waiting for exisintng sync requests in queue to finish. While it is waiting, one or other reader gets queued up and preempts the async queue. So we did schedule the async queue but never dispatched anything from it. This can repeat for long time hence practically starving Writers.

This patch allows async queue to dispatch atleast 1 requeust once it gets scheduled and denies preemption if async queue has been waiting for sync requests to drain and has not been able to dispatch a request yet.

One concern with this fix is that how does it impact readers in presence of heavy writting going on.

I did a test where I launch firefox, load a website and close firefox and measure the time. I ran the test 3 times and took average.

- Vanilla kernel time ~= 1 minute 40 seconds
- Patched kenrel time ~= 1 minute 35 seconds

In presence of heavy sync workload CFQ can starve asnc writes. If one launches multiple readers (say 16), then one can notice that CFQ can withhold dispatch of WRITEs for a very long time say 200 or 300 seconds.

Basically CFQ schedules an async queue but does not dispatch any writes because it is waiting for exisintng sync requests in queue to finish. While it is waiting, one or other reader gets queued up and preempts the async queue. So we did schedule the async queue but never dispatched anything from it. This can repeat for long time hence practically starving Writers.

This patch allows async queue to dispatch atleast 1 requeust once it gets scheduled and denies preemption if async queue has been waiting for sync requests to drain and has not been able to dispatch a request yet.

One concern with this fix is that how does it impact readers in presence of heavy writting going on.

I did a test where I launch firefox, load a website and close firefox and measure the time. I ran the test 3 times and took average.

- Vanilla kernel time ~= 1 minute 40 seconds
- Patched kenrel time ~= 1 minute 35 seconds

Basically it looks like that for this test times have not changed much for this test. But I would not claim that it does not impact reader's latencies at all. It might show up in other workloads.

I think we anyway need to fix writer starvation. If this patch causes issues, then we need to look at reducing writer's queue depth further to improve latencies for readers.

Reported-and-Tested-by Tao Ma <[email protected]>

Signed-off-by Vivek Goyal <[email protected]>

---
 block/cfq-iosched.c |    9 ++++++++-

 1 file changed, 8 insertions(+), 1 deletion(-)

Index: linux-2.6/block/cfq-iosched.c
===================================================================

block/cfq-iosched.c       2011-06-20 08:29:13.328186380 -0400 renamed from block/cfq-iosched.c  2011-06-10 10:05:34.660781278 -0400 +8 -2

@@ -3315,8 +3315,15 @@ cfq_should_preempt(struct cfq_data *cfqd
         * if the new request is sync, but the currently running queue is
         * not, let the sync request have priority.
         */
-       if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
+       if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq)) {
+               /*
+                * Allow atleast one dispatch otherwise this can repeat
+                * and writes can be starved completely
+                */
+               if (!cfqq->slice_dispatch)
+                       return false;
                return true;
+       }
 
        if (new_cfqq->cfqg != cfqq->cfqg)
                return false;
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Quoted 32 lines · Vivek Goyal

In presence of heavy sync workload CFQ can starve asnc writes. If one launches multiple readers (say 16), then one can notice that CFQ can withhold dispatch of WRITEs for a very long time say 200 or 300 seconds.

Basically CFQ schedules an async queue but does not dispatch any writes because it is waiting for exisintng sync requests in queue to finish. While it is waiting, one or other reader gets queued up and preempts the async queue. So we did schedule the async queue but never dispatched anything from it. This can repeat for long time hence practically starving Writers.

This patch allows async queue to dispatch atleast 1 requeust once it gets scheduled and denies preemption if async queue has been waiting for sync requests to drain and has not been able to dispatch a request yet.

One concern with this fix is that how does it impact readers in presence of heavy writting going on.

I did a test where I launch firefox, load a website and close firefox and measure the time. I ran the test 3 times and took average.

- Vanilla kernel time ~= 1 minute 40 seconds
- Patched kenrel time ~= 1 minute 35 seconds

Basically it looks like that for this test times have not changed much for this test. But I would not claim that it does not impact reader's latencies at all. It might show up in other workloads.

Quoted 3 lines

I think we anyway need to fix writer starvation. If this patch causes issues, then we need to look at reducing writer's queue depth further to improve latencies for readers.

Maybe we should be more specific about what it means to "fix writer starvation"

This makes the preemption logic slightly harder to understand, and I'm concerned we'll keep making little adjustments like this to the scheduler.

Quoted 37 lines

Reported-and-Tested-by Tao Ma <[email protected]>

Signed-off-by Vivek Goyal <[email protected]>

---
 block/cfq-iosched.c |    9 ++++++++-

 1 file changed, 8 insertions(+), 1 deletion(-)

Index: linux-2.6/block/cfq-iosched.c
===================================================================

block/cfq-iosched.c       2011-06-20 08:29:13.328186380 -0400 renamed from block/cfq-iosched.c  2011-06-10 10:05:34.660781278 -0400 +8 -2

@@ -3315,8 +3315,15 @@ cfq_should_preempt(struct cfq_data *cfqd
         * if the new request is sync, but the currently running queue is
         * not, let the sync request have priority.
         */
-       if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
+       if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq)) {
+               /*
+                * Allow atleast one dispatch otherwise this can repeat
+                * and writes can be starved completely
+                */
+               if (!cfqq->slice_dispatch)
+                       return false;
                return true;
+       }
 
        if (new_cfqq->cfqg != cfqq->cfqg)
                return false;
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Quoted 33 lines · Justin TerAvest

Quoted 32 lines · Vivek Goyal

In presence of heavy sync workload CFQ can starve asnc writes. If one launches multiple readers (say 16), then one can notice that CFQ can withhold dispatch of WRITEs for a very long time say 200 or 300 seconds.

Basically CFQ schedules an async queue but does not dispatch any writes because it is waiting for exisintng sync requests in queue to finish. While it is waiting, one or other reader gets queued up and preempts the async queue. So we did schedule the async queue but never dispatched anything from it. This can repeat for long time hence practically starving Writers.

This patch allows async queue to dispatch atleast 1 requeust once it gets scheduled and denies preemption if async queue has been waiting for sync requests to drain and has not been able to dispatch a request yet.

One concern with this fix is that how does it impact readers in presence of heavy writting going on.

I did a test where I launch firefox, load a website and close firefox and measure the time. I ran the test 3 times and took average.

- Vanilla kernel time ~= 1 minute 40 seconds
- Patched kenrel time ~= 1 minute 35 seconds

Basically it looks like that for this test times have not changed much for this test. But I would not claim that it does not impact reader's latencies at all. It might show up in other workloads.

Quoted 6 lines

Quoted 3 lines

I think we anyway need to fix writer starvation. If this patch causes issues, then we need to look at reducing writer's queue depth further to improve latencies for readers.

Maybe we should be more specific about what it means to "fix writer starvation"

Tao ma recently ran into issues with writer starvation. Here is the lkml thread.

https://lkml.org/lkml/2011/6/9/167

I also ran some fio based scripts launching multiple readers and multiple buffered writers and noticed that there are large windows where we don't dispatch even a single request from async queues. That's what starvation is. Time period for not dispatching request was in the range of 200 seconds.

Quoted 4 lines

This makes the preemption logic slightly harder to understand, and I'm concerned we'll keep making little adjustments like this to the scheduler.

If you have other ideas for handling this, we can definitely give it a try.

Thanks
Vivek

Quoted 37 lines

Quoted 37 lines

Reported-and-Tested-by Tao Ma <[email protected]>

Signed-off-by Vivek Goyal <[email protected]>

---
 block/cfq-iosched.c |    9 ++++++++-

 1 file changed, 8 insertions(+), 1 deletion(-)

Index: linux-2.6/block/cfq-iosched.c
===================================================================

block/cfq-iosched.c       2011-06-20 08:29:13.328186380 -0400 renamed from block/cfq-iosched.c  2011-06-10 10:05:34.660781278 -0400 +8 -2

@@ -3315,8 +3315,15 @@ cfq_should_preempt(struct cfq_data *cfqd
         * if the new request is sync, but the currently running queue is
         * not, let the sync request have priority.
         */
-       if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
+       if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq)) {
+               /*
+                * Allow atleast one dispatch otherwise this can repeat
+                * and writes can be starved completely
+                */
+               if (!cfqq->slice_dispatch)
+                       return false;
                return true;
+       }
 
        if (new_cfqq->cfqg != cfqq->cfqg)
                return false;
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

How do we establish what's acceptable? My complaint is that it's not obvious what tradeoffs to make in the I/O scheduler.

Quoted 7 lines

Quoted 4 lines

This makes the preemption logic slightly harder to understand, and I'm concerned we'll keep making little adjustments like this to the scheduler.

If you have other ideas for handling this, we can definitely give it a try.

I haven't written out a case to prove it, but it seems like other preemption logic (like the cfq_rq_close() case) could also cause some requests to be starved indefinitely.

I think if we want to make stronger guarantees about request starvation, we might have to rethink how preemption works.

In presence of heavy sync workload CFQ can starve asnc writes. If one launches multiple readers (say 16), then one can notice that CFQ can withhold dispatch of WRITEs for a very long time say 200 or 300 seconds.

Basically CFQ schedules an async queue but does not dispatch any writes because it is waiting for exisintng sync requests in queue to finish. While it is waiting, one or other reader gets queued up and preempts the async queue. So we did schedule the async queue but never dispatched anything from it. This can repeat for long time hence practically starving Writers.

This patch allows async queue to dispatch atleast 1 requeust once it gets scheduled and denies preemption if async queue has been waiting for sync requests to drain and has not been able to dispatch a request yet.

One concern with this fix is that how does it impact readers in presence of heavy writting going on.

I did a test where I launch firefox, load a website and close firefox and measure the time. I ran the test 3 times and took average.

- Vanilla kernel time ~= 1 minute 40 seconds
- Patched kenrel time ~= 1 minute 35 seconds

Basically it looks like that for this test times have not changed much for this test. But I would not claim that it does not impact reader's latencies at all. It might show up in other workloads.

I think we anyway need to fix writer starvation. If this patch causes issues, then we need to look at reducing writer's queue depth further to improve latencies for readers.

2011/6/20 Vivek Goyal <[email protected]>:

Quoted 32 lines

In presence of heavy sync workload CFQ can starve asnc writes. If one launches multiple readers (say 16), then one can notice that CFQ can withhold dispatch of WRITEs for a very long time say 200 or 300 seconds.

Basically CFQ schedules an async queue but does not dispatch any writes because it is waiting for exisintng sync requests in queue to finish. While it is waiting, one or other reader gets queued up and preempts the async queue. So we did schedule the async queue but never dispatched anything from it. This can repeat for long time hence practically starving Writers.

This patch allows async queue to dispatch atleast 1 requeust once it gets scheduled and denies preemption if async queue has been waiting for sync requests to drain and has not been able to dispatch a request yet.

One concern with this fix is that how does it impact readers in presence of heavy writting going on.

I did a test where I launch firefox, load a website and close firefox and measure the time. I ran the test 3 times and took average.

- Vanilla kernel time ~= 1 minute 40 seconds
- Patched kenrel time ~= 1 minute 35 seconds

Basically it looks like that for this test times have not changed much for this test. But I would not claim that it does not impact reader's latencies at all. It might show up in other workloads.

Quoted 3 lines

I think we anyway need to fix writer starvation. If this patch causes issues, then we need to look at reducing writer's queue depth further to improve latencies for readers.

I'm afraid this can causes read latency because cfq_dispatch_requests doesn't check preempt. we will dispatch 4 requests at least instead of just one. can we add a logic to force it just dispatches one request?

Quoted 36 lines · Shaohua Li

2011/6/20 Vivek Goyal <[email protected]>:

Quoted 35 lines

In presence of heavy sync workload CFQ can starve asnc writes. If one launches multiple readers (say 16), then one can notice that CFQ can withhold dispatch of WRITEs for a very long time say 200 or 300 seconds.

Basically CFQ schedules an async queue but does not dispatch any writes because it is waiting for exisintng sync requests in queue to finish. While it is waiting, one or other reader gets queued up and preempts the async queue. So we did schedule the async queue but never dispatched anything from it. This can repeat for long time hence practically starving Writers.

This patch allows async queue to dispatch atleast 1 requeust once it gets scheduled and denies preemption if async queue has been waiting for sync requests to drain and has not been able to dispatch a request yet.

One concern with this fix is that how does it impact readers in presence of heavy writting going on.

I did a test where I launch firefox, load a website and close firefox and measure the time. I ran the test 3 times and took average.

- Vanilla kernel time ~= 1 minute 40 seconds
- Patched kenrel time ~= 1 minute 35 seconds

Basically it looks like that for this test times have not changed much for this test. But I would not claim that it does not impact reader's latencies at all. It might show up in other workloads.

I think we anyway need to fix writer starvation. If this patch causes issues, then we need to look at reducing writer's queue depth further to improve latencies for readers.

Quoted 3 lines

I'm afraid this can causes read latency because cfq_dispatch_requests doesn't check preempt. we will dispatch 4 requests at least instead of just one. can we add a logic to force it just dispatches one request?

This will happen only if some other read queue does not preempt write queue after disptaching 1 request.

Anyway, agreed that with single reader, it will not preempt writer and then writer gets to dispatch bunch of requests.

If we want to protect against that, then we can simply expire writer after dispatching one request if there are busy queues.

I could change following code.

        /*
         * expire an async queue immediately if it has used up its slice.
         * idle
         * queue always expire after 1 dispatch round.
         */
        if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
            cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
            cfq_class_idle(cfqq))) {
                cfqq->slice_end = jiffies + 1;
                cfq_slice_expired(cfqd, 0);
        }

to look as follows.

        /*
         * expire an async queue and idle queue after 1 dispatch round.
         */
        if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) ||
	    cfq_class_idle(cfqq))) {
                cfqq->slice_end = jiffies + 1;
                cfq_slice_expired(cfqd, 0);
        }