Advanced Operating Systems

Fall 1997


Scott Stoller


Madhusudhan Govindaraju


Lectures: Monday and Wednesday, 1:00PM - 2:15PM, in WH004.
Discussion: Thursday, 7:15PM - 8:05PM, in WY015.
Instructor's Office Hours: Monday and Wednesday, 5:15PM - 6:15PM, or by appointment. Lindley Hall 201D.
A.I.'s Office Hours: Tuesday and Thursday, 4:30PM - 5:30PM. Lindley Hall 301E.

Home Pages from Previous Years

Fall 1996 P436/P536 Home Page

Official Description

Click above to see the official blurb describing this course.

Tentative Syllabus

2-8Processes and Threads: Synchronization, Scheduling, Deadlock
9-11Memory: Segmentation, Paging, Virtual Memory
12-14I/O, Filesystems
17Distributed Systems: Introduction
18-20Communication: Messages, RPC, Group Communication
21Name Servers
22-25Distributed Filesystems

The lectures are based in part on Tom Anderson's lecture notes for CS162 at UC Berkeley.


Andrew Tanenbaum, Modern Operating Systems (Prentice Hall, 1992).


The project is to design and implement parts of a small operating system, called Nachos, which runs in a simulator that runs on Sun workstations. You will be given a "skeleton" of the operating system and will be asked to implement some of the missing parts, e.g., synchronization primitives for threads, support for multiprogramming, and virtual memory management. You will work on the project in small teams. The programming is (almost) in C. A few simple features of C++ are used; they will be explained as needed. Here is a brief Overview of Nachos, from its developers at UC Berkeley.

Project Mechanics

Click above for information on accounts, software tools, submitting assignments, etc.

Project Guidelines

This handout describes what should be submitted for each assignment. It also covers grading policies, late-submission policies, etc.


The breakdown is:
Project + problem sets 50%
Midterm examination 19%
Second in-class exam10%
Final examination 21%
Grading on the project will emphasize good design as well as working code. Exams may cover all aspects of the course, including the project. The midterm will be a 75-minute, in-class exam. The final will be a 2-hour exam held at the time specified in the Registrar's Schedule of Final Examinations. The weights of the two exams are in proportion to their length.

Course Newsgroup: ac.csci.p536

If you have questions about the lectures or the project, this is a good place to ask them, so that other students can benefit from your questions. If you see a question and (think you) know the answer, post it! This will help your classmates and show us that you know what's going on.


hw1 (out of 10)7.81.9
proj1 (out of 20)19.02.5
hw2 (out of 10)5.81.2
proj2 (out of 50)47.23.4
midterm (out of 35)23.2 (66%)6.2
hw3 (out of 15)13.23.0
midterm2 (out of 40)30.0 (75%)4.5
proj3 (out of 50)49.11.3
proj4 (out of 50)48.11.7
proj5 (out of 50)45.44.1
final (out of 50)31.7 (63%)7.2


hw1 scores
proj1 scores
hw2 scores
proj2 scores
midterm scores
midterm2 scores

Weekly Announcements

Week of Dec 15


Final Exams: You can pick up your final exam booklet from me (in Lindley 201D) at any time.

Course Grades: Course grades have been sent by e-mail. If you didn't receive one, let me know.

Grading statistics: Statistics for the final exam and proj5 have been added to the table above.

Trivia: Number of course-related news/mail messages sent or received by the instructor this semester (excluding homework and project submissions): 1479.

Proj5: To avoid delays in the grading of proj5, please be certain that the permissions are set correctly for your proj5 files.

Week of Dec 8

FINAL EXAM ROOM CHANGE: Just a reminder... There were some complaints during the midterm that the classroom is too small (especially for open-book exams). So, I have reserved a larger room for the final exam: BU109. Exam time is 5pm-7pm.

Handout Reminder: During the weeks of 17 Nov and 24 Nov, a handout with a description of Sun NFS was distributed (photocopied from another textbook). If you did not get that handout, you might want to copy it from a classmate (or from me).

Old Final Exam: Here is the Fall 1996 Final Exam (with solutions). Note that Problems 8-10 and the extra-credit problem are on topics that were not covered this year.

