P536: Yu Ma
P436 Lectures: Mon and Wed, 4:00PM - 5:15PM, in BH 003.
P436 Discussion: Fri, 11:15AM - 12:05PM,
BH 204. (The info in the printed schedule of classes is obsolete.)
Instructor's Office Hours: Mon and Wed, 5:15PM - 6:15PM, or by
appointment, or by chance. LH 201C.
Kshitiz's Office Hours: Tue and Thu, 12:30PM-1:30PM, in LH 301I.
Yu Ma's Office Hours: Thu, 1:30PM-2:30PM, and Fri, 10AM-11AM, in LH 301E.
Students in both classes are welcome to attend office hours of both A.I.'s.
P436 Final exam: 2:45pm-4:45pm on Fri, 18 Dec 1998.
P536 Final exam: 5pm-7pm on Mon, 14 Dec 1998.
History
Fall 1997:
P436 Home Page,
P536 Home Page
Fall 1996: P436/P536 Home Page
Official Course Description
P436
Lectures | Topic |
1 | Introduction |
2-12 | Processes and Threads: Synchronization, Scheduling, Deadlock |
13-17 | Memory: Segmentation, Paging, Virtual Memory |
18-20 | I/O, Filesystems |
21-22 | Protection |
23 | Distributed Systems: Introduction |
24-25 | Communication: Messages, RPC, Group Communication |
26-28 | Distributed Filesystems |
The lectures are based in part on Tom Anderson's lecture notes for CS162 at UC Berkeley.
If you want another perspective on some of the material, 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 os@cs.indiana.edu or put hardcopy
under the door of LH201C or in the homework drop box near Lindley 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 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.
Solutions to problem sets will usually be posted within a day after the
assignment is due. If you have not submitted your work before solutions
are posted, you will receive a zero for that assignment.
Textbook
The 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.
Project
The project is based on Nachos, with some
ideas from Carla
Ellis at Duke. It involves significant amounts of programming in C++.
Students are expected to already know C.
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
explicitly.
Academic Integrity
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.
Course Newsgroup:
ac.csci.p436 /
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.
Newsgroups vs. Email
In general, questions should be posted to the course newsgroup; you are
more likely to get a prompt response, since other students, the A.I,'s,
and the instructor all read the newsgroup. Questions that you don't want
other students to see should be emailed to os@cs.indiana.edu. Questions that you
don't want other students or the A.I.'s to see should be emailed to stoller@cs.indiana.edu.
Project + problem sets | 45% |
Midterm 1 exam | 17% |
Midterm 2 exam | 17% |
Final exam | 21% |
Item | Mean | Std.Dev. | Histogram |
probset1 (out of 15) | 8.8 | 3.2 | |
proj1 (out of 20) | 17.9 | 1.8 | |
proj2 (out of 50) | 44.9 | 2.6 | |
probset2 (out of 25) | 15.0 | 3.4 | |
midterm1 (out of 60) | 33.1 (55%) | 8.9 | histogram |
proj3 (out of 50) | 36.0 | 7.6 | |
probset3 (out of 35) | 22.7 | 5.2 | |
midterm2 (out of 60) | 32.7 (54.5%) | 9.9 | histogram |
proj4 (out of 50) | 33.0 | 8.7 | |
final (out of 70) | 36.3 (52%) | 10 |
Item | Mean | Std.Dev. | Histogram |
probset1 (out of 15) | 12.7 | 1.5 | |
proj1 (out of 20) | 19.7 | 0.7 | |
proj2 (out of 50) | 48.1 | 2.1 | |
probset2 (out of 25) | 21.1 | 2.3 | |
midterm1 (out of 60) | 41.1 (68%) | 9.0 | histogram |
proj3 (out of 50) | 45.7 | 3.4 | |
probset3 (out of 35) | 30.4 | 5.3 | |
proj4 (out of 50) | 45.7 | 3.3 | |
midterm2 (out of 60) | 43.0 (72%) | 7.5 | histogram |
proj5 (out of 50) | 40.2 | 11.8 | |
final (out of 70) | 47.3 (68%) | 10.8 | histogram |
Final Exam: Grading statistics for the P436 final exam have been added above.
Project: Grading statistics for P536 proj5 have been added above.
Final Exam: Here are Solutions to most of the 1998 P536 final exam and Solutions to most of the 1998 P436 final exam. Solutions to the "nachos problems" will not be posted, since they might be the basis of extra-credit projects in future years. However, solutions to those problems are available in the instructor's office for your reading pleasure.
Grades: P536 course grades have been sent by email. If you didn't receive yours, let me know.
Final Exam Location: The final exam will be held in the same room as the lectures.
Office Hours: Scott will have office hours on Sun, 13 Dec, 11am-noon, and Thu, 17 Dec, 5pm-6pm. Those are the only office hours for P436/P536 next week.
Final Exam: As mentioned in lecture, the rules regarding what materials you may use during the exam are the same as for the midterms. Remember (from here): "Exams focus on lecture material and textbook readings but may cover all aspects of the course, including the project." The final exam will not contain any questions about RAID. It's a good bet that the exam will contain question(s) about the UNIX file system (as described in lecture and in the recent handout).
Reserve: I changed Silberschatz and Galvin from 24-hour reserve to 2-hour reserve in Swain Hall Library, so more students can access it.
Cool Command: Check out the truss
command. It will
tell you everything you ever wanted to know about your Solaris processes.
Questionnaire: If you were not in lecture today, please print a Questionnaire, fill it out, and stick it in my mailbox or under my door when I'm not looking.
Textbook Readings: FOR P536 ONLY: Sections 15.1-2.
Summary of Textbook Readings: This is merely a summary of the chapters/sections of Stallings that have already been assigned: 1,3,4,5,6.1-6.6,7,8,9,11,12.
Final Exam: The final exam will not cover the Windows NT file system. Tomorrow in lecture I will hand out copies of section 21.7 of Silberschatz and Galvin, Operating System Concepts, 5th ed. It contains a more detailed description of the UNIX file system than Stallings provides.
Course Eval: From one of the course evaluations:
Clarification: [This is in response to Alex's question during P436 yesterday.] With mount-based naming (at least in Sun NFS), mounts by a machine S acting as a server have no effect on other machines, including machines that mount directories from S. In short, as I said in lecture: A mount affects only 1 machine, namely, the machine that performs the mount.
Demos: Recall from the Project Guidelines:
Exams: Here is the 1997 P536 Final Exam. Here is the 1996 Final Exam. If you have questions about them, feel free to ask (preferably by posting to the newsgroup or by coming to office hours).
Schedule: Having 3 lectures during the last week does leave less time to study for the final. (This is more a concern for P536, which has an earlier final exam.) To alleviate this concern, the final exam won't contain questions on material discussed during the last lecture and not discussed in the textbook or the handouts on distributed file systems.
Handout: P536 ONLY: This handout about Sun NFS was distributed during lecture. The handout with the hand-drawn figures is not available on-line; if you didn't get a copy, stop by my office, or copy it from a classmate.
Colloquium: While debugging nachos, you might have gotten the impression that concurrent systems are relatively difficult to design and debug. What can be done about that? I encourage everyone to attend the CS Dept. Colloquium at 2:15pm on 4 December and hear Rance Cleaveland describe tools he has developed for simulating and verifying concurrent systems. Here's the abstract of his talk.
Erratum: Shortly after I posted the solutions to midterm2 on 16 Nov, I edited that file to correct the answer to problem 7 (the correct answer is 10 disk accesses; the old answer was 9). I thought nobody would have printed the file during that interval (about an hour, I think), but apparently some people did. Those people might want to print a new copy.
Clarification: probset3, problem 1b. As Stallings (page 325) says, in some systems with multi-level page tables, lower-level page tables are stored in virtual memory, so that lower-level page tables that have been allocated but have not been used recently can be paged out. In such systems, the non-lowest-level page tables contain virtual addresses rather than physical addresses, and typically the page tables are aligned to start on page boundaries, so the non-lowest-level page tables actually contain the VA divided by the page size (i.e., the VPN). (This is analogous to the alignment of the L2 page table on a 2-byte boundary in my solution to this problem.) If you answered problem 1b based on this assumption, that's fine. If you didn't get credit for it, please show us your solution, and we'll change the score.
Erratum: In my solution to Problem 2, two occurrences of i should be changed to i/T, and one occurrence of i0 should be changed to i0/T. It's easy to see which occurrences are incorrect by checking the units (PFF should have units of sec-1). I updated the on-line solutions.
Problem Set: Here are Solutions to Problem Set 3.
Erratum: In the lecture notes, Topic IV (Memory Mgmt), section 3.2.4, the following line of code was omitted from the end of the clock algorithm: "advance ptr to next candidate". Adding this line makes my description of the clock algorithm consistent with Stallings, Figure 8.14.
~os/bin/readable
is disabled, due to possible
security concerns. Sorry, you'll have to continue using
getfacl
for now.
Textbook Non-Readings: We won't be discussing chapter 13.
Non-Textbook Readings: Don't forget to pick up and read the handout on distributed file systems. If you'd like to read more about the Windows NT File System, see section 23.5 of Silberschatz and Galvin, Operating System Concepts, 5th ed. I requested that this book be put on reserve in Swain Lib.; it should be there by Nov 16.
Textbook Readings: The textbook's home page (see above link) contains an errata list (in case you didn't notice already).
Clarification: probset3, problem 3 (Stallings, problem 7.10). [superseded by comment above (11 Nov).]
Project: ~os/bin/readable
is sometimes inaccurate.
I'll let you know when I have fixed it.
Exam: The date of midterm2 has changed! Midterm2 will occur on 18 November.
Schedule Change: I will be out of town on Mon, 30 Nov. Consequently, during that week, a discussion section will be held in the lecture timeslot (and location) on Monday, and a lecture will be held in the discussion-section timeslot (and location) on Thu (for P536) or Fri (for P436).
Project: As you know, getfacl can be used to determine whether user
"os" can read a given file. An even easier method is now available,
absolutely free! Simply run ~os/bin/readable
, giving it the
name of a file as an argument. If user "os" can't read the specified
file, you will see a message like "foo.cc is unreadable by os or
nonexistent." (otherwise, you will see no message). Incidentally, this
shell script was easily written by exploiting the "set user-id bit", a
feature found in (almost?) all versions of UNIX.
Clarification: probset3, problem 7. You might also want to discuss related issues, for example, how much of the data structure is protected by each mutex (e.g., the entire table or just one entry).
Handout: Amazingly, our textbook lacks a chapter on distributed file systems. I photocopied some material on distributed file systems from another OS textbook. The copies are available in the Lindley 201 suite; they are in a box on your right just inside the door of the suite. Please pick one up (and read it).
Handouts: Distributed in today's lecture: Problem Set 3 and proj5.
Exam: Midterm2 potentially covers everything up to and including part 6 (Directories in UNIX) of Topic VI (Filesystems). The rules regarding what materials you may use during the exam are the same as for midterm1.
Project: In my email on 13 Oct about how to read in the executable,
in Method 2, I included three ASSERT statements reflecting properties of
executables produced by the cross-compiler. Those ASSERT statements are
not quite right. Here is an improved version. Thanks to sviswana and
grbarnet for pointing this out.
ASSERT(noffH.code.virtualAddr == 0);
ASSERT(noffH.initData.size == 0 || noffH.initData.virtualAddr == noffH.code.virtualAddr + noffH.code.size);
ASSERT(noffH.initData.size == 0 || noffH.initData.inFileAddr == noffH.code.inFileAddr + noffH.code.size);
dbx nachos
and then type
help check
and help suppress
.
Project: Some teams are having difficulty setting ACLs correctly. To help make this more convenient, I just revised part of the discussion of ACLs on the Project Mechanics page; click here to see the revised part.
Happy Halloween! (I never quite understood what Halloween is about, but I suppose any holiday is better than no holiday.)
Demos: P436 ONLY: proj3 demos should be completed by Nov 6.
Project: Some teams are having trouble with #include; the symptom is that the compiler complains that some classes and variables are undefined when they are first used. A good way to debug these problems is to look at the code produced by the C preprocessor. You can do this using the -E command-line option to CC or gcc (instead of the usual -c option), which sends the preprocessor's output to standard output, instead of compiling it. When you look at (e.g.) addrspace.h, note that ADDRSPACE_H is #define'd before the declarations in addrspace.h are actually processed.
Project: If you come to the instructor or an A.I. with questions
about nachos, we would appreciate it if you would first ensure that all of
your code is readable by user os
.
Colloquium: We encourage you to attend the colloquium tomorrow at 2:15pm!
Textbook Readings: Regarding Chapter 11, I haven't decided yet whether we will discuss RAID, so you can skip Section 11.7 for now.
Project: P536 ONLY: Each team should have received its proj3 score in lecture on Mon, 26 Oct.
Handout: Typical Steps in Memory Access was distributed in lecture on Mon, 26 Oct.
Handout: Readers/Writers using Locks and Condition Variables was distributed in lecture on Mon, 26 Oct., on the back of the Barrier Synchronization handout.
Project: P436 ONLY: Slip time consumed in your original proj3 submission (before midterm1) is restored, i.e., should not be subtracted from your remaining slip time.
Project: P436 ONLY: As announced in lecture about 2 weeks ago, P436 teams must re-submit proj3 on Mon, 26 Oct.
Grading: Some grading statistics have been added above.
Textbook Readings: I/O: Chapter 11. You can skip the material on disk scheduling policies (pp. 466-470). [Added on 28 Oct: I haven't decided yet whether we will discuss RAID, so you can skip Section 11.7 for now.]
Office Hours: I will have an extra office hour on Mon, 19 Oct, 10:15-11:15.
Problem Set: Here are (corrected) Solutions to Problem Set 2. The original solution to Problem 4b was incorrect. The corrected solutions say "Version: 15:10, 15 Oct 1998" near the top. Sorry for the confusion.
Exam: As part of preparing for midterm1, I recommend that you look over Thread Pseudo-Code. The latest version has "8 Sep 1998" in the first line.
Exam: Contrary to what I said in lecture yesterday, you can bring and use your own notebook for midterm1. (I don't expect this to have a significant effect on the results.) Of course, the exam is still open textbook (Stallings, OS, 3rd edition). You may not bring someone else's notebook 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. You may a dictionary, if you like.
Demos: From now on, the default location for all demos with Yu Ma is the Burrow (LH004). If you would like a different location, please mention this when you schedule your demo.
Problem Set: When I printed probset2, I had forgotten about the career and interview fairs, so the due date of probset2 is postponed to Wed, 14 Oct. Sorry for all the postponements.
Problem Set: For probset2, problem 3 (Stallings, problem 5.3), you can skip part b. Part a is slightly tricky, so think carefully about it. You should make the usual assumptions about concurrency, i.e., (1) preemption is possible after every machine instruction; (2) the scheduler is fair (hence each process eventually runs to completion) but otherwise arbitrary.
Office Hours: Kshitiz's office hour on 6 Oct (only) is moved to 3:30pm-4:30pm.
Project: FOR P436 ONLY: Due to the CS Career Fair and Interview Fair, the due date for proj3 is postponed to Fri, 9 Oct.
Grading: Grading Statistics for proj1 have been added above.
Project: As described in two recent news postings (with subject: eof), I modified machine/console.cc. You might want to copy the new version; you are also free to continue using the original version. (Reminder: Everyone should read the course newsgroup, as well as the web page.)
Project: FOR P436 ONLY: The due date of proj3 has been postponed to Wed, 7 Oct, because paging has not been discussed in P436 lecture yet (it will be discussed in discussion section on Fri and in lecture on Mon). (For P536, the due date of proj3 is unchanged.)
Project: The declaration of Join in syscall.h is unsatisfactory, because if Join returns -1, there is no way for the caller to know whether the child returned -1 or the call to Join produced an error (e.g., invalid argument). As a simple workaround, you can assume that processes never have exit values less than (say) -1000, so Join can use numbers below that to indicate its own errors. Here is a revised description of Join:
int Join(SpaceId id, int *exitStatus);
Project: In Exec, if there is not enough free memory to run the process, Exec should return an error value (e.g., -1).
Project: The description of proj3 mentions items (a)-(d) that you need to do. The easiest way to accomplish item (d) is to use the -rs command-line argument to nachos. See the code for details.
Project: I modified test/bad-child1.c. Please copy the new version. You might want to use it as a testcase.
Project: FOR P436 ONLY: The due date of proj3 has been postponed by one day. It is due (by midnight) on Mon, 5 Oct 1998. (For P536, the due date of proj3 is unchanged.)
Project: For projects 3 and after, it must be possible to run all of the testcases described in your README or TESTCASE file without recompiling nachos. (It would be nice if this is the case for project 2, too.)
char name[] = "test";
char *name = "test";
Demos: Please sign up for a demo for proj2! Demos will be held starting Tue, 29 Sep. To sign up, consult the appropriate signup sheet and then have one team member send email to the appropriate A.I., suggesting a few timeslots when your team is available. The A.I.s will update the signup sheets as timeslots get taken. For all teams in P436, the appropriate A.I. is Yu Ma. For teams in P536, some member of each team will receive email indicating which A.I. is holding demos for that team's projects. By default, for demos with Yu Ma, come to LH301E, and for demos with Kshitiz, come to LH301I. The "travelling A.I.s" will be happy to come to any room in Lindley Hall (including the Burrow) for your demo. So, if you prefer to hold your demo in a different room, please indicate the room number in your email, and the A.I. will meet you there. Each timeslot is only 20 min, so it is important for you to be on time; if you are late, you might be asked to re-schedule your demo. (I assume people saw this announcement about demos.)
Project: As someone pointed out in P436 lecture yesterday, in Nachos,
the Create system call returns void, so there is no way to indicate an
error to the user program. I can't imagine why nachos' designer did that.
The corresponding Solaris system call does have a return value (see
man -s2 creat
). Fortunately, this problem is easily fixed.
In userprog/syscall.h, change
void Create(char *name);
int Create(char *name);
Project: Preliminary design documents are optional for all remaining projects (i.e., proj3 and following). I have modified the proj2+3 handout to indicate that the preliminary design document is now optional for proj3. As mentioned in lecture, the proj2 preliminary design documents will not be included in the grading of proj2, due to the confusions that arose last week.
Project: I would like to re-emphasize two of the important points that were made in lecture today: (1) You should use FileSystem and OpenFile methods, as done in the supplied code in exception.cc. Since FILESYS_STUB is defined, the FileSystem and OpenFile methods call routines in machine/sysdep.cc; those routines call UNIX file system operations. (2) In preliminary design documents and READMEs, you may describe your design in whatever way you think is best, possibly but not necessarily using pseudo-code. Sorry for the confusion.
Project: Don't forget that the preliminary design document (described here) for project 2 is required and is due on 20 Sep (i.e., 1 week before proj2 is due). The submission procedure is described here.
Plagiarism: As you know (see Academic Integrity), copying another team's code, in part or whole, is prohibited. This semester, to help deter and detect such behavior, we will use software that automatically compares and reports similarities between programs.
Demos: More information about demos has been added here.
Textbook Readings: Chapter 5. You can skip the discussion of Dekker's Algorithm on pp. 197-202.
Problem Sets: Solutions to problem sets will usually be posted within a day after the assignment is due. If you have not submitted your work before solutions are posted, you will receive a zero for that assignment.
Handout: The Address-Space Example handout is not available on-line; ask the instructor or a classmate if you need a copy. Hardcopy distributed in lecture on 9 Sep.
Project: Projects 2+3 are now available. Harcopy distributed in lecture on 9 Sep.
Solutions: Here are Solutions to Problem Set 1. Harcopy distributed in lecture on 9 Sep.
Textbook Readings: Chapter 4.
Cancelled Office Hours: The instructor's office hours will be cancelled on Sep 14 and 16, since the instructor will be attending a conference. Kshitiz will give the lectures on those two days.
Schedule Change: The time for Yu Ma's office hour on Thursday is now 1:30pm-2:30pm.
Grading: 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.
Erratum: In the P536 lecture, I said that the pseudo-code for is a user-level implementation of threads. But the pseudo-code contains statements that enable or disable interrupts, and the kernel does not let user programs directly enable or disable interrupts. Thanks to the student who pointed this out. Sorry for the confusion. Let me try to clear it up. There are two ways to think about this code.
Handouts: The handout on Monday is: Thread Pseudo-Code.
Submitting Problem Sets: I added information about this above.
Office Hours: Students in both classes are welcome to attend office hours of both A.I.'s.
Repeat: I just want to make sure that everyone noticed the correction to probset 1 that was posted below on 2 Sep.
Erratum: In the Detailed Instructions
for Copying Nachos, there were a few places where I wrote
nachos
but should have written nachos-dfs
.
It is correct now.
Project Demos: I just updated the description of demos on the Project Guidelines page.
Cross-compiler: I just added some comments about Cross-Compiling User Programs to the Project Mechanics page.
Bug! I just corrected an error in /u/os/nachos-dfs/code/test/Makefile, so if you already copied nachos, please re-copy that file. Sorry for the inconvenience.
Textbook Readings: Chapter 3.
Grading: I decided to make the 3 exams carry closer-to-equal weights. Sorry for the vacillation.
Administrivia: Please read the comments about Newsgroups vs. Email.
Correction: For Probset 1, problem 3: assume data can be copied directly from any level to level 0, and re-define bi to be the time to transfer a block of data from memory level i to memory level 0. (This model is more general.) Also, for simplicity, assume there is no additional cost associated with discarding a block of data from a memory level (e.g., because the additional transfer needed if that block of data is dirty can be done concurrently with the transfer of the data that is replacing it). I have revised the on-line version of the problem set to reflect these changes.
Handouts:The handouts distributed on Wednesday are: Nachos code. If you didn't get a copy, you can pick one up from the box outside the instructor's door.
Textbook Readings: Chapter 1, including its appendices. You might also want to read the textbook's Errata, available via the textbook's home page (see link above).
On Reserve: I have requested that a copy of the textbook be put on 24-hour reserve in Swain Hall library; it should be available in about a week. If you want another perspective on some of the material, 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.
C++ Books: For students who are unfamiliar with both C and C++, I have added suggestions for two books on C++ to the Project Mechanics page.
Handouts:The handouts distributed on Monday are: Problem Set 1, Project 1, Project Guidelines, A Quick Introduction to C++, and Roadmap to Nachos. You can easily print them yourself. If you didn't get a copy of the Nachos code, let me know.
Project:
(1) Try to form teams by Monday, Sep. 7.
(2) Carefully read the Project Guidelines page.
(3) Carefully 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 ~os/nachos-dfs/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.