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."
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.
The task in question was anticipating things, so the test might not be all that fair.
"Probably the toughest time in anyone's life is when you have to murder a loved one because they're the devil." -Philips
I have a multithreaded perl app (yes perl has descent thread support in 5.6 and later) which does a lot of mixed write/read I/O to and from a database. With 2.4 and 40 threads I can hardly use the system (of course I dont have to abuse my computer with 80 threads but Im trying to prove a point here).
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.
I'm still anticipating the "t" in "point" myself...
--
http://www.aikiweb.com - AikiWeb Aikido Information
Too many connections
Things you think are in the Constitution, but are not.
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...
Hate me!
Me: Computer, I would like to open Netscape
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.
"Probably the toughest time in anyone's life is when you have to murder a loved one because they're the devil." -Philips
... the Mozilla developers added a special "Slashdotted" plugin you know. So you could launch a special tab that would keep hammering away at a site in the background until it did bloodywell load ;-)
Code, Hardware, stuff like that.
Quoeth the driver:
* 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.
Hilary Rosen's speech was about her love of money and her desire to roll around naked in a pile of money.
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 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)
I totally agree, but do find it sad that Apple spent all the time and effort only to find that creating an OS was beyond them, so they chucked it all out and went for Unix. And Unix had been there for them all along.
C'mon, try grounding your trolling in reality next time. Scheduling on OSX is handled by Mach, which was developed at CMU by Avi Tevanian, 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 in the early nineties, then that'd make a much better troll.
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
here is the clickable link
mirror of story to be found here
http://www.stuwo.net/download/ktrap.html
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"
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.
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.
"How can you claim that you are anti-crack, while still writing a window manager?" — Metacity README