CS422/522: Operating Systems, Spring 2013 [an error occurred while processing this directive] — Overview

Home  –  Schedule  –  Reference  –  Reading List  –  Tools  –  PIOS  –  Prior Years

  • Administrative
  • Overview
  • Reference Materials
  • Computers
  • Grading
  • Collaboration Policy
  • Attendance
  • Keeping In Touch

  • Administrative Information

    MW 1:00-2:15 PM, Room 200 AKW

    Bryan Ford, 411 Watson, 432-1055,
    Office hours: MW 2:30-3:30 PM, or by appointment.

    Teaching Assistant:
    Weiyi Wu, 404 Watson, weiyi dot wu at yale dot edu
    Office hours: TTh 2:30-4:00 PM, or by appointment.

    URL: http://zoo.cs.yale.edu/classes/cs422

    Course Overview and Grading

    This course covers the fundamentals of operating system design and implementation. The course takes a hands-on approach, emphasizing learning by studying the structure and implementation of existing operating systems and using this knowledge to build a new one.

    Prerequisites: CPSC 323 Introduction to Systems Programming and Computer Organization. For graduate students, an equivalent basic systems programming course or general knowledge covering C/C++ programming, programming with pointers, Unix shells, pipes, fork/join, etc.

    Lectures (20% of grade): Lectures in the first part of the course present basic operating system ideas and concepts, explaining how they manifest in the xv6 operating system, an instructional operating system that closely mirrors the structure of modern Unix systems while being much smaller and simpler.

    Labs (60% of grade): Throughout the semester, students will work in teams of 2-3 students to build their own version of PIOS, a small but real operating system, through a series of six programming labs. PIOS is substantially different in design from xv6, though it builds on the same general principles. In particular, PIOS is designed according to a microkernel philosophy, keeping the kernel as small as possible, providing only a few simple but powerfula abstractions.

    Midterm exam (20% of grade): The mid-term is held in-class, see the Schedule page. Open book, open nodes, but no electronic devices allowed. Unless prior arrangements are made, a grade of zero will be recorded for missed exam.

    Reference Materials

    This course will refer to the following textbook for background material; please either have a copy on-hand or plan to use the copy on reserve at the library:

    A. Silberschatz, P. Galvin, and G. Gagne, Operating System Concepts (Eighth Edition) , John Wiley & Sons, Inc., 2008. ISBN 0-470-12872-0. Available from the Yale bookstore or on the web.

    In lectures we will also use xv6: a teaching operating system, an instructional operating system and draft commentary by Russ Cox, Frans Kaashoek, and Robert Morris. This operating system is an x86-based rewrite of an early version of Unix, which still reflects accurately the basic structure of modern operating systems while being small and simple enough to be understood at source code level in a one-semester course.

    All xv6 materials are available online. The original xv6 home page is at MIT, but please refer to the local copies on the reference page for this class, to ensure that everyone is using the same version throughout the semester. You will want to obtain printed copies of both the xv6 commentary and source listing, preferably bound separately such that each packet lies flat and can be referred to side-by-side. We will arrange for printed and spiral-bound copies to be available from TYCO Printing.

    Several other books that may be useful in this course as optional, supplemental reference material have been placed on reserve at the Becton Library. See the reference page for a complete list, as well as links to many relevant resources available online.


    You will be using the Intel Linux PCs in the Zoo computing lab. You may access them either locally on the third floor of Watson Hall, or remotely via the following command, which will log you into a randomly-chosen Zoo machine in order to balance load on the cluster:
    	ssh netid@node.zoo.cs.yale.edu

    To access these PCs, you can either directly login from their consoles in the Zoo, or just remotely login from other machines across the campus.

    If you plan to take the course for credit, you should get an account on these machines in the first week. Please also visit the following web site to create a cs422 class directory (or just to sign up for a zoo account):


    Do not allow anyone else to use your accounts for any purpose. They are for your use alone, and you are responsible for any misuse. Your passwords control access to your accounts and should be kept secret.

    Lab Structure

    The programming labs in this course will require a substantial amount of time, both for understanding the necessary concepts, implementing the code, and (especially) debugging it. Debugging OS code is never easy — although the virtualization tools we will use in this course at least make it much easier than it used to be before those tools became readily available.

    Each programming lab will consist of two phases, each phase nominally lasting about a week:

    1. In the first phase, each student will individually implement and hand in a complete — but not necessarily fully functional or debugged — “first-cut” solution to the lab. These individual solutions will be graded only via quick visual inspection: i.e., the code must look more-or-less complete and roughly on-target, demonstrating a reasonable understanding of the material. Students are encouraged to get their first-cut solutions to compile and run as best they can during the first phase, but first-cut solutions will not be graded on functionality.

    2. In the second phase, students will work in teams of 2-3, comparing their individual first-cut solutions, combining their code as they see fit, and producing one fully functional and debugged solution per team. It is perfectly acceptable for a team simply to pick one of their members' first-cut solutions as the basis for the team solution — but if the team's membership stays the same throughout the course, the team should not always start with the same member's first-cut solution in every lab. Students may change teams throughout the semester but are not required to.

    Each lab will build on the prior lab's solution. Thus, a student's individual, first-cut solution to lab 2 will build on her team's collaborative solution to lab 1. For this reason, it is imperative that teams debug their code thoroughly. It is not uncommon for a solution to be buggy in a way that passes the automated tests we use for grading, but causes mysterious failures in subsequent labs, requiring you to go back and further debug the previous lab's code in order to get the current lab working.

    The last lab in the course will be a final project, which will not follow the two-phase model above. Instead, each team will come up with its own project idea, get instructor approval for the project, and work together to implement the project. The course will have no “sit-down” final; instead, during the final exam period, each team will demonstrate their final project to the class. This demonstration is a required part of the course, and all students are expected to show up at the final exam time unless they have made other arrangements via standard university procedures.

    Labs and Collaboration Policy

    Programming, like composition, is an individual creative process. Individuals must reach their own understanding of the problem and discover a path to its solution. During this time, discussions with friends are encouraged. However, when the time comes to write the individual solution for a given lab, such discussions are no longer appropriate: your individual solution must be your work alone (although you may ask teaching assistants or lab assistants for help in clarifying the problem or debugging your code). In your coding you are encouraged to adopt ideas suggested by classmates or other reference sources, but must carefully acknowledge the sources of those ideas in your own code and/or documentation. Once you begin to work on your team solution for phase 2, you may freely copy and combine code from any team member's individual solution, but must not copy code from any other team's solution for that lab.

    Do not, under any circumstances, copy another team's code. Writing code for use by another or using another's code in any form violates the University's academic regulations and will be dealt with harshly.

    Time Logging

    As you work on each of the programming labs, keep a detailed record of how you spend your time working on the lab. Since the programming labs are team-oriented, you are expected to work closely with your teammates on each lab, but EACH team member must keep a separate log of time spent on the lab. To do this, place a log file with a name of the form 'labN-netid.txt' in the top-level lab source directory. The log file should have the following general form, adopted from Prof. Eisenstat's CPSC 323 course:
    ESTIMATE of time to complete lab: 15 hours
          Start  Time  Lab
    Date  Time   Spent Part Work completed
    ----  -----  ----  ---- ---------
    2/08  10:15  1:00  1    Read assignment, completed cprintf exercise
    2/09  20:15  2:00  1    Studied IA-32 programmer's guide, got backtrace working
    2/10  12:45  0:30  2    Reading IA-32 system guide on trap handling
    2/10  14:00  0:30  2    Discussing trap handling approach with teammates
    2/10  16:00  2:00  2    Helped debug Bob's implementation of _alltraps
    2/12  21:20  2:00  4    First cut on coding up physical page allocation
    2/13  09:00  3:00  3    Meet, help teammates debug protected control transfer
    2/13  20:00  5:00  4    Mysterious memory corruption bug in my page allocator
    2/14  10:00  1:00  4    Aha!  Was overwriting the last page of the kernel.
    	    17:00  TOTAL time spent
    a brief discussion of the major difficulties encountered
    The format above is only an example, but your log must contain:

    Lab Handin Procedures

    For each lab, the TA will create a directory named /c/cs422/SUBMIT/labN.ontime, in which you are to copy your lab solution into a subdirectory named according to one of the teammate's NetIDs. (We know who the other members of your team are from the log files you include in the solution, so be sure to include the log files!) At the lab deadline, the TA will freeze the labN.ontime directory and create a labN.late1 directory in which to submit labs that will be considered one day late. This process will continue as needed with directories named labN.lateD for labs D days late.

    You will be using the Git version control system to manage source code in your programming labs, as will be laid out in Lab 1. When you turn in a lab, you are to include your team's entire Git repository, including the .git directory and all its contents. The recommended approach to using Git is for one team member to maintain a "master" Git repository for each lab in a known location, and for all team members to 'git clone' that repository to create their own working repositories. Each team member can then work concurrently and 'git push' their code back to the master repostiory when ready. Team members may alternatively use completely separate Git repositories, but in that case you should combine all of your repositories into one before submitting: for example, other team members can incorporate their repositories into the submitting team member's repository as separate branches using the command 'git push myrepository submitters-repository labN:labN-mynetid'.


    Attendance at lectures is expected but will not be recorded. Students are, however, fully responsible for all material presented in lectures, even if some of it does not appear in the "official" lecture notes. Class attendance is strongly recommended.

    Lecture notes will be made available, though they are by no means guaranteed to be a complete record of the class and cannot substitute for class attendance.

    Keeping In Touch

    The best way to contact the instructor and the TA is by electronic mail. To get help quickly, your best bet is to send email to cs422ta@cs, where it will be seen only by the instructor and TA, or to cs422@cs, where your message will also be forwarded to every student in the class. Use of the whole-class mailing list is encouraged especially in the case of clarifications or debugging questions, since it is likely that other teams will be encountering the same or similar difficulties that you are and may offer the quickest answer. All the course-related information will be kept on the web (URL: http://zoo.cs.yale.edu/classes/cs422).


    This course is heavily based on Frans Kaashoek's course 6.828: Operating System Engineering at MIT. It also draws material from prior versions of CPSC 422 at Yale taught by Zhong Shao, and in turn from Kai Li's operating systems course at Princeton.

    Copyright (c) 2000-2011 Zhong Shao and Bryan Ford, Department of Computer Science, Yale University
    Many course materials derived from 6.828 by Frans Kaashoek and others at MIT.