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

11 of 22 comments (clear)

  1. Paving the way for 2.6? by Anna+Merikin · · Score: 1

    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.

  2. 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 LordNimon · · Score: 1

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

      --
      And the men who hold high places must be the ones who start
      To mold a new reality... closer to the heart
    4. 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

    5. Re:Description of O(1) scheduler? by yugami · · Score: 1

      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.

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

  4. Re:The numbers thingy by Anonymous Coward · · Score: 1, Informative

    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.

  5. slashdot by steinerik · · Score: 1

    How often do you read the slashdot forums?

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