"The Linux kernel continues to evolve, incorporating new technologies and gaining in reliability, scalability, and performance. One of the most important features of the 2.6 kernel is a scheduler implemented by Ingo Molnar. This scheduler is dynamic, supports load-balancing, and operates in constant time -- O(1). This article explores these attributes of the Linux 2.6 scheduler, and more."
To view parent comment, click here.
To read all comments associated with this story, please click here.
Member since:2005-07-06
Actually it's been around since the 60s.
Which scheduler I was referring to should be obvious based on the title of the article..
In this instance it does. The O(1) scheduler is a perfect example of the way Linux developers come at problems without prior knowledge.
Of course they don't approach it prior knowledge. This is the first system they've built. It's not like they've got a bunch of kernels under their belt. On the other hand, code complexity is also an issue. For most tasks Linux was used for in the 1990s, an O(1) scheduler wouldn't be appreciably faster, and would've increased complexity a lot.
The so called O(n) scheduler was a poor choice for any process scheduler, which is why you don't find it in commercial systems more recent than, oh, 1965.
And all those systems running with the 4.4BSD scheduler don't count as "commercial"?
This is a good example of why after more a decade of development with more than six thousand people involved the Linux kernel is barely equal to systems that are twenty years older, but with a lot fewer development hours:
That's not really a fair characterization. Yes, there are thousands of people involved with Linux, but the core team doesn't contain nearly that many people. Also, many of those people aren't full-time paid employees.
Oh, and Linux is about an order of magnitude bigger in scope than any of the older systems you're talking about. All those people working on Linux are working on different pieces. There's people doing drivers for all sorts of systems, people working on optimizing it for desktops, servers, supercomputers, PDAs, and embedded applications.
Solaris, IRIX, AIX, all are pretty much only good for servers. Load up Nextenta on an x86 box sometime. It's interactive scheduling performance is at the level of Linux 2.4...
too little learning from the past, too much 'fix it when it breaks.'
Another way to see it is "don't fix what isn't broken". Or "don't fix it until you need to." Or the classical, "premature optimization is the root of all evil."
Member since:2006-02-15
"Actually it's been around since the 60s."
Which scheduler I was referring to should be obvious based on the title of the article..
Yes. It's Ingo's "O(1)" scheduler, which is identical to one I first saw described in DEC documentation for RSX11 back in 73.
Of course they don't approach it prior knowledge. This is the first system they've built. It's not like they've got a bunch of kernels under their belt.
What's wrong with reading and understanding the literature before you start reinventing the wheel?
And all those systems running with the 4.4BSD scheduler don't count as "commercial"?
4.4BSD did not use an O(n) scheduler. It used an O(C) scheduler, where C was then number of priority queues. Since C is constant at compile time, it was actualy an O(1) scheduler in Ingo's sense.
That's not really a fair characterization. Yes, there are thousands of people involved with Linux, but the core team doesn't contain nearly that many people. Also, many of those people aren't full-time paid employees.
There is no "core team." There are more than 1000 people paid full time to work on the Linux kernel. Check the professional attendence at OLS.
Or the classical, "premature optimization is the root of all evil."
Sigh. Selecting a constant time algorithm over an O(n) algorithm when the constant time algorithm is more than 20 years old and no more complex to implement is not "premature optimization".
And waiting 10 years to get around to fixing the O(n) algorithm is no less than 'fix it when it breaks.' And anyone who has seriously followed LKML for the last 6 years knows that 'wait until it breaks' is the first rule of Linux kernel developers, the second, apparently, being 'ignore the past'.
(By the way, I found IRIX worked very well on my SGI workstation back when I had one. You do realize that SGI was a workstation company before they got into servers, right?)
Member since:
2006-02-15
First, the O(1) scheduler is not new. The basic design was created in 2002. It'll be around in the next kernel version.
Actually it's been around since the 60s.
Second, the fact that its a huge improvement on the 2.4 scheduler does not imply the previous one was crappy.
In this instance it does. The O(1) scheduler is a perfect example of the way Linux developers come at problems without prior knowledge. The so called O(n) scheduler was a poor choice for any process scheduler, which is why you don't find it in commercial systems more recent than, oh, 1965.
This is a good example of why after more a decade of development with more than six thousand people involved the Linux kernel is barely equal to systems that are twenty years older, but with a lot fewer development hours: too little learning from the past, too much 'fix it when it breaks.'