teaching operating systems with source code UNIX

by Bob Gray
<bob@cs.colorado.edu>

Bob Gray is co-founder of Boulder Labs, a software consulting company. Designing architec-tures for performance has been his focus ever since he built an image processor system on UNIX in the late 1970s. He has a Ph.D. in computer science from the University of Colorado.

Thanks to Charles B Morrey, Art Messal, Mike Durian, Steve Gaede, and the students of OS3753.

It's early April and the end of spring break at the University of Colorado. I have a couple more days before the next lecture to finish grading the programming project that illustrates a file's on-disk layout. I also must work through the next project — implementing "undelete" in the kernel before assigning it to 95 college juniors.

Back in December, the computer science chair asked me to teach the undergraduate operating-systems course. I asked what resources were available to me and was offered a set of notes from the previous semester. That course's homework was based on binary-only Windows NT. I inspected the material and found the assignments were just "userland" programming projects.

I chose to teach the course using a source-code, production operating system. This article discusses the advantages and disadvantages of my decision. I'll outline a couple of the programming projects, with the lessons learned, and I'll pass along some of the students' comments. The course assignments and solutions are posted at <http://boulderlabs.com/os3753>.

Introduction

A long time ago, my undergraduate operating-systems class required that we cross-compile a small, standalone system and upload it to a PDP-11 minicomputer. We could do some limited debugging at the console if the program didn't crash. The development environment was poor; it was painful and time-consuming to get things working, but the experience was an overall confidence builder. I feel there is a huge advantage for a student to control the operations of a computer directly.

