- HAPPY HOLIDAYS!
- Go to our Piazza course page for the most up-to-date announcements.
- Links to papers on why you should consider closing your laptop in class in Resources
ProfessorFabián E. Bustamante
Technological Institute, L465
+1 847 491-2745
Location and Time
Lectures: Tuesdays and Thursdays 11:00AM-12:20PM
Frances Searle Building 1-421
Discussion Sessions: Wednesdays 6:00-6:50PM
Tech Institute M345
Professor Office Hours: by appointment
TA Office Hours: * Wednesdays: Immediately after discussion in T-Lab. 6:50 PM - 7:30 PM * Thursdays: After lecture in T-Lab. 12:30 PM - 1:30 PM
Final Exam:Tuesday Dec. 6, 2016 - 12-2PM
An introduction to basic concepts in modern operating systems. Topics include operating systems structures, processes, threads, synchronization, deadlocks, CPU scheduling, and memory management.
- EECS-214 Data structures and data management.
- EECS-213 Introduction to Computer Systems
- Familiarity with basic computer architecture concepts and proficiency in C programming in UNIX systems.
Operating systems control all of a computer's resources and present users with the equivalent of virtual machines that are easier to program than their underlying hardware. This course provides an overview of fundamental operating system principles, complemented with discussions of concrete modern systems to help you understand how these principles are applied in real OSs. Topics covered include an overview of the components of an operating system, mutual exclusion and synchronization, implementation of processes, threads, scheduling algorithms, memory management and file systems.
Although the main learning objective of the course is to understand the requirements, design and implementation of modern operating systems, at a higher level the course aims to provide you with a good grasp of basic abstractions employed in system-level software (such as processes, threads, virtual memory, caching, etc.), while uncovering the "magic" that happens inside the box.
The course has a strong project component intended to provide essential experience in designing and implementing complex systems and working as part of a team. In designing the projects and estimating their required effort/hours, I am assuming you are (1) familiar with basic computer organization and data structures and (2) capable of programming in C in UNIX (or UNIX-like) systems (experience with pointers, explicit dynamic memory allocation, multi-file projects, etc.).
The course is organized as a series of lectures, TA sessions, reading, quizzes/homeworks, projects and exams:
- Lectures - A set of lectures through which I present the core of the material.
- TA Sessions - Discussion sessions held by the TAs to answer questions about the lecture, readings, homework assignments, and projects.
- Readings - Textbook reading in preparation for (not substitution of) the lecture and additional reading for those interested in delving further into some topics. The outline includes the reading assignments. Each exam, midterm and final, will include two extra credit questions based on the reading list.
- Homework/Quizzes - A series of homework-type questions from (or similar to those in) your textbook, aimed at reinforcing the material covered in the reading and the lectures. This year we will try short in-class quizzes instead, with exactly the same goal as homework assignments. A last homework assignment on the reading material for our last lecture. Collectively, these assignments serve as a sample final.
- Projects - Four programming projects to give you a better understanding of the subject matter and some experience with system level programming including thread-level programming.
- Exams - A midterm and a final exam covering the material presented in lectures, homework assignments and projects. Each exam, midterm and final, will include two extra credit questions based on the reading list. You'll be able to bring one page of notes to assist you during the exam.
There are a number of communication channels set up for this class:
- We use the course web site to post homework assignments, projects, announcements, etc. You should check this regularly.
- We use Piazza for class discussion and announcements. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on our Piazza. To register go here.
- Finally, there is always email for questions that would be inappropriate to post on the newsgroup (source code being a good example).When using email to contact the staff, please start your subject line with "eecs343: helpful-comment" to ensure a prompt response.
Textbook and Reading ListThere is no "official" book for the course. A few books we have used in the past include:
- Operating System Concepts, 9th Ed., A. Silberschatz, P. Galvin and G. Gagne. John Wiley & Sons, 2012. (OSC)
- xv6 book, R. Cox, F. Kaashoek and R. Morris, 2012
- Operating Systems: Three Easy Pieces, R. and A. Arpaci-Dusseau
(the authors' case for "free online books")
- Modern Operating System, 4th Ed., A. Tanenbaum and H. Bos. Pearson, 2014. ("MOS")
A set of papers providing a deeper historical perspective of operating systems, in-depth treatment of some of the topics I can only briefly cover in class, and some useful practical advice in designing and implementing complex systems.
- The IBM 701 Computer at the General Motor Research Laboratories, George F. Ryckman, IEEE Annals, Apr-Jun 1983.
- An Experimental Time-Sharing System, Fernando J. Corbato, Marjorie M, Daggett and Robert C. Daley, Spring Joint Computer Conference (AIEE-IRE), May 1962.
- Pilot: an operating system for a personal computer, D. Redell, Y.K. Dalal, T.R. Horsley, H.C. Lauer, W.C. Lynch, P.R. McJones, H.G. Murraly and S.C. Purcell, Communication of the ACM, February 1980. [Exam question]
- Lottery scheduling: Flexible proportional-share resource management, Carl Waldspurger and William Weihl, Proc. of First USENIX Symoium on Operating Systems Design and Implementation, November 1994.[Exam question]
- Virtual Memory management in the VAX/VMS Operating System, H. Levy and P. Lipman, IEEE Computer, March 1982. [Exam question]
- The Slab Alloctor: An Object-Caching Kernell Memory Allocator, J. Bonwick, In Proc. of USENIX Summer, 1994.li>
- The Working Set Model for Program Behavior, Peter J. Denning, Proc. of the First ACM Symposium on Operating Systems Principles, October 1967.
- Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism, Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska and Henry M. Levy, Proc. of the ACM Symposium on Operating Systems Principles, October 1991. [Exam question]
- Experiences with Processes and Monitors in Mesa, Butler W. Lampson and David D. Redell, Communications of the ACM, 23(2):105-117, February 1980. [Exam question]
- Design and implementation of the log-structured file system, Mendel Rosenblum and John Ousterhout, Proc. of the ACM Symposium on Operating Systems Principles, October 1991. [Exam question]
- Arrakis: The Operating System is the Control Plane, Simon Peter, Jialin Li, Irene Zhang, Dan R. K. Ports, Doug Woos, Arvind Krishnamurthy, and Thomas Anderson, Timothy Roscoe, Proc. of the USENIX Symposium on Operating Sytstems Design and Implementation (OSDI), October 2014.[Required]
And here is a list of our readings (and links) over the years ...
I use a criterion-referenced method to assign your grade; in other words, your grade will be based on how well you do relative to predetermined performance levels, instead of in comparison with the rest of the class. Thus, if a test has 100 possible points, anyone with a score of 90 or greater will get an A, those with scores of 80 or greater will get a B, those with scores of 70 or greater will get a C, and so on. Notice that this means that if everyone works hard and gets >90, everyone gets an A.
Total scores (between 0 and 100) will be determined, roughly, as follows:
- Homework/Quizzes 20%
- Projects 40%
- Exams (20% each) 40%
A note about class participation: while not explicitly included as an item in the previous list, your participation in class will be taken into consideration throughout the quarter and when granting partial and final scores/grades.
To check your grades you can use this form.
Unless otherwise indicated, homework assignments and projects are due by midnight on their due date. If you hand in an assignment late, we will take off 10% for each day (or portion thereof) it is late. Assignments that are three or more days late receive no credit.
Cheating vs. Collaboration
Collaboration is a really good thing and we encourage it. On the other hand, cheating is considered a very serious offense. When in doubt, remember that it's OK to meet with colleagues, study for exams together, and discuss assignments with them. However, what you turn in must be your own (or for group projects, your group's own) work. Copying code, solution sets, etc. from other people or any other sources (yes, that includes the Web!) is strictly prohibited. All work on the homework assignments and exams must be done individually without help of any kind. You may ask clarifying questions of the TA's and the instructor.
Please read the McCormick's Academic Integrity policy.
Remember Ignorantia juris non excusat!
Course Outline and Approximate Dates
Because one has to be an optimist to begin an ambitious project, it is not surprising that underestimation of completion time is the norm.
-- Fernando J. Corbató, ``On Building Systems that Will Fail'', 1990 Turing Award Lecture.
|09/20||Introduction [PDF]||OSC 1; MOS 1.1-1.2|
|09/22||Architecture [PDF] and OS Concepts & Structure [PDF]||OSC 1, 2; MOS 1.3, 1.5-1.7
Redell et al., 1980
|09/27||Processes [PDF]||OSC 3; MOS 2.1|
|09/29||Scheduling I [PDF]||OSC 6; MOS 2.4
C. Waldspurger et al., 1994
|10/04||Scheduling II [PDF]||OSC 6; MOS 2.4|
|10/06||Memory Management [PDF]||OSC 8; MOS 3.1-3.2|
|10/11||Virtual Memory[PDF]||OSC 9; MOS 3.3, 3.7
H. Levy and P. Lipman, 1982
|10/13||Virtual Memory [PDF]||OSC 9; MOS 3.3|
|10/18||Virtual Memory [PDF]||OSC 9; MOS 3.4-3.6|
|10/20||Virtual Machines [PDF]||OSC 9; MOS 8.3|
|10/27||Threads [PDF]||OSC 4; MOS 2.2
Lampson and Redell, 1980
|11/01||Synchronization [PDF]||OSC 5; MOS 2.3, 2.5|
|11/03||Synchronization [PDF]||OSC 5; MOS 2.3, 2.5|
|11/08||Synchronization [PDF]||OSC 5; MOS 2.3, 2.5|
|11/10||Concurrency Bugs [PDF]||OSC 7; MOS 6|
|11/15||I/O [PDF]||OSC 13, 10; MOS 5.1-5.4|
|11/17||File Systems [PDF]||OSC 11; MOS 4.1-2
Rosenblum and Ousterhout, 1991
|11/22||File Systems [PDF]||OSC 12; MOS 4.3-5|
|11/29||Distributed Systems / Research [PDF]||OSC 12; MOS 4.3-5
S. Peter et al., 2014
This calendar shows the dates for the course, including lectures, assignments, exams, etc.
There will be two kinds of homework assignments given throughout the class: reading assignments and textbook-style questions. This year we will try a new model for homework assignments, we will do 1-2 homework questions, in class, once a week. You will have 5-10' to answer and I will go over the question/answer after that. The goals is to ensure you keep up with the assigned reading.
As you can deduce from the allocation of weights for grading, programming projects make up a major portion of this class. There will be four (4) projects. Except for the first part of project 1, all projects are to be done by teams of two to three (2-3) people. Team members should work cooperatively on the design, implementation, and testing of their solution.
This quarter you will have the chance to work on a real operating system - xv6. This is a port of a classic Unix to a modern architecture (x86) inspired by the famous Lyon's Commentary on Unix 6th edition. Here is a good page we put together to get you started.
The following table of deadlines should serve you as a guideline for planning your quarter. You are given about two weeks per project. This should be plenty of time if managed carefully. Keep in mind that projects cannot be handed in more than three days late (check the course late policy for details).
You can get a copy of the handout and skeleton for any of your projects here. The skeleton for any project would be available in the format blah.tar.gz. You should save (transfer) this file to your Unix box and run % gunzip blah.tar.gz and % tar xvf blah.tar, in that order. This will create a skeleton directory that will include the source code and makefile for the skeleton as well as the associated regression testing framework.
Info on the EECS Wilkinson and T labs.
To submit your projects use the following page: SUBMISSIONS.
|Project 1: System calls and processes||09/21||09/30||TBD|
|Project 2: Memory||10/05||10/18||TBD|
|Project 3: Threads||10/31||11/11||TBD|
|Project 4: File System||11/14||11/23||TBD|
As part of every project grading a subset of 2-8 teams will be randomly selected to conduct a walkthrough of their code for the TAs and instructor. A walkthrough is a form of software peer review in which a designer or programmer leads participants through the software product, while the participants ask questions and make comments on code functionality, style, compliance to standards, etc.
Note: To be granted full credit for a project you must be able to carry the walkthrough and unquestionably show a full understanding of your own code.
A few points on the topic
- For each of the four projects during the quarter, between 2-8 teams will be selected to conduct a walkthrough
- The selection will be random with replacement; in other words, your team could be selected multiple times over the quarter
- The walkthrough must be done in the first week immediately following submission
- All team members must be present; one of the members will conduct the walkthrough while the other(s) take note of the questions and comments
- Every participant (TAs, instructor and members of other teams) can ask question about and comment on the code
- All members of the team conducting the code-review must drive the walkthrough at different times during the meeting
- Members of other teams present during a code review session are require to provide comments on the code being presented (besides their own). They can submit their comments to the TA after the session for a total of 2.5% extra (from total) points.
- Advanced Programming in the Unix Environment, R. Stevens, Addison-Wesley, 1992. A fantastic reference book for anyone writing programs that run under Unix (Highly recommended). There is also a nicely updated second edition out there.
- The Practice of Programming, Brian W. Kernighan and Rob Pike. Addison-Wesley, 1999. There is more to writing a program than getting the syntax right, fixing the bugs you have noticed, and making it run fast enough. Programs are read not only by computers but also by programmers. A well-written program is easier to understand, grade, and modify than a poorly-written one. This book is packed with great practical advice on style, design, interfaces, testing and debugging, maintenance, ...; all issues that programmers must deal with in the real world.
- The C Programming Language, 2nd Ed., B. W. Kernighan and D. M. Ritchie, Prentice Hall, 1988. ``The'' reference book.
- Chapter 12 Kernel Memory Allocation, In UNIX Internals: The new frontier, Uresh Vahalia, 1996. A nice presentation of KMA, algorithms and their evaluation.
- Concurrent Data Structures, Mark Moir and Nir Shavit, In Handbook of Data Structures and Applications, CRC Press, 2004. A useful reference, if a bit out-of-date, on concurrent data structures.
- Xv6: a simple Unix-like teaching OS - source code and book
Why you should consider closing your laptop:
- F. Sana et al., Laptop multitasking hinders classroom learning for both users and nearby peers, Computers and Education, 62:24-31, March 2013
- P. Mueller and D. Oppenheimer, The pen is mightier than the keyboard: Advantages of longhand over laptop note taking, Psychological Science, 25(6):1159-1168, April 2014
When reading papers it is normally useful to write down a summary of about a page. Your summary should include at least:
- Paper title and its author(s).
- Brief one-line summary.
- A paragraph of the most important ideas: perhaps a combination of their motivations, observations, interesting parts of the design, or clever parts of their implementation.
- A paragraph of the largest flaws; maybe an experiment was poorly designed or the main idea had a narrow scope or applicability. Being able to assess weaknesses as well as strengths is an important skill for this course and beyond.
- A last paragraph where you state the relevance of the ideas today, potential future research suggested by the article, etc.
Some interesting videos:
- Timesharing: A Solution to Computer Bottlenecks, an interview to Fernando J. Corbato by MIT Science Reporter John Fitch (Recorded January 7, 1963).
- The Final Demonstration of the Xerox 'Star' Computer, David Liddle (Recorded June 17, 1998).
Potentially useful links and tools
Here is a list of potentially useful links:
- Efficient reading of papers in Science and Technology by Michael J. Hanson, 1990, revised 2000 Dylan McNamee.
- Setup instructions for class Virtual Machine: here.
- Working with Unix/Linux.
- Peter Dinda's Unix Systems Programming In A Nutshell.
- Emacs/XEmacs -- while you can use whatever editor you like best, XEmacs has some useful libraries for C programming.
- A very nice, short tutorial from Remzi and Andrea Arpaci-Dusseau's book Laboratory: Tutorial
- C power:
- Writing Makefiles -- Peter Dinda's Make Introduction.
- gdb to the rescue -- a nice short tutorial.
- Pair programming and how to do it.
- Keeping track of changes with version control system software -- a short introduction to CVS.