Page 1 of 1

Prof. Knuth's Algorithms book-series: OS dev

Posted: Sat Dec 12, 2020 4:49 pm
by PeterX
Does anybody know the benefits of Prof. Knuth's Algorithms book-series for OS developers? As far as I know those books cover a wide range of algorithms, in many different usage areas. So I guess some stuff in those books cover OS development.

Anybody has looked into those books? How interesting are they for OS developers?

Greetings
Peter

Re: Prof. Knuth's Algorithms book-series: OS dev

Posted: Sat Dec 12, 2020 4:56 pm
by Korona
TAoP rigorously addresses a broad range of algorithm theory. Several algorithms are relevant to OSdev: search tree or radix tree data structures, graphs (e.g., to represent dependencies between shared libraries), hash tables, sorting and selection algorithms, and probably much more. However, TAoP is quite dense -- it rigorously proves the correctness and running time properties of all algorithms and contains exercises from easy to research question levels. If you want to get into algorithm theory, I'd recommend a more hands-on book first, like the one from Corman et al. You can always look up the individual chapters of TAoP that you are specifically interested in.

Re: Prof. Knuth's Algorithms book-series: OS dev

Posted: Sun Dec 13, 2020 3:55 am
by xeyes
They are interesting reads (and practices) for anyone with a passion in CS in general and especially the more math like side of it.

Though IMO, from a pure engineering/project management aspect, there's not much value unless you are working on the OS as part of a big team (way more than 20,30 people) or the OS is already very very advanced that you can afford to specialize and do R&D in a small sub area.

A crude example, how do you implement spin lock in your kernel for x86?

Perhaps some 'original' flavor of the test test and set as appeared in the x86 manual, perhaps something more advanced.

And you may know that 30 years ago there's a paper introducing the MSC lock, which beats out 4 or 5 other flavors (variants) in terms of latency and system bus load in contentious periods where up to 80 CPUs compete for the same spin lock while maintaining FIFO.

More than 25 years later, after much deliberation of structure sizes, etc. and performance upsides, a variant of MSC lock is merged into the Linux kernel.

Now you have a few choices:

A. continue to use what you have, which will serve you well for a long time (at least Linux managed just fine well into 2010s without converting to MSC lock)
B. copy Linux, implement MSC lock (it is literally just a few lines of code), blindly (but correctly) believing in its 'proven correctness and performance'
C. come up with MSC lock yourself, or at least look at the answer and then mathematically prove its properties like correctness, latency and FIFO given the properties of primitives like atomic compare and exchange

Plunging into this set of books as a practical guide for OS dev is like making choice C for each design decision as small as 'how do you implement spin lock in your kernel for x86' . Good luck and have fun :wink:

Re: Prof. Knuth's Algorithms book-series: OS dev

Posted: Sun Dec 13, 2020 6:48 am
by thewrongchristian
PeterX wrote:Does anybody know the benefits of Prof. Knuth's Algorithms book-series for OS developers? As far as I know those books cover a wide range of algorithms, in many different usage areas. So I guess some stuff in those books cover OS development.

Anybody has looked into those books? How interesting are they for OS developers?

Greetings
Peter
I bought the books many moons ago, but I've ended up not looking at them much.

I can, though, recommend "Algorithms in C" by Robert Sedgewick. It provides example code in C and some basic algorithmic analysis. But if you're not interested in the algorithmic analysis, and just want to know how stuff works (and take it as read how well it works/scales) then this is a good book to have to hand. But it doesn't provide anything over and above what can be easily found on the web.

As for algorithms themselves, my main data structures in my kernel are the binary search tree, and a dynamically sized vector, both fronted with an abstract map interface which maps uintptr_t to uintptr_t (which can be wrapped with pointer based equivalents.) The interface could also front a hash based map, but I've found at this stage I've not needed to implement such a map. When I get somewhat feature complete, then I can do some performance measurements and see what would benefit from moving to a hash based map, but as it is at the moment, BSTs provide me with a scalable, searchable, ordered data structure that fulfills all my current needs.

I also have circular linked list structure and macros.

The trick is knowing what structure is appropriate to use when. And knowing what the performance characteristics of each data structure can be useful for the appropriate selection. I guess that's when these books come into their own.

Perhaps we should have a wiki page with recommendations on what data structures to use in which scenarios (if we haven't already)?