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."
...can be found here (PDF file).
I'm the author of that article..
The original article was MUCH MUCH more in depth it was toned down because of the "glaze over" effect people were getting. I didn't have much say in the editorial process in the matter.
I think this way atleast it appeals to a broader audience, not just the CS audience who would know what a binary min heap is if I were to use it.
To each his own I suppose.
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?
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. I suppose you could have a hardware scheduler, but I don't think it would be a good idea. Scheduling doesn't take much time (certainly not this O(1) jobby), so you would lose a lot of flexibility without a lot of gain.
autopr0n is like, down and stuff.
- 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.this guy says that the scheduling itself is O(1) but the balancing is O(n). I don't know this myself, but that makes a whole lot more sense; according to the ars article, the scheduler simply keeps two stacks of processes--which is can seemingly do in constant time--but of course doing the load balancing is proportionate to the number of processes (times some constant--you remove constant multipliers in big-O--to do the context switching).
Regarding "dumbing it down":
There is one exception to this load balancing rule -- some special processes may be fixed to a certain runqueue. This attribute is called "thread affinity;" a thread is simply another name for a process.
I think it over-simplified this a bit. Granted, Linux doesn't make all that much distinction between a "thread" and a "process" as compared to (say) Windows, but the distinction is still important.
Otherwise, it's a decent article, and gave me some insight to one of the major improvements in 2.6 (which I've yet to try out).
I remember when the "pre-empt" patch came out for 2.4, before it was integrated into the kernel. For a desktop (or otherwise interactive, like my media box) system, it really made a major perceived improvement in performance (while *actual* performance wasn't affected; it was just about priorities and scheduling, making it "feel" more responsive).
The O(1) scheduling algorithm likely improves this further, and is enough to tempt me to spend XMas evening upgrading... these things are important, especially on a desktop system.
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...
I enjoy seeing such improvements in the Linux kernel. The pre-empt patch (later integrated into the mainstream kernel) made a drastic usability improvement (especially when the box is also a web server, MySQL server, firewall/router, etc) and I couldn't see a Windows box handling similar tasks without becoming unusable (note: not unstable, just not practical to use when responsiveness is hindered).
I think the kernel team is on the right track with this, specifically for desktop applications (though it does help in many other applications as well; anything interactive, really, even over the network/Internet).
NGWave - Fast Sound Editor for Windows
http://67.163.90.104/~jim/scheduler.html Thats the completely unedited first draft its all I could find. That has zero editing done, and is even missing a quote up at the top. It goes further in depth, but as you can see...my unedited writing isn't so great ;)
I'm not particularly familiar with the O(1) scheduler, but I know enough about it to give an explanation that I believe is accurate enough.
There are two queues used in the Ingo scheduler. One contains processes that are ready to run. The other contains processes that have already run. The run queue is scanned, and when a process is found that can be run, it is automatically run without scanning the rest of the queue. When the process finishes its time quantum, it is put into the second queue.
When the first queue (the active one) is empty, the queues are switched. This is just done by swapping the pointers to the queues.
This scheduler is O(1) because it runs the first process it can run without scanning the entire queue as an O(n) scheduler would do. That's why it's O(1).
If you want a bit more information on it, search for the "Ingo scheduler" on Google or your other search engine of choice. I don't see any detailed explanations of what happens, but I suspect as the 2.6 kernel goes into wider use, those will come.
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.
A thread is not the same thing as a process. I hope that was the editors fault too.
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.
You raise a good question. Here's a link that might explain a little better than I can.
;-)
Your assumption is flawed, though. You seem to be assuming that only one process in the queue is runnable. We can't make that assumption that at any given time there's only one runnable process.
I believe you have a point about the worst case of the algorithm. That's not really relevant here, though. Consider the Quicksort algorithm. It has a nasty worst case - data that's already been sorted. As a matter of fact, the worst case is an O(n^2) and approaches the slowness that is the bubble sort. Despite this well-documented worst case, we say that quicksort is an O(n*log n) algorithm, which is a more typical case.
I believe the worst case of the Ingo scheduler is O(n). If only one process can be run, it indeed has to check n/2 processes on average, and therefore is O(n).
You raise a good question, and figuring out what order an algorithm is, is something I'm not particularly good at. Generally the average case is what matters, but I don't know how you determine what the average case is for the state of processes.
Anyone care to try to explain this?
It's not. However, instead of having a slight pause (that scales linearly with the number of processes in-flight) after all the processes have exhausted their timeslices, there is a constant *tiny* pause after each process exhausting their timeslice. Since previously, the kernel was not preemptable, the O(n) recalculation would potentially cause, on large systems especially, a pause while the timeslices were recalculated. The new scheduler increases system responsiveness by eliminating this mass-recalculation.
I think the majority of major improvements on the 2.6 kernel over 2.4 were placed for increasing system responsiveness.
(and yes, I'm using my Karma bonus)
Trashing occurs when you have to page out to virtual memory that is mapped to the hard drive. Your computer is spending more time moving data in and out of virtual memory than it is doing the actual computation.
This usually happens when a process is in a loop, and repeatedly uses the same memory blocks, but can't keep them all in physical memory. Thus, it has to replace the pages every time it accesses/modifies them.
Even if a process is at a low priority...if it comes on the CPU, it has the potential to trash memory and slow the works down.
If an application is trashing, then you might be able to get away with scheduling it to not hit the disk. If the OS is trashing, you are SOL.
Let's see if I can remember anything from my algorithms class.
How is this not O(n)?
Read on for an explanation. I do believe you gave the answer to your own question in your post. I will also assume that you understand "Big-O" notation well enough to follow the answer.
Each process still gets its time slice calcuated, it is removed from one queue, and inserted into another.
Correct. You've nailed it. Insertion into a Que operates in O(1) time. Removal from the Que is also a constant time algorithm. A Que inserts at the tail of the list (or the end of the array) and De-Ques from the Head of the list (or the beginning of the array). Ques do not permit searching, sorting or accessing the data after the first element.
If we De-Que a process, run it then calculate some information and Que it up that would run in O(c1*O(1)+c2*O(1)) = O(1).
This is still an oversimplification and does not take into account the possibility of a Priority Que in which insertion runs in O(lg n) and De-Queing runs in O(1). So a heap sort using a Priority Que runs in O(n*lg n).
Hope that helps.
I'm sure there are more detailed writeups on the O(1) scheduler in place in 2.6. Does anyone have any links? http://67.163.90.104/~jim/scheduler.html Unlike the Ars Technica article which seems to be nothing more than an overview of how schedulers work in general, this article goes into great technical detail about the actual implementation detauls of Linux's O(1) scheduler.
In your scheme, the low priority process will never get a chance to run, because the high priority process is running all the time. So the high priority process keeps running forever doing nothing useful.
So if your email client was checking mail in the background, its connection will time out, file sharing will completely die, background printing fails due to communication time-outs,Donate free food here
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!