Interview With Linux Kernel Guru Ingo Molnar

An anonymous reader writes "KernelTrap has posted an interview with Ingo Molnar, the Linux kernel guru who wrote the O(1) scheduler and improved threading enough to allow hundreds of thousands of threads to run in parallel. The interview covers a wide range of interesting topics, offering much insight into the latest and greatest improvements found in the Linux development kernel. From the new rmap VM, to BitKeeper, to TUX, to comparing Linux with FreeBSD, it's all there..."

Paving the way for 2.6?

[Anna Merikin]

Is it that 2.5 is getting so much better than 2.4 that its developers' enthusiasm is overcoming their natural reticence, or is it that there are OpenSource flacks working the free publicity mill for the impending release of 2.6?

Next, Google will put this on their front page, quoting /. as their source and linking to it.

BTW, has anyone at /. noticed a "Google effect?"

_______
I have seen war. You will not like it.

Description of O(1) scheduler?

[LordNimon]

It's been ten years since I had Comp Sci class. Does anyone have a pointer to an easy-to-understand description of the O(1) scheduler and how it differs from the previous one?

Re:Description of O(1) scheduler?

[Zapman]

Big O notation is a 'measure' (use that word very loosely) of how long an algorithm will take, depending on the number of inputs. For the scheduler, the number of inputs is the number of threads and processes. O(n) means that it has to loop over each process in order to make each scheduling decision. O(1) means that it's a constant time algorithm.

(For reference sorting an array of random numbers using bubble sort takes O(n^2), while using merge sort takes O(n*log(n)). Use google to see why. Also be aware that Big O is only a 'measure' of worst case time. Mergesort, if the data is in order takes O(n) (IIRC) )

You could throw 10 processes or 10 million at the O(1) scheduler, and it will still take the same time (witness the recent DSW of "I ran 1 million processes in parallel in 3 seconds!")

Re:Description of O(1) scheduler?

[iluvitar]

I think he intended for the question to be "how does the O(1) work?", and not "what's O(1)?". The article mentionned the two priority queues but nothing more.

There's a nice description about how it works here:
http://www.uwsg.iu.edu/hypermail/linux/kernel/0201 .0/0810.html [iu.edu]
Just scroll down to the "Design" section (quarter of the way down the page).

Re:Description of O(1) scheduler?

[LordNimon]

Duh, I know what O(1) means, I want to know about the scheduler itself!

Re:Description of O(1) scheduler?

[yugami]

note: I moded this informative, because while its a poor answer to the question it's a reply to, i think it answers many questions other readers may have.

Re:Description of O(1) scheduler?

[sesquiped]

http://www.cs.brown.edu/courses/cs167/lectures/13l inux.pdf [brown.edu]
pages 7-20

slight exageration..

[Anonymous Coward]

improved threading enough to allow hundreds of thousands of threads to run in parallel

Not exactly. His tests involved *creating* hundreds of thousands of threads and hibernating them instantly. Only a few thousand were ever running at once. That's not to discredit Mr. Molnar, but the x86 architecture (which linux is primarily geared towards) isn't up to the task -- at least not yet. Intel's hyperthreading may eventually change that.

Re: slight exageration? not.

[Ingo Molnar]

The test i did really involved the creation of 100,000 parallel threads, for a second or so. Obviously they did not do much work, other than go to sleep, but the runqueue length was definitely 100,000.

The test would be meaningless otherwise - you can create/destroy 100,000 threads in a row on any OS without any problem.

Furthermore, Anton Blanchard tested _1 million_ parallel threads on one of his big PowerPC boxen, using the new threading code - the test completed in roughly 30 seconds and he has got an insane load-average in the hundreds of thousands range - a further proof that the threads were running in parallel.

Re:The numbers thingy

[Anonymous Coward]

In Linux/Unix/BSD, why do people sometimes put numbers after programs? ie. rm(1)?

That's the manual section that they're in. Can't remember off the top of my head but it's roughly 1 is command line utils, 2 and 3 are API and runtime library, 5 for configuration files, 8 for admin utils/daemons, etc.

Sometimes there are entries in different sections with the same name - to find the one you want you have to specify the manual section on the 'man' command line. mkdir(1), for example, is a command line utility and mkdir(2) is a system call.

Note that this isn't the same as O(1) which is an upper bound on how an algorithm scales - see Zapman's (redundant) post above.

slashdot

[steinerik]

How often do you read the slashdot forums?