Slashdot Log In
Anticipatory Scheduler in Kernel 2.5+ Benchmarked
Posted by
timothy
on Wed Feb 26, 2003 06:22 PM
from the knew-you-were-going-to-say-that dept.
from the knew-you-were-going-to-say-that dept.
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."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Anticipatory (Score:4, Funny)
Re:Anticipatory (Score:5, Funny)
Parent
Re:Anticipatory (Score:5, Funny)
C'mon, try grounding your trolling in reality next time. Scheduling on OSX is handled by Mach [apple.com], which was developed at CMU by Avi Tevanian [apple.com], developed at NeXT and brought up to 3.0 at Apple.
Apple uses BSD for its UNIX compatibilty layer, but that doesn't handle scheduling, which is what this article is about.
Now, if you want to say Apple was dumb for chucking A/UX [faqs.org] in the early nineties, then that'd make a much better troll.
Parent
Ohh the agony... (Score:4, Funny)
Obvious joke... (Score:4, Funny)
unfotunately (Score:5, Funny)
The task in question was anticipating things, so the test might not be all that fair.
I've tried it and it rocks (Score:5, Interesting)
Switching to a new tabbed terminal in fluxbox it takes ages to redraw and switching between virtual desktops is an act of futility.
With 2.5 It get good interactive performance and don't see this effect much at all. For sure this is also a bit due to the new VM code.
Of course I would probably get the best interactivity with the SFQ scheduler but thats secondary in this case. At least xmms doesn't skip with this during very heavy I/O. I do not use the new NPTL code which would help further I suppose.
Re:I've tried it and it rocks (Score:4, Funny)
Fer sure.
Parent
Poin..... (Score:5, Funny)
I'm still anticipating the "t" in "point" myself...
Re:Poin..... (Score:5, Funny)
I think i need help...
Parent
Article text in case of /. effect: (Score:5, Funny)
Anti-slashdotting? (Score:5, Funny)
You know, you can ALMOST feel an admin over there just itching to type in "Fuck you Taco! And your site!" instead of the connection stuff...
Microsoft version: (Score:5, Funny)
Computer: I have anticipated you would like to open IE and have already opened it for you.
Me: Ok, then I would like to go to the game review site to see what I want to buy.
Computer: I have already begun the download of the new Age of Empires game, your account has been charged.
Me: Can I at least go to the bathroom?
Computer: No.
Re:Microsoft version: (Score:4, Funny)
Computer: I have already run auto update. all your warez are belong to us.
Parent
Re:Don't click that link (Score:5, Funny)
httpd: "Intensify the firewall, I don't want anything to get through."
iptables: "Httpd, look!"
httpd: "INTENSIFY THE FIREWALL!"
iptables: "Too late!"
Parent
It's about time... (Score:5, Funny)
Re:It's about time... (Score:5, Interesting)
If a site is down, Mozilla could pretty easily grab the google cache instead. Or, if there's no google cache or if the cache matches the current page, check archive.org. Mozilla could auto-generate a page offering the user some options. Think about it - it would be the end of 404 errors. Instead of
404 The requested page could not be found.
you could get
The site you requested is currently down. Would you like to use Google's cache [216.239.51.100] instead? I also have a snapshot of the page you requested from August 12, 2002 [archive.org] but older ones are available here [archive.org].
Parent
Re:It's about time... (Score:5, Insightful)
Parent
how it works (Score:5, Informative)
where it explains what anticipatory scheduling does.
(btw, it seems that freebsd had it for ages)
Rocky Horror Linux Show (Score:5, Funny)
Ok.. I'll bite... what's a Scheduler? (Score:4, Interesting)
Re:Ok.. I'll bite... what's a Scheduler? (Score:5, Informative)
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.
Parent
Re:Ok.. I'll bite... what's a Scheduler? (Score:5, Informative)
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
Parent
Disk I/O, not CPU schedulers (Score:5, Informative)
Re:Disk I/O, not CPU schedulers (Score:4, Funny)
Parent
Good stuff, but... (Score:5, Informative)
Check the mailing list for more info (Score:5, Informative)
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)
2.5 is the bomb so far, in so many ways.. (Score:5, Insightful)
When I first started hacking on Linux, I was working with a seasoned Linux kernel hacker who my company hired as a consultant. He helped us with some I/O issues and such, did some other tweaks and gave us a ton of inspiration to go get after it ourselves. (You be amazed at how many people are afraid to just start making changes to kernel code) He is a wickedly cool individual and as someone whose had a lot of schooling and experience it was one of the best learning experiences I can remember.
The first thing I started dorking with after that experience was the scheduler because I, like all other hakers, know how to schedule stuff. At the time, (early 2.x) the scheduler was also a fairly easy to digest piece of code that could have impacts on the system in great ways.
Well all my stuff got bit bucketed. I called up our consultant guy who my friend by now, "what's the deal? Linus doesn't like my stuff. How do you mail him stuff?" And his answer was that pretty much every body wants to tweak the scheduler, everybody sends stuff in. Linus is sage in his wisdom, schedulers are freaking hard because there is always a pedantic worst case that sucks and actually shows up in the real world. Linus has always done fairly simple things that aren't best but certainly aren't worst. So 2.0 had pretty straight round robin. 2.2 and 2.4 they started to add queuing schedulers with niceness. 2.5 we're going to get a pretty killer scheduler that has taken a ton of effort to tweak and there are still discussions to expose parameters to the user via /proc or something because you can find cases were it doesn't perform as well.
Now this IO scheduler is opening up a whole new can of worms, it's a new chunk of code called "scheduler" and all hackers know scheduling. In the past it has been fairly simple. It should be fun to watch and the kernel is going to kick mucho ass in the end. There will be a lot of talk and debate about this stuff. It's also distilled down to the trusted set that Linus will let play with things called "scheduler"
File I/O primitives (Score:4, Informative)
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.
Re:File I/O primitives (Score:4, Informative)
Parent
Re:Great! (Score:5, Funny)
* These chips are basically fucked by design, and getting this driver
* to work on every motherboard design that uses this screwed chip seems
* bloody well impossible. However, we're still trying.
Parent
Re:Great! (Score:5, Informative)
Parent
Re:Great! (Score:4, Interesting)
Although I _suspect_ they will run fine on 2.5, I don't want to risk it. It's still a little too bleeding edge for me. They call it bleeding edge for a reason, because you _will_ bleed and get hurt from time to time.
I guess I am a big fat ninny when it comes to bleeding edge stuff (although I do lust for all the new toys, the waiting just increases my contentness when such cool stuff gets part of stable stuff) :-)
Speaking of avoiding the bleeding edge, it would be sooo cool if this IO scheduler was backported to 2.4.
Parent
Re:It would be neat... (Score:4, Informative)
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.
Parent
Re:cache / copy / mirror of page is here (mod up!) (Score:5, Informative)
mirror of story to be found here [stuwo.net]
http://www.stuwo.net/download/ktrap.html
Parent
Re:Finally (Score:5, Interesting)
Nah, it handles certain start-up costs for complex applications better. This may or may not have anything to do with multithreading per se.
I don't run KDE, but I understand that it has had speed issues in the past because it uses a lot of interconnected C++ shared libraries, which really tax the dynamic loader. The Windows link scheme, by the way, is much more primitive (read: fast at runtime). Microsoft also uses a hack (disk layout profiling) to speed up load time further. (Not that "hack" is necessarily a bad thing - after all it does get the job done.)
A couple of years ago, Jakub Jelinek came up with a utility similar to IRIX Quickstart for ELF binaries / libraries, which does "prelinking" to dramatically reduce relocation overhead at runtime in the common cases (without sacrificing flexibility, for the uncommon cases). A side effect is reducing memory usage due to COW. I never heard what happened to that project - anyone know if it is considered production-quality yet, or if binutils / glibc will be shipping it any time soon? Apparently it helped KDE quite a bit.
Parent