P436: Operating Systems
P536: Advanced Operating Systems

Fall 1998

Instructor

Scott Stoller

A.I.

P436: Kshitiz Sharma

P536: Yu Ma

Table of Contents

Hours
History
Official Course Description
Syllabus
Textbook
Project, Project Guidelines, Project Mechanics
Guidelines for Problem Sets
Academic Integrity
Course Newsgroup
Newsgroups vs. Email
Grading
Statistics
Demo Signup Sheets
Announcements
On-line Course Evaluation for P436 / On-line Course Evaluation for P536

Hours

P536 Lectures: Mon and Wed, 2:30PM - 3:45PM, in SE 105.
P536 Discussion: Thu, 7:15PM - 8:05PM, in BH 006.

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

P536

Tentative Syllabus

LecturesTopic
1Introduction
2-12Processes and Threads: Synchronization, Scheduling, Deadlock
13-17Memory: Segmentation, Paging, Virtual Memory
18-20I/O, Filesystems
21-22Protection
23Distributed Systems: Introduction
24-25Communication: Messages, RPC, Group Communication
26-28Distributed Filesystems

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

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.

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.

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.

Project Guidelines

Project Mechanics

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.

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.

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.

Grading

The breakdown (updated 3 Sep 1998) is:
Project + problem sets45%
Midterm 1 exam17%
Midterm 2 exam17%
Final exam21%
Grading on the project emphasizes good design as well as working code. Exams focus on lecture material and textbook readings but may cover all aspects of the course, including the project. The midterms are 75-minute, in-class exams. The final is a 2-hour exam held at the time specified in the Registrar's
Schedule of Final Examinations. The exams are (potentially) cumulative, e.g., midterm2 and the final may cover material from the beginning of the course. All exams are "open textbook".

Grading Statistics

The following statistics and histograms may be slightly inaccurate, due to late submissions, score adjustments, etc.

P436 Statistics

ItemMeanStd.Dev.Histogram
probset1 (out of 15)8.83.2
proj1 (out of 20)17.91.8
proj2 (out of 50)44.92.6
probset2 (out of 25)15.03.4
midterm1 (out of 60)33.1 (55%) 8.9histogram
proj3 (out of 50)36.07.6
probset3 (out of 35)22.75.2
midterm2 (out of 60)32.7 (54.5%) 9.9histogram
proj4 (out of 50)33.08.7
final (out of 70)36.3 (52%)10

P536 Statistics

ItemMeanStd.Dev.Histogram
probset1 (out of 15)12.71.5
proj1 (out of 20)19.70.7
proj2 (out of 50)48.12.1
probset2 (out of 25)21.12.3
midterm1 (out of 60)41.1 (68%) 9.0histogram
proj3 (out of 50)45.73.4
probset3 (out of 35)30.45.3
proj4 (out of 50)45.73.3
midterm2 (out of 60)43.0 (72%) 7.5histogram
proj5 (out of 50)40.211.8
final (out of 70)47.3 (68%) 10.8histogram

Demo Signup Sheets

Yu Ma's Signup Sheet
Kshitiz's Signup Sheet


Announcements

20 Dec

Enjoy the Winter Break!

19 Dec

Grades: P436 course grades have been sent by email. If you didn't receive yours, let me know.

Final Exam: Grading statistics for the P436 final exam have been added above.

18 Dec

Final Exam: The solution to problem 6 of the p436 exam was incorrect. It has been fixed.

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.

17 Dec

Project: P536 students can pick up their graded proj5 README any time.

Grades: P536 course grades have been sent by email. If you didn't receive yours, let me know.

15 Dec

Final Exam: Grading statistics for the P536 final exam have been added above.

13 Dec

Course Eval: I would like to thank everyone who took the time to fill out the on-line course evaluation. I would like to thank the people who wrote good things even more. :-)

Final Exam Location: The final exam will be held in the same room as the lectures.

12 Dec

Final Exam Solutions: Here are solutions to the 1997 P536 final exam and the 1996 P436/P536 final exam.

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.

10 Dec

Final Exam Solutions: Here are the 1998 P436 final exam and the 1998 P536 final exam, with solutions. They are encrypted with triple DES.

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.

9 Dec

Extra Office Hour: I will have an extra office hour: 11am-noon, Sun, 13 Dec.

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.

8 Dec

Project: Grading statistics for P436 proj4 have been added above.

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:

