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

Comments

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!")