Instructor’s Guide for

Crowley’s Operating Systems Book

In this document I will clarify some aspects of the text that I think may be unclear, particularly some of the problems at the end of the chapters. In addition, I will discuss points that I think will add to the text. This reflects some changes in how I view these issues since the book was written

I tried to make the problems as good as I could but naturally some are better than others. In the section on each chapter, I will give you my rating of the problems. I rate highly problems that test whether the student understands some important point from the chapter.

Chapter 1

Chapter 1 is the overview and shows the three levels (User, OS, and hardware). Chapter 2 discusses the hardware interface the operating system is built on. Chapter 3 discusses the operating system interface to the user programs that the operating system implements. The rest of the book discusses the implementation of this interface.

Problem 1 (page 14). Some students have trouble understanding exactly what problem 1 is asking. They sometime think that the operating system loaded into a process in part a is somehow controlling the physical resources of the machine instead of the virtual resources provided by the underlying operating system.

Chapter 2

I was hesitant to define an imaginary machine (the CRA-1) for this book. I finally decided to do so because I wanted to show the details of process switching in chapter 5 and this is only possible with a specific machine. I avoided a real machine because of the complexity involved. An unfortunate side-effect of this choice is that code in chapter 5 does not have a simulator. I had to eliminate the machine dependencies in order to develop a simulator. There is more discussion about this in the notes on chapter 5.

Some students except that the "asm block" construct I describe on page 19 is a standard C feature. Some compilers do have similar facilities but most do not.

Some students are not clear on what "masking" an interrupt means (page 21). They should know that a masked interrupt is still recorded but it is prevented from occurring immediately. It will occur as soon as interrupts are enabled again (that is, unmasked).

Problem 1 (page 24). This problem is badly worded for what I wanted to get at. It should be two questions. (a) Why is there always more physical address space than physical memory? (b) Why is there usually less physical memory than memory address space?

Problem 8 (page 24). Some students find this problem hard to understand. The second and third questions ask if the specification of the hardware were changed to that the base and bound registers were used in system mode what problems would occur in building an operating system and how would we have to further modify the specification of the hardware to get a practical system.

Chapter 3

Many students coming into an OS class have never used system calls so I feel it is useful to spend some time introducing them to system calls and give them some experience using them. We also introduce several important OS concepts in this chapter.

The difference between a file and an open file is new to most students and it is important that they understand it. It introduces the idea of OS objects and appropriate operations on them. It also is a good example of the static/dynamic distinction which is common in all areas of computer science.

The program/process distinction is another example of the same static/dynamic distinction. The students need to understand what a process is since it is the most basic concept in operating systems.

Another important concept in this chapter is naming. The students need to understand the importance of naming and the different types of names that are possible. They should understand than objects can be given any type of name depending on what you want to do with them. I switched naming styles for the various objects I introduce (files, open files, processes, messages queues, and pipes). Some students think that message queues must have global, integer names and pipes must have character string names in the file system. They need to learn to distinguish the object from the name of the object.

Another important concept in the chapter is unification of the device and file interfaces. The students should understand that it is the interfaces that are being unified not the concepts themselves.

We introduce messages and pipes as alternative forms of IPC to show the students that there are different ways the same functionality can be packaged.

Problem 5 (page 74) By "differences between opening a file and opening a device" I mean differences in how the OS handles the two opens, that is, what different actions it will take. Making the open call will be the same in both cases because the file and device interfaces are unified.

Problem 20 (page 76). The answer should include timings of the two programs. In UNIX the "time" command can be used to get execution times. Some students need help understanding the output of "time". The "size" command can be used to find the size of a program. Just looking at the size of the executable is not sufficient since it may include symbols. The "which" command can be used to find the system "cp" program. By "robustness" I mean how resistant it is to errors and erroneous input (such as empty files, disk full errors, copying a file to itself, nonexistent files, etc.)

Some students need some help getting this program working. Prototypes for open, creat, read, write, and close are needed. These can just be inserted at the beginning of the program and gotten from the appropriate include files. The system calls are in the C++ library and so the linking should work without any special library specifications.

Chapter 4

This is the first design chapter. It begins by covering the design process and how the design techniques in this book fit into it. Students see some of this in software engineering. Two-level implementation is the most important and most useful design pattern presented in this chapter.

Problem 8 (pages 114-115). This problem is badly worded in places. The idea is that we want to try to write a library that converts one kind of system call to another. When I say "the library routines contain only calls in IOSetB" (in line 8 on page 115) I mean that you can only use system calls from IOSetB and no other system calls. You can use other programming language features like structures, arrays, variables, loops, if statements, etc. Anything is allowed but other system calls.

