Assignments

CS422/522: Operating Systems, Spring 2008, Yale University

Warning: please visit this web page for last-minute changes to project mechanics, assignment specifications, and assignment-submission procedures. -Zhong Shao (12/24/2007)

  • Overview and Mechanics
  • Programming Style

  • Assignment 1: Bootup Mechanism   (due on Jan 31)
  • Assignment 2: Non-Preemptive Kernel   (due on Feb 14)
  • Assignment 3: Preemptive Kernel   (due on Feb 28)
  • Assignment 4: IPC and Device Driver   (due on Apr 3)
  • Assignment 5: Virtual Memory   (due on Apr 17)
  • Assignment 6: File System   (due on May 2)

  • Overview and Mechanics

    The programming assignments for this course are to build an operating system from scratch. We believe that the best way for you to understand operating systems concepts is to build a real operating system and then to experiment with it. To help you get started, Prof. Kai Li of Princeton University and his colleagues at University of Tromso in Norway have developed a great set of instructional OS infrastructure and lab work. The project has six phases, corresponding to each of the major pieces of a modern operating system: bootup mechanism, non-preemptive kernel, preemptive kernel, virtual memory, IPC and device driver, and file system. At the end of the semester, you will have a small, real operating system kernel.

    Students will be paired as a working group for each project. Each project has two grading phases: design review and final submission. To conduct a graded design review, each working group or student will meet with your TA for 10 minutes one week before the project is due. The main purpose of the design review is to get you start on the projects early. Another purpose is to let you catch errors early to avoid frustrated debugging. Also, it gives you a chance to explain and defend your approach. Each student needs to prepare a short presentation to show your approach to the TA. You should pretend that you are in the real world and give your supervisors a design review presentation. Our advice is to prepare one or two pages showing your data structures, interfaces, and algorithms instead of showing encrypted code. Drawing diagrams are very helpful. Your presentation should take no more than five minutes and the feedback from the TA will normally take no more than five minutes.

    Note that you have to sign up for a design review session. No design review session = no grade for the design review. If you don't show up for your design review session, you'll have to make a new appointment and 10% of your design review grade will be subtracted.

    The final submission will be done online, following the specific instructions in each project description. You should include a small README file with your project submission. You should concisely describe your design and implementation. Also, you need to describe what parts work and what parts don't; and how to compile and run your program (if you are not using the Makefile we provided). You don't have to repeat anything you presented in the design review. The TA who is in charge of the project will grade the project without correcting your code. It is your responsibility to figure out how to correct your code by comparing your implementations with the released solutions.

    Normally, we will give the same grade to both students in a working group. If one of the students feel that the other student did more work and deserve more credits, please inform the TA who is in charge of the project by e-mail.

    Finally, a former student had the following suggestions for doing well in this course, and since we agree with all of them, we include them here:

  • Read the code that is handed out with the assignment first, until you pretty much understand it. Start with the ``.h'' files.
  • Don't code until you understand what you are doing. Design, design, design first. Only then split up what each of you will code.
  • Talk to as many other people as possible. CS is learned by talking to others, not by reading, or so it seems to me now.
  • Late-Assignments Policy

    Each student is given 8 discretionary late days (i.e., 192 hours) for the assignments, but any one assignment may only be up to 72 hours late. These are calendar days, not business days. As the homework assignments are submitted electronically, the "write date" on the student's homework file will be considered the completion date for late assignments.

    After you use up all of your discretionary late hours, assignments turned in late will be graded according to the following formula: S = R * (1 - t / c), where S is the grade given, R is the grade the work would have gotten if turned in on time, t is the amount of time by which the work was late, and c is equal to four days. Thus, the value of a late assignment decays daily, with a half-life of just over two days. Examples: work turned in five minutes late gets 99.9% credit, one hour late gets 99.0% credit, six hours late gets 93.8% credit, one day late gets 75.0% credit, two days late gets 50.0%, and three days late gets 25.0%. Assignments submitted more than 72 hours late will not be accepted.

    There will be no extensions due to scheduling conflicts, computer downtime, or other such factors, except under truly extraordinary circumstances. Extensions will be granted only for university-sanctioned excuses such as illness, and then only with the proper documentation. You are responsible for planning ahead and managing your time so that you can complete the assignments on time. You must either finish on time or accept the consequences of doing otherwise.


    Programming Style

    Question: how to build a large software system in a reasonable amount of time and make it work reliably?

    Programming is craft: something like a high-tech form of silversmithing. To make big systems work, it takes tremendous amount of discipline and structure.

  • Rule #0: simplicity. It is easy to make things complicated, harder to make them simple. Don't accept complexity.
  • Rule #1: don't over-generalize. Could start by building code that is so flexible, it can do anything! But then code is 10 times larger, more complex than it needs to be, and you will still need to modify it, because of things you can't predict.
  • Rule #2: if it is complex, throw it away, start over.
  • Rule #3: module testing. Every module should be simple enough to be completely testable on its own.
  • Rule #4: adopt a consistent style and use it everywhere. Decide on file organization, procedure structuring, naming conventions, location of curly braces, everything.
  • Rule #5: don't litter. Temptation is to make fast fixes that dirty things up. It is crucial to take the time to fix things right at the beginning. You will never have time to come back to it later.
  • Rule #6: document carefully as you go. Don't put this off! Most important things are interfaces: procedure headers and data structures and other things that tie together the parts of the system.
  • Rule #7: documentation should describe things at a higher level than code (but not too high a level). Examples of pathological cases: "Add one to i", "Now we have it the way we want it", "This is a hack".
  • Rule #8: Put documentation near the code: otherwise you forget to change the documentation when you change the code.
  • Rule #9: Quality, not quantity. Don't need enormous amounts of documentation if what you have is high-quality.
  • Summary: programming takes discipline and is a learned craft. Take time up front to save time later. Be willing to cut your losses.


    Last updated on December 24, 2007 by Zhong Shao, Dept. of Computer Science, Yale University.