Another proportional weight IO controller

If we start with bfq patches, this is how plan would look like:

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea

Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)

7 Start an offline email thread to keep track of progress on the above goals.

BFQ's support for hierarchy of cgroups means that its close to where we want to get. Any comments on what approach looks better?

Quoted 25 lines

Quoted 24 lines · Vivek Goyal

Quoted 7 lines · Nauman Rafique

In an attempt to make sure that this discussion leads to something useful, we have summarized the points raised in this discussion and have come up with a strategy for future. The goal of this is to find common ground between all the approaches proposed on this mailing list.

1 Start with Satoshi's latest patches.

I have had a brief look at both Satoshi's patch and bfq. I kind of like bfq's patches for keeping track of per cgroup, per queue data structures. May be we can look there also.

Quoted 12 lines

2 Do the following to support propotional division:
a) Give time slices in proportion to weights (configurable option). We can support both priorities and weights by doing propotional division between requests with same priorities.
3 Schedule time slices using WF2Q+ instead of round robin.
Test the performance impact (both throughput and jitter in latency).
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support exists in dm-ioband and is provided by Andrea Righi's patches too.

Quoted 5 lines

Quoted 3 lines

Does dm-iobnd support abosolute limit? I think till last version they did not. I have not check the latest version though.

No, dm-ioband still provides weight/share control only. Only Andrea Righi's patches support absolute limit.

Thanks for the correction.

Quoted 16 lines

Quoted 15 lines

Quoted 15 lines

c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
5 Support multiple layers of cgroups to align IO controller behavior
with CPU scheduling behavior (more discussion?)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)
7 Start an offline email thread to keep track of progress on the above goals.

Please feel free to add/modify items to the list
when you respond back. Any comments/suggestions are more than welcome.

From: Nauman Rafique <[email protected]>
Date: Mon, Nov 17, 2008 09:01:48PM -0800

If we start with bfq patches, this is how plan would look like:

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)

4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)
7 Start an offline email thread to keep track of progress on the above goals.

BFQ's support for hierarchy of cgroups means that its close to where we want to get. Any comments on what approach looks better?

If we start with bfq patches, this is how plan would look like:

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea

Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)

7 Start an offline email thread to keep track of progress on the above goals.

BFQ's support for hierarchy of cgroups means that its close to where we want to get. Any comments on what approach looks better?

Quoted 25 lines

Quoted 24 lines · Vivek Goyal

Quoted 7 lines · Nauman Rafique

In an attempt to make sure that this discussion leads to something useful, we have summarized the points raised in this discussion and have come up with a strategy for future. The goal of this is to find common ground between all the approaches proposed on this mailing list.

1 Start with Satoshi's latest patches.

I have had a brief look at both Satoshi's patch and bfq. I kind of like bfq's patches for keeping track of per cgroup, per queue data structures. May be we can look there also.

Quoted 12 lines

2 Do the following to support propotional division:
a) Give time slices in proportion to weights (configurable option). We can support both priorities and weights by doing propotional division between requests with same priorities.
3 Schedule time slices using WF2Q+ instead of round robin.
Test the performance impact (both throughput and jitter in latency).
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support exists in dm-ioband and is provided by Andrea Righi's patches too.

Quoted 5 lines

Quoted 3 lines

Does dm-iobnd support abosolute limit? I think till last version they did not. I have not check the latest version though.

No, dm-ioband still provides weight/share control only. Only Andrea Righi's patches support absolute limit.

Thanks for the correction.

Quoted 16 lines

Quoted 15 lines

Quoted 15 lines

c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
5 Support multiple layers of cgroups to align IO controller behavior
with CPU scheduling behavior (more discussion?)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)
7 Start an offline email thread to keep track of progress on the above goals.

Please feel free to add/modify items to the list
when you respond back. Any comments/suggestions are more than welcome.

If we start with bfq patches, this is how plan would look like:

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea

Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)

7 Start an offline email thread to keep track of progress on the above goals.

BFQ's support for hierarchy of cgroups means that its close to where we want to get. Any comments on what approach looks better?

Quoted 25 lines

Quoted 24 lines · Vivek Goyal

Quoted 7 lines · Nauman Rafique

In an attempt to make sure that this discussion leads to something useful, we have summarized the points raised in this discussion and have come up with a strategy for future. The goal of this is to find common ground between all the approaches proposed on this mailing list.

1 Start with Satoshi's latest patches.

I have had a brief look at both Satoshi's patch and bfq. I kind of like bfq's patches for keeping track of per cgroup, per queue data structures. May be we can look there also.

Quoted 12 lines

2 Do the following to support propotional division:
a) Give time slices in proportion to weights (configurable option). We can support both priorities and weights by doing propotional division between requests with same priorities.
3 Schedule time slices using WF2Q+ instead of round robin.
Test the performance impact (both throughput and jitter in latency).
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support exists in dm-ioband and is provided by Andrea Righi's patches too.

Quoted 5 lines

Quoted 3 lines

Does dm-iobnd support abosolute limit? I think till last version they did not. I have not check the latest version though.

No, dm-ioband still provides weight/share control only. Only Andrea Righi's patches support absolute limit.

Thanks for the correction.

Quoted 16 lines

Quoted 15 lines

Quoted 15 lines

c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
5 Support multiple layers of cgroups to align IO controller behavior
with CPU scheduling behavior (more discussion?)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)
7 Start an offline email thread to keep track of progress on the above goals.

Please feel free to add/modify items to the list
when you respond back. Any comments/suggestions are more than welcome.

Quoted 15 lines · Nauman Rafique

If we start with bfq patches, this is how plan would look like:

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea

Quoted 8 lines

Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)

The newest bio_cgroup doesn't use much memcg code I think. The older biocgroup tracks IO using mem_cgroup_charge(), and mem_cgroup_charge() remembers a struct page owns by which cgroup. But now biocgroup changes to directly put some hooks in __set_page_dirty() and some other places to track pages.

Quoted 7 lines

7 Start an offline email thread to keep track of progress on the above goals.

BFQ's support for hierarchy of cgroups means that its close to where we want to get. Any comments on what approach looks better?

Looks like a sane way :) . We are also trying to keep track of the discussion and development of IO controller. I'll start to have a look into BFQ.

Quoted 51 lines · Li Zefan

Quoted 25 lines

Quoted 24 lines · Vivek Goyal

Quoted 7 lines · Nauman Rafique

In an attempt to make sure that this discussion leads to something useful, we have summarized the points raised in this discussion and have come up with a strategy for future. The goal of this is to find common ground between all the approaches proposed on this mailing list.

1 Start with Satoshi's latest patches.

I have had a brief look at both Satoshi's patch and bfq. I kind of like bfq's patches for keeping track of per cgroup, per queue data structures. May be we can look there also.

Quoted 12 lines

2 Do the following to support propotional division:
a) Give time slices in proportion to weights (configurable option). We can support both priorities and weights by doing propotional division between requests with same priorities.
3 Schedule time slices using WF2Q+ instead of round robin.
Test the performance impact (both throughput and jitter in latency).
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support exists in dm-ioband and is provided by Andrea Righi's patches too.

Quoted 5 lines

Quoted 3 lines

Does dm-iobnd support abosolute limit? I think till last version they did not. I have not check the latest version though.

No, dm-ioband still provides weight/share control only. Only Andrea Righi's patches support absolute limit.

Thanks for the correction.

Quoted 16 lines

Quoted 15 lines

Quoted 15 lines

c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
5 Support multiple layers of cgroups to align IO controller behavior
with CPU scheduling behavior (more discussion?)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)
7 Start an offline email thread to keep track of progress on the above goals.

Please feel free to add/modify items to the list
when you respond back. Any comments/suggestions are more than welcome.

Quoted 15 lines · Nauman Rafique

If we start with bfq patches, this is how plan would look like:

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea

Quoted 8 lines

Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)

The newest bio_cgroup doesn't use much memcg code I think. The older biocgroup tracks IO using mem_cgroup_charge(), and mem_cgroup_charge() remembers a struct page owns by which cgroup. But now biocgroup changes to directly put some hooks in __set_page_dirty() and some other places to track pages.

Quoted 7 lines

7 Start an offline email thread to keep track of progress on the above goals.

BFQ's support for hierarchy of cgroups means that its close to where we want to get. Any comments on what approach looks better?

Looks like a sane way :) . We are also trying to keep track of the discussion and development of IO controller. I'll start to have a look into BFQ.

Quoted 51 lines · Li Zefan

Quoted 25 lines

Quoted 24 lines · Vivek Goyal

Quoted 7 lines · Nauman Rafique

In an attempt to make sure that this discussion leads to something useful, we have summarized the points raised in this discussion and have come up with a strategy for future. The goal of this is to find common ground between all the approaches proposed on this mailing list.

1 Start with Satoshi's latest patches.

I have had a brief look at both Satoshi's patch and bfq. I kind of like bfq's patches for keeping track of per cgroup, per queue data structures. May be we can look there also.

Quoted 12 lines

2 Do the following to support propotional division:
a) Give time slices in proportion to weights (configurable option). We can support both priorities and weights by doing propotional division between requests with same priorities.
3 Schedule time slices using WF2Q+ instead of round robin.
Test the performance impact (both throughput and jitter in latency).
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support exists in dm-ioband and is provided by Andrea Righi's patches too.

Quoted 5 lines

Quoted 3 lines

Does dm-iobnd support abosolute limit? I think till last version they did not. I have not check the latest version though.

No, dm-ioband still provides weight/share control only. Only Andrea Righi's patches support absolute limit.

Thanks for the correction.

Quoted 16 lines

Quoted 15 lines

Quoted 15 lines

c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
5 Support multiple layers of cgroups to align IO controller behavior
with CPU scheduling behavior (more discussion?)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)
7 Start an offline email thread to keep track of progress on the above goals.

Please feel free to add/modify items to the list
when you respond back. Any comments/suggestions are more than welcome.

Quoted 15 lines · Nauman Rafique

If we start with bfq patches, this is how plan would look like:

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea

Quoted 8 lines

Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)

The newest bio_cgroup doesn't use much memcg code I think. The older biocgroup tracks IO using mem_cgroup_charge(), and mem_cgroup_charge() remembers a struct page owns by which cgroup. But now biocgroup changes to directly put some hooks in __set_page_dirty() and some other places to track pages.

Quoted 7 lines

7 Start an offline email thread to keep track of progress on the above goals.