Chapter 5

This chapter shows code for a simple operating system in detail. I have found that it is very useful for students to go through this code and understand it completely. In the midterm exam I ask detailed questions about the code, things like what errors would occur if a particular line were eliminated. By seeing the details of the code the students start to understand exactly what an operating system is really doing. They tend to ask questions they would not think to ask if we had covered the basic operation of the OS at a higher level. I have found that students do not have that much trouble understanding the code.

The code in the book was not tested directly. A modified version of the code was tested using the MIPS simulator and the Java version was simulated using the Java simulator. So there are errors in some of the code that accesses the basic hardware (and the uses of queues) and there are some bugs that don’t affect the running of the system. See the Errata for these.

There is a bug regarding program loading that is hard to fix. Program loading uses the disk with no disk interrupts but it doesn’t check to see if the disk is already in use by the disk driver. I changed to code to check for that and wait but still the disk interrupt will be lost. The real solution is to use the disk driver to read in the process image but this requires a fair amount of machinery to keep track of the disk interrupts and the program loading and to return from the create process system call at the right time.

Note the typo in problem 4 (page 170).

Some students have trouble with problem 14 (pages 171-172). In order to make the problem simpler, I reserved the use of the timer for this problem. You can assume that you have a timer that works exactly like the one in described in chapter 2. You have exclusive use of this timer (assume there is another one that the dispatcher will use). You have to redefine the timer interrupt. The solution requires two pieces of code. The code to handle the new system call and the new version of the timer interrupt handler. Call the new system call "Sleep". Looping in the system call waiting for the timer to get to 0 is not a solution. Assume that there might be several timers counting down at the same time. This problem is essentially multiplexing the timer. The timer is really another resource that we did not talk about in chapter 1.

Some students need help getting the code in problem 15 (page 172) running. They need to include a prototype for "getpid". They should make two versions of the program and compile, run and time each one. Use the "time" command for timing. Experiment with the right number of iteration to make the time long enough to be accurate.

Chapter 6

In chapter 6 we look at parallelism at the operating system level and in chapter 7 we look at parallelism at the user level. Many of the same problems come up in both chapters but different solutions are used in the two cases. In particular, the OS level uses simple solutions using the hardware directly and the user level depends on the primitives provided by the system level.

The problem solved in this chapter is how to port the Simple OS to a two-processor system. In the course of doing that we encounter the typical problems of parallelism.

Threads are the software version of multiple processors and so they are discussed next and we show how to implement threads in the SOS. Kernel-mode processes are really threads in the kernel and are also a traditional implementation technique for UNIX systems.

In order to get problem 2 (page 225) students have to understand the details of how interrupts work, in particular, that an interrupt can be requested even though interrupts are masked. The interrupt stays pending until interrupts are enabled again (or until the interrupt is canceled).

In problem 22, it is important to be precise because subtle errors crop up in synchronization problems. Showing the code for the solution is necessary.

Chapter 7

Chapter 7 is not directly about operating systems. It is about how to effectively use the IPC primitives an operating system provides. Most students have little experience with parallel programming. This chapter shows them some typical ways that parallel processes communicate. Students will certainly encounter thread programming and need these skills.

The chapter also introduces the idea of patterns as general solutions to typical problems.

Finally these patterns are often used in operating systems too.

Chapter 8

Chapter 8 covers a variety of additional topics about processes that need to be covered. It doesn’t have a single unified theme.

We start with scheduling. Scheduling used to be given more time in OS courses but almost all OSs now use a multiple-level-queue system. So we cover the topic briefly here. We start with a motivating section about scheduling in real-world situations.

The students should study figure 8.4 carefully. This shows graphically how processes that block on an I/O system call leave the processor scheduling system and return, after the I/O is complete, as "new" jobs in the processor scheduling system.

The policy versus mechanism dichotomy is important in operating systems and should be stressed. Scheduling is a good place to see the differences clearly.

Students should be aware of the issues in deadlock and starvation because these issues come up frequently.

It is important to understand RPC. The instructor could talk about object broker systems here (that is, CORBA) because they are basically RPCs for object methods.

It is useful to see some other synchronization methods and compare them with messages. Of course, all computer science students should know about semaphores and monitors. It is useful to see the same synchronization problems solved with the various synchronization primitives. This gives them an important lesson in how there are various ways to solve a problem, each with good and bad points.

The section on the implementation and use of semaphores in the SOS is optional.

