Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

ArsTechnica Explains O(1) Scheduler

michael posted more than 10 years ago | from the time-to-kill dept.

Programming 295

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."

cancel ×

295 comments

Sorry! There are no comments related to the filter you selected.

Not a very INSIGHTFUL article. (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#7809823)

After I read this article I found that I had just wasted 5 minutes reading drivel which I knew already.

Ars have dumbed this topic down so much so that it does not even go on to talk about the problems with the 2.4 seheduler but instead talks about Zinf at the end (a media player).

I know its not the type of site typical slashdot readers (well educated computer enthuaists ) read, and its main audience is mac users they should atleast explain the difference this will make over the laymans 2.4 kernel [co..uk] .

Re:Not a very INSIGHTFUL article. (-1, Redundant)

Anonymous Coward | more than 10 years ago | (#7809974)

Modded down for being first

Re:Not a very INSIGHTFUL article. (0)

Anonymous Coward | more than 10 years ago | (#7810013)

Redundant? Where was the first comment mentioning this?

Re:Not a very INSIGHTFUL article. (0)

Anonymous Coward | more than 10 years ago | (#7810094)

Nowhere. The moderators are just stupid.

Re:Not a very INSIGHTFUL article. (1)

geogeek6_7 (566395) | more than 10 years ago | (#7810272)

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.

Merry Christmas from SFC (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7809825)

SFC (SIMONIGGER FAN CLUB) is the first organization which
gathers SIMONIGGER FANS from all over America and abroad for one common goal - being SIMONIGGER FANS.

Are you INTELLIGENT?
Are you a SLASHDOT READER?
Are you an INTELLIGENT SLASHDOT READER?

If you answered "Yes" to any of the above questions, then the SFC (SIMIONIKER FAN CLUB) might be exactly what you've been looking for!
Join SFC (SIMONIGGER FAN CLUB ) today, and enjoy all the benefits of being a full-time SFC member.
SFC (SIMONIGGER FAN CLUB ) is the fastest-growing SIMONIGGER FAN community with THOUSANDS of members all over United States of America. You, too, can be a part of SFC if you join today!

Why not? It's quick and easy - only 2 simple steps!

First, you have to obtain a copy of SIMONIGGERs list of stories [slashdot.org] [slashdot.org] and read them.

Second, you need to join the official SFC irc channel #SFC on EFNet, and apply for membership.
Talk to one of the ops or any of the other members in the channel to sign up today!

If you are having trouble locating #SFC, the official SIMONIGGER FAN CLUB irc channel, you might be on a wrong irc network. The correct network is EFNet, and you can connect to irc.secsup.org or irc.easynews.com as one of the EFNet servers.

If you have mod points and would like to support SFC, please moderate this post up.

This post brought to you by a proud member of SFC

Re:Merry Christmas from SFC (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7809944)

I'll wait to join until they've achieved a kernel backdoor with their holy seed.

Re:Merry Christmas from SFC (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7810005)

#sfc unable to join channel (invite only)
fag

Arse? (-1, Flamebait)

Anonymous Coward | more than 10 years ago | (#7809830)

Time to get another name, Arse Technica. A hint: "Bum Technica" won't work either.

Re:Arse? (-1, Redundant)

Anonymous Coward | more than 10 years ago | (#7809898)

How about "Rear Technica"?

Re:Arse? (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7810161)

Do you know that the US Navy actually has a rank named "rear admiral"? Hahahahahaha! OMFG, it makes me laugh every time.

Re:Arse? (0)

Anonymous Coward | more than 10 years ago | (#7810247)

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!

Ars' Piece (5, Interesting)

WarpFlyght (586558) | more than 10 years ago | (#7809832)

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?

Re:Ars' Piece (5, Informative)

sfe_software (220870) | more than 10 years ago | (#7809993)

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).

Re:Ars' Piece (2, Insightful)

moonbender (547943) | more than 10 years ago | (#7810132)

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).
It doesn't just "feel" more responsive, it is more responsive! It's a matter of definition, but I'd certainly call that an improvement of performance. Taking from the article (or comp.sci classes), while the throughput remains equal - I suppose it's even reduced - the latency is lower, too. Performance is both factors, not just the former.

Multi core proc's (2, Insightful)

niko9 (315647) | more than 10 years ago | (#7809839)

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?

Re:Multi core proc's (2, Insightful)

be-fan (61476) | more than 10 years ago | (#7809890)

A multi-core processor appears as multiple processors to the software. Even SMT processors appear as multiple processors to the software. So the software scheduler is needed to juggle the available processors among the threads competing for them.

Re:Multi core proc's (4, Informative)

autopr0n (534291) | more than 10 years ago | (#7809908)

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.

Many programs are multithreading now... (1)

Kjella (173770) | more than 10 years ago | (#7810148)

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

Re:Multi core proc's (2, Interesting)

KrispyKringle (672903) | more than 10 years ago | (#7809968)

I'm not sure I understand how a hardware scheduler would work. It would need to keep track of the process's state, including virtual memory and registers, no? I don't know how the hardware would do that without the OS's support. You would need a software scheduler to manage these things; otherwise, it seems like you'd be limited to one process per CPU. Correct me if I'm wrong, though.

Re:Multi core proc's -- flamebait? (0)

Anonymous Coward | more than 10 years ago | (#7810266)

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.

initramfs (2, Interesting)

FrostedWheat (172733) | more than 10 years ago | (#7809842)

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.

Re:initramfs (0, Offtopic)

adamy (78406) | more than 10 years ago | (#7809936)

I wonder if this is a Lilo issue. Which bootloader are you using?

Not surprised by this moderation (0)

Anonymous Coward | more than 10 years ago | (#7810075)

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

Re:Not surprised by this moderation (0)

Anonymous Coward | more than 10 years ago | (#7810079)

s/back/bad/;

Re:Not surprised by this moderation (0)

Anonymous Coward | more than 10 years ago | (#7810169)

>> 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

Linux is not Windows and Slashdot is not Microsoft, son.

Part of the zealotry here is improving Linux. Bugs are not costs, they are opportunities, ladders to fame... oh, and this is basic, you really should've noticed it on your own.

Check your facts.

Re:Not surprised by this moderation (0, Flamebait)

Anonymous Coward | more than 10 years ago | (#7810296)

Non-sequitur.

The person posted something that made Lunix look bad and guess what.. he got modded down.

End of story. Moderation around here is biased and sucks.

A more detailed description of O() notation... (4, Informative)

ctrl-alt-elite (679492) | more than 10 years ago | (#7809849)

...can be found here [washington.edu] (PDF file).

Re:A more detailed description of O() notation... (1)

gordyf (23004) | more than 10 years ago | (#7810069)

That's a set of slides from my class! Perkins would be proud.

Re:A more detailed description of O() notation... (1)

HungWeiLo (250320) | more than 10 years ago | (#7810168)

Ah. Good old CSE 143. A very good class to learn about divide and conquer - The class size halves after every midterm (2 or 3 of them in the quarter?)

that article sucked (1, Informative)

Anonymous Coward | more than 10 years ago | (#7809854)

Most of the article was just about scheduling definitions - the states of a process, what preemption is etc... What a waste of reading.

your mom sucked! (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7809990)

but i've seen worse

Don't critcize the article (-1, Offtopic)

Anonymous Coward | more than 10 years ago | (#7810101)

That moderation will teach you to NEVER speak out against the articles that are posted on Slashdot.

Hmm. (5, Interesting)

Anonymous Coward | more than 10 years ago | (#7809866)

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

Re:Hmm. (5, Informative)

AmirPC (735533) | more than 10 years ago | (#7809904)

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.

Re:Hmm. (2, Interesting)

WarpFlyght (586558) | more than 10 years ago | (#7809942)

I'm sorry to hear that some of the article's technical details were edited out. I can understand why the editors would do so, though. Ars obviously isn't only targeting Slashdot readers, hehe.

Would you be willing (or able) to post your original version of the article somewhere for interested parties to read?

Re:Hmm. (1)

AmirPC (735533) | more than 10 years ago | (#7809971)

Sure let me see if I have it around somewhere, the writing is of much lower quality (I'm a programmer after all) but it goes further in.

Re:Hmm. (5, Informative)

AmirPC (735533) | more than 10 years ago | (#7810034)

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 ;)

Ah-ha! (2, Insightful)

tsanth (619234) | more than 10 years ago | (#7810091)

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?

Thanks. (0)

Anonymous Coward | more than 10 years ago | (#7810156)

That was extremely informative; thank you for posting it.

-- Super Ugly Ultraman

Re:Hmm. (1)

Otter (3800) | more than 10 years ago | (#7810160)

That has zero editing done, and is even missing a quote up at the top.

OK, now you're targeting Slashdot readers!

Seriously, I never would have considered the Ars readership to be an intellectual step down from /..

Re:Hmm. (0)

Anonymous Coward | more than 10 years ago | (#7809983)

Shut up, you ars!

sidebars??? (3, Insightful)

mefus (34481) | more than 10 years ago | (#7810048)

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?

Preemption defined incorrectly, I think (4, Insightful)

vrt3 (62368) | more than 10 years ago | (#7810164)

In the article, you write:
It is important to remember that a process can be stopped in the middle of its timeslice; this is the purpose of preemption.
The purpose of preemption is not to stop processes in the middle of their timeslice; the purpose is to stop them when the scheduler decides to, not only when the process itself decides to give another process a chance to run. The latter is called cooperative multitasking, and is used in Windows 3.x and MacOS prior to X.

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.

Re:Hmm. (3, Informative)

SilentStrike (547628) | more than 10 years ago | (#7810166)

A thread is not the same thing as a process. I hope that was the editors fault too.

Re:Hmm. (1)

TwistedSquare (650445) | more than 10 years ago | (#7809927)

That would be handy, I don't quite understand why O(1) is so hard, unless it is all related to priority scheduling checks. Anyone have links/explanation?

Re:Hmm. (1, Insightful)

Anonymous Coward | more than 10 years ago | (#7809988)

You have 100 processes. Each has a priority. If you check each process individually every time you do a scheduling, you go into O(n) where n is the number of processes.

In other words, the magic lies in selecting a process based on its priority, without checking each processes priority, while still not leaving low priority processes starved of resources.

Now, I don't know how they did it, I'm not a kernel hacker. But just thinking about it, O(1) is never easy to achieve when dealing with n items .

Re:Hmm. (1)

Jesus 2.0 (701858) | more than 10 years ago | (#7810093)

I don't understand why it's so difficult to make an O(1) scheduler.

Trivial example (I'm sure it can be improved upon, it's just off the top of my head to show that O(1) is not difficult to make):

There are a fixed number of possible priorities. Keep an array of that many integers. At a particular index, store the number of processes with that particular priority.

Keep a linked list of the processes. When a new process is created, put it on the end of the list. When an old process dies, remove it from the list.

When it comes time to decide what process to give a time slice to:

(1) Loop through the array of processes at particular priorities. For a priority P, apply some O(1) function to the number of processes at that priority (basically, a weighting function - the higher the priority, the higher the weight). Sum over all priorities. Since there are a constant number of priorities, and since your function f is O(1), this operation is also O(1).

(2) Pop the top process off of the list (this is also O(1), of course). Check the priority of the process. Apply some O(1) function g to the priority and to the number that you arrived at in step (1). The result of function g is an amount of time. Basically, you're getting something like a percentage of total time that should be applied to this particular process, based on its priority and those of all the other processes.

(3) Let the process execute for that amount of time.

(4) Put the process on the tail of the list (also O(1), of course).

(5) Goto step (1).

Sorry about the heretical use of goto. But anyway, there you have an O(1) scheduler. What's the big deal?

Re:Hmm. (0)

Anonymous Coward | more than 10 years ago | (#7810218)

go to kernel.org [kernel.org] , get the kernel source, and write your own. i'm sure linus would be up for a better scheduler.

Re:Hmm. (1)

Jesus 2.0 (701858) | more than 10 years ago | (#7810232)

I'm not saying that I just designed the world's greatest scheduler. Far from it, I'm sure.

I'm just saying, I don't get the concept that merely making an O(1) scheduler is so incredibly difficult, and it's so utterly amazing that they were able to do so.

Re:Hmm. (1)

Otter (3800) | more than 10 years ago | (#7810287)

Maybe I misunderstand what you're doing in step 1 but isn't it O(N) for the number of processes?

Re:Hmm. (1)

GebsBeard (665887) | more than 10 years ago | (#7809965)

There are a few specific data structures that operate O(1). In general they are really gnarly to implement. You may want to look into Fibonacci heaps as the majority of their operations are either O(1) or O(1) amortized. There are other heap structures that are perfect for scheduling but they tend to be variations on a theme: Pairing heaps, Trinomial heaps, etc.

This is simply off the top of my head, since I have no further knowledge of the inside of Linux 2.6 kernel. I am fairly certain given the pain in designing a good data structure, let alone one with O(1) characteristics, this is a good place to start.

Re:Hmm. (4, Informative)

KrispyKringle (672903) | more than 10 years ago | (#7809979)

this [slashdot.org] 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).

Re:Hmm. (2, Interesting)

AmirPC (735533) | more than 10 years ago | (#7810050)

Balancing is never called O(1) in the article. I guess it was somewhat unclear but the scheduler itself is O(1) while load balancing is not constant. I guess it really depends on where you drawn the line between the scheduler and the rest of the kernel.

Re:Hmm. (4, Informative)

windows (452268) | more than 10 years ago | (#7810042)

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.

Re:Hmm. (1, Informative)

Anonymous Coward | more than 10 years ago | (#7810265)

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).

I don't follow your logic here.
Assume that you have a queue with n processes. In worst case when scanning through the queue, the first process that it can run is the last one; thus, it must check n processes. If the processes in the last are placed "in random", e.g. just put there, on average, the scanner would have to check n/2 processes before finding the correct one = O(n).

How can this be called O(1)? I'm not saying the scheduler in 2.6.0 isn't O(1) but I believe your explaination is flawed.

Look under "Timeslices and niceness" (1)

Kjella (173770) | more than 10 years ago | (#7810288)

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

Yay for Ars (3, Interesting)

be-fan (61476) | more than 10 years ago | (#7809872)

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!

Happy BirthYear (0)

Anonymous Coward | more than 10 years ago | (#7809916)

The newer G3 will be the powerful chip of the year 2004 and it is very useful for the decent linux-2.4.23.

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

what is the best 64 bits architecture? (0)

Anonymous Coward | more than 10 years ago | (#7810078)

The best scheme of page translation for the 64 bits architecture quicker is:

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

alpha (0)

Anonymous Coward | more than 10 years ago | (#7810167)

# 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 [goatse.cx]

Re:Yay for Ars (0)

Anonymous Coward | more than 10 years ago | (#7809991)

Yeah, Byte magazine used to kick ass. I remember when they used to carry hardware hacking articles and print PCB solder side masks.

Computercraft/Microcomputer Journal used to be a good one too before they went belly up. Jan Axelson's [lvr.com] articles were great.

I don't know of any current magazines that are like those two were.

Go Ahead (-1, Troll)

Anonymous Coward | more than 10 years ago | (#7809888)

> These can be hard to understand without a
> background in programming...

Well heck, don't let that stop you. It's never
made others in the Linux/Slashdot community from
making sweeping judgments about things they know
nothing about.

Ars (-1, Funny)

GerbilSocks (713781) | more than 10 years ago | (#7809923)

I, for one, welcome our new ArsTechnica overlords.

Brought to you by a Squadron of Gay Monkeys.

Interesting (5, Informative)

Gary Whittles (735467) | more than 10 years ago | (#7809939)

The scheduler is an important part of the kernel, so this is an important thing to understand. This article describes it well, but just to summarize a bit more technically, the benefits of the O(1) scheduler are:
  • 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.

What was the O value od the 2.4 scheduler? (0)

pt99par (588458) | more than 10 years ago | (#7809961)

see subject!

Re:What was the O value od the 2.4 scheduler? (0)

Anonymous Coward | more than 10 years ago | (#7810002)

n+1

Re:What was the O value od the 2.4 scheduler? (0)

Anonymous Coward | more than 10 years ago | (#7810009)

Linux 2.4 had a O(69) running time in it scheduler.
The Linux 2.6 O(1) scheduler is therefore better by a factor of 68.

Re:What was the O value od the 2.4 scheduler? (0)

Anonymous Coward | more than 10 years ago | (#7810030)

Actually, the O value of the 2.4 kernel's scheduler is inversely proportional to the square integral logarithmic equation of your dick's size.

Just kidding. The real O value of the 2.4 kernel is documented here [goatse.cx]

Re:What was the O value od the 2.4 scheduler? (0)

Anonymous Coward | more than 10 years ago | (#7810090)

Do you even know what an integral is?

Re:What was the O value od the 2.4 scheduler? (0)

Anonymous Coward | more than 10 years ago | (#7810109)

Why don't you shove it up your differential asshole, geek?

Re:What was the O value od the 2.4 scheduler? (0)

Anonymous Coward | more than 10 years ago | (#7810116)

Yes.

Do you? Or are you trying to leech knowledge for your calculus homework?

A question if anyone can answer (2, Insightful)

abhikhurana (325468) | more than 10 years ago | (#7809981)

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?

Re:A question if anyone can answer (1)

Tweaker_Phreaker (310297) | more than 10 years ago | (#7810064)

The thing that makes it an O(1) scheduler is that it has a static overhead. In high load it should achieve the same throughput but have lower latency when reacting to important events like user input.

Re:A question if anyone can answer (1)

abhikhurana (325468) | more than 10 years ago | (#7810106)

Yeah, it has a static overhead per task. As the number of tasks increase, teh overhead will increase as well. It no doubt will be able to maintain a lower latency but if teh CPU load is 100%, then every task switch becomes expensive, so I am not sure about the throughput part in such a case.

Re:A question if anyone can answer (1)

vadim_t (324782) | more than 10 years ago | (#7810199)

No, the idea is that the O(1) scheduler has static overhead period. Not per task. It always takes the same time, independently of whether 10 or 10000 processes are running.

Simple example of an O(1) operation: Accessing a position in an array. Whether there is one or 1000 elements, accessing one of them takes the same time. This is simple to exploit as well.

Suppose that depending on the value of a byte (random, so that any value has the same probability of happening) you have to do some work. You can write a switch with 256 choices. This will raise the time needed to do all the required tests linearly.

Or, you can store pointers to the functions that handle each task in a table, and call the function by the pointer stored in table[n]. In this case, you can have any number of functions, and the time needed to decide which one to call will still be the same.

Flash Blocker? (-1, Offtopic)

rudy_wayne (414635) | more than 10 years ago | (#7810028)


Does anyone make a program to block those annoying Flash ads?

Re:Flash Blocker? (0)

Anonymous Coward | more than 10 years ago | (#7810115)

Use a Mozilla [mozilla.org] with the Adblock-plugin [mozdev.org]

Re:Flash Blocker? (0)

Anonymous Coward | more than 10 years ago | (#7810159)

Plan9.

Re:Flash Blocker? (0)

Anonymous Coward | more than 10 years ago | (#7810194)

lynx?

Re:Flash Blocker? (1)

kars (100858) | more than 10 years ago | (#7810212)

http://www.squarefree.com/userstyles/xbl.html [squarefree.com] 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 [squarefree.com] where you can find bookmarklets that clean up a page after it's loaded. Very handy :)

Re:Flash Blocker? (0)

Anonymous Coward | more than 10 years ago | (#7810246)

easy, dont install that crap

What about the hardware? (0, Offtopic)

tloh (451585) | more than 10 years ago | (#7810040)

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?

English 101 (1)

kantai (719870) | more than 10 years ago | (#7810044)

introduces a number sweeping improvements

Looks as if someone forgot a certain important preposition :-)

Re:English 101 (0)

Anonymous Coward | more than 10 years ago | (#7810192)

It was not forgotten, it was there; but it was swept off. :-)

Re:English 101 (0)

Anonymous Coward | more than 10 years ago | (#7810238)

Looks as if someone forgot a certain important punctuation mark.

Re:English 101 (2, Funny)

geogeek6_7 (566395) | more than 10 years ago | (#7810299)

Err. Oops. I blame Soviet Russia.

Ars got it slightly wrong about O(1)... (5, Informative)

andy666 (666062) | more than 10 years ago | (#7810059)

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.

Re:Ars got it slightly wrong about O(1)... (2, Insightful)

qc_dk (734452) | more than 10 years ago | (#7810220)

that is not entirely true it means that for the worst case input, there exist a constant k and a smallest number of processes np where the following equation is fulfilled:

Time_To_Switch_n_proces(p)< k where p>np

that is not exactly the same as your definition.

Deep algorithm analysis? (1, Interesting)

Anonymous Coward | more than 10 years ago | (#7810147)

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.

Re:Deep algorithm analysis? (1)

vadim_t (324782) | more than 10 years ago | (#7810219)

Well, my computer has 114 processes running at the time. O(n^n) would be *very* bad here. Heck, it'd probably be bad even if I had just 10 running.

I don't think this will happen any time soon, but a way of working around a slow O(1) algorhitm would be simply measuring the amount of data, and switching to the algorhitm that's faster. Say, with 10 processes running it uses the old one, with more than 100 it switches to O(1).

Re:Deep algorithm analysis? (1, Informative)

Anonymous Coward | more than 10 years ago | (#7810239)

Yes, those questions are central to this discussions. Maybe they are dealt with in the original extended article whose link the author kindly posted above (but is slashdotted right now).

I seem to recall seeing benchmarks about O(1) in Kerneltrap, which confirmed that for a small (less than 50? I can't remember) number of processes, the old scheduler was better.

My main interest is the desktop/notebook/pda environments, though of course servers will benefit from this scheduler (due to their usually higher number of processes).

Even on the desktop, the O(1) could lead to benefits for those who load lots and lots of apps and keep them running. This is not my traditional usage today, as I turn off the computer at night.

But this can change. If anyone is interested, there's a Linux ecology howto, which presents ideas on how to make computers less power hungry.

hrrrm (-1)

Sarojin (446404) | more than 10 years ago | (#7810176)

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?

How is this different from the BSD/VMS schedulers? (2, Interesting)

Anonymous Coward | more than 10 years ago | (#7810195)

Is this new? BSD and before that VMS used the same mechanism, priority queues for twenty years. The VAX architecture even had instructions to do this in 28 instructions. Here is some BSD code:
static struct rq queues[32];
static u_int32_t queuebits;
int qi;

qi = (current->priority >> 2);
SetBit(&queuebits, qi);
InsertQueue(&queues[current->priority ], current);

qi = FindFirstSet(queuebits);
if (RemoveQueue(&queues[qi], &current) == Q_EMPTY)
ClearBit(&queuebits, qi);
You might want to look at this article:
www.usenix.org/publications/library/proceedings/al s00/2000papers/papers/full_papers/sears/sears_html /

Linus Didn't steal it from SCO. (3, Funny)

Anonymous Coward | more than 10 years ago | (#7810283)

Please stop posting SCO code here, it only gets Darl all excited.

Technically, this is not O(1) (2, Interesting)

Anonymous Coward | more than 10 years ago | (#7810202)

Let me explain: the Ars article says

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?

Well... (1)

tsanth (619234) | more than 10 years ago | (#7810249)

Yes, but it does need to inspect all the processes within a priority level, right??

The analysis in the thread above [slashdot.org] 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.

Trade offs? (1)

qc_dk (734452) | more than 10 years ago | (#7810236)

Does anybody know what tradeoffs if any have been made to make the scheduler O(1)??
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:
newprocess = processqueue.pop();

processqueue.push(oldprocess);
do_context_switch;
Which would be O(1) for a sensible choice of queue.

UNIX catches up with mainframes (5, Informative)

Animats (122034) | more than 10 years ago | (#7810276)

For historical reasons, revolving around the "process table" design in PDP-11 UNIX, the schedulers in UNIX-like OSs were originally very dumb. The one in V6 UNIX was so bad that if three processes were compute-bound, the scheduler would stall.

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.

Sounds like an RPG (4, Funny)

blixel (158224) | more than 10 years ago | (#7810298)

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.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>