BFQ's support for hierarchy of cgroups means that its close to where we want to get. Any comments on what approach looks better?

Looks like a sane way :) . We are also trying to keep track of the discussion and development of IO controller. I'll start to have a look into BFQ.

Quoted 51 lines · Li Zefan

Quoted 25 lines

Quoted 24 lines · Vivek Goyal

Quoted 7 lines · Nauman Rafique

In an attempt to make sure that this discussion leads to something useful, we have summarized the points raised in this discussion and have come up with a strategy for future. The goal of this is to find common ground between all the approaches proposed on this mailing list.

1 Start with Satoshi's latest patches.

I have had a brief look at both Satoshi's patch and bfq. I kind of like bfq's patches for keeping track of per cgroup, per queue data structures. May be we can look there also.

Quoted 12 lines

2 Do the following to support propotional division:
a) Give time slices in proportion to weights (configurable option). We can support both priorities and weights by doing propotional division between requests with same priorities.
3 Schedule time slices using WF2Q+ instead of round robin.
Test the performance impact (both throughput and jitter in latency).
4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support exists in dm-ioband and is provided by Andrea Righi's patches too.

Quoted 5 lines

Quoted 3 lines

Does dm-iobnd support abosolute limit? I think till last version they did not. I have not check the latest version though.

No, dm-ioband still provides weight/share control only. Only Andrea Righi's patches support absolute limit.

Thanks for the correction.

Quoted 16 lines

Quoted 15 lines

Quoted 15 lines

c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
5 Support multiple layers of cgroups to align IO controller behavior
with CPU scheduling behavior (more discussion?)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)
7 Start an offline email thread to keep track of progress on the above goals.

Please feel free to add/modify items to the list
when you respond back. Any comments/suggestions are more than welcome.

From: Nauman Rafique <[email protected]>
Date: Mon, Nov 17, 2008 09:01:48PM -0800

If we start with bfq patches, this is how plan would look like:

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)

4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)
7 Start an offline email thread to keep track of progress on the above goals.

BFQ's support for hierarchy of cgroups means that its close to where we want to get. Any comments on what approach looks better?

Hi,

Quoted 5 lines

From: Nauman Rafique <[email protected]>
Date: Mon, Nov 17, 2008 09:01:48PM -0800

If we start with bfq patches, this is how plan would look like:

Quoted 8 lines

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)

it should be possible without altering the code. The slices can be
assigned in the time domain using big values for max_budget. The logic
is: each process is assigned a budget (in the range [max_budget/2, max_budget], choosen from the feedback mechanism, driven in __bfq_bfqq_recalc_budget()), and if it does not complete it in timeout_sync milliseconds, it is charged a fixed amount of sectors of service.

Using big values for max_budget (where big means greater than two times the number of sectors the hard drive can transfer in timeout_sync milliseconds) makes the budgets always to time out, so the disk time is scheduled in slices of timeout_sync.

However this is just a temporary workaround to do some basic testing.

Modifying the scheduler to support time slices instead of sector budgets would indeed simplify the code; I think that the drawback would be being too unfair in the service domain. Of course we have to consider how much is important to be fair in the service domain, and how much added complexity/new code can we accept for it.

[ Better service domain fairness is one of the main reasons why
we started working on bfq, so, talking for me and Paolo it _is_ important :) ]

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

Hi,

Quoted 5 lines

From: Nauman Rafique <[email protected]>
Date: Mon, Nov 17, 2008 09:01:48PM -0800

If we start with bfq patches, this is how plan would look like:

Quoted 8 lines

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)

it should be possible without altering the code. The slices can be
assigned in the time domain using big values for max_budget. The logic
is: each process is assigned a budget (in the range [max_budget/2, max_budget], choosen from the feedback mechanism, driven in __bfq_bfqq_recalc_budget()), and if it does not complete it in timeout_sync milliseconds, it is charged a fixed amount of sectors of service.

Using big values for max_budget (where big means greater than two times the number of sectors the hard drive can transfer in timeout_sync milliseconds) makes the budgets always to time out, so the disk time is scheduled in slices of timeout_sync.

However this is just a temporary workaround to do some basic testing.

Modifying the scheduler to support time slices instead of sector budgets would indeed simplify the code; I think that the drawback would be being too unfair in the service domain. Of course we have to consider how much is important to be fair in the service domain, and how much added complexity/new code can we accept for it.

[ Better service domain fairness is one of the main reasons why
we started working on bfq, so, talking for me and Paolo it _is_ important :) ]

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

Quoted 18 lines

4 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which re-uses memory resource controller code but is not dependent on it (may be biocgroup patches from dm-ioband can be used here directly)
7 Start an offline email thread to keep track of progress on the above goals.

Quoted 3 lines

BFQ's support for hierarchy of cgroups means that its close to where we want to get. Any comments on what approach looks better?

The main problems with this approach (as with the cfq-based ones) in my opinion are:
- the request descriptor allocation problem Divyesh talked about,
- the impossibility of respecting different weights, resulting from the interlock problem with synchronous requests Vivek talked about [ in cfq/bfq this can happen when idling is disabled, e.g., for SSDs, or when using NCQ ],

but I think that correctly addressing your points 4.a) and 4.b) should solve them.

Hi,

Quoted 5 lines

From: Nauman Rafique <[email protected]>
Date: Mon, Nov 17, 2008 09:01:48PM -0800

If we start with bfq patches, this is how plan would look like:

Quoted 8 lines

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)

it should be possible without altering the code. The slices can be
assigned in the time domain using big values for max_budget. The logic
is: each process is assigned a budget (in the range [max_budget/2, max_budget], choosen from the feedback mechanism, driven in __bfq_bfqq_recalc_budget()), and if it does not complete it in timeout_sync milliseconds, it is charged a fixed amount of sectors of service.

Using big values for max_budget (where big means greater than two times the number of sectors the hard drive can transfer in timeout_sync milliseconds) makes the budgets always to time out, so the disk time is scheduled in slices of timeout_sync.

However this is just a temporary workaround to do some basic testing.

Modifying the scheduler to support time slices instead of sector budgets would indeed simplify the code; I think that the drawback would be being too unfair in the service domain. Of course we have to consider how much is important to be fair in the service domain, and how much added complexity/new code can we accept for it.

[ Better service domain fairness is one of the main reasons why
we started working on bfq, so, talking for me and Paolo it _is_ important :) ]

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

Hi,

Quoted 5 lines

From: Nauman Rafique <[email protected]>
Date: Mon, Nov 17, 2008 09:01:48PM -0800

If we start with bfq patches, this is how plan would look like:

Quoted 8 lines

1 Start with BFQ take 2.
2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for disk time budgets, besides sector budget that is currently available (configurable option). (Fabio: Do you think we can just emulate
that using the existing code?). Another approach would be to give time slices just like CFQ (discussing?)

it should be possible without altering the code. The slices can be
assigned in the time domain using big values for max_budget. The logic
is: each process is assigned a budget (in the range [max_budget/2, max_budget], choosen from the feedback mechanism, driven in __bfq_bfqq_recalc_budget()), and if it does not complete it in timeout_sync milliseconds, it is charged a fixed amount of sectors of service.

Using big values for max_budget (where big means greater than two times the number of sectors the hard drive can transfer in timeout_sync milliseconds) makes the budgets always to time out, so the disk time is scheduled in slices of timeout_sync.

However this is just a temporary workaround to do some basic testing.

Modifying the scheduler to support time slices instead of sector budgets would indeed simplify the code; I think that the drawback would be being too unfair in the service domain. Of course we have to consider how much is important to be fair in the service domain, and how much added complexity/new code can we accept for it.

[ Better service domain fairness is one of the main reasons why
we started working on bfq, so, talking for me and Paolo it _is_ important :) ]

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

Signature · 1 line

Jens Axboe

From: Jens Axboe <[email protected]>
Date: Tue, Nov 18, 2008 08:12:08PM +0100

Quoted 4 lines · Fabio Checconi

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

--
Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

Signature · 1 line

Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

Signature · 1 line

Jens Axboe

From: Jens Axboe <[email protected]>
Date: Tue, Nov 18, 2008 08:12:08PM +0100

Quoted 4 lines · Fabio Checconi

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Quoted 8 lines

From: Jens Axboe <[email protected]>
Date: Tue, Nov 18, 2008 08:12:08PM +0100

Quoted 4 lines · Fabio Checconi

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

...

Quoted 11 lines

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

Quoted 8 lines

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

Ok, I can do that, I need just a little bit of time to organize the work.

About these small (some of them are really small) changes, a mixed list of things that they will touch and/or things that I'd like to have clear before starting to write the patches (maybe we can start another thread for them):

