simple deadline I/O scheduler

Against 2.5.2-pre7

Quoted 1 line · Jens Axboe

Against 2.5.2-pre7

There was a stupid bug in the last version (last minute change...) which caused a non-expired write to preempt an expired read, not optimal :-). Here's a fixed version.

I've played around with implementing an I/O scheduler that _tries_ to start request within a given time limit. Note that it makes no guarentees of any sort, it's simply a "how does this work in real life" sort of thing. It's main use is actually to properly extend the i/o scheduler / elevator api to be able to implement more advanced schedulers (eg cello).

Would it be possible to introduce concept of I/O priority? I.e. I want updatedb not to load disk if I need it for something else?

Quoted 2 lines

Would it be possible to introduce concept of I/O priority? I.e. I want updatedb not to load disk if I need it for something else?

makes sense to me. actually, VM is another place where priority could be quite useful - for instance, how hard the VM scavenges a proc's pages. oops, there I go advocating a tunable...

VM_SWAP_ME_HARDER anyone?

Hi!

Quoted 6 lines

I've played around with implementing an I/O scheduler that _tries_ to start request within a given time limit. Note that it makes no guarentees of any sort, it's simply a "how does this work in real life" sort of thing. It's main use is actually to properly extend the i/o scheduler / elevator api to be able to implement more advanced schedulers (eg cello).

Would it be possible to introduce concept of I/O priority? I.e. I want updatedb not to load disk if I need it for something else?

I've played around with implementing an I/O scheduler that _tries_ to start request within a given time limit. Note that it makes no guarentees of any sort, it's simply a "how does this work in real life" sort of thing. It's main use is actually to properly extend the i/o scheduler / elevator api to be able to implement more advanced schedulers (eg cello).

The construction of this new i/o scheduler is similar to how cello is build -- you have several "low level" schedulers and a class independent one on top of those that decides which one to start processing.

Each request is sorted into two lists -- one is purely sector sorted, the other is sorted [1] by expire time. We always serve request from the sector sorted list, until one of the front requests on the expire list has its deadline violated. Then we start following the sorted list from the point of the deadline violated request. This is always done in batches of eg 8 or 16 requests, to avoid seeking like mad if we can't keep up with the deadlines.

Quoted 11 lines · Jens Axboe

I've played around with implementing an I/O scheduler that _tries_ to start request within a given time limit. Note that it makes no guarentees of any sort, it's simply a "how does this work in real life" sort of thing. It's main use is actually to properly extend the i/o scheduler / elevator api to be able to implement more advanced schedulers (eg cello).

The construction of this new i/o scheduler is similar to how cello is build -- you have several "low level" schedulers and a class independent one on top of those that decides which one to start processing.

Quoted 7 lines

Each request is sorted into two lists -- one is purely sector sorted, the other is sorted [1] by expire time. We always serve request from the sector sorted list, until one of the front requests on the expire list has its deadline violated. Then we start following the sorted list from the point of the deadline violated request. This is always done in batches of eg 8 or 16 requests, to avoid seeking like mad if we can't keep up with the deadlines.

This post never seemed to get the attention it deserves. Do you have performance measurements now?

As part of my experimental hack to get rid of buffer_heads I was casting around for a structure to replace the dirty buffer list. I find myself heading towards the conclusion I want a structure that's remarkably similar to what you've cooked up here, but that lives at a higher level in the system. The idea is that a page goes into the queue as soon as it's dirtied and the elevator takes care of scheduling and merging from there. Admittedly these ideas are half-formed at the moment, but what I see developing is a situation where we have attempts at IO scheduling going on at two levels in the system, the VM and bio, and the more I think about it the less sense it makes. It's trying to be one subsystem.

Andrew Morton is also working in here, with a collection of ideas that I hope are complementary if looked at the right way. See his '[patch] delayed disk block allocation' post.

Quoted 3 lines · Daniel Phillips

Andrew Morton is also working in here, with a collection of ideas that I hope are complementary if looked at the right way. See his '[patch] delayed disk block allocation' post.

Right, I noticed. We could get good write clustering in general with vm merging, though.

Quoted 7 lines · Jens Axboe

Quoted 3 lines · Daniel Phillips

Andrew Morton is also working in here, with a collection of ideas that I hope are complementary if looked at the right way. See his '[patch] delayed disk block allocation' post.

Right, I noticed. We could get good write clustering in general with vm merging, though.

Sorry, I can't parse that, do you mean 'if the elevator merging is merged with vm's' or 'if vm does merging' or... ?