I’m teaching a small Advanced Operating Systems course this spring. Preparing for the course over winter break, I spent some time reading various Linux subsystems such as the scheduler, and was a bit shocked at how complex it has become. I’ve been using Linux, looking at its code, and occasionally hacking it for more than 20 years, and it seems that my impression of it as a fairly simple, easy-to-follow kernel has become badly out of date. It’s not that this glorious 7991-line file is impossible to understand, but rather that it — along with the other 16,000 lines of code in the kernel/sched directory — isn’t obviously the correct thing to inflict on some undergrads who are interested enough in operating systems to take a second course.
While looking around for alternatives I tried out xv6, which I had known about for a while but hadn’t looked at closely. xv6 is a rewrite of v6 UNIX in modern C that runs on multicore x86 chips. It compiles in a couple of seconds and is trivial to boot up in QEMU. It took me a while to see the genius of xv6, which is that it is simpler than I would have thought a working multicore OS with shell and filesystem could be. For example, it lacks wait queues and ready queues — in xv6, both wakeup and scheduling are accomplished by looping over the all-process table. Similarly, there’s no malloc() in the kernel, but rather just a page allocator. The pipe implementation copies one byte at a time. Amazingly, even the bootloader is a pleasure to read. Another nice thing about xv6 is that it comes with a short textbook that explains OS concepts in terms of their implementations in xv6.
So what did we do with xv6 beside read it? One exercise was to speed up its pipe implementation as much as possible while preserving UNIX semantics. This turned out to be a really nice exercise (I thought). It is fairly easy to get within a factor of two of Linux pipe throughput on a two-core VM. We implemented a ring buffer for zero-copy bulk data transfer between processes. Finally, we added priorities and ready queues.
I have no real complaints about xv6: the code is clean and commented, the functions are small, and overall it makes a great instructional OS. The look and feel are very similar to what I remember from hacking on Minix when I took an advanced OS class around 1994. Actually I do have one small complaint, which is that in a few places liberties are taken with error checking. For example, in the allocuvm() function from vm.c, which grows a process, there is a call to mappages() that mysteriously fails to check the return value. Is there some reason that this particular call cannot fail? If so, a comment explaining the reasoning is needed. If not, error checking is required. I’m sensitive about this issue since I tell the students over and over that they cannot ignore failures in this kind of code.
Another OS that we’ve been learning from is the Windows 2000 kernel which is — surprisingly, to many people — a simple and elegant multicore OS that provides some real-world contrast to xv6’s over-simplicity. I haven’t seen any Windows kernels later than 2000, I’d be curious to hear if they have remained so nice.
15 responses to “xv6”
How did you get the Windows 2000 source code?
Hi Sam, parts of Win2k (including the parts I wanted to look at) were leaked some time ago, it’s not too hard to find a copy on the web.
You can also get the most of the source under an academic license officially from: https://www.facultyresourcecenter.com/curriculum/pfv.aspx?ID=7366&c1=en-us&c2=0 …
Dan, thanks, I didn’t know about this!
It probably depends a lot on what your course schedule is ought to include. For instance, is it studying a ready-made operating system internals, or extensively tinkering, or implementing your own?
Last time I looked at Xv6 (this is quite a while ago) I got the feeling it really is a v6 reimplementation – including almost complete lack of concepts of multiprocessor and virtual memory subsystems. It is not that realistic for a modern OS, unless your course leans towards embedded systems. For real-world, complete system with less complexity than Linux kernel, I’d probably try to find old enough version of BSD variants. Sufficiently old versions can be supported by reading McKusick et al. The Design and Implementation of [Free]BSD Operating System, yet also include VM and at least “giant lock” SMP. Of course, even old BSDs are much more complex than Xv6…
If you’re after “build your own” course, my personal, biased preference has been Buenos (http://www.niksula.hut.fi/~buenos/buenos.html), which is built as a sort of a “proper” replacement for (in)famous Nachos operating system. In it, large portions of operating system are left to exercise for students. It is paired with somewhat simplistic MIPS32 virtual machine, but was really built ground up to include concepts of modern multiprocessing and virtual memory. You have to understand the goal of this OS, though: implementation of virtual memory is mostly left as an exercise. Browsing through the roadmap and exercises in there is worth the effort.
Have you looked at the Minix 3 by any chance? It lifts a lot from NetBSD (which makes it more usable than the previous incarnations were) but at the same time its core components are easy to read and follow.
Having a look at ReactOS wouldn’t be a bad idea either. It’s an open source OS implemented to provide binary compatibility with the NT kernel.
It’s very well documented and there quite a few talks about it on the net.
Hi Dominik, I haven’t looked at Minix since 1.x, you’re right that I should look again.
jag, I just spent a little while reading some of the ReactOS kernel (the scheduler) and it is amazingly similar to the NT scheduler. I mean, many of the internal function calls and data structures have the same names between the two OSes. The implementation is *very* similar. Is this really a cleanroom re-implementation? Maybe that phrase does not mean what I think it means.
“I’m sensitive about this issue since I tell the students over and over that they cannot ignore failures in this kind of code.”
And yet, here’s a system that does, so maybe you can. I’ve worked on production systems for 10 years and people ignore errors all over the place. Can people not ignore these because it will have some meaningful benefit to them or their users, or because the ghost of Dijkstra says so?
If it can fail, then why not write a program that shows the students how it fails, i.e., a functional test? That will be more memorable than just telling them 100 times. Or make it a student assignment to make it fail because of this omitted check.
Otherwise, hearing “You should always check return values” comes across as sounding like “You should eat 5 servings of vegetables a day”. College kids will think, “I’ve been living on mac-and-cheese, and ignoring C stdlib error flags, and it’s never once caused a problem. Professor is just being paranoid.” Then they’ll file it away in their brain under “Useless, well-intentioned but.”
P.S., your blog has 13 script tags. Do all of them check for every possible error condition?
Hi Devil, of course I do not always check error codes. What I do is make a reasonable judgement for a given situation about whether checking them is worthwhile. And the more nuanced version of what I said in the post is that I teach students to do the same thing. Making an informed decision not to check for malloc() returning NULL is very different from being incapable of dealing with error conditions in a systematic way. I hope your colleagues for the last 10 years are doing the first one and not the second.
Regarding the test case, you have a good point, but my sense is that the stress testing that would be required to make this particular call fail would make all sorts of other stuff fail first — this isn’t a production-grade OS by any means.
Have you looked at Genode OS by any chance? Would love to hear your comments.
http://genode.org/
Why do they write something like that in C? Should we be giving up on C altogether? What is the alternative?
A potential alternate higher level companion book that explains the concepts of an os quite well might be Operating Systems: Three Easy Pieces. It hits everything and does so in a light, non terrifying manner. Additionally, its available for free online, is updated fairly often, and is broken into easily digestible morsels. Perhaps something to recommend if students are looking for a higher view before diving into the code?
I think another research/teaching OS which is fairly simple to understand is Xinu. I don think Xinu has multi core support yet, but I did my operating systems course and then TAed for the same course, we used Xinu in both cases ( though on different platforms ). Very similar to Xv6, it is very simple to understand and comes with a (not free ) textbook.
Another possibility to look into is Bryan Ford’s PIOS, which is a microkernel system derived from his Determinator work. It’s about half the size of xv6, but by the end of a course, the system can run on multi-node clusters. The fact that it diverges somewhat from the traditional Unix mold might be a pro or a con, depending on your goals.