- In cfq_exit_single_io_context() and in changed_ioprio(), cic->key is dereferenced without holding any lock. As I reported in [1] this seems to be a problem when an exit() races with a cfq_exit_queue() and in a few other cases. In BFQ we used a somehow involved mechanism to avoid that, abusing rcu (of course we'll have to wait the patch to talk about it :) ), but given my lack of understanding of some parts of the block layer, I'd be interested in knowing if the race is possible and/or if there is something more involved going on that can cause the same effects.

- set_task_ioprio() in fs/ioprio.c doesn't seem to have a write memory barrier to pair with the dependent read one in cfq_get_io_context().

- CFQ_MIN_TT is 2ms, this can result, depending on the value of HZ in timeouts of one jiffy, that may expire too early, so we are just wasting time and do not actually wait for the task to present its new request. Dealing with seeky traffic we've seen a lot of early timeouts due to one jiffy timers expiring too early, is it worth fixing or can we live with that?

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

- Initially, cic->last_request_pos is zero, so the sdist charged to a task for its first seek depends on the position on the disk that is accessed first, independently from its seekiness. Even if there is a cap on that value, we choose to not charge the first seek to processes; that resulted in less wrong predictions for purely sequential loads.

- From my understanding, with shared I/O contexts, two different tasks may concurrently lookup for a cfqd into the same ioc. This may result in cfq_drop_dead_cic() being called two times for the same cic. Am I missing something that prevents that from happening?

Regarding the code splitup, do you think you'll go for the CFS(BFQ) way, using a single compilation unit and including the .c files, or a layout with different compilation units (like the ll_rw_blk.c splitup)?

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

From: Aaron Carroll <[email protected]>
Date: Wed, Nov 19, 2008 12:52:42PM +1100

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

From some quick experiments, what happens is that when a process starts,

From: Fabio Checconi <[email protected]>
Date: Wed, Nov 19, 2008 11:17:01AM +0100

Quoted 12 lines

From: Aaron Carroll <[email protected]>
Date: Wed, Nov 19, 2008 12:52:42PM +1100

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Quoted 3 lines

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

If you look at bfq_update_hw_tag(), the logic introduced by the patch you mention is still there; BFQ starts with ->hw_tag = 1, and updates it every 32 valid samples. What changed WRT your patch, apart from the number of samples, is that the condition for a sample to be valid is:

bfqd->rq_in_driver + bfqd->queued >= 5

while in your patch it is:

  cfqd->rq_queued > 5 || cfqd->rq_in_driver > 5

We preferred the first one because that sum better reflects the number of requests that could have been dispatched, and I don't think that this is wrong.

There is a problem, but it's not within the tag detection logic itself. From some quick experiments, what happens is that when a process starts, CFQ considers it seeky (*), BFQ doesn't. As a side effect BFQ does not always dispatch enough requests to correctly detect tagging.

At the first seek you cannot tell if the process is going to bee seeky or not, and we have chosen to consider it sequential because it improved fairness in some sequential workloads (the CIC_SEEKY heuristic is used also to determine the idle_window length in [bc]fq_arm_slice_timer()).

Anyway, we're dealing with heuristics, and they tend to favor some workload over other ones. If recovering this thoughput loss is more important than a transient unfairness due to short idling windows assigned to sequential processes when they start, I've no problems in switching the CIC_SEEKY logic to consider a process seeky when it starts.

Thank you for testing and for pointing out this issue, we missed it in our testing.

(*) to be correct, the initial classification depends on the position
of the first accessed sector.

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Quoted 5 lines

Quoted 3 lines

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

If you look at bfq_update_hw_tag(), the logic introduced by the patch you mention is still there; BFQ starts with ->hw_tag = 1, and updates it

Quoted 5 lines

every 32 valid samples. What changed WRT your patch, apart from the number of samples, is that the condition for a sample to be valid is:

bfqd->rq_in_driver + bfqd->queued >= 5

Quoted 7 lines

while in your patch it is:

  cfqd->rq_queued > 5 || cfqd->rq_in_driver > 5

We preferred the first one because that sum better reflects the number of requests that could have been dispatched, and I don't think that this is wrong.

Quoted 20 lines

There is a problem, but it's not within the tag detection logic itself. From some quick experiments, what happens is that when a process starts, CFQ considers it seeky (*), BFQ doesn't. As a side effect BFQ does not always dispatch enough requests to correctly detect tagging.

At the first seek you cannot tell if the process is going to bee seeky or not, and we have chosen to consider it sequential because it improved fairness in some sequential workloads (the CIC_SEEKY heuristic is used also to determine the idle_window length in [bc]fq_arm_slice_timer()).

Anyway, we're dealing with heuristics, and they tend to favor some workload over other ones. If recovering this thoughput loss is more important than a transient unfairness due to short idling windows assigned to sequential processes when they start, I've no problems in switching the CIC_SEEKY logic to consider a process seeky when it starts.

Thank you for testing and for pointing out this issue, we missed it in our testing.

Quoted 2 lines

(*) to be correct, the initial classification depends on the position
of the first accessed sector.

Sorry, I forgot the patch... This seems to solve the problem with your workload here, does it work for you?

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Quoted 5 lines

Quoted 3 lines

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

If you look at bfq_update_hw_tag(), the logic introduced by the patch you mention is still there; BFQ starts with ->hw_tag = 1, and updates it

Quoted 5 lines

every 32 valid samples. What changed WRT your patch, apart from the number of samples, is that the condition for a sample to be valid is:

bfqd->rq_in_driver + bfqd->queued >= 5

Quoted 7 lines

while in your patch it is:

  cfqd->rq_queued > 5 || cfqd->rq_in_driver > 5

We preferred the first one because that sum better reflects the number of requests that could have been dispatched, and I don't think that this is wrong.

Quoted 20 lines

There is a problem, but it's not within the tag detection logic itself. From some quick experiments, what happens is that when a process starts, CFQ considers it seeky (*), BFQ doesn't. As a side effect BFQ does not always dispatch enough requests to correctly detect tagging.

At the first seek you cannot tell if the process is going to bee seeky or not, and we have chosen to consider it sequential because it improved fairness in some sequential workloads (the CIC_SEEKY heuristic is used also to determine the idle_window length in [bc]fq_arm_slice_timer()).

Anyway, we're dealing with heuristics, and they tend to favor some workload over other ones. If recovering this thoughput loss is more important than a transient unfairness due to short idling windows assigned to sequential processes when they start, I've no problems in switching the CIC_SEEKY logic to consider a process seeky when it starts.

Thank you for testing and for pointing out this issue, we missed it in our testing.

Quoted 2 lines

(*) to be correct, the initial classification depends on the position
of the first accessed sector.

Sorry, I forgot the patch... This seems to solve the problem with your workload here, does it work for you?

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Quoted 5 lines

Quoted 3 lines

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

If you look at bfq_update_hw_tag(), the logic introduced by the patch you mention is still there; BFQ starts with ->hw_tag = 1, and updates it

Quoted 5 lines

every 32 valid samples. What changed WRT your patch, apart from the number of samples, is that the condition for a sample to be valid is:

bfqd->rq_in_driver + bfqd->queued >= 5

Quoted 7 lines

while in your patch it is:

  cfqd->rq_queued > 5 || cfqd->rq_in_driver > 5

We preferred the first one because that sum better reflects the number of requests that could have been dispatched, and I don't think that this is wrong.

Quoted 20 lines

There is a problem, but it's not within the tag detection logic itself. From some quick experiments, what happens is that when a process starts, CFQ considers it seeky (*), BFQ doesn't. As a side effect BFQ does not always dispatch enough requests to correctly detect tagging.

At the first seek you cannot tell if the process is going to bee seeky or not, and we have chosen to consider it sequential because it improved fairness in some sequential workloads (the CIC_SEEKY heuristic is used also to determine the idle_window length in [bc]fq_arm_slice_timer()).

Anyway, we're dealing with heuristics, and they tend to favor some workload over other ones. If recovering this thoughput loss is more important than a transient unfairness due to short idling windows assigned to sequential processes when they start, I've no problems in switching the CIC_SEEKY logic to consider a process seeky when it starts.

Thank you for testing and for pointing out this issue, we missed it in our testing.

Quoted 2 lines

(*) to be correct, the initial classification depends on the position
of the first accessed sector.

Sorry, I forgot the patch... This seems to solve the problem with your workload here, does it work for you?

From: Aaron Carroll <[email protected]>
Date: Thu, Nov 20, 2008 03:45:02PM +1100

Quoted 8 lines · Fabio Checconi

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Quoted 5 lines

Quoted 5 lines

Quoted 3 lines

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

If you look at bfq_update_hw_tag(), the logic introduced by the patch you mention is still there; BFQ starts with ->hw_tag = 1, and updates it

Yes, I missed that. So which part of CFQ's hw_tag detection is strange?

Quoted 5 lines

Quoted 5 lines

every 32 valid samples. What changed WRT your patch, apart from the number of samples, is that the condition for a sample to be valid is:

bfqd->rq_in_driver + bfqd->queued >= 5

Quoted 7 lines

Quoted 7 lines

while in your patch it is:

  cfqd->rq_queued > 5 || cfqd->rq_in_driver > 5

We preferred the first one because that sum better reflects the number of requests that could have been dispatched, and I don't think that this is wrong.

I think it's fine too. CFQ's condition accounts for a few rare situations, such as the device stalling or hw_tag being updated right after a bunch of requests are queued. They are probably irrelevant, but can't hurt.

Quoted 20 lines

Quoted 20 lines

There is a problem, but it's not within the tag detection logic itself. From some quick experiments, what happens is that when a process starts, CFQ considers it seeky (*), BFQ doesn't. As a side effect BFQ does not always dispatch enough requests to correctly detect tagging.

At the first seek you cannot tell if the process is going to bee seeky or not, and we have chosen to consider it sequential because it improved fairness in some sequential workloads (the CIC_SEEKY heuristic is used also to determine the idle_window length in [bc]fq_arm_slice_timer()).

Anyway, we're dealing with heuristics, and they tend to favor some workload over other ones. If recovering this thoughput loss is more important than a transient unfairness due to short idling windows assigned to sequential processes when they start, I've no problems in switching the CIC_SEEKY logic to consider a process seeky when it starts.

Thank you for testing and for pointing out this issue, we missed it in our testing.

Quoted 5 lines

Quoted 2 lines

(*) to be correct, the initial classification depends on the position
of the first accessed sector.

Sorry, I forgot the patch... This seems to solve the problem with your workload here, does it work for you?

Yes, it works fine now :)

However, hw_tag detection (in CFQ and BFQ) is still broken in a few ways:
* If you go from queue_depth=1 to queue_depth=large, it's possible that the detection logic fails. This could happen if setting queue_depth to a larger value at boot, which seems a reasonable situation.

* It depends too much on the hardware. If you have a seekly load on a fast disk with a unit queue depth, idling sucks for performance (I imagine this is particularly bad on SSDs). If you have any disk with a deep queue, not idling sucks for fairness.

I suppose CFQ's slice_resid is supposed to help here, but as far as I can tell, it doesn't do a thing.

From: Aaron Carroll <[email protected]>
Date: Thu, Nov 20, 2008 03:45:02PM +1100

Quoted 8 lines · Fabio Checconi

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Quoted 5 lines

Quoted 5 lines

Quoted 3 lines

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

If you look at bfq_update_hw_tag(), the logic introduced by the patch you mention is still there; BFQ starts with ->hw_tag = 1, and updates it

Yes, I missed that. So which part of CFQ's hw_tag detection is strange?

Quoted 5 lines

Quoted 5 lines

every 32 valid samples. What changed WRT your patch, apart from the number of samples, is that the condition for a sample to be valid is:

bfqd->rq_in_driver + bfqd->queued >= 5

Quoted 7 lines

Quoted 7 lines

while in your patch it is:

  cfqd->rq_queued > 5 || cfqd->rq_in_driver > 5

We preferred the first one because that sum better reflects the number of requests that could have been dispatched, and I don't think that this is wrong.

I think it's fine too. CFQ's condition accounts for a few rare situations, such as the device stalling or hw_tag being updated right after a bunch of requests are queued. They are probably irrelevant, but can't hurt.

Quoted 20 lines