I also cover the Ada95 synchronization primitives because they are interesting and show yet another approach to the problem. This section is optional.

Problem 18 is somewhat ambiguous (although I think it is a good problem for students to work on). If you assign it make it clear than only one process can reach age 10 at a time. When it does all other processes in stage 1 must release all their locks but their age does not increase (so none of them reach 10 also). Also, only one process at a time can increase it’s age so it is not possible for two processes to reach age 10 simultaneously. One way to think of this is that increasing the age is a critical section and only one process at a time can do it.

Chapter 9

Indirection is probably the single most useful design technique of all. Indirection always adds flexibility. Adding a level of indirection is the first solution you should look for when presented with a design problem.

Reducing a problem to a special case is also a common design technique that is used very frequently.

The main point of using models for inspiration is to not use models to prove that an idea will work. Models are used for generating ideas. So you never have to justify the use of a model. If the ideas it generates are useful then the model is good. It does not have to be "correct."

Adding a new facility is the most uncommonly stated design technique in the book (I have never seen anything like it anywhere else) but it can be used in most design situations. The point is that it is useful as a guide for generating new design solutions to try.

Chapter 10

Chapter 10 covers several topics related to memory management and leads up to the development of paging in chapter 11. First we distinguish between per-process memory management and OS memory management. Often students get these two confused. They should see that the basic problem is the same at each level but the design requirements are different and so different solutions are required.

This is a good place to talk about object modules, load modules, linking and loading. Many students will have already seen this but many will not have so it is useful to cover it. This leads to dynamic loading which most students have not seen before.

We present the general dynamic memory management problem even though operating systems always use specialized versions of this. It is a good design analysis example. We present SOS code for this in case students have not seen (or programmed) this problem before.

Chapter 11

The main point of chapter 11 is to describe the design process that leads to modern paging systems. We present the problem (fragmentation) and go through a series of solutions. Each solution gets better and solves a problem with the previous solution but causes a new problem.

Students should be clear on the idea of contiguous address spaces and the difference between contiguous logical address spaces and contiguous physical address spaces.

It is important for students to understand TLBs, how they work and why they are important. This is yet another example of caching.

I cover the historical techniques of swapping and overlays because I think students should have exposure to them. The ideas crop up in other places and undoubtedly will come back again in other forms.

I think it is important for students to realize how infrequent page faults have to be in order for the system to be feasible.

It is also useful for students to understand the mechanics of paging, that is, what operating systems do on each paging event.

File mapping is found in nearly every operating system now and students should understand it and realize its advantages

Chapter 12

The various approximations of LRU and working set are good examples of engineering.

The working set concept is the most important one of the chapter. This is just another example of the principle of locality. WSClock is a clever algorithm.

Another interesting point is that a dumb algorithm (like FIFO) combined with a standby list is just as good as a sophisticated paging algorithm.

The development of paging algorithms is an excellent example of computer science. Researchers developed a series of models of a real-world phenomenon (page referencing behavior). Each model was better than the previous one.

Thrashing is an interesting concept that shows up in other places, whenever you have a positive-feedback cycle.

The future of paging is with very large address spaces. One-level paging is just not adequate any more. There is presently a lot of research on the best organization for very large page tables.

It is important to understand segmentation even though it only exists now in paged segments which are not in the spirit of true segmentation but really a variation on two-level paging.

Chapter 13

Multiplexing describes how to share resources. Students should clearly understand the differences between time and space multiplexing.

Late binding, static versus dynamic, and space-time tradeoffs all have to do with efficiency and are all related. Binding time is the most basic concept. Static is early binding and dynamic is late binding. Trading space for time is often associated with early binding and trading time for space is often associated with late binding.

Binding time is an important concept in programming languages as well as operating systems. In programming languages we have eager and lazy evaluation. Lazy languages allow computation with infinite objects. The lazy concept in general is often an effective optimization technique. In general, binding time issues allow us to choose when a computation will take place.

Static and dynamic is the most common dividing line between early and late binding. It is an important concept in many areas of operating systems and computer science.

Space-time tradeoffs relate to the fundamental dichotomy between space and time, storage and computation, noun and verb.

I included the section on simple analytic models to get students used to the idea of using theory to gain insight into systems and their behavior. Students should be able to do simple "back of the envelope" calculations to see if a design solution is feasible.

Chapter 14

The purpose of chapter 14 is to familiarize students with the various types of devices that an operating system has to manage. Students will often know some of this material and you can often cover it quickly. It also is a good introduction to several design techniques.

