P536: Yu (Marie) Ma
P436 Lectures: Mon and Wed, 4:00PM - 5:15PM, WH 007.
P436 Discussion: Fri, 11:15AM - 12:05PM, BH 204.
Instructor's Office Hours: Mon and Wed, 5:15PM - 6:15PM, or by
appointment, or by chance. LH 201C.
Yu Ma's Office Hours: Thu, 5pm-6pm, and Fri, 10am-11am. LH 301G.
Ying Feng's Office Hours: Tue and Thu, 4pm-5pm. LH 301G.
Students in both classes are welcome to attend office hours of both A.I.'s.
P436 Final exam: 2:45pm-4:45pm on Fri, 17 Dec 1999.
P536 Final exam: 7:15pm-9:15pm on Mon, 13 Dec 1999.
The P536 final exam will be held in WY 005, not in the usual classroom (SY 103).
P436/P536 Home Page
Fall 1997: P436 Home Page, P536 Home Page
Fall 1996: P436/P536 Home Page
Official Course Description
Syllabus and Readings
|1||Introduction to OS||ch. 1|
|2-3||Processes and Threads||chs. 3-4|
|4-12||Synchronization, Deadlock, Processor Scheduling||chs. 5 (except Dekker's Alg., pp. 197-202, and section 5.6), 6.1-6.6, 9.|
|13-17||Memory: Segmentation, Paging, Virtual Memory||chs. 7-8|
|18-20||I/O, Filesystems||chs. 11-12 (except Disk Scheduling, pp. 466-470); S & G, pp. 675-683.|
|25-28||Distributed Filesystems||S & G, pp. 519-548.|
The syllabus for P436 is similar, except that there will be a few lectures about C and C++ during the first two weeks.
The lecture numbers given above are approximate. Actual lecture pace may vary.
Readings are from Stallings' book (see below) unless otherwise specified. "S&G" refers to: A. Silberschatz and P. Galvin, Operating System Concepts, 5th ed., Addison-Wesley, 1998. Readings from S&G will be photocopied and distributed in class.
The lectures are based in part on Tom Anderson's lecture notes for CS162 at UC Berkeley.
For P436, there is a second textbook (students already familiar with C++
can probably get by without it): Timothy Budd,
for Java Programmers, Addison Wesley Longman, 1999.
For another perspective on OS, you might want to read: Andrew
S. Tanenbaum, Modern operating systems, Prentice Hall, 1992. This
book is also on 24-hour reserve in Swain Hall Library.
By default, all assignments in this course are due by the end (midnight)
of the specified day. To submit a problem set, either email it to firstname.lastname@example.org or put hardcopy
under the door of LH 201C or in the homework drop box near LH 215. If you
use the homework drop box, be sure the instructor's name appears on your
problem set, so the staff knows to whom to give it. If you submit
electronically, please send ASCII, PostScript, or PDF; Microsoft Word
(.doc) files are less convenient. If you want to include a file
containing ASCII text in an email message, please insert the contents of
the file in your message, instead of attaching the file as a MIME
attachment. This is more convenient for us. Thanks.
If you have questions about the grading of an assignment, please talk
first to an A.I. (since the A.I.'s do most of the grading) and then
(if you still think there is a problem) to the instructor.
Problem sets submitted after the due date and before solutions are posted
will receive a penalty of 10% per day or fraction thereof. No credit is
given for problem sets submitted after solutions are posted. Solutions to
problem sets may be posted any time after the assignment is due.
Private questions should be emailed to email@example.com or (if you don't
want the A.I.'s to see your message) to firstname.lastname@example.org.
Links to the course newsgroups are here.
The primary textbook is: William Stallings, Operating Systems: Internals
and Design Principles, 3rd edition, Prentice Hall, 1998. This
book is on 24-hour reserve in Swain Hall Library.
The project is based on Nachos, with some
ideas from Carla
Ellis at Duke. It involves significant amounts of programming in C++.
P536 students are expected to already know C. P436 students are expected
to already know Java and to be able to learn C++ quickly.
Guidelines for Problem Sets
All problem sets are done individually, not in teams. You must always
show the arguments and calculations that justify your answers. You may
make additional assumptions, if you think they are necessary and
realistic; in that case, be sure to state your additional assumptions
Be sure to read and follow the Computer Science
Department Statement on Academic Integrity. Copying someone else's
code, in part or whole, is prohibited. To help deter and detect such
behavior, we will use software that automatically compares and reports
similarities between programs.
Newsgroups and Email
Most questions should be posted to the course newsgroup. This is better
than email because: (1) you are more likely to get a prompt response,
since other students, the A.I,'s, and the instructor all read the
newsgroup; (2) other students benefit from seeing your questions and the
answers. If you see a question and (think you) know the answer, post it!
This helps your classmates and shows us that you know what's going on.
If I receive by email a question that should have been posted to the
newsgroup, I will simply forward it to the newsgroup.
The breakdown is:
For P436, there is a second textbook (students already familiar with C++ can probably get by without it): Timothy Budd, C++ for Java Programmers, Addison Wesley Longman, 1999.
For another perspective on OS, you might want to read: Andrew S. Tanenbaum, Modern operating systems, Prentice Hall, 1992. This book is also on 24-hour reserve in Swain Hall Library.
By default, all assignments in this course are due by the end (midnight) of the specified day. To submit a problem set, either email it to email@example.com or put hardcopy under the door of LH 201C or in the homework drop box near LH 215. If you use the homework drop box, be sure the instructor's name appears on your problem set, so the staff knows to whom to give it. If you submit electronically, please send ASCII, PostScript, or PDF; Microsoft Word (.doc) files are less convenient. If you want to include a file containing ASCII text in an email message, please insert the contents of the file in your message, instead of attaching the file as a MIME attachment. This is more convenient for us. Thanks.
If you have questions about the grading of an assignment, please talk first to an A.I. (since the A.I.'s do most of the grading) and then (if you still think there is a problem) to the instructor.
Problem sets submitted after the due date and before solutions are posted will receive a penalty of 10% per day or fraction thereof. No credit is given for problem sets submitted after solutions are posted. Solutions to problem sets may be posted any time after the assignment is due.
Private questions should be emailed to firstname.lastname@example.org or (if you don't want the A.I.'s to see your message) to email@example.com.
Links to the course newsgroups are here.
|Project + problem sets||45%|
|Midterm 1 exam||17%|
|Midterm 2 exam||17%|
The following statistics and histograms may be slightly inaccurate,
due to late submissions, score adjustments, etc.
|probset1 (out of 30)||16.6||5.5|
|proj1 (out of 80)||47.5||18.7|
|probset2 (out of 50)||23.7||5.7|
|midterm1 (out of 50)||27||7.7||histogram|
|proj2 (out of 120)||82.5||17.9|
|probset3 (out of 40)||21.9||8.8|
|midterm2 (out of 100)||49.4||19.0||histogram|
|proj3 (out of 100)||67.2||20.0|
|final (out of 50)||31.9 (64%)||8.8|
|probset1 (out of 25)||18.5||6.5|
|proj1 (out of 75)||63.1||15.4|
|probset2 (out of 50)||38.7||9.6|
|midterm1 (out of 50)||32.8||11.4||histogram|
|proj2 (out of 120)||96.9||30.2|
|probset3 (out of 40)||32.3||5.3|
|proj3 (out of 100)||89.6||16.3|
|midterm2 (out of 100)||59.5||22.3||histogram|
|proj4 (out of 100)||89.2||13.2|
|final (out of 60)||43.8 (73%)||9.7|
Project: P536 only: your graded proj4 is in the mailbox of one of the team members, if at least one team member has a CS Dept mailbox. Other proj4's can be picked up from my office (any time I'm there).
Virtual Handout: To help you prepare for the final exam, here are 1997 Final Exam Solution and 1998 Final Exam Solution.
Reading: P436 only: A modification to the above reading list: you are not responsible for Stallings, section 11.6 (RAID) or Windows NT filesystem (section 12.8).
Trivia: Number of course-related news/mail messages sent or received by the instructor so far this semester (excluding homework and project submissions): 1866.
Course Eval: I have added links to the On-line Course Evaluation pages for the A.I.s. P436 students can't fill out the form for Marie, and P536 students can't fill out the form for Ying, but if you would like to put comments in my form or the other A.I.'s form, we can forward your comments.
Virtual Handout: To help you prepare for the final exam, here are 1997 Final Exam and 1998 Final Exam.
Schedule Change: Reminder: Discussion sections and Marie's office hours on 9 and 10 Dec are cancelled. Marie will hold office hours 2pm-3pm on Sun, 12 Dec, and 1pm-2pm on Wed, 15 Dec.
Handout: P536 Only: In class on Dec 1, a one-sheet double-sided handout on Sun NFS was distributed.
Project: A few days ago, gcc was upgraded from 2.8.1 to 2.95.2. If you were compiling nachos with g++ instead of CC, you might get some errors when compiling. gcc 2.8.1 is still available in /l/gcc281/bin (put that directory first in your PATH). I was able to compile ~os/nachos-dfs/code/network/nachos with the new g++ by deleting 2 lines in post.h; so, you might also try copying the new version of post.h.
Exam: If you have questions about the grading of your midterm2, please start by asking the person who graded the problem in question: Marie for problem 1; Ying for problem 2 and P436-problem3; Scott for P536-problem3.
Project: A comment regarding bullet-proofing in proj4: It is OK for an assertion violation to occur if a machine is missing (e.g., if you run "../network/nachos -m 0 -o 2 ..." and there is no Solaris process corresponding to machine 1).
Schedule Change: Discussion sections and Marie's office hours on 9 and 10 Dec are cancelled. Marie will hold office hours 2pm-3pm on Sun, 12 Dec, and 1pm-2pm on Wed, 15 Dec.
Exam: Grading statistics for midterm2 have been added above. You can pick up your graded midterm2 during Ying's office hour tomorrow or, if you cannot make it then, from Scott's office until 4pm.
Exam: The P536 final exam will be held in WY 005, not in the usual classroom (SY 103). The usual classroom is somewhat cramped; WY 005 is larger.
Probset: Grading statistics for P536 proj3 have been added above.
Problem Set: If you have questions about the grading of probset3, please start by asking the person who graded the problem in question (preferably during office hours): Marie for problems 2 and 3; Ying for problems 1 and 4.
Virtual Quasi-Handout: The link for the virtual quasi-handout was broken; I just fixed it. Sorry for the trouble.
Virtual Quasi-Handout: Here is Midterm 2 with solutions, encrypted with triple DES in CBC (Cipher Block Chaining) mode. If you can decrypt it, and show me how you did it :-), you will get 100% on the exam.
Virtual Handout: Here are 1997 Midterm2 Solution and 1998 Midterm2 Solution.
Virtual Handout: Here is a Solution to Probset3.
Schedule Change: Marie's office hours on 18 and 19 Nov are cancelled. During the discussion sections on those two days, Ying will answer all of your OS-related questions.
Project: For P436: Grading statistics for proj2 have been added above.
Exam: To help you prepare for midterm2, here are 1997 Midterm2 and 1998 Midterm2.
Trivia: Here is an interesting tidbit about System-Call Counts.
Project: Here is some info about Grading of Proj3.
Exam: During midterm2, you may use the course textbook, your own notes, a dictionary, and handouts that were distributed in class or posted on the course web page. You may not bring someone else's notes or a mechanical reproduction of all or part thereof. You may not bring a different textbook or a mechanical reproduction of all or part thereof.
Handout: Probset3 was distributed in class today.
Debugger: For those of you who haven't been using
workshop and would like help getting started, Marie will
repeat her "Intro to
workshop" starting at 5:30pm on Thu, 11
Nov, in LH 301G.
Project: For full credit on this project, it suffices for testcases involving N concurrent processes to run correctly with 2*N page frames. You may get some extra credit for difficult testcases that run with fewer page frames.
Project: As part of the new submission procedure, I modified "make clean" so that it also deletes cross-compiled executables in code/test and bin/coff2noff. Both can easily be re-made.
Demos: Reminder for P436: Send email to Ying to sign up for a demo for proj2, if you haven't already! Remember, the proj2 demo deadline is 5 Nov.
Project: A new project submission mechanism has been instituted. For future project submissions, please follow the instructions at the bottom of the Project Mechanics page.
Project: For P536: Grading statistics for proj2 have been added above.
Exam: Grading statistics for midterm1 have been added above. If you have questions about the grading of midterm1, please start by asking the person who graded the problem in question (during office hours, if possible): Scott for problem 3; Marie for problems 2 and 5; Ying for problems 1 and 4. This will help ensure consistency of grading.
Exam: During midterm1, you may use all handouts that were distributed in class or posted on the course web page.
Exam: midterm1 will not cover section 5.6 (Message Passsing).
Virtual Handout: Here is a Solution to Probset2.
Exam: During midterm1, you may use the course textbook, your own notes, and a dictionary. You may not bring someone else's notes or a mechanical reproduction of all or part thereof. You may not bring a different textbook or a mechanical reproduction of all or part thereof. [Added on 20 Oct: You may use all handouts that were distributed in class or posted on the course web page.]
Handout: The following files will become readable at 8am on Mon, 18 Oct 1999: 1997 Midterm1 Solution and 1998 Midterm1 Solution.
Handout: P536 only: Typical Steps in Memory Access was distributed in class last week.
Project: I modified the project submission form. Please read it carefully before filling it out and sending it in. One important change is the inclusion of the scheduled demo time.
Project: Second reminder for P536: Don't forget to sign up to demo proj2. As stated on the proj2 handout, proj2 demo deadline for P536 is 22 Oct 1999.
Handouts: The following handouts were distributed in class. Print them only if you missed class and did not receive them. Readers-Writers using Locks and Condition Variables. Barrier Synchronization using Semaphores
Project: P436 Only: If you didn't get your proj2 design back during discussion section, you can pick it up from LH 201C or get it back during lecture on Monday.
Project: Here is some info about Grading of Proj2.
Exams: A reminder of an announcement from 9 Sep: Midterm1 will be on 20 Oct. Midterm2 will be on 17 Nov.
Schedule Change: Ying's office hour on 19 Oct is cancelled.
make fork-testin code/test compiled those programs incorrectly. If you are using fork-test and fork-test-child, please re-copy test/Makefile and then re-make those programs. Sorry for the inconvenience.
Schedule Change: My earlier office hour on 19 Oct will be noon-1pm, instead of 11am-noon. I changed this in the announcement below.
Schedule Change: Lecture and Scott's office hour on Mon, 18 Oct, are cancelled. Instead, Scott will hold two office hours on Tue, 19 Oct, at noon-1pm and 3:30pm-4:30pm. This is mainly to answer questions that might arise as part of preparation for midterm1; other questions are fine,
Schedule Change: Marie's office hour on Thu, 14 Oct, is moved from 5pm-6pm to 3pm-4pm.
Exam: To help you prepare for the midterm, here are 1997 Midterm1 and 1998 Midterm1.
Handout: Probset2 was distributed in class today. The first problem is cancelled.
Project: I inserted the third sentence in the following paragraph in the proj2 handout:
Project: I added the following paragraph to the proj2 handout, in the section IMPLEMENTING MULTITASKING AND TIME-SLICING:
Project: Someone asked for a preliminary version of proj3, since some designs for proj2 might be easier to extend for proj3 than others. So, here is a rough draft of proj3. Warning: Until proj3 is actually assigned (sometime near the proj2 due date), all aspects of it (including due dates) are subject to change!
Proj1: Here are comments about Grading of Proj1.
Grading: The total weight of the projects will be 2 or 3 times the total weight of the problem sets, depending on the length and difficulty of the remaining problem sets. Each project has a similar weight, except for the first project, whose weight will be 1/2 to 1/3 of the weight of the others. There will probably be 3 problem sets.
Probset1: Here is a Solution to Probset1.
Office Hours: Henceforth, both Marie and Ying will hold office hours in LH 301G. Ying will henceforth hold office hours at 4pm-5pm on Tue and Thu, instead of 11:15am-12:15pm.
Proj1: As mentioned in lecture, everyone who submitted a proj1 that does basic things like compile without errors and calls Yield in some places (which is to say, everyone) gets a baseline number of points added to the score that they received last week. For P436, the baseline is 25 points; for P536, it's 20 points. Grading statistics for proj1 have been added to the table above.
Project: Due dates for proj2 have changed! I updated the on-line copy of the proj2 handout to reflect the new dates, which are:
|P536||Design due||24 Sep 1999|
|Project due||9 Oct 1999|
|Demo by||22 Oct 1999|
|P436||Design due||5 Oct 1999|
|Project due||23 Oct 1999|
|Demo by||5 Nov 1999|
Problem Sets: I just updated the last paragraph in Guidelines for Problem Sets. Please read it.
Handout: P436 only: Probset1 was distributed in class yesterday.
Handout: P536 only: Probset1 was distributed in class on 8 Sep. It is due on 15 Sep.
Discussion Section: Here's a useful link: Using Sun WorkShop.
Correction: P536 only: In lecture on 6 Sep, I suggested that, if a device signals an interrupt while interrupts of that level are disabled (masked), the device would need to keep the appropriate interrupt line(s) raised until the CPU handles the interrupt. That is incorrect. In conventional designs, the CPU or interrupt controller remembers whether an interrupt of each level has been seen but not yet serviced. When the interrupt mask changes, the highest-priority pending unmasked interrupt is serviced. Sorry for the confusion.
Readings: I revised Syllabus and Readings to indicate the readings associated with each topic. This should help you read ahead, if desired. Since information about readings is now collected in one place, I will cease putting individual announcements for readings on this web page.
Clarification: P536 only: Yesterday, in Section 2.2 (Interrupt-based solution for mutex), I said that disabling interrupts should be used for mutex only if several conditions hold, one of which is that the CSs (critical sections) do not block or yield. I did not justify that condition correctly. If a thread blocks or yields while in a CS, the main problem is that the next thread to run might (disable interrupts and then) zoom right into a CS. Thanks to Ning Li for pointing this out.
Handouts: I made minor changes to a few files after I printed the code handout and sent it for photocopying. Those minor changes shouldn't cause confusion. I also made major changes to one file, namely, filesys/openfile.cc. So, I recommend that you print pretty-printed openfile.cc (gzip'd PostScript) and discard the printout of filesys/openfile.cc in the code handout (i.e., the first 3 sheets).
Handouts: There were 5 handouts today:
Project Mechanics: I just fixed an error on the Project Mechanics page, by changing the line
(setq backup-by-copying-when-mismatch t)
(setq backup-by-copying t)
Project Mechanics: You might want to add a line like
setfacl -r -f /u/os/faclfile Makefile
make dependmight (depending on your umask) create Makefiles that are not readable by your teammates.
Project: For 436 Only: Due date of proj1 is changed to 15 Sep.
Project: When compiling nachos, be sure to use GNU make (/usr/local/gnu/bin/make), not Sun make (/usr/ccs/bin/make). One way to do this is to set your PATH appropriately. Another is to type gmake (a synonym for /usr/local/gnu/bin/make) instead of make.
Discussion Section: Next week, discussion section will meet in LH 115 again. Marie will demonstrate workshop (a debugger), using nachos as an example.
Project: Here is Project 1. Hardcopies will be distributed in class on Monday (if the photocopy service copies it on time).
Team formation: For people who have not informed me of a team by 10pm on Mon, 6 Sep, I will somehow (e.g., randomly) form teams for them. (I am open to suggestions for better methods of team formation.)
Discussion Section: Here are the notes on Makefiles and Tags.
Lecture: I will be attending a conference and therefore unable to attend class on Sep 20 and 22. Two options are:
osmust have read access to all of the files that you submit for each project. If we cannot access some of those files when we attempt to grade a project, you will receive a 10% penalty on that project. If your files are reabable by other students (e.g., are world-readable or group-readable), you will receive a 10% penalty on that project.
getfaclto check the ACLs, there is no reason for you to submit an assignment with the ACLs set incorrectly.
Office Hours: Office hours have been scheduled. See Hours above.
Project: I am still modifying ~os/nachos-dfs, so do not copy it yet. I just made that directory non-world-readable. I will restore read permission when it is ready for copying.
1. Form teams by Mon, Sep 6.
2. Carefully read the Project Guidelines page.
3. Read the Project Mechanics page.
4. P536: If you are not already familiar with C++, read A Quick Introduction to C++.