Quoted 20 lines

There is a problem, but it's not within the tag detection logic itself. From some quick experiments, what happens is that when a process starts, CFQ considers it seeky (*), BFQ doesn't. As a side effect BFQ does not always dispatch enough requests to correctly detect tagging.

At the first seek you cannot tell if the process is going to bee seeky or not, and we have chosen to consider it sequential because it improved fairness in some sequential workloads (the CIC_SEEKY heuristic is used also to determine the idle_window length in [bc]fq_arm_slice_timer()).

Anyway, we're dealing with heuristics, and they tend to favor some workload over other ones. If recovering this thoughput loss is more important than a transient unfairness due to short idling windows assigned to sequential processes when they start, I've no problems in switching the CIC_SEEKY logic to consider a process seeky when it starts.

Thank you for testing and for pointing out this issue, we missed it in our testing.

Quoted 5 lines

Quoted 2 lines

(*) to be correct, the initial classification depends on the position
of the first accessed sector.

Sorry, I forgot the patch... This seems to solve the problem with your workload here, does it work for you?

Yes, it works fine now :)

However, hw_tag detection (in CFQ and BFQ) is still broken in a few ways:
* If you go from queue_depth=1 to queue_depth=large, it's possible that the detection logic fails. This could happen if setting queue_depth to a larger value at boot, which seems a reasonable situation.

* It depends too much on the hardware. If you have a seekly load on a fast disk with a unit queue depth, idling sucks for performance (I imagine this is particularly bad on SSDs). If you have any disk with a deep queue, not idling sucks for fairness.

I suppose CFQ's slice_resid is supposed to help here, but as far as I can tell, it doesn't do a thing.

From: Aaron Carroll <[email protected]>
Date: Thu, Nov 20, 2008 03:45:02PM +1100

Quoted 8 lines · Fabio Checconi

Quoted 8 lines

Quoted 8 lines

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Quoted 5 lines

Quoted 5 lines

Quoted 3 lines

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

If you look at bfq_update_hw_tag(), the logic introduced by the patch you mention is still there; BFQ starts with ->hw_tag = 1, and updates it

Yes, I missed that. So which part of CFQ's hw_tag detection is strange?

Quoted 5 lines

Quoted 5 lines

every 32 valid samples. What changed WRT your patch, apart from the number of samples, is that the condition for a sample to be valid is:

bfqd->rq_in_driver + bfqd->queued >= 5

Quoted 7 lines

Quoted 7 lines

while in your patch it is:

  cfqd->rq_queued > 5 || cfqd->rq_in_driver > 5

We preferred the first one because that sum better reflects the number of requests that could have been dispatched, and I don't think that this is wrong.

I think it's fine too. CFQ's condition accounts for a few rare situations, such as the device stalling or hw_tag being updated right after a bunch of requests are queued. They are probably irrelevant, but can't hurt.

Quoted 20 lines

Quoted 20 lines

There is a problem, but it's not within the tag detection logic itself. From some quick experiments, what happens is that when a process starts, CFQ considers it seeky (*), BFQ doesn't. As a side effect BFQ does not always dispatch enough requests to correctly detect tagging.

At the first seek you cannot tell if the process is going to bee seeky or not, and we have chosen to consider it sequential because it improved fairness in some sequential workloads (the CIC_SEEKY heuristic is used also to determine the idle_window length in [bc]fq_arm_slice_timer()).

Anyway, we're dealing with heuristics, and they tend to favor some workload over other ones. If recovering this thoughput loss is more important than a transient unfairness due to short idling windows assigned to sequential processes when they start, I've no problems in switching the CIC_SEEKY logic to consider a process seeky when it starts.

Thank you for testing and for pointing out this issue, we missed it in our testing.

Quoted 5 lines

Quoted 2 lines

(*) to be correct, the initial classification depends on the position
of the first accessed sector.

Sorry, I forgot the patch... This seems to solve the problem with your workload here, does it work for you?

Yes, it works fine now :)

However, hw_tag detection (in CFQ and BFQ) is still broken in a few ways:
* If you go from queue_depth=1 to queue_depth=large, it's possible that the detection logic fails. This could happen if setting queue_depth to a larger value at boot, which seems a reasonable situation.

* It depends too much on the hardware. If you have a seekly load on a fast disk with a unit queue depth, idling sucks for performance (I imagine this is particularly bad on SSDs). If you have any disk with a deep queue, not idling sucks for fairness.

I suppose CFQ's slice_resid is supposed to help here, but as far as I can tell, it doesn't do a thing.

From: Fabio Checconi <[email protected]>
Date: Wed, Nov 19, 2008 11:17:01AM +0100

Quoted 12 lines

From: Aaron Carroll <[email protected]>
Date: Wed, Nov 19, 2008 12:52:42PM +1100

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Quoted 3 lines

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

If you look at bfq_update_hw_tag(), the logic introduced by the patch you mention is still there; BFQ starts with ->hw_tag = 1, and updates it every 32 valid samples. What changed WRT your patch, apart from the number of samples, is that the condition for a sample to be valid is:

bfqd->rq_in_driver + bfqd->queued >= 5

while in your patch it is:

  cfqd->rq_queued > 5 || cfqd->rq_in_driver > 5

We preferred the first one because that sum better reflects the number of requests that could have been dispatched, and I don't think that this is wrong.

There is a problem, but it's not within the tag detection logic itself. From some quick experiments, what happens is that when a process starts, CFQ considers it seeky (*), BFQ doesn't. As a side effect BFQ does not always dispatch enough requests to correctly detect tagging.

At the first seek you cannot tell if the process is going to bee seeky or not, and we have chosen to consider it sequential because it improved fairness in some sequential workloads (the CIC_SEEKY heuristic is used also to determine the idle_window length in [bc]fq_arm_slice_timer()).

Anyway, we're dealing with heuristics, and they tend to favor some workload over other ones. If recovering this thoughput loss is more important than a transient unfairness due to short idling windows assigned to sequential processes when they start, I've no problems in switching the CIC_SEEKY logic to consider a process seeky when it starts.

Thank you for testing and for pointing out this issue, we missed it in our testing.

(*) to be correct, the initial classification depends on the position
of the first accessed sector.

From: Aaron Carroll <[email protected]>
Date: Wed, Nov 19, 2008 12:52:42PM +1100

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

From: Aaron Carroll <[email protected]>
Date: Wed, Nov 19, 2008 12:52:42PM +1100

Quoted 7 lines · Fabio Checconi

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

BFQ's tag detection logic is broken in the same way that CFQ's used to be. Explanation is in this patch:

Quoted 8 lines

From: Jens Axboe <[email protected]>
Date: Tue, Nov 18, 2008 08:12:08PM +0100

Quoted 4 lines · Fabio Checconi

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

...

Quoted 11 lines

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

Quoted 8 lines

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

Ok, I can do that, I need just a little bit of time to organize the work.

About these small (some of them are really small) changes, a mixed list of things that they will touch and/or things that I'd like to have clear before starting to write the patches (maybe we can start another thread for them):