Terminals are rapidly becoming obsolete but I include them because it will be years before terminal emulators are obsolete. It is a good example of using emulation to protect your investment in old software. Also the event model is built into modern GUI systems. Also it is useful for students to see how keyboard events are interpreted and turned into typed characters. This will help to understand, for example, the Java AWT model of keyboard event (three events: key down, key up, key typed).

Modern graphics devices are basically fancy terminals and it is useful for students to understand the difference between the screen and the controller and why we have both of them. Color maps will be obsolete in a few years.

I like to emphasize the emulator aspect because the students will have worked with terminal emulators and, most likely, PPP and it is useful to understand what exactly they are doing behind the scenes.

Students may have seen disks explained before but maybe not RAID. You can expand on the RAID coverage if you want (I plan to in the next edition).

Finally it is useful to understand what SCSI is.

Chapter 15

Basically the whole story here is device drivers. Device drivers are the core of the I/O system. There is some device-independent code but not that much. Students should understand the role of device drivers and device driver interfaces. This is something anyone who uses an operating system should know something about.

Disk scheduling is interesting but often not really that important since it is not common to have a large queue of waiting disk requests. An important idea is that of disk models and how they affect the analysis of the scheduling algorithms.

We get to see in this chapter how the unification of devices and files is accomplished.

The concept of device drivers constructing various virtual (that is, false) images of the real hardware is interesting and helps students understand again how software can transform hardware in many ways.

Disk caching has traditionally been the most important optimization in an operating system. These days it is being taken over by file mapping and the paging systems but it is still useful to study the concept separately.

Chapter 16

Many students will be familiar with most of the material on file naming but it is useful to record it systematically here. Most students will not be familiar with the typical file system operations.

The file system data structures described here are based on those used in UNIX but any operating system will need similar data structures. I think it is useful to understand figures 16.12 and 16.13 and see the flow of control of a file system call. This shows how the data structures work together. Figures 16.15 through 16.19 should complete this picture.

The sections on how to connect device drivers to special files and the handling of special files are useful so that students will understand how this works and the importance of tables in an operating system.

Directory implementation is straightforward but it is useful to do through the algorithm quickly.

Going through the implementation code at the end of the chapter will solidify the student’s understanding of file system implementation but you may want to skip it in the interest of time.

Chapter 17

This is another area where the information is quite practical. System managers need to know about file systems and file system layouts. Modern computer systems are networked and create a user’s file name space using network mounts. It is useful for students to understand how the naming hierarchies from various file systems are combined.

The details of how file blocks are stored on disk is interesting and shows some useful engineering techniques (like making it work for large and small files efficiently). It shows several standard data structuring techniques in a different context.

Many students will not have seen how booting works before. Backups and file system consistency checkers are concepts that all computer scientists should understand.

Chapter 18

This is the last design chapter. We have seen a lot of design techniques so far.

Caching is the most powerful optimization technique available. It depends on locality to work well. Students should understand the issues of cache invalidation. This leads to the concept of hints which is alos powerful but not as widely used or discussed as caching.

Hierarchical naming systems are so powerful that they are almost the only type used. I also discuss some general topics in the area of naming.

Chapter 19

Chapter 19 covers several topics in resource management. Some of these topics we have seen before but here we try to treat them in a unified way to show resource management in the entire operating systems.

We look briefly at queuing theory which allows us to mathematically model some aspects of resource scheduling. We present this as some simple analytic models that can help us gain insight into how our scheduling systems will perform. We also briefly mention scheduling in real-time operating systems.

The second part of the chapter is a unified presentation of protection and security in operating systems. We look at the important concepts of authentication and authorization. We look at the hardware an software structure that make up the protection system.

Access control lists are a common method of protection (since they are used in Windows NT) and students should understand how they work. Students should also understand the concept of a protection domain. Students should also understand the basic issues in Trojan horse attacks (related to protection domains) and the confinement problem.

Protection is another area where the distinction between mechanism and policy is very important.

Finally we briefly cover some issues in cryptography and how it can be used for authentication. All students should understand the basic ideas of cryptography and public-key cryptosystems.

Chapter 20

Chapter 20 introduces the idea of system processes and micro-kernel operating systems. The code for making the disk driver a system process shows how easy this is to do. This is a nice unification of system calls and messages so messages are the only way a process communicates with the world outside the process. It removes the difference between the operating system and other processes. They are both servers that provide services to the process. We end by looking very briefly at networked and distributed operating systems.

Good: 3, 5, 10, 11, 12