Anticipatory Scheduler in Kernel 2.5+ Benchmarked

gmuslera points to this article at KernelTrap comparing available benchmarks for schedulers available for the 2.5 kernel, with the 2.4's scheduler as a reference poin. "In some cases, the new Anticipatory Scheduler performs several times better than the others, doing a task in a few seconds instead minutes like the others."

Comments

how it works

[diegocgteleline.es]

Given that kerneltrap has "Too many connections", i don't know if they have this link: http://www.cs.rice.edu/~ssiyer/r/antsched

where it explains what anticipatory scheduling does.


(btw, it seems that freebsd had it for ages)

Re:Ok.. I'll bite... what's a Scheduler?

[Caoch93]

In this case, they're talking about an I/O Scheduler, which is in charge of planning I/O through some resource so that activities on that resource correctly complete as quickly as possible. To be specific, this scheduler is for the hard disk I/O Scheduler, which plans reads and writes from/to your hard disks.

The Anticipatory Scheduler is designed to optimize your disk I/O based on the assumption that reads of related material tend to happen in short succession, while writes tend to be singular and larger. As a result, when the scheduler encounters a read, it anticipates that there will be other reads in short succession, so it waits and then checks for them and, if they're there, they move to the front of the line. The name comes from the tiny waiting period when it anticipates future reads.

This is, of course, a condensed version of what I think I've learned from reading KernelTrap for the last few months. Someone's bound to tell you I'm talking arse.

Good stuff, but...

[Corbet]

...of course, LWN readers knew about the anticipatory scheduler back in January. We also looked at the SFQ and CFQ I/O schedulers two weeks ago.

Check the mailing list for more info

[Miles]

If you're really curious, you can check out the mailing list for more info. Try searching for "IO scheduler benchmarking" or "iosched". To save the mailing lists, here's a few interesting benchmarks:

Parallel streaming reads:
Here we see how well the scheduler can cope with multiple processes reading
multiple large files. We read ten well laid out 100 megabyte files in
parallel (ten readers):

for i in $(seq 0 9)
do
time cat 100-meg-file-$i > /dev/null &
done

2.4.21-pre4:

0.00s user 0.18s system 2% cpu 6.115 total
0.02s user 0.22s system 1% cpu 14.312 total ...(up to)
0.01s user 0.16s system 0% cpu 37.007 total

2.5.61+hacks:

0.01s user 0.16s system 0% cpu 2:12.00 total
0.01s user 0.15s system 0% cpu 2:12.12 total ...(up to)
0.01s user 0.19s system 0% cpu 2:13.51 total

2.5.61+CFQ:

0.01s user 0.16s system 0% cpu 50.778 total
0.01s user 0.16s system 0% cpu 51.067 total ...(up to)
0.01s user 0.18s system 0% cpu 1:32.34 total

2.5.61+AS

0.01s user 0.17s system 0% cpu 27.995 total
0.01s user 0.18s system 0% cpu 30.550 total ...(up to)
0.01s user 0.16s system 0% cpu 34.832 total

streaming write and interactivity:
It peeves me that if a machine is writing heavily, it takes *ages* to get a
login prompt.

Here we start a large streaming write, wait for that to reach steady state
and then see how long it takes to pop up an xterm from the machine under
test with

time ssh testbox xterm -e true

there is quite a lot of variability here.

2.4.21-4: 62 seconds
2.5.61+hacks: 14 seconds
2.5.61+CFQ: 11 seconds
2.5.61+AS: 12 seconds

Streaming reads and interactivity:
Similarly, start a large streaming read on the test box and see how long it
then takes to pop up an x client running on that box with

time ssh testbox xterm -e true

2.4.21-4: 45 seconds
2.5.61+hacks: 5 seconds
2.5.61+CFQ: 8 seconds
2.5.61+AS: 9 seconds

copy many small files:
This test is very approximately the "busy web server" workload. We set up a
number of processes each of which are reading many small files from different
parts of the disk.

Set up six separate copies of the 2.4.19 kernel tree, and then run, in
parallel, six processes which are reading them:

for i in 1 2 3 4 5 6
do
time (find kernel-tree-$i -type f | xargs cat > /dev/null ) &
done

With this test we have six read requests in the queue all the time. It's
what the anticipatory scheduler was designed for.

2.4.21-pre4:
6m57.537s ...(up to)
6m57.916s

2.5.61+hacks:
3m40.188s ...(up to)
3m56.791s

2.5.61+CFQ:
5m15.932s ...(others)
5m50.602s

2.5.61+AS:
0m44.573s ...(up to)
0m53.087s

This was a little unfair to 2.4 because three of the trees were laid out by
the pre-Orlov ext2. So I reran the test with 2.4.21-pre4 when all six trees
were laid out by 2.5's Orlov allocator:

6m12.767s ...(up to)
6m13.085s

Not much difference there, although Orlov is worth a 4x speedup in this test
when there is only a single reader (or multiple readers + anticipatory
scheduler)

Re:cache / copy / mirror of page is here (mod up!)

[Anonymous Coward]

here is the clickable link

mirror of story to be found here

http://www.stuwo.net/download/ktrap.html

Re:Ok.. I'll bite... what's a Scheduler?

[RainbowSix]

Other forms of disk scheduling are a little more simple. Assume that the disk is really slow, and lots of requests are coming in that are buffered somewhere. Obviously you want to handle requests that are close to where the disk head currently is since it is faster and you won't have your head going all over the place.

FCFS (first come first serve) - easy stupid way. Take requests as they come. If you need front end front end, performance suffers because obviously you want to do front front end end.

SSTF (shortest seek time first) - do the request that is shortest to the head first. The problem with this is if you keep asking for stuff at the front of the disk and have a lone request for the end of the disk, the lone request could get ignored for a long time (starved) since the scheduler does the stuff at the front since seek times are much lower.

SCAN - the head starts at one end of the disk and goes to the end, servicing requests along the way, but never going back so that that lone request from the previous method does get serviced. When it gets to the end the head moves back toward the front, servicing requests along the way. It keeps going back and forth.

C-SCAN -Variant of SCAN where it doesn't go back and forth. It goes from front to back servicing requests then goes all the way back to the front before it starts servicing again. It gives more uniform times because if you're using SCAN and your request at the beginning is just missed by the head, you have to wait until it goes all the way to the other end and comes all the way back. In this method it goes to the end and then you're the next request to be serviced if you are at the beginning.

LOOK - The same as CSCAN and SCAN except it doesn't blindly go to the end of the disk; it stops and turns around when there aren't any more requests in the direction. Of course, if you show up right after the head changes direction, sucks to be you :)