- In cfq_exit_single_io_context() and in changed_ioprio(), cic->key is dereferenced without holding any lock. As I reported in [1] this seems to be a problem when an exit() races with a cfq_exit_queue() and in a few other cases. In BFQ we used a somehow involved mechanism to avoid that, abusing rcu (of course we'll have to wait the patch to talk about it :) ), but given my lack of understanding of some parts of the block layer, I'd be interested in knowing if the race is possible and/or if there is something more involved going on that can cause the same effects.

- set_task_ioprio() in fs/ioprio.c doesn't seem to have a write memory barrier to pair with the dependent read one in cfq_get_io_context().

- CFQ_MIN_TT is 2ms, this can result, depending on the value of HZ in timeouts of one jiffy, that may expire too early, so we are just wasting time and do not actually wait for the task to present its new request. Dealing with seeky traffic we've seen a lot of early timeouts due to one jiffy timers expiring too early, is it worth fixing or can we live with that?

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

- Initially, cic->last_request_pos is zero, so the sdist charged to a task for its first seek depends on the position on the disk that is accessed first, independently from its seekiness. Even if there is a cap on that value, we choose to not charge the first seek to processes; that resulted in less wrong predictions for purely sequential loads.

- From my understanding, with shared I/O contexts, two different tasks may concurrently lookup for a cfqd into the same ioc. This may result in cfq_drop_dead_cic() being called two times for the same cic. Am I missing something that prevents that from happening?

Regarding the code splitup, do you think you'll go for the CFS(BFQ) way, using a single compilation unit and including the .c files, or a layout with different compilation units (like the ll_rw_blk.c splitup)?

Quoted 8 lines

From: Jens Axboe <[email protected]>
Date: Tue, Nov 18, 2008 08:12:08PM +0100

Quoted 4 lines · Fabio Checconi

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

...

Quoted 11 lines

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

Quoted 8 lines

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

Ok, I can do that, I need just a little bit of time to organize the work.

About these small (some of them are really small) changes, a mixed list of things that they will touch and/or things that I'd like to have clear before starting to write the patches (maybe we can start another thread for them):

- In cfq_exit_single_io_context() and in changed_ioprio(), cic->key is dereferenced without holding any lock. As I reported in [1] this seems to be a problem when an exit() races with a cfq_exit_queue() and in a few other cases. In BFQ we used a somehow involved mechanism to avoid that, abusing rcu (of course we'll have to wait the patch to talk about it :) ), but given my lack of understanding of some parts of the block layer, I'd be interested in knowing if the race is possible and/or if there is something more involved going on that can cause the same effects.

- set_task_ioprio() in fs/ioprio.c doesn't seem to have a write memory barrier to pair with the dependent read one in cfq_get_io_context().

- CFQ_MIN_TT is 2ms, this can result, depending on the value of HZ in timeouts of one jiffy, that may expire too early, so we are just wasting time and do not actually wait for the task to present its new request. Dealing with seeky traffic we've seen a lot of early timeouts due to one jiffy timers expiring too early, is it worth fixing or can we live with that?

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

- Initially, cic->last_request_pos is zero, so the sdist charged to a task for its first seek depends on the position on the disk that is accessed first, independently from its seekiness. Even if there is a cap on that value, we choose to not charge the first seek to processes; that resulted in less wrong predictions for purely sequential loads.

- From my understanding, with shared I/O contexts, two different tasks may concurrently lookup for a cfqd into the same ioc. This may result in cfq_drop_dead_cic() being called two times for the same cic. Am I missing something that prevents that from happening?

Regarding the code splitup, do you think you'll go for the CFS(BFQ) way, using a single compilation unit and including the .c files, or a layout with different compilation units (like the ll_rw_blk.c splitup)?

From: Jens Axboe <[email protected]>
Date: Wed, Nov 19, 2008 03:30:07PM +0100

On Tue, Nov 18 2008, Fabio Checconi wrote:

Quoted 9 lines

- In cfq_exit_single_io_context() and in changed_ioprio(), cic->key is dereferenced without holding any lock. As I reported in [1] this seems to be a problem when an exit() races with a cfq_exit_queue() and in a few other cases. In BFQ we used a somehow involved mechanism to avoid that, abusing rcu (of course we'll have to wait the patch to talk about it :) ), but given my lack of understanding of some parts of the block layer, I'd be interested in knowing if the race is possible and/or if there is something more involved going on that can cause the same effects.

OK, I'm assuming this is where Nikanth got his idea for the patch from?

It does seem racy in spots, we can definitely proceed on getting that tightened up some more.

Quoted 3 lines

- set_task_ioprio() in fs/ioprio.c doesn't seem to have a write memory barrier to pair with the dependent read one in cfq_get_io_context().

Agree, that needs fixing.

Quoted 6 lines

- CFQ_MIN_TT is 2ms, this can result, depending on the value of HZ in timeouts of one jiffy, that may expire too early, so we are just wasting time and do not actually wait for the task to present its new request. Dealing with seeky traffic we've seen a lot of early timeouts due to one jiffy timers expiring too early, is it worth fixing or can we live with that?

We probably just need to enfore a '2 jiffies minimum' rule for that.

Quoted 7 lines

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Not sure this matters a whole lot, but your approach makes sense. Have you seen the later change to the CFQ logic from Aaron?

Quoted 6 lines

- Initially, cic->last_request_pos is zero, so the sdist charged to a task for its first seek depends on the position on the disk that is accessed first, independently from its seekiness. Even if there is a cap on that value, we choose to not charge the first seek to processes; that resulted in less wrong predictions for purely sequential loads.

Agreed, that's is definitely off.

Quoted 5 lines

- From my understanding, with shared I/O contexts, two different tasks may concurrently lookup for a cfqd into the same ioc. This may result in cfq_drop_dead_cic() being called two times for the same cic. Am I missing something that prevents that from happening?

That also looks problematic. I guess we need to recheck that under the lock when in cfq_drop_dead_cic().

Quoted 3 lines

Regarding the code splitup, do you think you'll go for the CFS(BFQ) way, using a single compilation unit and including the .c files, or a layout with different compilation units (like the ll_rw_blk.c splitup)?

Different compilation units would be my preferred choice.

From: Jens Axboe <[email protected]>
Date: Wed, Nov 19, 2008 03:30:07PM +0100

On Tue, Nov 18 2008, Fabio Checconi wrote:

Quoted 9 lines

- In cfq_exit_single_io_context() and in changed_ioprio(), cic->key is dereferenced without holding any lock. As I reported in [1] this seems to be a problem when an exit() races with a cfq_exit_queue() and in a few other cases. In BFQ we used a somehow involved mechanism to avoid that, abusing rcu (of course we'll have to wait the patch to talk about it :) ), but given my lack of understanding of some parts of the block layer, I'd be interested in knowing if the race is possible and/or if there is something more involved going on that can cause the same effects.

OK, I'm assuming this is where Nikanth got his idea for the patch from?

It does seem racy in spots, we can definitely proceed on getting that tightened up some more.

Quoted 3 lines

- set_task_ioprio() in fs/ioprio.c doesn't seem to have a write memory barrier to pair with the dependent read one in cfq_get_io_context().

Agree, that needs fixing.

Quoted 6 lines

- CFQ_MIN_TT is 2ms, this can result, depending on the value of HZ in timeouts of one jiffy, that may expire too early, so we are just wasting time and do not actually wait for the task to present its new request. Dealing with seeky traffic we've seen a lot of early timeouts due to one jiffy timers expiring too early, is it worth fixing or can we live with that?

We probably just need to enfore a '2 jiffies minimum' rule for that.

Quoted 7 lines

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Not sure this matters a whole lot, but your approach makes sense. Have you seen the later change to the CFQ logic from Aaron?

Quoted 6 lines

- Initially, cic->last_request_pos is zero, so the sdist charged to a task for its first seek depends on the position on the disk that is accessed first, independently from its seekiness. Even if there is a cap on that value, we choose to not charge the first seek to processes; that resulted in less wrong predictions for purely sequential loads.

Agreed, that's is definitely off.

Quoted 5 lines

- From my understanding, with shared I/O contexts, two different tasks may concurrently lookup for a cfqd into the same ioc. This may result in cfq_drop_dead_cic() being called two times for the same cic. Am I missing something that prevents that from happening?

That also looks problematic. I guess we need to recheck that under the lock when in cfq_drop_dead_cic().

Quoted 3 lines

Regarding the code splitup, do you think you'll go for the CFS(BFQ) way, using a single compilation unit and including the .c files, or a layout with different compilation units (like the ll_rw_blk.c splitup)?

Different compilation units would be my preferred choice.

From: Jens Axboe <[email protected]>
Date: Wed, Nov 19, 2008 03:30:07PM +0100

On Tue, Nov 18 2008, Fabio Checconi wrote:

Quoted 9 lines

- In cfq_exit_single_io_context() and in changed_ioprio(), cic->key is dereferenced without holding any lock. As I reported in [1] this seems to be a problem when an exit() races with a cfq_exit_queue() and in a few other cases. In BFQ we used a somehow involved mechanism to avoid that, abusing rcu (of course we'll have to wait the patch to talk about it :) ), but given my lack of understanding of some parts of the block layer, I'd be interested in knowing if the race is possible and/or if there is something more involved going on that can cause the same effects.

OK, I'm assuming this is where Nikanth got his idea for the patch from?

It does seem racy in spots, we can definitely proceed on getting that tightened up some more.

Quoted 3 lines

- set_task_ioprio() in fs/ioprio.c doesn't seem to have a write memory barrier to pair with the dependent read one in cfq_get_io_context().

Agree, that needs fixing.

Quoted 6 lines

- CFQ_MIN_TT is 2ms, this can result, depending on the value of HZ in timeouts of one jiffy, that may expire too early, so we are just wasting time and do not actually wait for the task to present its new request. Dealing with seeky traffic we've seen a lot of early timeouts due to one jiffy timers expiring too early, is it worth fixing or can we live with that?

We probably just need to enfore a '2 jiffies minimum' rule for that.

Quoted 7 lines

- To detect hw tagging in BFQ we consider a sample valid iff the number of requests that the scheduler could have dispatched (given by cfqd->rb_queued + cfqd->rq_in_driver, i.e., the ones still into the scheduler plus the ones into the driver) is higher than the CFQ_HW_QUEUE_MIN threshold. This obviously caused no problems during testing, but the way CFQ uses now seems a little bit strange.

Not sure this matters a whole lot, but your approach makes sense. Have you seen the later change to the CFQ logic from Aaron?

Quoted 6 lines

- Initially, cic->last_request_pos is zero, so the sdist charged to a task for its first seek depends on the position on the disk that is accessed first, independently from its seekiness. Even if there is a cap on that value, we choose to not charge the first seek to processes; that resulted in less wrong predictions for purely sequential loads.

Agreed, that's is definitely off.

Quoted 5 lines

- From my understanding, with shared I/O contexts, two different tasks may concurrently lookup for a cfqd into the same ioc. This may result in cfq_drop_dead_cic() being called two times for the same cic. Am I missing something that prevents that from happening?

That also looks problematic. I guess we need to recheck that under the lock when in cfq_drop_dead_cic().

Quoted 3 lines

Regarding the code splitup, do you think you'll go for the CFS(BFQ) way, using a single compilation unit and including the .c files, or a layout with different compilation units (like the ll_rw_blk.c splitup)?

Different compilation units would be my preferred choice.

From: Jens Axboe <[email protected]>
Date: Tue, Nov 18, 2008 08:12:08PM +0100

Quoted 4 lines · Fabio Checconi

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

--
Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

My main goal here is basically avoiding addition of Yet Another IO scheduler, especially one that is so closely tied to CFQ already.

I'll start things off by splitting cfq into a few files similar to what bfq has done, as I think it makes a lot of sense. Fabio, if you could create patches for the small behavioural changes you made, we can discuss and hopefully merge those next.

--
Jens Axboe

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

that subset of the problem, that avoids touching the io scheduler. If we can get this supported 'generically', then I'd be happy to help out.

--
Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

that subset of the problem, that avoids touching the io scheduler. If we can get this supported 'generically', then I'd be happy to help out.

--
Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

that subset of the problem, that avoids touching the io scheduler. If we can get this supported 'generically', then I'd be happy to help out.

--
Jens Axboe

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Quoted 113 lines · Jens Axboe

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Thanks
Vivek

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Quoted 113 lines · Jens Axboe

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Thanks
Vivek

Quoted 113 lines · Jens Axboe

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Thanks
Vivek

Quoted 161 lines · Vivek Goyal

Quoted 113 lines · Jens Axboe

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Quoted 8 lines

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Thanks
Vivek

It seems that we have a solution if we can figure out a way to share cgroup code between different schedulers. I am thinking how other schedulers (AS, Deadline, No-op) would use cgroups. Will they have proportional division between requests from different cgroups? And use their own policy (e.g deadline scheduling) within a cgroup? How about if we have both threads and cgroups at a particular level? I think putting all threads in a default cgroup seems like a reasonable choice in this case.

Here is a high level design that comes to mind.

Put proportional division code and state in common code. Each level of the hierarchy which has more than one cgroup would have some state maintained in common code. At leaf level of hiearchy, we can have a cgroup specific scheduler (created when a cgroup is created). We can choose a different scheduler for each cgroup (we can have a no-op for one cgroup while cfq for another).

The scheduler gets a callback (just like it does right now from driver) when the common code schedules a time slice (or budget) from that cgroup. No buffering/queuing is done in the common code, so it will still be a single level scheduler. When a request arrives, it is routed to its scheduler's queues based on its cgroup.

The common code proportional scheduler uses specified weights to schedule time slices. Please let me know if it makes any sense. And then we can start talking about lower level details.

Quoted 161 lines · Vivek Goyal

Quoted 113 lines · Jens Axboe

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Quoted 8 lines

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Thanks
Vivek

It seems that we have a solution if we can figure out a way to share cgroup code between different schedulers. I am thinking how other schedulers (AS, Deadline, No-op) would use cgroups. Will they have proportional division between requests from different cgroups? And use their own policy (e.g deadline scheduling) within a cgroup? How about if we have both threads and cgroups at a particular level? I think putting all threads in a default cgroup seems like a reasonable choice in this case.

Here is a high level design that comes to mind.

Put proportional division code and state in common code. Each level of the hierarchy which has more than one cgroup would have some state maintained in common code. At leaf level of hiearchy, we can have a cgroup specific scheduler (created when a cgroup is created). We can choose a different scheduler for each cgroup (we can have a no-op for one cgroup while cfq for another).

The scheduler gets a callback (just like it does right now from driver) when the common code schedules a time slice (or budget) from that cgroup. No buffering/queuing is done in the common code, so it will still be a single level scheduler. When a request arrives, it is routed to its scheduler's queues based on its cgroup.

The common code proportional scheduler uses specified weights to schedule time slices. Please let me know if it makes any sense. And then we can start talking about lower level details.

Quoted 161 lines · Vivek Goyal

Quoted 113 lines · Jens Axboe

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Quoted 8 lines

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Thanks
Vivek

It seems that we have a solution if we can figure out a way to share cgroup code between different schedulers. I am thinking how other schedulers (AS, Deadline, No-op) would use cgroups. Will they have proportional division between requests from different cgroups? And use their own policy (e.g deadline scheduling) within a cgroup? How about if we have both threads and cgroups at a particular level? I think putting all threads in a default cgroup seems like a reasonable choice in this case.

Here is a high level design that comes to mind.

Put proportional division code and state in common code. Each level of the hierarchy which has more than one cgroup would have some state maintained in common code. At leaf level of hiearchy, we can have a cgroup specific scheduler (created when a cgroup is created). We can choose a different scheduler for each cgroup (we can have a no-op for one cgroup while cfq for another).

The scheduler gets a callback (just like it does right now from driver) when the common code schedules a time slice (or budget) from that cgroup. No buffering/queuing is done in the common code, so it will still be a single level scheduler. When a request arrives, it is routed to its scheduler's queues based on its cgroup.

The common code proportional scheduler uses specified weights to schedule time slices. Please let me know if it makes any sense. And then we can start talking about lower level details.

Quoted 180 lines · Nauman Rafique

Quoted 161 lines · Vivek Goyal

Quoted 113 lines · Jens Axboe

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Quoted 8 lines

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Thanks
Vivek

It seems that we have a solution if we can figure out a way to share cgroup code between different schedulers. I am thinking how other schedulers (AS, Deadline, No-op) would use cgroups. Will they have proportional division between requests from different cgroups? And use their own policy (e.g deadline scheduling) within a cgroup? How about if we have both threads and cgroups at a particular level? I think putting all threads in a default cgroup seems like a reasonable choice in this case.

Quoted 8 lines

Here is a high level design that comes to mind.

Put proportional division code and state in common code. Each level of the hierarchy which has more than one cgroup would have some state maintained in common code. At leaf level of hiearchy, we can have a cgroup specific scheduler (created when a cgroup is created). We can choose a different scheduler for each cgroup (we can have a no-op for one cgroup while cfq for another).

I am not sure that I understand the different scheduler for each cgroup aspect of it. What's the need? It makes things even more complicated I think.

But moving proportional division code out of particular scheduler and make it common makes sense.

Looking at BFQ, I was thinking that we can just keep large part of the code. This common code can think of everything as scheduling entity. This scheduling entity (SE) will be defined by underlying scheduler depending on how queue management is done by underlying scheduler. So for CFQ, at each level, an SE can be either task or group. For the schedulers which don't maintain separate queues for tasks, it will simply be group at all levels.

We probably can employ B-WFQ2+ to provide hierarchical fairness between secheduling entities of this tree. Common layer will do the scheduling of entities (without knowing what is contained inside) and underlying scheduler will take care of dispatching the requests from the scheduled entity. (It could be a task queue for CFQ or a group queue for other schedulers).

The tricky part would be how to abstract it in a clean way. It should lead to reduced code in CFQ/BFQ because B-WFQ2+ logic will be put into a common layer (for large part).

Quoted 11 lines

The scheduler gets a callback (just like it does right now from driver) when the common code schedules a time slice (or budget) from that cgroup. No buffering/queuing is done in the common code, so it will still be a single level scheduler. When a request arrives, it is routed to its scheduler's queues based on its cgroup.

The common code proportional scheduler uses specified weights to schedule time slices. Please let me know if it makes any sense. And then we can start talking about lower level details.

We can use either time slices or budgets (may be configurable) depending on which gives better results.

Thanks
Vivek

Quoted 180 lines · Nauman Rafique

Quoted 161 lines · Vivek Goyal

Quoted 113 lines · Jens Axboe

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Quoted 8 lines

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Thanks
Vivek

It seems that we have a solution if we can figure out a way to share cgroup code between different schedulers. I am thinking how other schedulers (AS, Deadline, No-op) would use cgroups. Will they have proportional division between requests from different cgroups? And use their own policy (e.g deadline scheduling) within a cgroup? How about if we have both threads and cgroups at a particular level? I think putting all threads in a default cgroup seems like a reasonable choice in this case.

Quoted 8 lines

Here is a high level design that comes to mind.

Put proportional division code and state in common code. Each level of the hierarchy which has more than one cgroup would have some state maintained in common code. At leaf level of hiearchy, we can have a cgroup specific scheduler (created when a cgroup is created). We can choose a different scheduler for each cgroup (we can have a no-op for one cgroup while cfq for another).

I am not sure that I understand the different scheduler for each cgroup aspect of it. What's the need? It makes things even more complicated I think.

But moving proportional division code out of particular scheduler and make it common makes sense.

Looking at BFQ, I was thinking that we can just keep large part of the code. This common code can think of everything as scheduling entity. This scheduling entity (SE) will be defined by underlying scheduler depending on how queue management is done by underlying scheduler. So for CFQ, at each level, an SE can be either task or group. For the schedulers which don't maintain separate queues for tasks, it will simply be group at all levels.

We probably can employ B-WFQ2+ to provide hierarchical fairness between secheduling entities of this tree. Common layer will do the scheduling of entities (without knowing what is contained inside) and underlying scheduler will take care of dispatching the requests from the scheduled entity. (It could be a task queue for CFQ or a group queue for other schedulers).

The tricky part would be how to abstract it in a clean way. It should lead to reduced code in CFQ/BFQ because B-WFQ2+ logic will be put into a common layer (for large part).

Quoted 11 lines

The scheduler gets a callback (just like it does right now from driver) when the common code schedules a time slice (or budget) from that cgroup. No buffering/queuing is done in the common code, so it will still be a single level scheduler. When a request arrives, it is routed to its scheduler's queues based on its cgroup.

The common code proportional scheduler uses specified weights to schedule time slices. Please let me know if it makes any sense. And then we can start talking about lower level details.

We can use either time slices or budgets (may be configurable) depending on which gives better results.

Thanks
Vivek

Quoted 180 lines · Nauman Rafique

Quoted 161 lines · Vivek Goyal

Quoted 113 lines · Jens Axboe

Quoted 104 lines · Divyesh Shah

Quoted 90 lines · Jens Axboe

Quoted 57 lines · Nauman Rafique

Quoted 56 lines · Jens Axboe

Quoted 45 lines · Fabio Checconi

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

Quoted 3 lines

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

My preferred approach here would be, in order or TODO:

- Create and test the smallish patches for seekiness, hw_tag checking, and so on for CFQ.
- Create and test a WF2Q+ service dispatching patch for CFQ.

Quoted 7 lines

Quoted 4 lines

and if there are leftovers after that, we could even conditionally enable some of those if appropriate. I think the WF2Q+ is quite cool and could be easily usable as the default, so it's definitely a viable alternative.

1 Merge BFQ into CFQ (Jens and Fabio). I am assuming that this would result in time slices being scheduled using WF2Q+

Yep, at least that is my preference.

Quoted 22 lines

2 Do the following to support proportional division:
a) Expose the per device weight interface to user, instead of calculating from priority.
b) Add support for scheduling bandwidth among a hierarchy of cgroups
(besides threads)
3 Do the following to support the goals of 2 level schedulers:
a) Limit the request descriptors allocated to each cgroup by adding functionality to elv_may_queue()
b) Add support for putting an absolute limit on IO consumed by a cgroup. Such support is provided by Andrea
Righi's patches too.
c) Add support (configurable option) to keep track of total disk
time/sectors/count
consumed at each device, and factor that into scheduling decision (more discussion needed here)
6 Incorporate an IO tracking approach which can allow tracking cgroups for asynchronous reads/writes.
7 Start an offline email thread to keep track of progress on the above goals.

