Slashdot Mirror

← Back to Stories (view on slashdot.org)

Interview With Linux Kernel Guru Ingo Molnar

Posted by timothy on from the tux-is-interesting dept.

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

6 of 22 comments (clear)

  1. Description of O(1) scheduler? by LordNimon · · Score: 3, Interesting

    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?

    --
    And the men who hold high places must be the ones who start
    To mold a new reality... closer to the heart
    1. Re:Description of O(1) scheduler? by Zapman · · Score: 2, Redundant

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

      --
      Zapman
    2. Re:Description of O(1) scheduler? by iluvitar · · Score: 2, Informative

      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
      Just scroll down to the "Design" section (quarter of the way down the page).

    3. Re:Description of O(1) scheduler? by sesquiped · · Score: 4, Informative

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

  2. slight exageration.. by Anonymous Coward · · Score: 2, Interesting
    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.

  3. Re: slight exageration? not. by Ingo+Molnar · · Score: 5, Informative
    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.