Practice Problems for Final: Here are Solutions to Selected Practice Problems for Final Exam. Solutions to other practice problems will not be distributed, but if after working on the problems, you have doubts about some of your solutions, you can post your solutions and your doubts to the newsgroup, or email them to c536, or come to my office during the office hour at 2pm on Sunday (or at other times).

Course Evaluation: Please fill out the On-line Course Evaluation. Your evaluation and comments would be appreciated. Due to an administrative mistake, P536 students should select "p436-stol" as the course. (We can still distinguish responses from P436 and P536.)

Proj4: Grading statistics for proj4 have been added above.

Final Exam: The final exam will probably have 1 question about nachos. The question might deal with threads or user programs. It would not deal with details of the MIPS R2000 simulation; the only files in machine that it might assume familiarity with are machine/interrupt.*. I just eliminated machine/timer.cc from here, because it is not in the nachos code handout. Sorry for the confusion.

Course Evaluation: Please fill out the On-line Course Evaluation. The course has changed considerably from last year. Your evaluation and comments can influence its future. Due to an administrative mistake, P536 students should select "p436-stol" as the course. We can still distinguish responses from P436 and P536.

Week of Dec 1

Proj3: Grading statistics for proj3 have been added above.

Proj5: As posted to the newsgroup a while ago (I'm just reminding you here), implementing write-locks in proj5 is optional.

Final Exam: Here is a list of Practice Problems for Final Exam. Basically, I have listed all problems in Tanenbaum that correspond to material covered in lecture.

Proj5: Please read the Proj5 FAQ.

Final Exam: You are strongly encouraged to bring a copy of the original nachos code to the final exam (you don't need to bring the code you wrote).

Final Exam: The final exam will cover the entire course. (The exam will not necessarily emphasize later material.)

Proj5: As mentioned in a newsgroup posting, ~c536/proj5 now contains code for writing to remote files.

Midterm2: Grading statistics and a histogram have been added above.

Final exam: Like the first midterm, the final exam will be open book and open notes. "Book" means Tanenbaum; no other books. "Notes" means your own handwritten notes: no photocopies of other people's notes. You can also bring all course handouts (problem sets, Nachos code, etc.).

FINAL EXAM ROOM CHANGE: There were some complaints during the midterm that the classroom is too small (especially for open-book exams). So, I have reserved a larger room for the final exam: BU109.

Textbook Readings: By now, you should have read Tanenbaum, Chapter 9. Now read Tanenbaum, Chapter 13. Note that Tanenbaum's description of Sun NFS is (inconveniently) split between these two chapters. We won't have time to cover the material in Chapters 10-12.

Proj5: As I mentioned in lecture on Dec 1, the code in ~c536/proj5 has a "security hole", because it does not check whether the file descriptor supplied by a user process in a read or close system call is valid, i.e., corresponds to a file opened by that process. I mention this issue again here for the sake of people who missed that lecture.

Handout: In the handout with pictures of the tables used by Sun NFS, in the lower figure, entry 18 in the v-node table should contain "remote, 4" (instead of being empty). Don't forget that the pictures in this handout should not be taken too literally; for example, the i-node numbers (like 207 and 999) should really be entire file handles.

Midterm2: If you have questions about the grading of midterm2, please ask the appropriate person during their office hours (if possible): Madhu for problems 1-2; Scott for problems 3-6; Leena for problems 7-8. This will help ensure consistency of grading.

Week of Nov 24

Solutions to Midterm2 are now available.

Project: More advice on proj5. I recommend the following two-stage approach: (1) Implement the remaining operations (Write, Create, and Remove) for remote files (note: although there is no system call corresponding to FileSystem::Remove, you should implement Remove for remote files anyway, so that you can remove a remote swap file when the corresponding process exits). (2) Implement caching of blocks.

Project: An update to the "Very Important Advice" in the proj5 handout. Implementing write-locks will be counted as extra-credit. So, the requirements are to implement everything described in the handout except write locks, and to describe in the README file how you would implement write locks.

Week of Nov 17

Practice Problems: Here are Solutions to Selected Practice Problems for 2nd Exam.

Extra Office Hours: Due to the exam, the instructor will have two extra office hours: Friday, 2pm-3pm, and Mon, 10am-11am.

Practice Problems: Here are Practice Problems for 2nd Exam.

Exam: The second in-class exam will cover Topics IV (Memory Management), V (I/O Hardware), and VI (File Systems).

Project: Project 5 is now available.

Textbook Readings: Tanenbaum, Chapter 9.

Week of Nov 10

Project: An important requirement was added for proj4. It is described in a newsgroup posting, duplicated here for your convenience.

Project: In deciding how to use your slip time, keep in mind that there will be one more required project (proj5).

Project: Proj4 is due on Nov. 11. Don't forget! Also, don't forget to follow all the instructions in the project handout, especially those regarding the minimal required contents of your readme and testcase files.

Week of Nov 3

Grading Info: I updated the histogram of midterm scores (and the mean and std deviation) to reflect grading corrections. I also added the mean and std deviation for hw3 to the above table.

Textbook Readings: Tanenbaum, Section 5.1-5.3.

Exam: There will be an in-class exam on Mon, 24 Nov, worth approximately 10% of your course grade. The approximate weight of the final exam is therefore reduced by 10%. This in-class exam will be open textbook but closed everything else. At least two of the problems on the exam will be taken from the textbook, possibly with some numbers changed. This in-class exam does not cover material already covered on the midterm. Of course, the final exam covers everything in the course.

Week of Oct 27

Recommended Activities: This is almost too obvious to mention, but anyway... A good way to check your understanding of lectures is to do the problems in Tanenbaum, or in any other standard OS textbook (such as the one by Stallings, mentioned below, or Silberschatz et al.). For example, this would be a good time to do a bunch of problems from the Memory Management chapter(s) of any of these books.

Recommended Readings: A textbook that is (in places) clearer and more detailed than Tanenbaum is: William Stallings, Operating Systems, 2nd edition (Prentice-Hall, 1995). You might find this book useful to clear up the vague points from Tanenbaum's discussions or from lecture. I requested (on Oct 29) that this book be put on 24-hour reserve (i.e., you can check it out for 24 hrs) in Swain Library. The book should be available there within 10 days (it is checked out right now). If availability of the book becomes a problem, let me know, and I will have the status changed to 2-hour reserve.

Textbook Readings: Tanenbaum, Chapter 3 and Section 7.5.2.

Week of Oct 20

Project 4 handout is now available.

Week of Oct 13

Midterm: If you have questions about the grading of the midterm, please ask the appropriate person during their office hours (if possible): Leena for problems 1 and 2; Madhu for problems 3 and 5; Scott for problems 4, 6, and 7. This will help ensure consistency of grading.

The new due date for Project 3 is Tuesday, 21 Oct.

There are new sections above with grading statistics and histograms, to help you see how your scores compare to those of other students. Those sections will be updated periodically.

Week of Oct 6

Solutions to Midterm are now available.

Solutions to Practice Problems for Midterm are now available.

Solutions to Homework 3 are now available.

Project 3 is due on 19 Oct (this is a change from the original due date). The preliminary design document for proj3 is due on 12 Oct.

Practice Problems are now available.

Late Homework Policy: For homework (i.e., problem sets), there are no slip days. Late homework will be marked off 10% per day, until solutions are posted. Homework submitted after solutions are posted will be ignored.

Homework 3 was posted on 6 Oct and is due on 10 Oct.

Midterm: To minimize memorization anxiety, the midterm will be open book and open notes. "Book" means Tanenbaum; no other books. "Notes" means your own handwritten notes: no photocopies of other people's notes. You can also bring all course handouts (problem sets, Nachos code, etc.).

Grading of Homework: In homeworks, all problems (except extra-credit problems, if any) are of equal weight, unless the homework indicates otherwise.

Proj3: Some clarifications were posted to the newsgroup; they are repeated here for ease of reference. 1. You do not need to implement the Fork and Yield system calls. 2. For Join, you can require that a process Join only on its children. Without this requirement, there is a garbage-collection problem (it's never safe to discard the return-value of a process). If Join is called with a SpaceID that does not correspond to one of the caller's children, Join should return immediately, with (say) a return-value of -1 to indicate that an error occurred.

Solution to Homework 2.

Week of Sep 29

No announcements. Great!

Week of Sep 22

CPU Scheduling was covered in class on Sept 22.

Deadlock was covered in class on Sept 24.

Office Hours: The instructor's office hours on Sep. 22 and Sep. 24 are cancelled. The A.I.'s office hours are not affected.

Reminder: Preliminary design document for proj2 is due on 24 Sep. It should show us that you know what to do. For example, it should describe where the significant chunks of code will go (i.e., how they will fit into the Nachos skeleton that you are given) and what they will do.

Reminder: Homework2 is due on 22 Sep.

Week of Sep 15

Project: Projects 2+3 are now available.

Questions about Grading: If you have questions about the grading of homework or programming assignments, talk to Madhu first, since he does most of the grading. If you are not satisfied after talking to Madhu, then you should talk to the instructor.

Happy Mid-Autumn Festival!

Midterm will be held in class on Mon, 13 Oct. Don't miss it!

Homework 2 was posted on 15 Sep and is due on 22 Sep.

Exam Policy: Exams may cover all aspects of the course, including the project. This is partly to discourage people from letting their teammates do all of the work on the project.

Abridged Solution to Homework 1.

Late Homework Policy: see above (Week of Oct 6).

Week of September 8

Please send course-related email to c536@cs.indiana.edu rather than stoller@cs.indiana.edu.

Project: Project 1 was posted on Sep. 9 and is due Sep. 16.

Textbook Readings: Tanenbaum, Section 12.1.

Textbook Readings: Tanenbaum, Chapter 2.

Handouts: Buggy versions of Thread Pseudo-Code were distributed in lecture on Mon., Sep. 8 and Wed., Sep. 10. A corrected version of Thread Pseudo-Code is available here. The corrections are described in some newsgroup postings. You should read the pseudo-code and (to check your understanding) trace the execution of the example (involving procedures main, B, C, and A' or A'') that I traced during lecture.

Reminder: Homework 1 is due on Wed, Sep 10.

Week of September 1

Additional Assumption for Homework 1: To simplify the problem, please make the following assumption about CPU scheduling: when a new process is created by the daemon, that new process immediately gets a chance to run, even if other processes are waiting for the CPU. Here is a revised Homework 1, containing this additional assumption (and the clarifications posted to the newsgroup).

Textbook Readings: Tanenbaum, Chapter 1.

Homework: Homework 1 was distributed on Wed, Sep 3, and is due on Wed, Sep 10. Like all homeworks (but not programming projects) in this course: (1) it is due by midnight on the due date, and (2) it may be submitted by email to c536@cs.indiana.edu or by hardcopy to the instructor (mailbox or homework drop box near Lindley 215, or office in Lindley 201D). If you use the homework drop box, be sure to mention my name on your homework, so the staff knows to whom to give it.

Handouts: 5 handouts were distributed in lecture on Sep 3. They are: (1) Nachos code, (2) A Quick Introduction to C++, (3) Project Guidelines, (4) Roadmap to Nachos (5) Homework 1. You can easily print all of these yourself, except the Nachos code. If you didn't get a copy of the Nachos code, let me know.


(1) Try to form teams by Monday, Sep. 8.

(2) Read the Project Guidelines (handout).

(3) Read the Project Mechanics page.

(4) Read A Quick Introduction to C++ (handout).

(5) Read sections 1, 2, and 3 of A Road Map Through Nachos (handout) and the threads code (in the thick handout of Nachos code, or online in ~c536/nachos-3.4/code/threads). In the thick handout, the files are arranged alphabetically by directory and filename; for example, "threads/scheduler.cc" comes before "threads/synch.cc", which comes before "userprog/addrspace.cc" Also, each ".h" file immediately precedes the corresponding ".cc" file.

(6) Another helpful resource is Mike O'Donnell's Guide to Reading the [Nachos] Source Code. Mike's Guide is available only in HTML format, so we won't be supplying printouts.