Jens, what is your opinion everything beyond (1) in the above list?

Quoted 7 lines

Quoted 3 lines

It would be great if work on (1) and (2)-(7) can happen in parallel so that we can see "proportional division of IO bandwidth to cgroups" in tree sooner than later.

Sounds feasible, I'd like to see the cgroups approach get more traction. My primary concern is just that I don't want to merge it into specific IO schedulers.

Jens,
So are you saying you don't prefer cgroups based proportional IO
division solutions in the IO scheduler but at a layer above so it can be shared with all IO schedulers?

Quoted 7 lines

If yes, then in that case, what do you think about Vivek Goyal's
patch or dm-ioband that achieve that. Of course, both solutions don't meet all the requirements in the list above, but we can work on that once we know which direction we should be heading in. In fact, it would help if you could express the reservations (if you have any) about these approaches. That would help in coming up with a plan that everyone agrees on.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Quoted 8 lines

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Thanks
Vivek

It seems that we have a solution if we can figure out a way to share cgroup code between different schedulers. I am thinking how other schedulers (AS, Deadline, No-op) would use cgroups. Will they have proportional division between requests from different cgroups? And use their own policy (e.g deadline scheduling) within a cgroup? How about if we have both threads and cgroups at a particular level? I think putting all threads in a default cgroup seems like a reasonable choice in this case.

Quoted 8 lines

Here is a high level design that comes to mind.

Put proportional division code and state in common code. Each level of the hierarchy which has more than one cgroup would have some state maintained in common code. At leaf level of hiearchy, we can have a cgroup specific scheduler (created when a cgroup is created). We can choose a different scheduler for each cgroup (we can have a no-op for one cgroup while cfq for another).

