Introduction to NachOS

You want to build a thread system? Experiment with an OS with memory protection and virtual memory? You want to do that without a lot of rebooting, Bochs/VMWaremagic and writing drivers? Well, then Nachos (Not Another Completely Heuristic Operating System) is for you. Nachos is an Operating System simulator. Hmm… . If you’re a bit like me, you’ll be wondering what in the world that is.

Overview

I have been very interested in OSes for years and have also been an avid OSNews reader, but I had never encountered this term (or Nachos in particular) before.

In Nachos’ case Operating System simulator simply means, that you can run an OS (a guest OS) on top of another one (the host OS).
If this sounds a little like Bochs/VMWare, then you’re right, because it works similar to them. It actually features emulation for

• a CPU (a MIPS CPU)
• a hard drive
• misc. stuff like an interrupt controller, timer,…
• etc.

which are there to run the Nachos userspace applications. That means that you can actually write programs for Nachos, compile them with a real compiler (an old gcc crosscompiler that produces code for MIPS) and run them. The Nachos kernel instead is compiled to the platform of the Host OS and thus runs natively on the Host OS’ CPU.

If you are not excited about this idea (or at least mildly interested), you have to consider what this means. People interested in OSes can easily experiment with high level matters like multiprogramming, VM organization and file systems rather than fiddling around with writing a bootloader (a task which has been tackled thousands of times by aspiring Torvaldses all over the world) first. Not to mention much easier debugging; if you want to output something from inside the Nachos kernel, just use a comfortable printf, instead of having to rely on your own console code (using BIOS, VGA,…) which might not always work reliably. Not to mention that you can easily log the debugging messages of your OS (for later thorough inspection) by simply redirecting stdout of Nachos to a file on your Host OS.

Don’t get me wrong, all these low level things are of course interesting too, and fiddling around with
bits, device control registers,… are be very educational (to learn how computers really work). But,
these tasks can also be very frustrating. With Nachos you can get a somewhat high level
overview of the task of writing an OS without all the tedious details. It could be argumented, that
the low level stuff helps to weed out the meek, and only leaves the best, hardcore bit fiddlers to
OS development. But I think approaches like Nachos make it easier to get the hang of OSes without
all the cruft; with the experience from the highlevel view, it might be easier for people to do the
low level parts.

Internals

After the basics, let’s now take a look at Nachos’ internals. Nachos was (/is) written with CS
students and Operating Systems 101 courses in mind. The source is prepared for several
assignments where different parts of the system can be explored and features implemented.
I won’t go into details about the source code and it’s organization, since there is a lot of very good
documentation about that on the web; I will instead explain some Nachos internals using the assignments.

Note: This article is concerned with Nachos 3.4, as this was the version I used in my
course.

Threads assignment

This assignment is included so people can get acquainted with the source.
Nachos isn’t much of an operating
system yet; actually it’s mostly just the implementation of a userspace thread library. To avoid confusion,
we are talking about userspace from the host OS’ point of view: at this moment, Nachos is nothing
but kernel, and this kernel is multithreaded. There is not much else in the compiled binary;
the MIPS emulation is running, but it is not used. One of the tasks (for which some stub code
is already contained in the source), is the implementation of the thread synchronization facilities
Lock and Condition Variable. The other part is to implement Join functionality (ie. one thread T1 can
request to be blocked until a thread T2 terminates).

Syscalls, Multiprogramming and Memory protection assignment

This is where it gets interesting and where important OS features are implemented.
For many of theses features, there are already code stubs in the Nachos source.
There is, eg. already a fully implemented syscall in there, complete with (MIPS) code
showing how to use it from the userspace.

There is also code for the memory protection code. A class implementing code necessary
for setting up an address space and reading an executable file is already in there. What you
have to add, though, is code to properly handle the page tables for the processes and the
processes own data, like file handles etc.

This is rather spread out over different places in the code. It starts with implementing an
EXEC syscall, goes on to implementing a process table and defining process states, and
doesn’t stop with work on the address space again (eg. where do you have to put what, to
allow your applications main() function to access parameters passed in by
the EXEC syscall, ie. the argc and argv parameters. I found this rather interesting, since
you deal with these things daily, but don’t really know, how they actually work).

Virtual Memory and software-managed TLB

This assignment (the last I had to do in my course), is all about virtual memory. To be clear:
this concerns the whole swapping related parts of the memory system; ie. moving parts of the
memory from RAM to some backingstore on the systems hard disk (I mention this, since there
seems some confusion about the terms, since memory protection (with page tables,… etc.)
is also called virtual memory). There is nothing spectacular here, and no code is provided
by Nachos for this task.

