holliday@duke.cs.duke.edu (Mark A. Holliday) (05/16/88)
I have taught the undergraduate operating system course here at Duke University for the last two semesters using Professor Tanenbaum's textbook and the MINIX operating system. Below I describe my impressions. My comments are fairly lengthy. The main points are 1) the textbook is very well-written, but the "concepts" sections should be longer, and 2) MINIX is a major advance as a base for operating system class projects, but use of the PC simulator for initial debugging appears very important (and thus, I recommend that the simulator be included as part of the PC diskette distribution). Section 1: The Textbook By the textbook I primarily mean the "concepts" part (that is, the first half of chapters one through five). It is well-written and I like the ordering of topics. The extended discussion of I/O devices is especially nice. On the other hand, I found that I had to expand the material substantially in my lectures. If a second edition is ever considered, I would recommend expanding this part of the textbook. Finkel is a good example of another well-written operating system textbook that has a more extensive treatment. I have some specific comments on the material. Chapter 1: 1) Though you have appendices on C and the IBM PC you do not have one on UNIX at the user level. Instead there is section 1.3 and an appendix of man pages for the MINIX commands. Perhaps an additional appendix would be appropriate that bridges the gap by tersely covering more of the generic UNIX interface (such as, more about the Bourne Shell than the very brief man page). 2) In using MINIX as the class project, writing C programs that exercise MINIX via system calls is very important. The main description of the system call interface is section 1.4 and the programs in directory /test. This section is not precise enough to be a reference guide. Return code values and the different library routine interfaces to execve are examples of things that could be made clearer. 3) Figure 1-9 does not include the "access" system call. 4) Invariably, a large number of students think all uses of the "pipe" system call should use the format of figure 1-14. It should be made clearer in the text and caption that the closing of STD_OUTPUT and STD_INPUT and use of the "dup" system call are only needed when the shell is creating a pipe. Chapter 2: 1) I would expand explaining how semaphores can be implemented using test-and-set instructions. In particular, I would distinguish between busy-waiting and blocking implementations. 2) I would have expanded the discussion of monitors. I would make more rigorous the definition of a monitor (as in Finkel). I would also call the procedures in the monitor that can be called from outside "guard procedures" and explicitly export their names. 3) Your implementation of monitors using semaphores (page 72) does not ensure the woken waiter will be the next process to enter the monitor after a signal. The goal is to implement Brinch Hansen monitors and thus the signaled condition is supposed to be true when the woken waiter runs. If another process is allowed to run first, not only is there not fairness, but the condition may become false. The proposed solution is: On monitor exit the process always does an "UP(mutex);". A WAIT on condition variable "c" becomes "UP(mutex); DOWN(c);DOWN(mutex);". The problem is that some other process could come in after the UP(mutex) of the signaler and before the DOWN(mutex) of the ex-waiter. The corrected solution is have the signaler hand his exclusion over to the ex-waiter. In particular, on a monitor exit after a signal do not do an UP(mutex), do nothing. Also, a WAIT(c) becomes just "UP(mutex); DOWN(c);". Chapter 3: 1) It should be made clearer that the discussion on pages 124 and 125 on deadlock is in the context of a single instance of each resource class (I do not think the sentence, "Resource graphs can also be generalized ..." on the top of page 127 is enougy). In particular, it should be noted that a cycle in the resource graph implies a deadlock is only true in the single instance case. 2) It would be nice to mention the recent work on VSCAN and CVSCAN when discussing disk scheduling. Chapter 4: 1) Your buddy system example (page 204) has a mistake. On the Request of 60K the free 64K buddy of the region allocated to B should be used instead of the 128K free region that is split. 2) The page replacement algorithm you call NRU (Not Recently Used) might better be called Page Classes (which is what Peterson and Silberschatz call it). This is especially confusing because Finkel uses the name NUR (Not Used Recently) for a different algorithm. 3) My understanding is that the Clock page replacement algorithm goes in page table order not in a circular FIFO list. 4) I would describe WSCLOCK. Chapter 5: 1)I would describe public-key cryptography. Section 2: MINIX The students in the class were primarily sophmores and juniors who had never used C or UNIX before. Both semesters we had three programming assignments. The first assignment both times was to implement five C programs that together exercised a large number of the system calls. The second assignment in the Fall semester added tracing of the low-level routines for interrupts, system calls, and message passing various parts of which are toggled by two extra function keys. Also tracing of the short-term scheduler was added, again controlled by toggling a function key. The third assignment in the Fall semester was exercises 3-37 (add a special key for erasing the previous word) and 4-22 (take the release of the current memory image into consideration when determining if a hole large enough for the new memory image will exist). The second assignment in the Spring semester was exercises 2-31 (dump a matrix counting the number of messages sent between different processes when the F4 key is hit) and 2-32 (modify the short-term scheduler so that when the next process to run is chosen from the user ready queue, the process whose total time run so far is the least, is chosen). The third assignment in the Spring semester was to modify the allocation routines of mm so that main memory is compacted, if the initial attempt to create a large enough hole in response to a fork or an exec fails (This assignment was based on a description of a similar assigment by Ganesh Gopalakrishnan of the University of Utah.). I think that the general reaction both semesters was an initial strong enthusiasm followed by a frustation with the slowness and difficulty of debugging. Whether the frustation was enough to negate the enthusiasm varied depending on the student. The machines available to the students are XTs with two floppy drives and 640K RAM. MINIX version 1.1 was used both semesters. The basic problem was the following. If a student makes a change to one .c file in /kernel, then the time to recompile that one .c file, create a new kernel binary, and create a new boot diskette is approximately 21 minutes. If the student has a bug the result is that when he boots up and presses the "=" key, the system simply hangs. The long compile cycle and extremely limited feedback when something fails, makes debugging very tedious and frustating. The long compile cycle is partly due to the low performance of an XT and partly due to the MINIX C compiler. The lack of feedback is probably inherent in the modification of a machine's native operating system. A possible solution is to use the PC simulator provided on the VAX distribution for the initial debugging. I have not tried this yet, so my following comments are speculative. Using the PC simulator should make finding bugs much easier. Moreover if it is run on a higher performance machine (such as a vax or a sun), then the compile time will be much less. When a change runs on the simulator, the student could then download to the PC and run it for real. If using the PC simulator is as important for debugging in an instructional setting as I think it is, I think that it should be added to the PC diskette distribution. As a result, it could be used on the PC if no other machine is available. Moreover, it would mean that the instructor would not have to buy two copies (a PC diskette version and a VAX tape distribution). If a VAX or Sun is available, the instructor could copy it over from the PC. Mark Holliday Department of Computer Science Duke University
vandys@hpindda.HP.COM (Andy Valencia) (05/17/88)
Thank you for the excellent review of the MINIX book's material! I'm going to file these comments away with the book itself (in case I ever have to teach a course). Let me add a couple of points which came to mind while reading your comments. 1. Development cycle speed I started out doing my RS-232 driver for MINIX on an XT (4.77 Mhz) with dual floppies. Very quickly I got a hard drive partition working, and then got an Orchid accelerator. This made it just barely tolerable. Since I was changing tty.c, and since that's where the kernel printf()s go, I perhaps had a worse time than others might. By the time you're running a turbo AT (mine is 10Mhz, no wait states), the whole picture has changed-- compiles zip by at a reasonable rate. I bet a '386 would be something to see! 2. The simulator Don't count on it for an increase in performance--after all, it's trying to emulate one machine on another. I'd say your $$$ would be better spent upgrading those XTs to clone turbo ATs, rather than trying to make your campus minis run fast enough to support a class full of students running the simulator. 3. Driver writing As it turns out, it is much easier to write drivers for UNIX than MINIX. UNIX has a fairly stable and well-designed set of routines to use--very much refined over time. This may be little comfort to the student taking your class, but it might ease their minds about getting a job doing UNIX kernel maintenance! Andy Valencia vandys%hpindda.UUCP@hplabs.hp.com