I am not sure that I understand the different scheduler for each cgroup aspect of it. What's the need? It makes things even more complicated I think.

But moving proportional division code out of particular scheduler and make it common makes sense.

Looking at BFQ, I was thinking that we can just keep large part of the code. This common code can think of everything as scheduling entity. This scheduling entity (SE) will be defined by underlying scheduler depending on how queue management is done by underlying scheduler. So for CFQ, at each level, an SE can be either task or group. For the schedulers which don't maintain separate queues for tasks, it will simply be group at all levels.

We probably can employ B-WFQ2+ to provide hierarchical fairness between secheduling entities of this tree. Common layer will do the scheduling of entities (without knowing what is contained inside) and underlying scheduler will take care of dispatching the requests from the scheduled entity. (It could be a task queue for CFQ or a group queue for other schedulers).

The tricky part would be how to abstract it in a clean way. It should lead to reduced code in CFQ/BFQ because B-WFQ2+ logic will be put into a common layer (for large part).

Quoted 11 lines

The scheduler gets a callback (just like it does right now from driver) when the common code schedules a time slice (or budget) from that cgroup. No buffering/queuing is done in the common code, so it will still be a single level scheduler. When a request arrives, it is routed to its scheduler's queues based on its cgroup.

The common code proportional scheduler uses specified weights to schedule time slices. Please let me know if it makes any sense. And then we can start talking about lower level details.

We can use either time slices or budgets (may be configurable) depending on which gives better results.

Thanks
Vivek

Quoted 18 lines

Quoted 9 lines

It seems that we have a solution if we can figure out a way to share cgroup code between different schedulers. I am thinking how other schedulers (AS, Deadline, No-op) would use cgroups. Will they have proportional division between requests from different cgroups? And use their own policy (e.g deadline scheduling) within a cgroup? How about if we have both threads and cgroups at a particular level? I think putting all threads in a default cgroup seems like a reasonable choice in this case.

Quoted 8 lines

Here is a high level design that comes to mind.

Put proportional division code and state in common code. Each level of the hierarchy which has more than one cgroup would have some state maintained in common code. At leaf level of hiearchy, we can have a cgroup specific scheduler (created when a cgroup is created). We can choose a different scheduler for each cgroup (we can have a no-op for one cgroup while cfq for another).

Quoted 3 lines

I am not sure that I understand the different scheduler for each cgroup aspect of it. What's the need? It makes things even more complicated I think.

With the design I had in my mind, it seemed like that would come for free. But if it does not, I completely agree with you that its not as important.

Quoted 11 lines

But moving proportional division code out of particular scheduler and make it common makes sense.

Looking at BFQ, I was thinking that we can just keep large part of the code. This common code can think of everything as scheduling entity. This scheduling entity (SE) will be defined by underlying scheduler depending on how queue management is done by underlying scheduler. So for CFQ, at each level, an SE can be either task or group. For the schedulers which don't maintain separate queues for tasks, it will simply be group at all levels.

So the structure of hierarchy would be dependent on the underlying scheduler?

Quoted 10 lines

We probably can employ B-WFQ2+ to provide hierarchical fairness between secheduling entities of this tree. Common layer will do the scheduling of entities (without knowing what is contained inside) and underlying scheduler will take care of dispatching the requests from the scheduled entity. (It could be a task queue for CFQ or a group queue for other schedulers).

The tricky part would be how to abstract it in a clean way. It should lead to reduced code in CFQ/BFQ because B-WFQ2+ logic will be put into a common layer (for large part).