The other part of this assignment is more interesting. In the previous assignment, memory protection
was implemented by use of page tables, ie. each address space had a page table in a specific
format, and at a context switch, the MIPS CPU was given a pointer to the current page table.
This is basically the method, that the x86 CPU uses. I was somewhat surprised, when I heard
about software-managed TLBs. I knew about TLBs but only in the x86 way, where they are just
a cache for the pagetable. On the x86, you don’t know about the TLB, and you actually can’t
explicitly modify it (you can only flush it using a trick, ie, changing the control register
that stores the address of the page table). Few (if any?) RISC CPUs use this approach, but
instead have a software managed TLB, where it’s the OS’ task to set the entries, and the CPU
never actually sees the page table. This approach means some considerable (not immense, but
not trivial either) change in the way the memory system works. Due to the limited size of
the TLB, the OS now has to implement the cache behaviour for the TLB (ie. the CPU needs the
page translation for page x but the TLB is full, which page translation entry can/should be thrown
out now, etc.).

Filesystem and Networks assignments

These are actually two assignments, but I haven’t done them, so I can’t talk much about them.
The file system interface is actually already available in the 2nd assignment, ie. you can use
the file system from the Nachos kernel and the userspace applications (by way of the syscall interface);
the reason is, that in that assignment, all calls to the file system are simply mapped to the
host OS’ filesystem. This is a rather useful approach, since it allows using the FS early on without
actually having to deal with sectors, cylinders etc., and if you have finished your own FS, just
one line in a Makefile has to be changed to let the kernel use it instead of the host OS’ FS.

Problems

Working with Nachos has certainly been an interesting experience… although some aspects of the
system are less than ideal.

• Code quality:
  Nachos is written in C++ … kind of. This is not modern, high level C++, but actually your
  grandfathers C++, basically C with classes. Nachos is a nice example of a software project
  that uses an OOP language, but is not even remotely object oriented. To cut a long story short,
  classes are only used to emulate namespaces (to avoid having to give function names prefixes,
  as is customary in C) and as somewhat more convenient structs.
  Neglect of OOP features isn’t the only problem with the source. There are some hacks
  in the code that just seem out of place and just aren’t good style (I won’t go into
  detail here, if you’re interested, get the code).
• User space multithreading:
  
  In the course of working through the assignments, you’ll turn Nachos into a preemptive OS.
  After you’ve done that, you’ll certainly want to show of the capabilities of your OS,
  for instance by having several applications output stuff at the same time (you know,
  application A outputs “A”, application B outputs “B” which should get you a nice
  output of something like “AABABABBBBAABABA”, depending on the implementation of your scheduler).
  
  Cool. Until you try launching several applications from a shell (a sample shell is
  provided). The problem? Well, a command line shell is basically just a process doing a
  read() call on STDIN. This call is blocking, meaning the application is
  halted until this call returns (ie. when some data is entered). Now, in a preemptive OS,
  this should not be a problem; a blocking app is simply not scheduled to run and other
  apps get their share of CPU time, nothing special about that.
  The problem is Nachos homegrown, userspace thread model. The downside of userspace threading
  is that a blocking call to an OS syscall, blocks all threads in the process’
  address space. As each process in Nachos is mapped to a Nachos thread, this means that a
  blocking call (like read()) will block the whole system, ie. all processes.
  
  This means, that you cannot have an interactive shell in Nachos to launch background
  processes and that one application invoking a blocking call will halt the whole OS.
  
  People have found ways to get around this situation, but they are only hacks and don’t solve
  the real problem. (In case you’re wondering: the trick is to use select() for
  all blocking I/O. You use select() in a loop and set a short timeout on the
  operation. If the function returns, you either have data, in which case you’ll exit the loop;
  if you don’t have any data, this means the timeout kicked in; you now call yield()
  which tells the scheduler to let other threads work. When the thread gets control again,
  you simply continue in the loop and call select() again).

Conclusion and References

Nachos is a great system for teaching OS technoloy. Its use of an emulated CPU allows very realistic
insights into the work of OS developers, while hiding some annoying low level details.

The future

Nachos is a rather old project and is in its second decade already. It shows its age, as I already mentioned,
in the Problems section of this text. Some of those problems might be solved by Nachos 5.0j, which is
a port of the C++ code to Java. One major advantage is that Nachos finally gets a 1:1 threading system
and does not have to rely on the crufty userspace threading model it has been using.

References

• Nachos’ Home. Here you can
  find several versions of the Nachos distribution and all the documentation you’ll need.
• Nachos 5.0j The
  Java version of Nachos.
• Mini Stdio for Nachos programs This is a small library including a version of printf() that can be used
  with applications that run on the Nachos OS. This will come in handy, as using the normal
  Write() syscalls is quite tedious. It might be somewhat buggy and/or incomplete, but it works.

About the Author:
“murphee (Werner Schuster) is a student at the TU Graz, Austria, where he dabbles in Software Engineering matters. His interests besides Operating Systems are anything concerning Java (mostly the Virtual Machine internals). Find his Weblog here.”