Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

thanks!

share|improve this question

migrated from stackoverflow.com Jun 23 '11 at 0:54

This question came from our site for professional and enthusiast programmers.

    
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 Jun 23 '11 at 4:08

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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