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."
Somehow, I just *knew* this was coming. ;)
I watched C-beams glitter in the dark near the Tannhauser gate.
Now if only I could get 2.5 series to not b0rk when booting off my CMD649 ide controller...
--Kevin
The anticipation is killing me .
If only kerneltrap.org were running the new schedu... oh, never mind.
What has *science* done?!? -- Dr. Weird (ATHF)
Seems to be slashdotted already... Wonder if it saw that coming.
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.
It reminds of the old song and Heinz Ketchup commercial:
"Anticipation is making me wait"...
crazy how my brain just filled in the missing letter.
scary.
glad you pointed it out...i need to read more carefully.
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.
A task? I thought schedulers were for multitasking...
They're not using an IIS server are they? Naughty, naughty.
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
It's a trap! We've got to give this website more time. Concentrate all firepower on the next article below!
/ackbar
... 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.
damnit man, i told you to lay off the coke.
If some new scheduler would use fancy statistical methods to learn about your machine's usage patterns, and adapt its predictions to it.
Of course, and I highly suspect it, I may be talking out of my ass.
magic is obscurity
Now it just seems to be:
<html><body></body></html>
Things you think are in the Constitution, but are not.
Hehehehehe... your email address is funny:
Teeter....
Ass.... huhuhuhuhuhuhuhuhuhuhuh
Teeter and ass!
Couldn't find a google cache...poor kerneltrap. Thei Antispamist There 4 I am
not really...dups are pretty frequent...if there is less than two a day i feel violated.
it does take a sage to predict if it will be a same day dup...now thats talent
anyone wanna wager?
Would you mind if I used this in my sig?
Of course, and I highly suspect it, I may be talking out of my ass. -oqti
You know it's already been done. But if *you* had a plugin that meant you could load slashdotted pages when no one else could easily, and you knew it would only work as long as you didn't give it to other people, would you *really* give to everyone? Then no one would benefit, and the servers would stay hosed even longer...
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)
What does it do for kernel performance? Or does it do anything for performance? ...I haven't run Linux on a desktop for almost a year. It hurts mommy.. please make the bad man go away!
- Jimbob
doing a task in a few seconds instead minutes like the others
Excellent point the article! I'm glad I saw this Slashdot first. I can't wait the new kernel to be released.
Cool. Let's see a beowulf cluster of these in sovjet russia..
What the heck is a scheduler? What is it doing in a kernel, anyway?
The blurb didn't mention that the article is comparing disk schedulers, not CPU schedulers.
Too many connections
/.ed
I'd read the thing but it's been
I can't wait until 2.6 comes out. It's going to be fscking awesome.
No, .sigs don't show up for ACs.
I remember Ingo Molnar introducing this scheduler running in O(1) time months ago, sometimes late in 2002... AFAIK it is a part of the 2.5 kernel for quite a long time.. and at the time it was first tested there were some benchmarks.. I vaguely remember something about "we tried to launch several hundreds of processes, w.o. the scheduler: 15 minutes, w. the scheduler: 2 seconds." So what is so new about some benchmarks being available?
Or am I completely off-topic? ;)
the webserver is now OFFLINE completely. those poor swiss uunet foolz cant even take some decent slashdotting.
guess 's time to change the provider real soon now.
UUNET sure is bancrupt after this story i'd say.
...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
>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.
Why do you think it takes so long to startup and login, but IE loads so fast.
It should anticipate the slashdot effect and teleport 3 new servers into the room, and mirror the website onto them and install a load balencer.
Or maybe it should just say "There have been 2000 slashdot whores here in the last 10 seconds, I anticipate your one too, so LEAVE NOW!"
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)
a valid copy and cache of the page is here to be found.
mod up:
http://www.stuwo.net/download/ktrap.html
Is there a comparison, on the same hardware, under same conditions, of the same benchmarks applied on other systems, such as FreeBSD (4-STABLE as well as 5-CURRENT, they are different in many ways) and Windows (both 2k and XP)?
-- Sig down
Use something else!
the apache + php combination can not handle many connections easily.
You can put a proxy cache in front, which is an easy way to help on some sites.
here is a working mirror
mirror of kerneltrap article here
http://www.stuwo.net/download/ktrap.html
I know the free software community hates software patents. But how do you fight bad software patents?
In the business world, companies fight other people's dumb patents with their own dumb patents.
sortof. You can download this plugin for Phoenix,
:( Use sparingly...
tabbed browsing extensions (and I'm there's probably one for mozilla too) that has an auto-reload feature. You can have phoenix reload a page every few seconds or minutes.
As a warning, I set it to reload slashdot every 60 seconds at work and left it on over the weekend only to come back to work banned
What's wrong with simply reading ahead? The amount extra to read could be tweaked per thread based on previous behaviour, so that threads reading large files sequentially would quickly establish large readaheads, while threads making random access would establish low read aheads. And no need to sit around idly waiting for requests...
... but that was 15 minutes ago.
After upgrading from RH 7.2 to RH 7.3 w/ 2.4.18 I noticed X hangs for literally several seconds (possibly 5 seconds) if anacron kicks off some significant disk activity like when updating the slocate database. Anyone know if this is a known problem?
Sigs are dynamic until the story is archived.
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"
I'm currently enrolled in cs 162 (OSs) at UC Berkeley, todays lecture was on different flavors of schedulers and this scheduler was mentioned breifly. For more theoretical info see http://webcast.berkeley.edu/courses/archive.html?p rog=116&group=52 for a webcast of the lecture or http://inst.eecs.berkeley.edu/~cs162/Lectures/L11. pdf for a pdf of the lecutre notes.
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.
Despite what you slashdot monkeys may think (half of you have probably never ran Linux), Linux is incredibly slow when compared to Windows. Windows simply handles multithreading better. Mozilla takes 2x as long to open in linux and if I try to open multiple apps at once, it takes minutes for any of them to come up. And you can tell the I/O is crap just by looking at KDE's performance when compared to Win2k. Windows just flies. Part of this of course is that my version of Linux (Debian) can be recompiled to run on many platforms and everyone can tell you that portability comes at the cost of platform-specific performance. But still the i/o and multithreading in linux sucks. But then again, I didn't pay for it.
No, this is different. Ingo's O(1) scheduler is Linux's process scheduler, what determines when different processes get to use the CPU. The anticipatory scheduler is Nick Piggins' baby; it's an I/O scheduler, which decides when processes get to read to and write from devices.
Part of the idea is: prefer reads to writes, and assume that if you read once, more reads will follow (usually true), so wait for the next read(s) to come in and service them all at once; often, subsequent reads are to contiguous locations on disk, so if you just service them all at once you don't have to seek back if you service one, then go do something else, then get the next read.
We have something that any commercial OS had right from the get go. How exciting. Now how about fixing a little thing I like to call CaSe SEnSiTIvitY.
This is where the full text of the aticle would be, as I finally was able to see it. But alas, Slashdot's stupid fucking lameness filter won't let me add it.
When I was browsing at -1 to make sure I wasn't the 57th person to add the article text, I noticed some lovely ASCII depicting a gay man's ass though, that, accoring to the lameness filter, is LESS lame than this article. Perhaps the troll-moron that posted it should submit it as a story to slashdot.
Sorry 'bout your uid, man.
That's just great. If this is gonna be anything like the db benchmarking boom a year ago in lkml for the new vm which resulted some increase in db benches and fscked up the interactivity completely (by being a really happy page thrower), we're looking for a real nice desktop scheduler... :)
Seriously though, Morton's a great chap and one of the few that has really worked for also a desktopwise usable kernel (low latency patches, lock breaking patches, and the list would go on forever).
I can barely wait for 61-AS to compile...
1 Earth is warming, 2 It's us, 3 it's royally bad, 4 we need to take action NOW
The article mentions multiple simultaneous writes and reads... Doing two tasks at once in much more expensive than doing them sequentially.
.5 second to get a login screen.
Why not use the download manager programs... for all file transfering?
My priorities:
1. user interface responds effectively in realtime.
2. CD writes don't fail
3. Video doesn't skip
4. files transfer quickly.
I would actually like the ability to switch the mode of the file schedualer.
If I am not doing 2. or 3. then why not switch to something that makes 4 happen?
I saw something rediculous, like a 10 second wait for a login prompt??!?!
The system should have that all ready ahead of time, and it should take no more than
--I don't care about spelling enough to spend the vast quantity of time to get this to the spell checker.
Please use [ informative / summarizing ] SUBJECT LINES
Flame me here
When I copy two things at once, that is because I don't want to be arround the computer to select the next file.
I rarely care when it does it, I just don't want to be there.
Some times I want to move a file to make room for another file that I have to get.
If I could tell the computer to start downloading as soon as the move is done, I'd walk away from the computer and go exercise or something. (I'm thinking p2p, full HD, I could probably already do this with shell scripting)
I spend WAY too much time sitting in front of the computer watching status bars slowly lengthen, then shorten...
Please use [ informative / summarizing ] SUBJECT LINES
Flame me here
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.
I can't wait for the anticipatory scheduler to be used in a stable kernel release... I'm really looking forward to it.
-- Ed Avis ed@membled.com
It's called profile guided optimisation. Most decent compilers support it these days.
Heinz Ketchup has a squeeze bottle on the market now. Don't know if they still have the glass. If so, they'll probably be phasing it out.
Even Ketchup has the need for speed!
Will be adding a gearshift to a Linux box soon, ie a control that allows us to switch the machine from Web Server to DVD machine to interactive development station ?
The difference between waiting 60 seconds and 15 seconds for a login prompt MATTERS !
Methinks we need new benchmarks that take interactivity into account explicitly, or things will never improve.
This is not a signature.
...the article is utterly unreadable. Just a plain text dumb. Come on people, is it that hard to plot a few datapoints in a graph?
I want to know what it was like meeting Princess Diana!
Diana: Her True Story in Her Own Words by Andrew Morton
I'd really like on to enable this feature. surely it can be done..? Or is this patch compatible with the 2.4.20 series kernel?
The static copy of the story dosen't indicate if the I/O scheduler blocks on all filesystems, or separately on each one? Ie if I have a read on filesystem A, would another write on filesystem B be affected?
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...
It's a HYDROSPANNER. Your innacurate Star Wars references make me laugh.
--
"Outlook not so good." That magic 8-ball knows everything! I'll ask about Exchange Server next.
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.
You don't know what you are talking about. I've run plenty of Linux and M$ configurations, and every time Linux has been faster. My 500Mhz K6-2 Linux system takes less than 30 seconds to boot, including the 10-15 seconds the BIOS takes.
Yeah whatever. Linux handles forking many times better.
What are you comparing against? Mozilla on Linux vs IE on Windows? You do realize MS preloads the IE binaries on boot? If it's Mozilla on each platform, I'd want to know why it takes longer. Does your binary have GNOME/KDE dependencies? The developers may also have put in MS Windows specific stuff--Netscape's primary focus was and is MS Windows for the most part, and their developers suck--which is why Mozilla/Netscape Navigator are so bloated and crappy in the first place.
The reason it takes so long to start up because it is a bloated piece of crap, and the other apps who take minutes to come up must be bloated too. (you mentioned KDE, it is not essential, and it is very bloated. It also requires a daemon called DCOP, which probably accounts for half the startup time.) This is why your "linux" apps take a long time to start.
I don't run KDE or GNOME. Most of my programs don't take more than 5 seconds to load, and start instantly if their files are already in my cache. The only two that don't are GIMP and Mozilla. The GIMP takes less than 15 seconds, and only so because it has tonnes of plugins to load. Mozilla is bloated like I said.
Yes, KDE's performance. Not the performance of Linux. Not XFree86's performance. KDE's performance. You do not need KDE or GNOME to run a Linux workstation. I don't get why people do this.
A bogus statement. If you have a good compiler[1] and use optimizing flags, then cross-"platform"[2] programs don't have a significant performance hit, and not any more than MS's designs. There are some types of applications where assembly language (meaning processor specific instructions) will make the program perform better, but if you look closely, many of the open source projects which will benefit from this already do it--for at least the IA32 (80386+) processors, if not others.
[1] gcc 2.95.3 is good enough for me, but I hear Intel's Linux compiler works even better for processors made by Intel. The assumption where cross platform applications don't perform well is FUD spread by Microsoft.
[2] Here I think you mean different processor designs, but it can apply to different operating systems too.
Go on... With or without credit, I don't really care. :)
Heh
magic is obscurity
Why not do a script that karma-whores the web page to slashdot the second the site gets slashdotted. Auto karma!
Actually, I think several people already have such a script.