The Design and Implementation of the FreeBSD Operating System

Marshall Kirk McKusick, George V. Neville-Neil

Mentioned 5

FreeBSD - Comprehensive, up-to-date, and authoritative - truly the latest and greatest from the source!

More on

Mentioned in questions and answers.

I'm planning to write an operating system and I don't know very much about operating systems. Are there any good resources or books to read in order for me to learn? What are your recommendations?

Operating System Concepts is the book we used at University. It's quite ugly BUT the information inside are well explain (from basic memory management, to how to OS decide what to execute or how to avoid deadlock). Pretty wide.

alt text

While old, these books are very good:

Operating System Design with Xinu

alt text

Operating System Design-Internetworking With XINU, Vol. II

alt text

3: http://Operating System Design-Internetworking With XINU, Vol. II

Operating Systems Implementation Prentice Software

alt text

This book is written by Tanenbaum, the main guy behind Minix, which is what Linux was based on. It provides good overviews for basic OS concepts like memory management, file systems, processes, etc. The concepts in this book book are intimately tied to examples of the Minix OS, which is a good thing.

I think you should start by something like that.

We used Andrew Tannenbaum's Modern Operating Systems at the university I attended. I highly recommend it for it's clear explanations of the tradeoffs inherent in many of the design decisions that you'll run up against. This book is a little bit more "fair and balanced" than the Minix book.

alt text

I also recommend this book because, despite his net-famous flame war with Linus Torvalds, few of his biases come through in the book. Also, he's a pretty decent writer, and the book is actually entertaining.

I'd like to gain better knowledge of operating system internals. Process management, memory management, and stuff like that.
I was thinking of learning by getting to know either linux or BSD kernel.
Which one kernel is better for learning purposes?
What's the best place to start?
Can you recommend any good books?

There's no substitute for diving into the code. Try to find a driver or subsystem that you're interested in and poke around with it. With tools like VMware Workstation it's super easy to make whatever changes you want, snapshot the VM, and run your modified kernel. If the kernel panics on boot, who cares? Just jump back to the snapshot and fix the problem.

For books, I strongly recommend Linux Kernel Development by Robert Love. It's a wonderfully written book -- lots of information, organized sanely, and humorous... not dry reading at all.

Noting the lack of BSDs here, I figured I'd chip in:

I haven't taken any of the courses myself, but I've heard Marshall Kirk McKusick speak on other occasions, and he is really good at what he does.

And of course the BSD man pages, which are an excellent resource as they are maintained to a far greater extent than your average Linux man-page. Take for instance the uvm(9) man-page, describing the virtual memory interface in OpenBSD.

Not quite related, but I'll also recommend the video History of the Berkeley Software Distributions as it gives a nice introduction to the BSD parts of the UNIX history and culture as well as plenty of hilarious anectodes from back when.

I had previously bought these books on recommendation for the same purpose but I never got to studying them myself so only take them as second-hand advice.

In college, I had an operating systems class where we used a book by Tanenbaum. In the class, we implemented a device driver in the Minix operating system. It was a lot of fun, and we learned a lot.

One thing to note though, if you pick Minix, it is designed for learning. It is a microkernel, while Linux and BSD are a monolithic kernel, so what you learn may not be 100% translatable to be able to work with Linux or BSD, but you can still gain a lot out of it, without having to process quite as much information.

As a side note, if you've read Just for Fun, Linus actually was playing with Minix before he wrote Linux, but it just wasn't enough for his purposes.

What are some tiny open source operating systems? I'm looking for something several orders of magnitude smaller than Puppy Linux, Feather Linux, DSL, etc. I want to run a command-line text editor and compiler; anything else is extraneous. I'm looking for a system I can take apart and acquire a fairly good understanding of the whole thing in a reasonable period of time. Bonus points for something that is portable and well-documented.

I'll agree on Minix. Also the book:

is actually fairly comprehensible. (Unlike some books on similar topics, thinking of "Understanding the Linux kernel" here.) It's quite expensive, but you can probably pick up an earlier edition second-hand.

(NB. I'm not in any way affiliated with the book, it's just good :) )

OpenBSD could be a good choice, I think the default install (no X11) has something like 15 processes. FreeBSD is a close second. Either way you'll want to read "The Design and Implementation of the FreeBSD Operating System"

BTW, I've spent a considerable amount of time on AIX, Solaris, FreeBSD, and Linux... and I think the OpenBSD man pages are the best around.