I'm also unimpressed with the wording of many of the questions on the evaluation form. Some day I'll try to get the wording improved.

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.

7 Dec

Course Eval: Please fill out the On-line Course Evaluation. (I put links to it the Table of Contents so you can easily find them later.) Your comments and suggestions would be appreciated. The deadline is 14 Dec. If you fill out the evaluation form and then change your mind, you can revise your answers until the same deadline.

6 Dec

Project: Extra-credit projects can be submitted separately; submit them in the same way as other projects. Extra-credit projects must be demo'd to Yu Ma or Kshitiz. All demos must be completed by Tuesday, December 15. All projects (including extra-credit) must be submitted at least 24 hours before being demo'd, to give the A.I. time to look over it. Extra-credit projects can be demo'd at the same time as proj4 or proj5, provided the above timing constraint is satisfied.

Demos: Recall from the Project Guidelines:

If there exists a team member who has not been the spokesperson for any demo so far, then some such member must be the spokesperson for the team's last demo. (I believe there are no teams with more than one such member.)

2 Dec

Colloquium: While debugging nachos, you might have gotten the impression that concurrent systems are relatively difficult to design and debug. I encourage everyone to attend the Colloquium at 2:15pm on Fri, 4 Dec, and hear Prof. Rance Cleaveland from SUNY Stony Brook describe tools he has developed for simulating and verifying concurrent systems.

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.

1 Dec

Project: Regarding proj5: You should think about and briefly discuss in your README the behavior of your cache when multiple user processes in a single nachos "machine" (Solaris process) open the same file. (This issue was already mentioned in discussion section.)

23 Nov

[Thanksgiving] Happy Thanksgiving!
(It took me a long time to find this picture of a "tofu turkey".)

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.

20 Nov

Project: FOR P436 ONLY: proj4 demos should be finished by 4 Dec. The "slip-time clock" for proj4 does not tick during Thanksgiving break, defined as the end of Tue, 24 Nov, through the end of Sun, 29 Nov. For example, if you submit proj4 at 1 AM on Mon, 30 Nov, then you used up 25 hours of slip time.

19 Nov

Exam: Here are Solutions to Midterm2. If you have questions about the grading of midterm2, please start by asking the person who graded the problem in question (during office hours, if possible): Scott for problems 2, 4, and Extra Credit; Yu Ma for problems 1 and 3; Kshitiz for problems 5 and 6. This will help ensure consistency of grading.

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.

18 Nov

Grading: Grading statistics for midterm2 have been added above. Exam booklets will be returned during discussion section on Thu (for P536) or Fri (for P436).

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.

17 Nov

Grading: Grading statistics for P536 proj4 have been added above.

16 Nov

Exam: Here are Solutions to 1997 Midterm2.

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.

15 Nov

Office Hours: My office hour on Wed, 18 Oct, will be 10:15-11:15.

13 Nov

Grading: Grading statistics for probset3 have been added above.

12 Nov

Erratum: The proj5 handout mentions calling Remove on remote files as a testcase. Ignore that; you don't need to implement remove for local or remote files. I updated the on-line version of the handout.

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.

11 Nov

Clarification: probset3, problem 3 (Stallings, problem 7.10). Below (9 Nov), I wrote: "f is the average fraction of memory occupied by the hole." Actually, it is somewhat simpler to interpret f as including memory in segments that have been deleted, as well as memory in the hole. Either interpretation is fine, provided you state your interpretation explicitly. Incidentally, these two interpretations of f differ by a factor of 2, because on average, half of the free memory is in the hole.

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.

10 Nov

Project: ~os/bin/readable is disabled, due to possible security concerns. Sorry, you'll have to continue using getfacl for now.

9 Nov

Non-Textbook Non-Readings: Too many to list. :-)

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.

8 Nov

Grading: Grading statistics for P436 proj3 have been added above.

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.

7 Nov

Project: Protection is an important aspect of OS. One small thing you learn in this course is how Solaris file protection works. You can demonstrate this knowledge by submitting proj4 (for P436) or proj5 (for P536) with correct file permissions. This means: user "os" can read the files, and other students cannot read the files. If the permissions are not set correctly, 3 points will be deducted from your score. If you believe the information about ACLs on the Project Mechanics page provides insufficient background for this task, please tell me the deficiencies, and I will remedy them.

5 Nov