Another approach for teaching operating systems is to provide a controlled runtime and development environment using a simulator. Several universities teach operating-system concepts using the Nachos simulator (<http://www.cs.washington.edu/homes/tom/nachos>). The advantage is that the instructor can easily control much of the environment for assignments, and the students don't waste time with crashes, kernel builds, and rebooting. These kinds of systems can be very simplistic and lack realism.

As a private pilot, I know that aviation simulation goes only so far. You need to spend some time in the sky, in the air-traffic-control system, in the weather, and with the attendant dangers, to absorb and appreciate the training fully. A two-hour actual flight lesson is often fatiguing and draining; but the same amount of time in a simulator is more like a classroom experience. Similarly, students sense the difference between working in a safe simulator environment and working on a real kernel. Lessons with the latter seem more dramatic.

Source-Code Operating-System Course

The theory and concepts of operating systems at an undergraduate level are not difficult or time-consuming. We quickly covered them with the excellent textbook by Silberschatz and Galvin, Operating System Concepts (Wiley, 1999). The implementation is the difficult part, and I claim that until someone actually digs into the code, they haven't fully learned the important stuff.

I wanted my students to gain an appreciation of how "it really works"; therefore, a source-code operating system was required. Most students have an Intel-compatible personal computer, so any of the Linux or BSD distribution would have been fine. I standardized my class on FreeBSD, thanks to a donation of 100 CD-ROM sets from Walnut Creek CDROM (<http://www.cdrom.com>).

Some students groaned about loading another operating system onto their machines, but firmly restating my plan and handing each of them a new four-disk package quickly ended the discussion. I wouldn't want to introduce more complexity in the course by encouraging variations. The university supplied a few old Pentiums for several students who didn't have equipment. For them, we installed big disks so that a couple of students could share a machine and still each have their own, unique disk partition.

The first operating-system project was to load the system and configure a custom kernel for their hardware. For most, the project was fairly easy, but given all of the variations of cheap PC hardware, a number of problems arose. A high percentage of the class needed to split their Win9x partition to make room for UNIX. Some older BIOSes have the constraint that you cannot boot an operating system if it is beyond cylinder 1023 or beyond 8GB. Also, there were the usual difficulties with various graphic chips and certain Plug'n'Play hardware.

After two weeks, almost all students had completed the first assignment and were running solid systems. My role in assisting in their success was to provide written resources and some of my time. I offered to help overcome loading problems if the students would carry their PCs to an on-campus lab. (They didn't have to carry their monitors.) I enlisted the help of several friends and system administrators to accelerate the process of handling all of the weird or problematic machines. Bringing up 95 machines was a lot of work for me and some of the students.

For each programming assignment, I've asked the students to submit a report containing these sections: Introduction, Methodology, Analysis, and Summary. The idea is to put on paper the essence of the project — their target audience is former operating-system students. They include enough information that, armed with the assignment specification sheet, some other competent programmer could obtain the same results.

I encourage students to speculate on what is going on in the system and to substantiate their hypotheses with measurements. If they don't have the time or resources to investigate certain phenomena, I ask them to at least suggest additional experiments that could help describe the system.

Even though I have a teaching assistant and a grader for my course, I also read the students' reports. I'm delighted when some of them make subtle observations or raise interesting questions. Sometimes I find logical thinking and reasoning but incorrect conclusions. For these situations, I point out the problem and try to get them back on track. Here's where the ratio of students to instructor is crucial — there must be enough time to understand the difficulties and to handle them.

More than once, I had handfuls of students with the same inappropriate mental model. Because they have gone to the trouble of explaining the model on paper, it is both easy and dramatic to cover the misconceptions in a lecture. For example, some students observed that the filesystem block addresses were increasing by 8 for sequential pieces of a file. They hypothesized that the file system block layout was "interleaved" to allow time for disk-controller set-up between I/O requests without losing a revolution. I pointed out that "interleaving" is no longer necessary with today's disk controllers, which are always reading into their hardware caches. So even if a request for a sector occurs after it passes under the reading head, the data will be immediately transferred to the computer. The address jumps actually represented contiguous blocks — the FFS allocates blocks in 8KB pieces, addressable in 1KB units.

Because production operating systems have been highly optimized, it is a challenge to create student projects that are useful, interesting, nontrivial, but not too hard. Much of the kernel code base is superfluous to the important course concepts and can overwhelm individuals. I'd say that this is the main disadvantage of my approach. However, I found that by working a solution beforehand, I was able to guide students along a productive path and save them from numerous traps. As necessary, I provided code fragments or other hints to focus their efforts. Most students seemed to enjoy the challenge of working in the kernel, even though it turned out to be time-consuming.

Kernel Instrumentation Project

One of the early projects involved inserting instrumentation into the kernel, running a synthetic load, and analyzing the results. We measured the time to create a new process (fork) and observed what factors influenced the event. Students learned about the high-resolution timer available on PCs and gained some knowledge about statistics. In the kernel, they learned about the cost of copying a process's environment and how to add instrumentation wherever needed. Here is a typical student summary (given with permission):

From this exercise I have learned quite a bit about the creation of a new process and how it is added to the runnable queue. It appears that the creation process takes generally the same amount of time for each process. . . . When doing this assignment, I wondered if the forking process takes longer when more CPU intense programs are running. If I had more time, I would investigate the question by creating tight algorithms that hog the CPU. If I had more time, I would also like to check the time for each individual subroutine calls of the fork1 function to determine what takes the most time. By doing so I could also determine which ones remain completely constant and which ones vary slightly. This would help pinpoint the important parts in the fork process.

File System Project

The latest project required that the students print the filesystem block address for selected files. They had to learn a lot in a short amount of time. Their main resources were include files and man pages. A gratifying part of teaching is reading student conclusions such as the following:

The FreeBSD file system is a complicated beast when you first look at the source code. However, as you page though the seemingly endless code, man pages, and header files, the logical structure emerges. Along the way, I encountered several problems that I still do not understand. . . . This assignment was a great learning experience, however, it was, by far, the most time consuming task I've encountered in this class.

In general, the Berkeley Fast File System seems to be a great performer, lumping large portions of files together contiguously in order to try to minimize the number of I/O operations required to read them. Also, only a very small percentage of disk space is wasted in indexing these block addresses. Random (direct) access to disk blocks and sectors is very efficient, requiring only 3 I/O operations at most to get to any given disk block. There is less external file fragmentation since portions of files can reside in any size hole, and very little internal fragmentation since each filesystem block can be broken down into fragments which are each individually addressable. This is leaps and bounds better than pure linked allocation or pure contiguous allocation. UNIX provides an efficient file system that can be navigated to explore how and where files are stored on disk. I followed the steps listed in the assignment closely and found it hard to understand everything I was seeing, but having to explore and interpret the file system on my own increased my confidence to explore a complex OS. This was a pretty cool assignment, I don't think that I've ever read as many man pages and header files. It is interesting that with operator privilege you can get in otherwise "permission-protected" files. In summary this was a good exercise to enhance one's understanding of how the raw disk management of a file takes place. It is so easy [to forget that] behind the glitz and glamour of Window's and Linux's flashy GUIs and program managers all of those files are actually just strips of magnetically encoded information on a series of spinning disks. It would be interesting to conduct tests to see how the results of our program would differ as a disk's fragmentation level increased, as contrasted with a freshly defragged disk.

Virtual-Memory Project

For one project, I had the students add kernel code to capture information about page faults. I then supplied three "mystery" binary programs, and I asked them to figure out what was going on with respect to the virtual-memory system. Here are a couple of pieces of their summaries:

I found this assignment to be eye-opening. The virtual memory concepts were always abstract in my mind, but now that I've seen the graphic representation of its behavior, it makes much more sense. In fact, now I wonder why I had such a complicated mental image before.

In doing this lab, I learned quite a bit about the virtual memory system and how to analyze programs. I found this assignment very interesting and helpful to my diagnosis skills. By looking at the three mystery programs, I could see how the operating system deals with the access of variables and it was much more complicated than I imagined. From program 1, I was able to observe sequential accesses coming from possibly three different arrays or possibly a recursive call. From program 2, I was able to observe an array that was quite high in the stack and must have had other values that were initialized before it. Finally in the third program I was able to observe random access followed by a backwards sequential access of a different array. If I had more time, I would like to find more about the gaps in my graphs which were probably due to interrupts and disk accesses. I would also like to find out what each program accessed near the 16000 and near the 79000 range. From what I can tell it must be some type of overhead that the operating system has to go through with a process.

In summary I can say that this was a very successful experiment. By placing instrumentation into the kernel we were able to confirm some of what we know about how the contents of a program are laid out in memory. The text and global data segments are in the lower part of memory with the heap growing upward from there and the stack sits in the highest memory and grows downward. It is important to note, however that virtual address space is different [from] the physical address space. The pages that we were looking at could be anywhere in physical memory and do not have to be laid out in such a nice order as implied by our graphs. It was most interesting to try and create a program that attempted to simulate what some of the program had done. It was this experimentation that gave me the most insight into the differences in a global variable and a local variable, the heap and the stack, and where the code segment lies.

This assignment was the best learning experience yet. I read a lot about VM, and was reminded of the fact that "main" is just another function with its own stack for its own "local" variables. I tend to think of main's variables as global, but they do reside on the stack — as the graph of my own thrasher showed. It would seem that only those variables declared outside of main appear low in memory, and all others reside on the stack.

Summary

I feel that my approach of using source code UNIX has been successful for both teaching operating-system concepts and for building confidence for working in a large code base. Before the class started, I had expected enrollment to drop once the students learned how much work was expected. Instead, word got around that this semester's course was going to be substantially different from the previous systems-programming course, and enrollment increased 15%. Any course that requires programming suggests a lot of work for both the instructor and the students. I've gained a lot from this experience and I suspect the same is true for many of my students. Next time there is the opportunity, I'll again employ source code UNIX for teaching operating systems.