My current project for an operating systems course is to design and implement a basic file system. I've read the chapters in our book about file systems, but I'm lost on where to start. I know some of the structures needed (file control blocks, system-wide open file table, per-process open file table, r+w buffers, directory structure), and the operations I need to support (open, read, write, delete, create, close).

I've been provided with a 10MB 'drive' to implement the file system inside of. Any help with resources or direct answers will be greatly appreciated.

EDIT: here's a link to the assignment

You've asked a very broad question. And it wasn't clear if you have to implement a real file system but now it looks like you need to implement a set of operations that that your prof defined.

You write:

I know some of the structures needed (file control blocks, system-wide open file table, per-process open file table, r+w buffers, directory structure)

It seems to me you're focusing on the wrong things. These are the in-memory structures used by a real operating system to support efficient access to a file system.

  • file control blocks - your version of this could be very simple
  • system-wide open file table - you don't need this to support a single user
  • per-process open file table - you only need one and it could be pretty simple.
  • r+w buffers - this is a performance enhancement, not strictly required by the assignment and can be added later if desired.
  • directory structure - ahh, now you're on to something.

I read the assignment's mention "directory structure" as referring to on-disk structure. And that's what you probably need to focus on. You're given a big block of storage and you need to hand out little pieces. So you're going to need to write a storage allocator. The hard part really is designing the on-disk structures. You'll have to track which blocks are free. Files can be deleted, so you'll wind up with holes. Two simple approaches are using a bit map or a list of continuous free spaces. Whichever approach you pick, they'll be some part of your code where you'll wish you picked the other.

You'll also need a structure to track names. When a user creates a file, he names it. To open the file later, he gives the same name. On-disk structures are required to support this. There are other meta-data as well: last modified date (your assignment specifically requires this), file size, location of data. You can use your allocator to get space to store your meta data.

It's common to have a fixed block at (or near) the beginning of your storage to hold configuration information and pointers to other storage needed to get your filesystem loaded.

For a good overview of Unix filesystem concepts, I can recommend "The Design and Implementation of the FreeBSD Operating System" by Marshall Kirk McKusick and George V. Neville-Neil, Chapter 8 Local Filesystems.

Specifically these sub-chapters:

  • 8.8. The Local Filestore
  • 8.3. Naming
  • 8.9. The Berkeley Fast Filesystem

This helps one to think separately about storage allocation and naming.

Your assignment page includes some great references. I've had a chance to look over Practical File System Design, which the author has generously posted online. I can specifically recommend these chapters:

  • Chapter 4 The Data Structures of BFS
  • Chapter 6 Allocation Policies

Plus maybe:

  • Appendix A File System Construction Kit

Maybe the problem you're having is the project seems large and overwhelming. It really helps to break it down into smaller parts. If you're still lost, start by implementing the the part you understand the best.

Let's get back to the specifics of your assignment. It mentions these filesystem constraints:

  • Files can be up to 16384 bytes in size
  • The allocation units, or blocks on the disk are each 512 bytes.
  • Your total storage area is 2-10 MB

Constraints in this context are not bad, the're good because they limit what you have to deal with and allow you to cut a few corners. (I'm not saying any more because figuring out the details is the point of your assignment.)

If you're still stuck, you could read the source code to a simple file system like FAT. Here's a pretty accessible description of FAT:

(Also check out Wikipedia.)

Here's a link to a C implementation of FAT intended for embedded applications:

The source code is only about 5K lines.

Good luck.

For example, a process waiting for disk I/O to complete will sleep on the address of the buffer header corresponding to the data being transferred. When the interrupt routine for the disk driver notes that the transfer is complete, it calls wakeup on the buffer header. The interrupt uses the kernel stack for whatever process happened to be running at the time, and the wakeup is done from that system process.

Can you please explain the last line in the paragraph which I have emphasised. It is about waking up the process which has been waiting for some event to occur and thus has slept. This para is from Galvin. By the way can you suggest some good book or link for studying unix operating systems?


There is some process running at the time the interrupt is received. The kernel doesn't change over to some other process context to handle it -- that would take time -- it just does what's necessary in the current context, and lets the scheduler know that the next time it schedules, the waiting process is ready to proceed.

There are a number of good internals books around. I'm fond of the various McKusick et al books, like The Design and Implementation of the FreeBSD Operating System.

Maurice Bach's Design of the Unix Operating System is the most well-known and comprehensive book on the subject.