Exams: Here is the 1997 P436/P536 Midterm2.

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).

4 Nov

Typo: In probset3, problem 2, please change "one or ways" to "one or two ways". (I fixed the on-line version.)

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.

3 Nov

Demos: P436 ONLY: Reminder: proj3 demos should be completed by 6 Nov.

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);

2 Nov

Project: workshop often dies when debugging nachos with access checking enabled. This is unfortunate, since access checking is quite useful. If you want to use access checking, try running dbx directly (from a shell or inside emacs or xemacs) instead of using workshop. For help on access checking, run 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.

31 Oct

Project: I just added the following to the end of the proj4 handout: For extra credit, you might want to implement the Fork and Yield system calls, to provide support for multi-threaded user programs. This is worth up to 15% extra credit. Naturally, the actual amount of extra credit will depend on the correctness and efficiency of your design and implementation and the quality of your documentation. P536 ONLY: The extra credit does not need to be completed by the proj4 due date; you can also include it as part of your proj5 submission.

Happy Halloween! (I never quite understood what Halloween is about, but I suppose any holiday is better than no holiday.)

30 Oct

Office Hours: Yu Ma's office hour on 6 Nov is moved to 4pm-5pm.

29 Oct

Demos: P536 ONLY: proj4 demos should be completed by Nov 13.

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!

28 Oct

Textbook Readings: File Systems: Chapter 12.

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.

27 Oct

Project: I intended to mention this in the proj4 handout but forgot. (Sorry.) When a page fault occurs, Machine::RaiseException stores the offending virtual address in BadVAddrReg, so your exception handler can obtain it by using machine->ReadRegister(BadVAddrReg).

26 Oct

Handout: In the Barrier Synchronization handout, please change the two upside-down exclamation points to "less than" symbols (<). Also, the code in the handout relies on the following assumption about the implementation of semaphores: If one or more threads are blocked on semaphore s when Up(s) is called, then one of those blocked threads is woken up. I believe this assumption holds for all reasonable uniprocessor implementations of semaphores. However, my original specification of semaphores does not imply this property, and multiprocessor implementations of semaphores that use busy-waiting might not satisfy it. Sorry for the confusion. Here is an updated version of the handout, reflecting these corrections: Barrier Synchronization.

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.

23 Oct

Project: Implementing pre-cleaning is worth up to 15% extra credit for proj4. Naturally, the actual amount of extra credit will depend on the correctness and efficiency of your design and implementation and the quality of your documentation. P536 ONLY: The extra credit does not need to be completed by the proj4 due date; you can also include it as part of your proj5 submission.

Project: P436 ONLY: As announced in lecture about 2 weeks ago, P436 teams must re-submit proj3 on Mon, 26 Oct.

22 Oct

Exam: Midterm2 will occur on 16 November.

21 Oct

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.

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.]

19 Oct

Exam: Here are Solutions to Midterm1. 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 problems 1 and 3; Yu Ma for problems 4 and 6; Kshitiz for problems 2 and 5. This will help ensure consistency of grading.

16 Oct

Demos: Teams in P536 must hold their demo for proj3 by Fri, 23 Oct.

Office Hours: I will have an extra office hour on Mon, 19 Oct, 10:15-11:15.

15 Oct

Exam: You can bring all course handouts (e.g., Address-Space Example and official solutions to problem sets). You can bring your own solutions to problem sets. You may not bring another student's solutions or a mechanical reproduction of all or part thereof.

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.

14 Oct

Project: proj4 is now available, though I don't expect or recommend that people start working on it until after midterm1.

13 Oct

Clarification: For probset2, problem 4, part b. You get different answers depending on whether you assume ((0-1)\%2) equals 1 (i.e., standard modulo arithemtic) or -1 (as in C). Please use the former interpretation. However, if you have already done the problem using the latter interpretation, we'll accept it.

12 Oct

Midterm: Midterm1 will potentially cover all material (from lecture or assigned textbook readings) that precedes memory management. Also, you might want to re-read the general comments about exams.

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.

6 Oct

ACLs: If you are still having trouble with ACLs, you might want to read the updated version of Rob's Intro to ACLs.

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.

5 Oct

Problem Set: Problem Set 2 was distributed in lecture today (but I ran out of them in P436).

Office Hours: Kshitiz's office hour on 6 Oct (only) is moved to 3:30pm-4:30pm.

4 Oct

