Friday 24 December 2010

Queuing theory and BFS

I had pointed out to me on IRC by Damentz the queuing theory video that was linked by a slashdot article.

For those who haven't seen it, the video is here:
Why the other line is likely to move faster

Anyway, the relevance of that video is that BFS uses a single queue, whereas the mainline Linux kernel uses a multiple queue design. The people are tasks, and the checkouts are CPUs. Of course there's a lot more to a CPU scheduler than just the queue design, but I thought this video was very relevant :)

Merry Christmas everyone.


  1. Merry XMas to you too! And thanks for your gifts (BFS, -ck, lrzip ..) and your blog all over the year!

    PS: But the problem with only one queue: If there is a lock, than the tailback is for all. Remember on my old OS/2 days ...But I hope, with BFS it is completely different ;)

    CU sysitos

    PPS: Merry XMas to the other readers here of course too!

  2. thanks for all your work Con and best wishes! :)

  3. Happy holidays Con! Thanks for the interesting video. :)