How important is knowledge of data structures and algorithms for an Operating Systems and Systems Programming course where we will be required to design and implement a kernel of a real-time operating system (done using C and 68K)?

How useful will programming experience implementing data structures like linked lists, queues, binary trees etc. in C++ be for this type of course?


  • You ought to ask what you need to know in general to do this, unless you accidentally just happen to know everything else.
    – Ira Baxter
    Commented Jun 23, 2011 at 4:08

4 Answers 4


Linked lists and queues are likely to be essential for any practical operating system implementation. Other data structures will probably come in handy as well. If you have C++ experience with these data structures, you should have no problem implementing them in C once you get comfortable with the differences between the languages.


all the data structures you have mentioned will come in handy. In addition to that, it is also likely that you will be given a network-programming related project, since that is the area where threads are most of the time used in real-life. So, in addition to that, it may be helpful to learn about socket and networking stuff. Just in case, you can read this article recommended by my OS professor.


You will need a lot of those data structures for the scheduler. Depending on which algorithm you use to schedule processes, you will use different data structures. The most popular, a round-robin algorithm will utilize a queue (FIFO).

You'll also do a lot of threading, and fork/exec which aren't really data structure dependent, but utilize a lot of "synchronization" programming.

In the class I took we didn't actually write the operating system, we just used the basic API that the OS provides (such as reading from a buffer, writing to a buffer, fork, exec, etc...), and also utilized higher level languages like C# and Java to implement multithreaded applications.

Understanding the concepts behind resources, producer consumer problems (livelocking, deadlocking) will be very useful.


You always need to know your basic data structures: how to implement sets (ordered and unordered), queues, lists, etc.

You better have a very good understanding of the hardware architecture (instruction sets, registers, hardware pushdown stacks, traps, interrupts, context-save/restores, memory maps/address spaces) or how the OS works won't make any sense, and you won't have any chance of implementing a real scheduler.

And you better be comfortable with the idea that many programs ("processes") can be executed in parallel (both simulated and for real) under and OS, and that the interactions between these processes has to be managed to prevent total chaos.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.