Exams: Here is the 1997 P436/P536 Midterm, with solutions.

Project: FOR P436 ONLY: Due to the CS Career Fair and Interview Fair, the due date for proj3 is postponed to Fri, 9 Oct.

3 Oct

Project: FOR P536 ONLY: The due date for proj3 is postponed to Mon, 5 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.)

1 Oct

Project: I just added this sentence to the description of READMEs on the Project Guidelines page: If you think of a nifty design for some nachos feature but decide to implement a limited or less efficient design due to time constraints, describe the nifty design in your README, so we know you thought of it. (Describe the implemented design, too.)

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:

Next year, I plan to change the declaration of Join in syscall.h to be:
int Join(SpaceId id, int *exitStatus);
The idea is that Join always returns its own status and if the call to Join is successful, the exit status of the child is stored in 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.

30 Sep

Textbook Readings: Memory Management: Chapters 7 and 8.

28 Sep

Clarification:In today's P436 lecture, someone asked whether the interrupt level needs to be restored in Semaphore::Down or Thread::Sleep. I said yes. In fact, the answer is no. By inspection of the thread-pseudo-code or the code in threads.cc and scheduler.cc, you can convince youself that the following invariant holds: interrupts are always off when SWITCH is called. So, when a thread get the CPU back, if it wants interrupts to be off, it doesn't need to do anything. Conseuqently, convention C2 should be revised slightly. The new version is: A caller of Sleep must disable interrupts before calling Sleep and must re-enable interrupts at an appropriate point after Sleep returns (because interrupts are disabled when Sleep returns). In Semaphore::Down, the appropriate point for re-enabling interrupts is at the end of the method body.

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.)

27 Sep

Project: If nobody on your team received a message indicating which A.I. is conducting demos for your team, please let me know.

25 Sep

Exam: The first midterm exam will be in class on 19 October.

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.)

24 Sep

Project: In cross-compiled programs, do not use declarations of the form
char name[] = "test";
Use
char *name = "test";
instead.

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.)

23 Sep

Erratum: In the P536 lecture, when I wrote convention C2 on the chalkboard, I accidentally omitted part of it (namely, the part in italics below). The correct version is: A caller of Sleep must save the interrupt level and disable interrupts before calling Sleep, and must restore the interrupt level after calling Sleep.

22 Sep

Project: Here's a summary (which appeared in a news posting yesterday) of what you need to do for proj2: implement console I/O; implement the Create system call; bullet-proofing; write and run testcases for valid and invalid arguments to the system calls. [30 Sep: I should have added: in Exit, close all open files of the exiting process.]

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);
to
int Create(char *name);
I made this change in ~os/nachos-dfs/code/userprog/syscall.h . Everyone should copy the modified file or make the change directly. You also need to add code in exception.cc to put the return value in the appropriate register (just like the other system calls with return values). You should also modify your user-level test programs to take account of Create's return value.

21 Sep

Project: The proj2+3 handout says not to change files in the machine directory. This is not because we want to stifle your creativity. It is because most of the files in that directory define the simulated hardware, and programmers do not normally have the opportunity to modify the hardware. Some files in that directory (such as sysdep.cc) do not define simulated hardware. If you want to change those files, that's OK, provided you describe and justify those changes in your README.

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.

16 Sep

Here are the lecture notes on CPU Scheduling.

14 Sep

Here are the lecture notes on Deadlock.

12 Sep

Textbook Readings: Deadlock: Sections 6.1-6.6. CPU scheduling: Chapter 9.

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.

10 Sep

Bug! When you start working on proj2, you will need to compile nachos in the userprog directory. It will complain that PerformanceTest, Copy, and Print are undefined. This is because of a mistake in code/Makefile.common, which I have just fixed (10 Sep, 10:32). Please re-copy this file! (In case you are interested, the changes are: adding ../filesys/fstest.cc to USERPROG_C and adding fstest.o to USERPROG_O.)

Week of 7 Sep

Statistics: Grading statistics appear above.

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.

In Nachos, the thread code is kernel-level with respect to the simulated hardware and user-level with respect to the real hardware. Thus, simulated timer interrupts can cause context switches, but real timer interrupts don't. I was confused during the P536 lecture because I forgot to distinguish between the real and simulated worlds. Don't do that!

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.

Week of 31 Aug

Growth Rate: This web page will grow more slowly in the future.

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.