Mark Wong recently posted a series of benchmark results that show how the Linux scheduler has improved since early on in the 2.5 development cycle. The results were generated with Rusty Russell’s Hackbench, a modified ‘chat benchmark’. Read the full story at KernelTrap.
Measuring Linux Scheduler Improvements
About The Author
Eugenia Loli
Ex-programmer, ex-editor in chief at OSNews.com, now a visual artist/filmmaker.
Follow me on Twitter @EugeniaLoli
All thats left to compare now is how well the 2.6 scheduler fairs against other Operating systems out there.
That would be totally interesting and infact beneficial to all parties concerned.
All in all the improvements seen between linux kernel versions looks to be too kool.
Im surprised this story hasnt generated any traffic.
Wierd!!
Because it’s too technical, most people around here don’t have a clue about kernel development, they can only bark loud, so they do it.
What effect it may have on various server apps. Does anybody have any info about this? (file server, etc)
Probably.
Personally, I only had problems with that new scheduler. I tried 2.6.0-test4 and 2.4.22 with ck patches (that includes that new scheduler) and it was much less responsive than the standard kernel with the famous preempt patch. Perhaps the throughput was better, but that’s not what really matters on a desktop system (IMO).
Wrawrat, I’ve had problems with it too. A lot of skipping in xmms when I load webpages in galeon. Running 2.6.0-test5. Not sure why I’m not seeing the improvements.
Would anybody know of a place to get all of Linux’s scheduling algorithms.
Please dont tell me to look at th source code. The only prog. Ive ever written is the Hello world prog. — :>)
It sure would be kool to look at the algo that driving it all though.
Im talking about the I/O scheduler, MM, … the lot.
Much appreciated.
See ya.
Actually I’m kinda interested in these cases:
linux-2.5.33 36.1 -34.0
linux-2.5.34 54.0 49.9
linux-2.5.36 17.2 -68.2
linux-2.5.44 34.5 100.6
<snip>
linux-2.5.53 36.9 0.8
linux-2.5.54 17.7 -52.0
I wonder what happened between .44 and .53 that pushed the timings back up to over 30 seconds.
I’m also curious as to whether or not it’s truly O(1). I’ve no doubt the actual task selection part of the scheduler is, since it’s just picking tasks from sorted lists. Thing that is confusing me is that some other code external to the task selection code is having to sort the task lists and I can’t see how that code can be O(1). Maybe I’m missing something, but I get the impression that a lot of the improvement is down to reducing the number of sorts taking place which probably increases complexity and reduces any self-righting capability (Simple example: You sort when X happens, but never considered sorting when Y happens, so Y becomes an aberrent case. If you sort all the time then that case disappears). It’s still a neat idea, guess I need to read some more and improve my understanding.
There is a good article (with graphs) of 2.6 vs 2.4 scheduler performance here…
http://linuxdevices.com/articles/AT7751365763.html
The improvements are impressive.
Nice article, but it raises more questions than it answers.
If their explanation of the scheduler is correct then it seriously looks like a round robin variant with variable timeslices and sorting after each iteration through the list (That sort is just not going to be O(1) and time to run it will be dependant on the number of processes in the list. Don’t believe me? Try creating an O(1) sort algorithm then). Since response time is the big thing people are going on about (And presumably why it’s felt to be so much better) there’s probably some for user-interactive applications to “jump” the queue. Get enough queue jumpers and some process languishing at the bottom of the current queue is going to have to wait an eternity to be scheduled because it has to wait for all the tasks above it to expend their timeslices (Or block).
Nobody seems to be answering the more interesting questions. Let’s say I have 4 or 5 movies running muted, a 3d game running in a window, XMMS playing an Ogg, an sshd session running a top on a remote computer, and I’m typing in an Open Office window while waving the mouse around the screen like a madman. Which application suffers first?
Or a different one. I’m logged into a server that’s got Apache serving a few 100 clients that uses scripting that itself uses a remote MySQL database. I login to update a few files via ssh. What gets priority? Since all of them are going to be using ports and tcp/ip exactly what gets priority and how can you tell? Being selfish I’d like it to be me so I can update whatever I need to and get out as quickly as possible.
I’m surprised they haven’t showed up yet. I’m glad to hear that the scheduler is *still* being worked on and is *still* improving. One question, at what point does an OS become a real time OS? I’ve heard about RTOS but I really don’t understand the concept. What are the criteria for RTOS, or real time OS?
Then why do you bother to call them?
Jeremy, did you noticed any jerkiness with your mouse while you load web sites with Galeon? I have that problem with Mozilla & O(1). Terminals under GNOME and KDE are also taking seconds to close. Seconds to _close_ a _terminal_!
Btw, do you have a nForce2 chipset? That’s what I have and I suspect some incompatibility with it.
Then why do you bother to call them?
Osnews isn’t fun without them
I am saying the word “nay!!!”
“One question, at what point does an OS become a real time OS?”
Roughly, a realtime OS is one that can guaruntee certain operations to be performance in a given time period. Usually, this has nothing to do with the responsiveness of the UI on the machine… if anything, responsiveness may suffer because the realtime guaruntee is probably restricted to a set of important processes. Usually this kind of stuff is very important in embedded computers or DSPs.
Roughly, a realtime OS is one that can guaruntee certain operations to be performance in a given time period.
->
Roughly, a realtime OS is one that can guaruntee certain operations to be performed in a given time period.
No preview and beer make Homer, “Go crazy?” OK ackackack….
@the guy who asked about documentation:
You might not understand most of the docs, because they concern data structures and algorithms that you probably haven’t studied if all you’ve done is hello world. But, they’re there:
New I/O scheduler: http://kerneltrap.org/node/view/843
MM documentation: http://linux-mm.org
Other stuff should be in text-files in the “Documentation” directory of the source tree.
@the guy who asked about the RTOS:
“Real Time OS” has a very specific meaning. In an RTOS, the application can tell the OS a deadline it has to meet. If the OS decides that the there is enough CPU available to meet the deadline, it can *guarantee* to the application that the deadline will be met. It can also make guarantees like that if an event (usually an interrupt from some critical hardware) happens, a handler will be run in no more than X milliseconds. RTOS has nothing to do with speed or scalability, it simply means that an OS has deterministic scheduling. Now, you often hear about soft-RTOSs. These are not real RTOSs in that they cannot guarantee deadlines. Instead, they have very low average response times, which means they’ll usually make the deadline, but sometimes might not. A soft-RTOS is usually okay for something like a media workstation, where a missed deadline is just a skipped frame or audio pop, but not something like a nuclear station monitor (excepting the new nuclear stations which are self-regulating
Wrawrat, i have the same weird problems with 2.6 (the jerkiness you’re talking about when using Mozilla, poor Nvaudio quality when using the ALSA driver…) and i own a motherboard with the nForce 2 chipset. I regret this purchase more and more, since the Linux support for it is crap.
I feel very enlightened. Thank you much. 🙂
Because it’s too technical, most people around here don’t have a clue about kernel development, they can only bark loud, so they do it.
No, I’d say that people who are interested in it, such as myself, would tend to hang out at kerneltrap anyway, even without a headline from osnews.com.
“One question, at what point does an OS become a real time OS? I’ve heard about RTOS but I really don’t understand the concept. What are the criteria for RTOS, or real time OS?”
Originally, “real time” meant that the computer could calculate a physical model as fast as it happens in real life. For example, calculate the trajectory of a shell in the time it takes for a real shell to travel.
This was achieved decades ago, for shells.
Nowadays, it means that the calculations and response for a computer that controls a physical process (factory automation, space craft navigation) are guaranteed to be completed within a defined time. Obviously the time chosen has to be short enough for the thing to be useful.
In the case of a computer that controls the sluice gates of a dam, a response time of several minutes would be fine, while a computer in a car braking system would be specified to a much shorter time.
So for some uses a C64 could run a real time control program, while for other uses you might need the fastest computer available today. The operating system will usually have to be designed specifically for control purposes – QNX is a well known example. It is not practical to use an OS that is liable to interrupt a control task to do hard drive houekeeping, for instance, as the task might take 2 seconds to complete one time and 30 seconds another time.
To all the guys above who are having nforce2 probs with the new kernel please note that it may be the fault of the drivers and not the kernel.
The problem used to be there for me too when I had used the 1.0261 ( the latest ) drivers.
What would happen was my comp. who function perfectly AS long as I didnt access the net card. Aytime I accessed the net card my comp. would kinda freeze and its the feeling u get when U havent turned DMA on.
So maybe U could try downgrading ur drivers to the 1.0256
Hopefully that will work for U guys.
See ya
P.S.– Hey Rayiner for the links. By the way the first eg. Rayiner mentioned above just preceeding the soft-RTOS is whats known as ( funnily enough ) a hard-RTOS.
Hey Rayiner ,
I meant thanx for the links
I’m not using any driver from nVidia as I don’t use the integrated stuff. I suppose I’ll fill a bug report if there’s not already one…