How about this plan:
1 Start with CFQ patched with some BFQ like patches (This is what we will have if Jens takes some of Fabio's patches). This will have no cgroup related logic (correct me if I am wrong).
2 Repeat proportional scheduling logic for cgroups in the common layer, without touching the code produced in step 1. That means that we will have WF2Q+ used for scheduling cgroup time slices proportional to weight in the common code. If CFQ (step 1 output) is used as scheduler, WF2Q+ would be used there too, but to schedule time slices (in proportion to priorities?) between different threads. Common code logic will be completely oblivious of the actual scheduler used (patched CFQ, Deadline, AS etc).

cgroup tracking has to be implemented as part of step 2. The good thing is that step 2 can proceed independent of step 1, as the output of step 1 will have the same interface as the existing CFQ scheduler.

Quoted 18 lines

Quoted 9 lines

It seems that we have a solution if we can figure out a way to share cgroup code between different schedulers. I am thinking how other schedulers (AS, Deadline, No-op) would use cgroups. Will they have proportional division between requests from different cgroups? And use their own policy (e.g deadline scheduling) within a cgroup? How about if we have both threads and cgroups at a particular level? I think putting all threads in a default cgroup seems like a reasonable choice in this case.

Quoted 8 lines

Here is a high level design that comes to mind.

Put proportional division code and state in common code. Each level of the hierarchy which has more than one cgroup would have some state maintained in common code. At leaf level of hiearchy, we can have a cgroup specific scheduler (created when a cgroup is created). We can choose a different scheduler for each cgroup (we can have a no-op for one cgroup while cfq for another).

Quoted 3 lines

I am not sure that I understand the different scheduler for each cgroup aspect of it. What's the need? It makes things even more complicated I think.

With the design I had in my mind, it seemed like that would come for free. But if it does not, I completely agree with you that its not as important.

Quoted 11 lines

But moving proportional division code out of particular scheduler and make it common makes sense.

Looking at BFQ, I was thinking that we can just keep large part of the code. This common code can think of everything as scheduling entity. This scheduling entity (SE) will be defined by underlying scheduler depending on how queue management is done by underlying scheduler. So for CFQ, at each level, an SE can be either task or group. For the schedulers which don't maintain separate queues for tasks, it will simply be group at all levels.

So the structure of hierarchy would be dependent on the underlying scheduler?

Quoted 10 lines

We probably can employ B-WFQ2+ to provide hierarchical fairness between secheduling entities of this tree. Common layer will do the scheduling of entities (without knowing what is contained inside) and underlying scheduler will take care of dispatching the requests from the scheduled entity. (It could be a task queue for CFQ or a group queue for other schedulers).

The tricky part would be how to abstract it in a clean way. It should lead to reduced code in CFQ/BFQ because B-WFQ2+ logic will be put into a common layer (for large part).

How about this plan:
1 Start with CFQ patched with some BFQ like patches (This is what we will have if Jens takes some of Fabio's patches). This will have no cgroup related logic (correct me if I am wrong).
2 Repeat proportional scheduling logic for cgroups in the common layer, without touching the code produced in step 1. That means that we will have WF2Q+ used for scheduling cgroup time slices proportional to weight in the common code. If CFQ (step 1 output) is used as scheduler, WF2Q+ would be used there too, but to schedule time slices (in proportion to priorities?) between different threads. Common code logic will be completely oblivious of the actual scheduler used (patched CFQ, Deadline, AS etc).

cgroup tracking has to be implemented as part of step 2. The good thing is that step 2 can proceed independent of step 1, as the output of step 1 will have the same interface as the existing CFQ scheduler.

Quoted 18 lines

Quoted 9 lines

It seems that we have a solution if we can figure out a way to share cgroup code between different schedulers. I am thinking how other schedulers (AS, Deadline, No-op) would use cgroups. Will they have proportional division between requests from different cgroups? And use their own policy (e.g deadline scheduling) within a cgroup? How about if we have both threads and cgroups at a particular level? I think putting all threads in a default cgroup seems like a reasonable choice in this case.

Quoted 8 lines

Here is a high level design that comes to mind.

Put proportional division code and state in common code. Each level of the hierarchy which has more than one cgroup would have some state maintained in common code. At leaf level of hiearchy, we can have a cgroup specific scheduler (created when a cgroup is created). We can choose a different scheduler for each cgroup (we can have a no-op for one cgroup while cfq for another).

Quoted 3 lines

I am not sure that I understand the different scheduler for each cgroup aspect of it. What's the need? It makes things even more complicated I think.

With the design I had in my mind, it seemed like that would come for free. But if it does not, I completely agree with you that its not as important.

Quoted 11 lines

But moving proportional division code out of particular scheduler and make it common makes sense.

Looking at BFQ, I was thinking that we can just keep large part of the code. This common code can think of everything as scheduling entity. This scheduling entity (SE) will be defined by underlying scheduler depending on how queue management is done by underlying scheduler. So for CFQ, at each level, an SE can be either task or group. For the schedulers which don't maintain separate queues for tasks, it will simply be group at all levels.

So the structure of hierarchy would be dependent on the underlying scheduler?

Quoted 10 lines

We probably can employ B-WFQ2+ to provide hierarchical fairness between secheduling entities of this tree. Common layer will do the scheduling of entities (without knowing what is contained inside) and underlying scheduler will take care of dispatching the requests from the scheduled entity. (It could be a task queue for CFQ or a group queue for other schedulers).

The tricky part would be how to abstract it in a clean way. It should lead to reduced code in CFQ/BFQ because B-WFQ2+ logic will be put into a common layer (for large part).

How about this plan:
1 Start with CFQ patched with some BFQ like patches (This is what we will have if Jens takes some of Fabio's patches). This will have no cgroup related logic (correct me if I am wrong).
2 Repeat proportional scheduling logic for cgroups in the common layer, without touching the code produced in step 1. That means that we will have WF2Q+ used for scheduling cgroup time slices proportional to weight in the common code. If CFQ (step 1 output) is used as scheduler, WF2Q+ would be used there too, but to schedule time slices (in proportion to priorities?) between different threads. Common code logic will be completely oblivious of the actual scheduler used (patched CFQ, Deadline, AS etc).

cgroup tracking has to be implemented as part of step 2. The good thing is that step 2 can proceed independent of step 1, as the output of step 1 will have the same interface as the existing CFQ scheduler.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

Quoted 12 lines · Vivek Goyal

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Quoted 6 lines

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

The problem with stacking devices is that we do not know how the IO going through the leaf nodes contributes to the aggregate throughput seen by the application/cgroup that generated it, which is what end users care about.

The block device could be a plain old sata device, a loop device, a stacking device, a SSD, you name it, but their topologies and the fact that some of them do not even use an elevator should be transparent to the user.

If you wanted to do resource management at the leaf nodes some kind of topology information should be passed down to the elevators controlling the underlying devices, which in turn would need to work cooperatively.

Quoted 2 lines

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

For the reasons stated above the two level scheduling approach seems cleaner to me.

Quoted 6 lines

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

Please notice that the such an IO controller would only get in the way of the elevator in case of contention for the device.

What is more,
depending on the workload it turns out that buffering at higher layers in a per-cgroup or per-task basis, like dm-band does, may actually increase the aggregate throughput (I think that the dm-band team observed this behavior too). The reason seems to be that bios buffered in such way tend to be highly correlated and thus very likely to get merged when released to the elevator.

Quoted 11 lines

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Quoted 6 lines

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

If deemed necessary this case could be handled too, but it does not look like a show-stopper.

Quoted 4 lines

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

As discussed above, I still think that the two level scheduling approach makes more sense.

Regarding the sharing of cgroup code among IO
schedulers I am all for it. If we consider that elevators should only care about maximizing usage of the underlying devices, implementing other non-hardware-dependent scheduling disciplines (that prioritize according to the task or cgroup that generated the IO, for example) at higher layers so that we can reuse code makes a lot of sense.

Thanks,

Fernando

Quoted 12 lines · Vivek Goyal

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Quoted 6 lines

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

The problem with stacking devices is that we do not know how the IO going through the leaf nodes contributes to the aggregate throughput seen by the application/cgroup that generated it, which is what end users care about.

The block device could be a plain old sata device, a loop device, a stacking device, a SSD, you name it, but their topologies and the fact that some of them do not even use an elevator should be transparent to the user.

If you wanted to do resource management at the leaf nodes some kind of topology information should be passed down to the elevators controlling the underlying devices, which in turn would need to work cooperatively.

Quoted 2 lines

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

For the reasons stated above the two level scheduling approach seems cleaner to me.

Quoted 6 lines

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

Please notice that the such an IO controller would only get in the way of the elevator in case of contention for the device.

What is more,
depending on the workload it turns out that buffering at higher layers in a per-cgroup or per-task basis, like dm-band does, may actually increase the aggregate throughput (I think that the dm-band team observed this behavior too). The reason seems to be that bios buffered in such way tend to be highly correlated and thus very likely to get merged when released to the elevator.

Quoted 11 lines

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Quoted 6 lines

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

If deemed necessary this case could be handled too, but it does not look like a show-stopper.

Quoted 4 lines

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

As discussed above, I still think that the two level scheduling approach makes more sense.

Regarding the sharing of cgroup code among IO
schedulers I am all for it. If we consider that elevators should only care about maximizing usage of the underlying devices, implementing other non-hardware-dependent scheduling disciplines (that prioritize according to the task or cgroup that generated the IO, for example) at higher layers so that we can reuse code makes a lot of sense.

Thanks,

Fernando

Quoted 12 lines · Vivek Goyal

Quoted 6 lines

The dm approach has some merrits, the major one being that it'll fit directly into existing setups that use dm and can be controlled with familiar tools. That is a bonus. The draw back is partially the same - it'll require dm. So it's still not a fit-all approach, unfortunately.

So I'd prefer an approach that doesn't force you to use dm.

Hi Jens,

My patches met the goal of not using the dm for every device one wants to control.

Quoted 6 lines

Having said that, few things come to mind.

- In what cases do we need to control the higher level logical devices like dm. It looks like real contention for resources is at leaf nodes. Hence any kind of resource management/fair queueing should probably be done at leaf nodes and not at higher level logical nodes.

The problem with stacking devices is that we do not know how the IO going through the leaf nodes contributes to the aggregate throughput seen by the application/cgroup that generated it, which is what end users care about.

The block device could be a plain old sata device, a loop device, a stacking device, a SSD, you name it, but their topologies and the fact that some of them do not even use an elevator should be transparent to the user.

If you wanted to do resource management at the leaf nodes some kind of topology information should be passed down to the elevators controlling the underlying devices, which in turn would need to work cooperatively.

Quoted 2 lines

If that makes sense, then probably we don't need to control dm device and we don't need such higher level solutions.

For the reasons stated above the two level scheduling approach seems cleaner to me.

Quoted 6 lines

- Any kind of 2 level scheduler solution has the potential to break the underlying IO scheduler. Higher level solution requires buffering of bios and controlled release of bios to lower layers. This control breaks the assumptions of lower layer IO scheduler which knows in what order bios should be dispatched to device to meet the semantics exported by the IO scheduler.

Please notice that the such an IO controller would only get in the way of the elevator in case of contention for the device.

What is more,
depending on the workload it turns out that buffering at higher layers in a per-cgroup or per-task basis, like dm-band does, may actually increase the aggregate throughput (I think that the dm-band team observed this behavior too). The reason seems to be that bios buffered in such way tend to be highly correlated and thus very likely to get merged when released to the elevator.

Quoted 11 lines

- 2nd level scheduler does not keep track of tasks but task groups lets every group dispatch fair share. This has got little semantic problem in the sense that tasks and groups in root cgroup will not be considered at same level. "root" will be considered one group at same level with all child group hence competing with them for resources.

This looks little odd. Considering tasks and groups same level kind of makes more sense. cpu scheduler also consideres tasks and groups at same level and deviation from that probably is not very good.

Quoted 6 lines

Considering tasks and groups at same level will matter only if IO scheduler maintains separate queue for the task, like CFQ. Because in that case IO scheduler tries to provide fairness among various task queues. Some schedulers like noop don't have any notion of separate task queues and fairness among them. In that case probably we don't have a choice but to assume root group competing with child groups.

If deemed necessary this case could be handled too, but it does not look like a show-stopper.

Quoted 4 lines

Keeping above points in mind, probably two level scheduling is not a very good idea. If putting the code in a particular IO scheduler is a concern we can probably explore ways regarding how we can maximize the sharing of cgroup code among IO schedulers.

As discussed above, I still think that the two level scheduling approach makes more sense.

Regarding the sharing of cgroup code among IO
schedulers I am all for it. If we consider that elevators should only care about maximizing usage of the underlying devices, implementing other non-hardware-dependent scheduling disciplines (that prioritize according to the task or cgroup that generated the IO, for example) at higher layers so that we can reuse code makes a lot of sense.

Thanks,

Fernando

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

Quoted 4 lines

From: Vivek Goyal <[email protected]>
Date: Tue, Nov 18, 2008 09:07:51AM -0500

On Tue, Nov 18, 2008 at 01:05:08PM +0100, Fabio Checconi wrote:

...

Quoted 17 lines

Quoted 4 lines

I have to think a little bit on how it would be possible to support an option for time-only budgets, coexisting with the current behavior, but I think it can be done.

IIUC, bfq and cfq are different in following manner.

a. BFQ employs WF2Q+ for fairness and CFQ employes weighted round robin. b. BFQ uses the budget (sector count) as notion of service and CFQ uses
time slices.
c. BFQ supports hierarchical fair queuing and CFQ does not.

We are looking forward for implementation of point C. Fabio seems to thinking of supporting time slice as a service (B). It seems like convergence of CFQ and BFQ except the point A (WF2Q+ vs weighted round robin).

Quoted 5 lines

It looks like WF2Q+ provides tighter service bound and bfq guys mention that they have been able to ensure throughput while ensuring tighter bounds. If that's the case, does that mean BFQ is a replacement for CFQ down the line?

BFQ started from CFQ, extending it in the way you correctly describe, so it is indeed very similar. There are also some minor changes to locking, cic handling, hw_tag detection and to the CIC_SEEKY heuristic.

The two schedulers share similar goals, and in my opinion BFQ can be considered, in the long term, a CFQ replacement; *but* before talking about replacing CFQ we have to consider that:

- it *needs* review and testing; we've done our best, but for sure

    it's not enough; review and testing are never enough;

- the service domain fairness, which was one of our objectives, requires some extra complexity; the mechanisms we used and the design choices we've made may not fit all the needs, or may not be as generic as the simpler CFQ's ones;
- CFQ has years of history behind and has been tuned for a wider variety of environments than the ones we've been able to test.

If time-based fairness is considered more robust and the loss of service-domain fairness is not a problem, then the two schedulers can be made even more similar.

From: Vivek Goyal <[email protected]>
Date: Thu, Nov 20, 2008 04:31:55PM -0500

Hi Fabio,

I though will give bfq a try. I get following when I put my current shell into a newly created cgroup and then try to do "ls".

Quoted 3 lines

From: Vivek Goyal <[email protected]>
Date: Thu, Nov 20, 2008 04:31:55PM -0500

...

Quoted 5 lines

Hi Fabio,

I though will give bfq a try. I get following when I put my current shell into a newly created cgroup and then try to do "ls".

The posted patch cannot work as it is, I'm sorry for that ugly bug. Do you still have problems with this one applied?

---

block/bfq-cgroup.c +0 -0

index efb03fc..ed8c597 100644

Quoted 3 lines

From: Vivek Goyal <[email protected]>
Date: Thu, Nov 20, 2008 04:31:55PM -0500

...

Quoted 5 lines

Hi Fabio,

I though will give bfq a try. I get following when I put my current shell into a newly created cgroup and then try to do "ls".

The posted patch cannot work as it is, I'm sorry for that ugly bug. Do you still have problems with this one applied?

---

block/bfq-cgroup.c +0 -0

index efb03fc..ed8c597 100644

Quoted 3 lines

From: Vivek Goyal <[email protected]>
Date: Thu, Nov 20, 2008 04:31:55PM -0500

...

Quoted 5 lines

Hi Fabio,

I though will give bfq a try. I get following when I put my current shell into a newly created cgroup and then try to do "ls".

The posted patch cannot work as it is, I'm sorry for that ugly bug. Do you still have problems with this one applied?

---

block/bfq-cgroup.c +0 -0

index efb03fc..ed8c597 100644

From: Vivek Goyal <[email protected]>
Date: Fri, Nov 21, 2008 09:58:23AM -0500

Quoted 20 lines · Fabio Checconi

Quoted 3 lines

From: Vivek Goyal <[email protected]>
Date: Thu, Nov 20, 2008 04:31:55PM -0500

...

Quoted 5 lines

Hi Fabio,

I though will give bfq a try. I get following when I put my current shell into a newly created cgroup and then try to do "ls".

The posted patch cannot work as it is, I'm sorry for that ugly bug. Do you still have problems with this one applied?

---

block/bfq-cgroup.c +0 -0

index efb03fc..ed8c597 100644
@@ -168,7 +168,7 @@ static void bfq_group_chain_link(struct bfq_data *bfqd, struct cgroup *cgroup,