Slashdot Mirror
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."
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)
The blurb didn't mention that the article is comparing disk schedulers, not CPU schedulers.
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.
...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.
Jonathan Corbet, LWN.net
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:
/dev/null &
...(up to)
...(up to)
...(up to)
...(up to)
/dev/null ) &
...(up to)
...(up to)
...(others)
...(up to)
...(up to)
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 >
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
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
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
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
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 >
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
6m57.916s
2.5.61+hacks:
3m40.188s
3m56.791s
2.5.61+CFQ:
5m15.932s
5m50.602s
2.5.61+AS:
0m44.573s
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
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)
GCC (and I assume others) can do this. Basically, you compile with -fprofile-arcs, run the executable enough to generate sufficient data, then compile with -fbranch-probabilities. This will try to order basic blocks so that the CPU predicts branches correctly most often.
I have never done it, but it is supposed to work. Unfortunately, it is pretty much limited to static analysis -- it doesn't allow for programs whose usage patterns change with time. For that you need some kind of dynamic recompilation, such as provided by HP's Dynamo, Transmeta's code morphing, or perhaps some Java JITs (I don't know if any of them implement this).
Personally, I think profile directed optimization done by a static compiler is a waste of time. All optimizations should be done at the best place, and for many optimizations, that is the static compiler, but many others can be better done by run time optimizers, or the CPU, and this is one of them.
I'm sorry to sound like an Trolling AC, but I can't imagine why you would need 80 threads. Unless you using threads instead of a queue. I love threads, but they are and over used and hard to control and debug. The most complex thread system I've needed had ~25 threads running on 5 computers.
It's far easier to maintain any multiplicity of state machines using threads rather than queues. Think of multi-user servers using stateful protocols. You might have hundreds or thousands of threads.
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
a valid copy and cache of the page is here to be found.
mod up:
http://www.stuwo.net/download/ktrap.html
The snippet you quote is from the cmd640 driver, which covers only the chipset by the same name. Subsequent CMD chips, including the 649, use the cmd64x driver and are not fucked.
Also, I doubt that one could alter the I/O scheduler (let alone install an alternative) in the win* operating systems.
The AS I/O scheduler is very very interesting. I hope some kind soul would backport it to 2.4.
No, they didn't. And it wasn't a cease-and-desist letter. All they said was, "Hi, I'm a google lawyer (TM). We like our trademark, which for obvious reasons you'll understand. Could you please indicate that google is a trademark in your definition, or, if it's easier, just remove it? Thanks.".
Unlike you, I'm not too lazy to type "google" into the Slashdot search box you probably see at the top-right of this page, click search, and click through to the article and from there the (NON-cease-and-desist) letter.
It reads, in full:
Now quit spreading FUD. I love Google.
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
--------
It's OK to be social, just don't tell anyone about it.
The problem is that such I/O layers need to be implemented at least partially outside user-space in the case where the file is being simultaneously accessed to allow interprocess coordination. Also, to get best use, everything should use it.
Actually Mach was developed at CMU under Rick Rashid. Tevanian was a graduate student of his. Most of the Mach team is at Microsoft Research, including Rashid (who heads up Microsoft Research). They tried to convince Tevanian to come there, but he decided instead to go to NeXT Computer, which also was based on the Mach microkernel. When Apple acquired NeXT, it took most of their OS and development philosophy also.
Are you sure that you are not seeing the improved desktop interactivity from the kernel premption and low latency patches in 2.5? I suspect that they would affect desktop interactivity more than this scheduler...
KDE has gained quite some speed with the last version changes. The gap is not as large as you remember.
Here is the explanation of what anticipatory scheduling is. From what I have understood (please correct me if I am wrong, I am not a kernel hacker), 'anticipatory scheduling' means the following:
The I/O subsystem (the part of the operating system that reads/writes to/from the hard disk) waits a little longer before servicing an I/O request from an application other than the current one; if the current application issues another I/O request while the I/O subsystem is waiting, the overall system throughput is higher because the hard disk's head moves less.