Slashdot Mirror
ArsTechnica Explains O(1) Scheduler
geogeek writes "The recent release of Linux's 2.6 kernel introduces a number sweeping improvements. These can be hard to understand without a background in programming. This week's Linux.ars examines the improved scheduler for an enthusiast audience, concisely explaining its nuances and the practical effects of an O(1) design."
I read this piece yesterday, and while it did "dumb down" the basics (as the first poster noted), I thought it did a very good job of putting it all into a nutshell that those of us not as familiar with Big-O and schedulers in general might easily understand. For Linux.Ars' format, I thought it was of appropriate length, and had enough detail to "belong." I'm sure there are more detailed writeups on the O(1) scheduler in place in 2.6. Does anyone have any links?
"Aye, and if my grandmother had wheels, she'd be a wagon!" -- Montgomery Scott, ST:III
With all the recent talk about multi core processors, will this sort of thing be relegated to hardware; or will there still be a need for software scheduler?
I setup a small computer today with 2.6. It boots from an initrd but I noticed during bootup the kernel will pause for a few seconds with:
checking if image is initramfs...it isn't (no cpio magic); looks like an initrd
I couldn't google much info on it. Anybody know more about it? Or how I can stop the kernel checking for it.
...can be found here (PDF file).
Most of the article was just about scheduling definitions - the states of a process, what preemption is etc... What a waste of reading.
I clicked on this article expecting to see an explanation of how it was that the O(1) scheduler worked, and by what tricks it was able to schedule in O(1) rather than having to spend extra time as extra processes are added, and what the real-life effects of such a situation are.
Instead the article was just "This is what O(1) is. This is what a scheduler is. This is what "preemptive" means. The 2.6 SMP can load-balance effectively across many processors. I used this really cool mp3 player this week." and just about nothing else.
Anyone want to explain exactly how it is that an O(1) scheduler is a difficult thing, and how exactly linux 2.6 achieves it?
-- Super Ugly Ultraman
While Ars definately isn't targeted at the same audience as, say, KernelTrap, its nice to see there are a few technology websites/publications that aren't dumbed down. I remember when Byte magazine used to publish articles detailing the PowerPC architecture, down to the level of registers and the types of pipelines in the first set of implementations. Compare this to the ZD rags, which are a hair away from calling the CPU the "brain" of the computer!
A deep unwavering belief is a sure sign you're missing something...
The AMD64 architecture is very, very bad because the long mode PAGE TRANSLATION MULTILEVEL (4 LEVELS) is an ASSHOLE versus legacy mode PAGE TRANSLATION BILEVEL (2 LEVELS) of the chips 32 bits.
open4free
- Lean and mean (low overhead).
- Scales well with the number of tasks (O(1)).
- Scales well with the number of processors (O(1) for scheduling, O(N) for balancing).
- Strong affinity avoids tasks bouncing needlessly between CPUs.
- Initial affinity makes it likely that request/response-type tasks stay on the same CPU (i.e., good for LMbench lat_udp et al)
BTW, It's good to see that the starvation and affinity problems that plagued the early versions of the O(1) scheduler have been ironed out.see subject!
That was kinda interesting though it doesn't really explain how they achieve the O(1)ness, and for example how did kernel 2.4 fare in comparison. Anyway, an O(1) scheduler is nice and all under low to moderate loads, but at high loads, when a lot of threads are running, the O(1) behaviour should enusre that the tasks are switching extremely fast, and as every context switch has some related overhead in terms of saving the context etc., that means that performance of the O(1) schedular should be worse than that of 2.4(where tasks are not switching as fast) in theory atleast. So is this really true?
What's under yellowstone?
Redundant? Where was the first comment mentioning this?
My first experience with Linux a few years ago was rather awkward when I had to learn how to prune Redhat 5.2 enough so that my 486 worked decently as a GUI desktop. Granted, the latest Linux still runs better than the latest Redmond has to offer on the the same hardware. I still think in order for Linux to gain more legitimacy, we need to defeat some of our own FUD. Some Linux evangelists I've met have made outrageously vague and ambiguous remarks regarding the speed and efficiency of Linux that make no sense when applied to a modern multimedia PC. It wouldn't be supprising if there are Linux novices out there who have been told of the extreme efficiency of the Linux kernel and are trying to run the latest kernel on obsolete hardware. I knew nothing of linux when I first started out, but I had a geek background and I was stubborn. Most folks weaned on Microsoft may not be as persistant. If you are just starting out with Linux as I was a few years ago, how do you make the appropriate hardware decisions? Does all this new kernel stuff matter to you? If so, why? How do you know it's important?
Stay sentient. Don't drink bad milk.
introduces a number sweeping improvements
:-)
Looks as if someone forgot a certain important preposition
Isn't that what a sidebar is for?
Couldn't they have linked out into more in depth treatments, and saved the complexity for the interested (technically) reader while saving 'readability' for the non-technical ppl?
mefus
In Open Society, GPL Software frees YOU!
O(1) doesn't mean the time is constant, but that in the limit it is bounded by a constant. It can get enourmous, then shrink for large inputs. It could go to 0 in fact.
Don't post anything about problems with Linux.. you'll get modded down for making Linux look back, and we can't have any of that
Scheme page-16KiB translation tri-level
Each page-16KiB contains 2Ki-entries
The virtual memory of the processes can address upto 2Ki*2Ki*2Ki 16KiB-pages = 8Gi 16KiB-pages = 128 TiB (huge space for many big applications).
open4free
Thanks; that third paragraph alone was much, much more informative than the linked article. Perhaps, if the editors can be bothered to edit a bit more (unlikely), could Ars provide links to these more technical articles?
Nowhere. The moderators are just stupid.
Use a Mozilla with the Adblock-plugin
While O(1) certainly might sound impressive to someone who's taken a first semester computer science course in university, anyone beyond that would obviously realize you've got to worry about the average case analysis.
To achieve O(1) you usually have to do some tricks that will get you quite a large constant. With an appropriately small number of processes, which I assume is the case with most computers, even an O(n^n) scheduler could be faster if the constant is very, very small.
Have any sites done an average case analysis to show at what point the O(1) scheduler is faster than the old 2.4 kernel? Certainly it isn't always faster or else the old one really did suck.
Well, only if you want to run only as many threads as you have CPUs. The windows machine I'm using right now has 37 processes, some I'm sure with multiple threads.
Did a quick check here, 54 processes, 461 threads. Something tells me I won't see a computer with 4-500 CPU cores in my desktop, ever. Not to mention that if you did, I'd want some to be more important. I'm sure many of those threads are just sitting there waiting for input, e.g. GUI threads...
Kjella
Live today, because you never know what tomorrow brings
That was extremely informative; thank you for posting it.
-- Super Ugly Ultraman
Plan9.
Timeslices are used in order to implement preemption: a process stops either when it blocks (waiting for I/O) or otherwise voluntarily gives up the rest of its timeslice, or when it's timeslice is used up.
About the article in general: I'm surprised about the dumbing down. Other articles on Ars, including but not limited to the series about processor technologies (e.g. the one about hyperthreading) are much more thorough and detailed.
This sig under construction. Please check back later.
# Important Stuff: Please try to keep posts on topic.
# Try to reply to other people's comments instead of starting new threads.
# Read other people's messages before posting your own to avoid simply duplicating what has already been said.
# Use a clear subject that describes what your message is about.
# Offtopic, Inflammatory, Inappropriate, Illegal, or Offensive comments might be moderated. (You can read everything, even moderated posts, by
adjusting your threshold on the User Preferences Page)
See lovely pictures of Compaq and HP executives here
lynx?
www.usenix.org/publications/library/proceedings/a
When it comes time to select a process, the scheduler finds the highest priority level containing available processes. It then selects a process from the desired priority level. Because the number of priority levels is fixed, the scheduler always takes a constant amount of time.
Yes, but it does need to inspect all the processes within a priority level, right??
As the total number of processes grows, the average number of processes within a priority level also grows, and so does scheduling time. So it's not O(1).
Unless choosing a process from a priority level is also constant time -- say, if it were a round-robin queue.
What am I missing?
http://www.squarefree.com/userstyles/xbl.html has some info on setting this up in Mozilla. The nice thing about this method is that you'll actually get a clickable button. The flash animation doesn't show up until you click it.
:)
Or you can go to http://www.squarefree.com/bookmarklets/zap.html where you can find bookmarklets that clean up a page after it's loaded. Very handy
Take life easy: one bit at a time.
Is it a better algorithm implementing the same scheduling scheme or has the scheme changed??
I mean a O(1) scheduler is extremely easy if you are satisfied with a round robin scheduler: Which would be O(1) for a sensible choice of queue.
easy, dont install that crap
It gets even better: Do you know what the highest rank in the German navy is? It's called "Grossadmiral". I think thats pretty gross!
Yes, but it does need to inspect all the processes within a priority level, right??
The analysis in the thread above reveals that this needn't be the case: assuming that find_first_bit() takes O(1) time, that makes the search time only as large as the number of priority levels; presumably, that number is also constant. When the article says "selects a process," I believe it ought to mean, "selects the first eligible process in that priority level"--given either a bitmap or a priority queue, that operation takes O(1) time.
Mod me down, but keep the parent post either offtopic, redundant, overrated, or whatever. It's not flamebait , read the fscking moderator guidelines. Djees, stupid mods.
If you were say, something other than a reactionist troll, you might have realized a couple of things:
Big-O notation is not intuitive.
Linux.ars is a generalized Linux publication.
Because Big-0 notation is unintuitive, and indeed because the function of a scheduler is not known to most, Ars made an effort to explain it. If you already knew the information it provided, good for you! At least you have intelligence in some areas of your existence.
Because Linux.ars is a generalized publication, they also review software and other such tidbits relating to linux. I suggest following it week to week-- its an enjoyable and informative read.
Mainframe schedulers have been O(1) for a long time. The one for UNIVAC 1108 EXEC 8 was O(1) in 1967. (And you can still buy a Unisys ClearPath server with that code in it.)
The traditional implementation is a set of FIFO queues, one for each priority. For systems with only a few priorities, that's just fine. As the number of different priorities increases, you spend too much time checking the empty queues, so there are tree-like structures to get around that problem.
Scheduling today is more complex because of cache issues. If you context-switch too much, you thrash in the CPU caches. On the other hand, everybody has so much memory today that paging is mostly unnecessary.
Please stop posting SCO code here, it only gets Darl all excited.
Personally, I didn't feel it said much until you got here:
"The scheduler keeps track of all these timeslices with two lists of processes. The first list contains processes that have yet to use their timeslice; the second contains those processes which have used their time. When a process uses its timeslice, the scheduler calculates a new timeslice (...). The process then gets inserted in the second list. When the first list becomes empty, the second list takes the place of the first, and vice-versa."
That's it, basicly... They move the processes from one list (unused) to another (spent), and when empty reverse direction and role. They calculate the new timeslice every time a process is moved, so each task change is in constant time, O(1).
Of course, that doesn't really explain why that's a really good idea. To do that, you'd have to compare it to other ways of doing it, which would get rather involved, and rather technical quite quickly. For one, Linux has been doing it by calculating all the timeslices at once (i.e. the "unused" list), executing the tasks in that list and starting over. Which is O(n), since the task of calculating all the timeslices was increasing with n.
Another thing is the speed of inserting and deleting processes. Which is very simple in the O(1) scheduler - you simply append it to the unused list, or delete it (when it's processed? at a flip? dunno). As opposed to having some kind of list where you'd get "holes" from removals, the constant flow back and forth "closes" any such holes.
It might sound fairly simple, but it's far from trivial making it actually work well. It may be O(1), which is nice for scaling, but it still needs to make a smart schedule. For one, how can it "adapt" to say, many other high-priority processes running, and still being O(1)?
It can't simply assume that just because it has a high priority, award itself a huge timeslice. There may be many of them, or higher prioritated tasks, it's all relative. But if you loop through the process list to check, you have a O(n) algorithm again.
So, there's actually quite a bit of work behind it, which is also why it's first here now in 2.6. If it was that easy, I think someone would have thought of it sooner...
Kjella
Live today, because you never know what tomorrow brings
When a process uses its timeslice, the scheduler calculates a new timeslice by adding the dynamic priority bonus to the static priority. The process then gets inserted in the second list. When the first list becomes empty, the second list takes the place of the first, and vice-versa. This allows the scheduler to continuously calculate timeslices with minimal computational overhead.
Sounds like the rules to an AD&D adventure.
Thanks for the link. How anybody can read an article with a flashing/animated ad is beyond me.
Don't forget, Christmas is coming, and I check my list twice!
Would tell you enough to understand how it works. We already knew what O(1) means.
The mechanism for recalculation of timeslices in previous Linux kernel's was very simple. When every process had its timeslice completely depleted (they were all 0) the kernel would simply go through every process and recalculate its timeslice and start execution again at the highest priority runnable process. While this is the most obvious solution it is also very inefficient, executing in O(n) time.
Ok, its easy to see why this is O(n).
The 2.6 scheduler uses a simple yet effective method for getting rid of this problem, it uses two priority arrays! One priority array is for processes that are runnable, and one priority array is for processes that are not runnable (they have depleted their timeslice). This way if when a process has depleted its timeslice the scheduler simply recalculates its timeslice, removes it from the active array, and inserts it into the expired array.
How is this not O(n)? The time slice calculation still occurs for each process, just not all at once for all processes. Each process still gets its time slice calcuated, it is removed from one queue, and inserted into another. Is there some other unmentioned trick that eliminates the calculations? Or was there something else that made the 2.4 scheduler O(n), such as finding the highest priority process?
So when all processes have depleted their timeslices there is no need to recalculate timeslices for every process, the two arrays are just switched (for the code oriented among us: they are accessed via pointers and the pointers are simply switched).
So the calculation is done per process as they finish their time slice, rather then at the end when all the processes are done. I still don't see why this would imply better efficiency. Am I missing something?
At any rate, thanks for the link, it was much more informative than the published article.
...I don't think I've ever seen an algorithm where O(1) didn't imply that the time was constant. They concentrated on the important part, O(1) vs O(f(n)). Ok maybe you can construct a formula that is O(1) and non-constant, but it's not very relevant to this article or even computing time algorithms in general.
Personally, I'd think that the difference between constant and constant time disappeared in the "dumbing down". Once you start talking about "being bounded in the limit by a constant", most people won't understand it at sight. Even the ones that once knew it would probably have to look up a math book to remember what exactly that ment.
Either that, or it was simply mixed up in editing. They ment to say "The scheduler is using a constant time, and is so O(1)", rather than "The scheduler is O(1), and is so using a constant time." Either way, I think it's quibbling compared to the relevance and intended audience of the article.
Kjella
Live today, because you never know what tomorrow brings
Who was it that started this belief that redundancy necessarily means something has already been stated? It doesn't.
Webster's Revised Unabridged Dictionary (1913)
Redundant Re*dun"dant (-dant), a. L. redundans, -antis, p.
1. Exceeding what is natural or necessary; superabundant; exuberant; as, a redundant quantity of bile or food.
2. Using more words or images than are necessary or useful; pleonastic.
Syn: Superfluous; superabundant; excessive; exuberant; overflowing; plentiful; copious.
whats wierd is they have a rear admiral upper half and rear admiral lower half. nice troll by the way
The benefits of preemption are great enough that the kernel developers decided to make the kernel itself preemptible. This allows a kernel task such as disk I/O to be preempted, for instance, by a keyboard event. This allows the system to be more responsive to the user's demands. The 2.6 kernel is able to efficiently manage its own tasks in addition to user processes.
One of the most time-wasting, counterproductive things for me on Windows, and to a lesser extent on Linux, is that background tasks can essentially take over the computer because of disk thrashing. Sometimes (on Windows XP) I've seen it literally take minutes to bring a window to the front and repaint it while the disk is thrashing doing god-knows-what in the background. It is impossible to get any serious work done when that is happening. Setting my process to highest priority (on Windows) doesn't seem to help when disk thrashing is involved. I can understand how it might take a few seconds to swap another process out and bring mine in, but not minutes.
Now I don't know exactly what's happening behind the scenes, but as soon as I click on a window to bring it in focus, I want everything on the computer to be devoted to doing just that until its done, regardless of what disk blocks from other processes are in the queue. My disk block requests should go in front of all of the others unconditionally. In other words I should see essentially no more latency than if the computer were completely idle in the background, other than just the minimum delay required to bring it back into memory if it's swapped out. For all I care just completely freeze all other processes on the computer until my request is finished, or at least give me the option to specify that it be done that way. My productivity should override everything else on my own desktop/workstation computer.
So, educate me about what I may be overlooking here, and will 2.6 help this? I mean for Linux of course, not Windows, which may be a lost cause (:
My Mac runs a BSD layer on a Mach microkernel (duh), so I know just a little about Unix-ish OS structure and function. Dipshit. (sorry, feeding the troll.) What I want to know is what scheduler does Darwin use? If I had to guess, I'd say Apple uses whatever the BSDs use, but I have noticed a dearth in harcr0e technical press covering Darwin's internals. Sure, YDL might use the 2.6 kernel with that wonderful scheduling Ars talks about, but I like my Photoshop, and my Final Cut Express, and my iTunes - I even adore my OS X/Darwin; it's just as stable and flexible as YDL 3.0 IME, and it's a hell of a lot better supported. So, I'm sure some slashdotter wants to display his/her vast p00ter knowlege...how does the Darwin scheduler work, and how does it stack up against Linux? (Or does Mach handle the scheduling?)
Facts do not cease to exist because they are ignored. - Aldous Huxley
...we could have a standardized hardware scheduler chip that would be uber-fast. Unfortunately, they wont standardize, and to ice the cake there's no truly 'optimum' scheduler for all systems and user loads, so it looks like you're SOL.
Facts do not cease to exist because they are ignored. - Aldous Huxley
Considering that most /. readers are people who have a background in CS the article was too skimpy on details.
(methinks) Someone has a little something stuck in his craw.
Could there possibly be a reason for an offtopic mod? Lets see:
-- Article/thread about an article about the linux scheduler.
-- Respondent asks a technical support question having nothing to do with the article referenced or the scheduler in general.
-- Respondent gets moded down for jumping off topic because this isn't a Linux support forum nor is it generally an audience who would want it to *become* a support forum.
-- Someone who doesn't like to see a lot of the linux-centricisim in the forum *complains* BECAUSE others who don't want to read a technical support thread mod the offtopic post... "offtopic."
===
As a side note, you rigorous thinker you, a question or comment in the range of "I don't know why" ("this pause here with that message there confuses me", et. al.) indicates that the user wants information about his system and is not prima facia evidence that there is something "making Linux look bad" in any meaningful sense.
Consider: Sort of like saying that a single customer asking "what are the ingreedents of the 'special sauce', cause it feels oily?" must automatically make McDonalds "look bad" for filling the oily sauce role with an oily sauce not understood by a single questioner.
If you took the time to gather one single iota of information you would know that the message he doesn't like is in the startup sequence and happens only once (per boot) and lasts a couple of seconds at most.
If, on the other hand, he even vaguely intimated that the message lasted X seconds and was repeated every N seconds, then there would be some "looking bad" to be had here. If he could *FURTHER* even remotely tie this to the scheduler then the post would suddnely not be "offtopic".
Shame none of that happened. Which kind of leaves you wearing the inflatable rubber ducky on the subway there dude. You probably shoud stop yelling about the rising watter too. (IF you can follow a cultural metaphore there dude. 8-)
====
Point of (bonus) fact, there wasn't enough information in the question to even address an answer. Even so, (and without even checking), if the initrd (etc) system is compiled in there but the user isn't using initrd then he should compile the kernel without this bit. If he *IS* using the initrd image then it is kind of normal that the unpacking and mounting of the initrd image would cause a pause at that point because the kernel is working on something that everything else has to wait for.
So, nothing to see here folks, conspiracy theorist presenting tinfoil-hat theory about an demonstrably offtopic post getting modded down for being demostrably off topic. These arn't the droids your looking for. Move along... 8-)
====
Not hard to see why you posted AC...
Innocent people shouldn't be forced to pay for inferior software development.
--"Code Complete" Microsoft Press
What was the big-O of 2.4 and earlier?
whats wierd is they have a rear admiral upper half and rear admiral lower half. nice troll by the way
That sounds like they are filling parts in a large horse costume.
Don't blame Durga. I voted for Centauri.
"The recent release of Linux's 2.6 kernel introduces a number sweeping improvements"
"number sweeping"? Is this a new algorithm? Did i miss something here?
Natural Selection: self-destruction of the poor and lazy
gvim sched.c
Oops, looks like my copy of 2.4 (gentoo-sources) already has the O(1) scheduler backported? Heh, 2.4 already has the feature in question. ;-)
Ok, ssh over to my Slackware 7 box that is running 2.2... It looks like 2.2's scheduler is O(n), where n is number of processes. (It goes through a linked list of all the processes and picks one with the best "goodness".) So I guess 2.4's original scheduler was probably about the same: linear.
Heh, I hardly ever look at this stuff. Whenever I do, I'm kind of amazed at how small and managable the Linux kernel is. It really doesn't look like all that big of a project. Anyone can read and understand this stuff, and things are easy to find. I'm serious; dive in, and there it all is. A shame they indent with tabs instead of spaces, but I guess that's another religeous war. And the gotos, oh, the gotos...
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
Is the new kernel going to reach/exceed this level of performance for the desktop? This would be a big thing for the corporate desktop feel too, plus for me. Not that it is really important but can you play multiple movies and do other tasks without jumping? SGI Irix didn't used to be able to do that on even high end machines, don't know about now (well they will be running 2.6 I suppose..). I'd like to know if a modern distro will run in a sane manner for a gui desktop on 128MB of memory, (yeah I'll get more memory but..) and to know if I should make sure to put 2.6 on systems that need it (I'm thinking about a server which will do both I/O and visualization).
God you suck.
you do something in Windows Explorer that blocks (spin up a CD drive) and everything else (the "desktop", task bar, etc) all become unresponsive...
Yes, this is MAJORLY bad. I've had whole machines become totally unusable (mouse moves, that's about it) simply because of a dirty CD put in the drive, or a buggy drive (perhaps the mechanism is loose, etc). Windows wants to down the entire machine to devote all computational power to waiting for the CD drive! Linux is not off entirely scot-free, but it's definitely better at handling this situation, IMHO.
There must be a way of reducing the priority on these actions?
mogorific carpentry experiments
Nice work BigA: Ya bi*chslapped a well-deserving dweeb, while advancing & informing the yeomanry. We're now ready for part_2 !
bitch
We've been speaking of kernel scheduling, but a given GUI implementation can also have a dramatic effect on whether delays in one part of the system will result in sluggish UI response. IIRC, KDE is largely single-threaded and there are lots of cases where it will be momentarily hung-up waiting on some global resource. Maybe someone could elaborate.
One thing I haven't really seen pointed out is that the O(1) scheduler is not strictly present just in the 2.6 kernel - a number of distributions have had backported versions in 2.4-based systems; I believe Red Hat has had it integrated into their kernels since Red Hat 8, for example..
If you "grok" (who uses crap like this in real life anyways, except people who have something to prove? Not me, and I have a degree in CS and 15 years experience. Go read the jargon file some more, it makes you look supercool) kernels and your Mac so much, why don't you know what "Darwin" uses? It's based on FreeBSD, so, "dipshit", it definately uses whatever the "BSDs" use. It IS BSD, running on top of Mach. Yes the MACH layer is also scheduling itself, but your question was about "Darwin". Darwin is FreeBSD on Mach.
./ posters...
From Apples site: "We should note, however, that apart from a few architectural differences (such as our use of the Mach kernel), we try to keep Darwin as compatible as possible with FreeBSD (our BSD reference platform)."
You want "harcr0e" [sic] technical press covering Darwin's internals? Start reading the FreeBSD coverage. Though, at the hardware layer (device drivers), Darwin is interfacing with Mach, while FreeBSD interfaces with hardware. The scheduler is software only, thus, untouched.
Just enough "knowledge" to think you know what you are talking about. Not singling you out, (though it fits), I mean 92% of
AC because I can't be bothered to make an account.
...but wouldnt' the fact that only one process is operated on at a time (i.e. a fixed amount of computing) as opposed to scanning the enitre list of processes (could be one...could be thousands) each time make the difference between O(n) and O(1)? Sure, things will be slower if you have 10,000 things to check as opposed to one, but at least here we're not checking 10,000 things for each and every one in the list...
(IANAKH)
CAn'T CompreHend SARcaSm?
I like the bit at the top of your homepage by the way, and I feel exactly the same about telemarketers.. getting calls from them is a bright spot in the day when you can exercise passive phone terrorism over the poor workers at Sprint and MCI.
mogorific carpentry experiments
There's also: unelectable.
I have one toy-box which I use to test my stuff before I put the changes on my server. However, it takes me quite a while to sync it again with the server if I totally mess it up. So I'm still hesitant to try this all by my own.
I'm currently running 2.4.23, but I am very interested about the cryptoloop and new scheduler.
So, to the point. Anyone have a link to describe how to install 2.6.0 to debian-stable?
I briefly tried it, and googled a bit, and got the impression that it isn't exactly trivial....
Bot Assisted Blogging
However there are some stones unturned
I wonder how different scheduler classes get scheduled.
And how does scheduler differentiate load balancing for processes running on same core (SMT) and on different processors.
It would be nice to have more technical article published somewhere...
...why ARS gets so much press space here on SlashDot ? I mean, I also write a lot of articles about technical stuffs, but I never get any press space ?
/. become a front for AT ?
Has
As far as I can tell from the description in the article, there's nothing particularly new in this O(1) scheduler: what was described could have been the scheduler on just about any OS I can think of: one queue per priority level, pick the next available job from the highest level queue. Could have been taken from the Amiga manuals in 1985... either there's something missing from the description of the new algorithm or there was something really strange about the 2.4 scheduler.
What did it used to do?
[100% ISO 646 Compliant]
SVM, ERGO MONSTRO.
The article was okay, I guess. Very, very elementary. I would assert that most schedulers are O(1), though. Its really nothing new. This article was probably good for someone who never heard of a scheduler or worked with one.
Although the article was about scheduling, I would have like to have seen some more text about Big-O notation and why it is important to programmers. To me, any good programmer should have a good concept of Big-O notation, how it relates to traversing data structures (such as trees), et cetera.
The article did not make a point as to why good schedulers use priority queues. Which is simple, really. All priority queues are O(1) for getting the next item in the queue. It has nothing to do with scheduling, but it is the nature of the priority queue itself... as a data structure.
I would have liked to have seen the article in its whole form. I wonder if it went into more depth about Big-O, et cetera.
Windows XP, for example, isn't all that great in this area, and often one process can too easily slow things down. This is even further emphasized when all the processes you're working with are actually the main "explorer.exe" process; eg, you do something in Windows Explorer that blocks (spin up a CD drive) and everything else (the "desktop", task bar, etc) all become unresponsive...
/bin/sh and tell it to do something for you. It means that you send "events" to the currently-running EXPLORER.EXE with an idea of what you want it to do for you.
Unfortunately, even the best kernel process scheduler in the known universe would not fix this design flaw in Microsoft Windows, because what you're seeing is not a thread/process scheduling problem.
As you correctly observed, many Windows programs are forced to make "shell calls" -- which doesn't mean the same thing it does in Unix, where you fork a
The reason it bogs down when it's busy is because it is waiting on a single event queue. Mounting/unmounting of media, network lag, other processes sending/receiving messages, etc. all give EXPLORER.EXE more events to wait on. That's why it's a bottleneck, even when there's plenty of CPU to go around.
It's an awful design, and it's one of those things that's fundamentally broken about Windows.
Tired of FB/Google censorship? Visit UNCENSORED!
Many of your plurals, but not all, use apostrophe-s: eg. "algorithm's" but "processors". I don't believe that this is random and I'm very interested to know if you can see the subconscious rule you're following to decide when to use s and when to use apostrophe-s.
This is really not a veiled criticism. I'm genuinely interested in linguistic phenomena, and I am convinced there must be a rule somewhere. I can't see it myself and I'm hoping that you can help.
I think the reason is quite simple: Generally you have very few running tasks, so even though inserting a new one is O(lg N), it's basically free, whereas checking 160 bits (to find the first one set), can only be done efficiently by exploiting (hopefully existing) architecture specific assembler instructions, and is still slower than using a normal priority queue (assuming more than 32 task priorities are defined).
Adding to this, one does not need to keep a priority queue of all active tasks, but can use a priority queue of at which priorities we have tasks running, and use buckets like in Ingolfs schedular -- that way we get an upper bound on inserting/removing: logarithmic in the number of priorities (so O(1)).
So that gives us a faster schedule, but a worst-case slower insert/remove (but still O(1)). So what to prefer? That depends on how the machine will be used (and if it even allows efficient bit field operations).
From the article it sounds like other things were also changed with the introduction of Ingolfs schedular (like changing the timer frequency), and that may explain the perceived performance increase? I do not use Linux myself, so I cannot comment on these subjective things.
A 2.6 distro will probably feel quite snappy on modern (1Ghz+) machines (RH9 is still 2.4 based with a few patches to reduce latency but there is no kernel preemption and that makes a noticible difference).
Robert Love pointed out that BeOS often traded throughput for latency (point 2) coupled with that fact it was highly threaded for its reknowed responsiveness. On weaker (PII or less) machines I suspect BeOS will always feel faster but there will come a point where CPUs context switch so quickly extra effort beyond preemption will not be worth the effort.
By the way, most desktop OSes these days have preemptive multitasking. It is only older OSes such as OS9 and Windows 3.11 which do not.
From Apples site: "We should note, however, that apart from a few architectural differences (such as our use of the Mach kernel), we try to keep Darwin as compatible as possible with FreeBSD (our BSD reference platform)."
They're referring to the BSD userland (ls, rm, cp, etc.) there. Those have nothing (or very little) to do with the kernel or microkernel -- as can be evidenced by the fact that they all can be recompiled on most versions of UNIX, and many of those have very different schedulers. But as someone with a degree in CSc and 15 years of experience, I'm sure you were aware of that and just got emotionally excited.
The kernel/microkernel in Darwin have basically nothing in common with FreeBSD. Feel free to confirm this for yourself by reading the sources to both.
Interesting. Which "shell calls" are we talking about exactly? It would be nice to know which these are and then spawn a thread to handle them if possible.
Windows API calls that are handeled by the running shell, explorer.exe.
While functionally similar, I always learned the "Big O" notations as:
O(k)
O(kn)
O(k * log n)
O(k * n log n)
O(kn^2)
O(k * n^n)
etc.
where K is some given constant...slightly more clear than O(1) for constant time.
Are you telling me that *ALL* Win32 API calls are handled through explorer.exe!? That's ridiculous.
Only if they're shell calls...Generally, filesystem operations are handeled by Explorer; other API calls are made to the respective services providing that functionality.