Course Assignments

This course is mostly a team-based project course.  The first assignment is an individual assignment and the following three are team assignments.  There will be four or five students per team.  The first assignment familiarizes everyone with working with the Nachos system.  The other three assignments implement extensions to the base operating system.  The assignments are the same for each team.  Individually, the teams decide their own specifications, design and implementation for the three team assignments.

Project Phases

A brief description of each assignment follows along with the approximate length of time allowed for completion.

Threads (1 week)

This assignment gets every person in the class familiar with the Nachos structure.  The assignment simulates one of the classic thread synchronization problems.  Each student will select one problem to implement as a multi-threaded system in the Nachos kernel.  The problems highlight synchronization between the threads.

User processes and multi-programming (3 1/2 weeks)

This assignment adds multiple user process running concurrently.  The OS must handle loading these processes from disk and allocating memory for each process.  Processes must all fit in within the bounds of physical memory.

Virtual memory (3 1/2 weeks)

All modern operating systems provide virtual memory support.  In this assignment you will choose a virtual memory technique and implement it.  This will require you to implement a strategy for the software TLB to handle page faults.

File systems (2 weeks)

Each team will design their own file system hierarchy that provides flexible data storage while trading-off fragmentation and space wasting

Discussion of Concepts

Shortly after the start of each assignment there will be classroom discussion on the particular operating system topic highlighted by that assignment.  These discussions will provide useful information as each team begins considering the design choices for the next assignment.

Each student is expected to review the concepts from the coverage in CS440 - Operating Systems in preparation for the class.   Each individual will submit a one page "Initial Ideas and Thoughts" about the work for that phase in order to participate in the discussion of the phase. The instructor will collect these from each individual at the beginning of the discussion.  These ideas can include, but are not limited to, concepts that you must investigate further, rough ideas for how to solve some parts of the problem, lists of design choices that will have to be made later, etc. With participation from all students this will be an opportunity to discuss the trade-offs of different strategies for virtual memory, file system hierarchies, etc. during the initial period when the teams are designing their own implementations.  If in your "Initial Ideas and Thoughts" you have questions that need clarification by the instructor ask for the clarification during the discussion.  If other questions needing clarification arise later, ask them on the course newsgroup so that all groups will benefit from the discussion of those questions.

Assignment Grading

The instructor will grade each assignment based on the following factors:

• design presentation, if required for the assignment

• demonstration of the working assignment

• design documentation

• documentation of testing performed

• quality of code and adherence to the team's coding standards

The "Initial Ideas and Thoughts" collected from individual students will be used as an adjustment to the team grade for individual students.  The Team Peer review submitted at the end of the project will also provide the basis for adjustments to the grade of individual team members.

There will be a rough 50/50 split between points for design related items (presentation, documentation) vs. implementation (code, functionality, test generation and documentation).

Design Presentation

The design presentation is a "formal" presentation done about one week into an assignment.  Each team should present an overview of the high-level class design for the assignment.  For each assignment you should state an overall design philosophy in at most a handful of sentences.  This should be clearly stated on one of the initial slides that is shown to set the stage for the presentation to follow.  Provide justification for the team's selection of that philosophy, such as why you located the program stack where you did or chose paged segmentation, and explain how the particular class structure supports it.  The design presentation should not just be "Here are the classes that we selected" but rather "Here is what we are attempting to accomplish and how our particular class design supports that."  Your presentation should also discuss any alternative designs that were rejected.  Anyone on the team should be able to answer questions such as "Why do you need the XYZ data member in the GHI class?" or "Which classes make use of the ABC member function?"  In the presentation also discuss the interaction between your code and the base Nachos system.

Design Documentation

Design documentation will consist of three items:

1. A UML class diagram of your components.  You should provide member information for the classes that you have added or significantly modified.  You do not need to display accessor or mutator member functions in the class box.  Classes in the Nachos machine directory only need to be shown as a box with a class name.  You only need to show classes from the machine directory that you directly interact with.  You do not need to show the interaction between machine directory classes.  It is suggested that you use Rational Rose for creating your UML diagram.  You can see information about using Rose here.

2. A 4 to 8 page overview of your design philosophy, how the class structure supports it and how the components you added interact with the base Nachos system.  In this document, describe your design philosophy and rationale for the class design you choose.  This is the material that you discuss in the design presentation.  The document should mention each class at least briefly stating how it fits into the overall design and what the general boundaries of the classes responsibilities are.

3. Either class interface files (.h files) or an appendix to your design document that lists the member variables and functions for your components.  If you provide the interface files they should have full function headers with descriptions of the parameters and return values for functions.  If you provide an appendix to your design document the description for parameters and return values can be in the text given for each function.  Descriptions of state variables should be as comments in the interface files or at the beginning of each class's discussion in the appendix.

Each team will submit paper copies of their design documentation on the date specified in the course schedule.  This is generally the day of the first design presentation.  Depending on the number of teams there may be more than a single day for presentations.  The documentation can be submitted in class the first of presentations day or, for teams not presenting on the first day, to the CS office for placement in your instructor's mailbox.  It must be submitted by the time that class starts that day.

Phase Submission Final Documentation

On the day that the assignment is due, you will submit updated documentation consisting of the following components:

1. Updated UML diagram

2. Updated overview document.  Near the beginning of this document include two bullet lists.  One lists what the team considers the high points of their solution.  The other lists the low points, limitations and places where the solution fell short.  Each of these points should be described with no more than one or two sentences.  You will expand on this in the rest of the final documentation.

Adjustments may be made to these arrangements based on the particular term when the course runs.  The first assignment will have a final submission and no presentations or demonstrations.  The file system assignment may not have design presentations and some demos may occur during finals week.

Demonstration Presentation

For the presentation and demonstration of a project phase you should also consider this to be a "formal" presentation in that it requires preparation ahead of time.  Additional preparation is necessary to smoothly merge the presentation with a demonstration of your implementation.  To make a good presentation you must provide visual material to assist your audience in following what you are saying.  Here are some points to consider:

1. Review of your design would be appropriate. Maybe you were good enough and got it right from the start. Say so but your audience does not remember what it was so show the design.
   
2. Present a class diagram of the overall system abstracting away much of the state and method detail especially if not modified for this assignment. Highlight the classes where the major work for this assignment was located.
   
3. Discuss the main responsibilities for each class that was added or had major changes. This could be a slide for each class. Abstract the information into a few bullets. Don't read each function name.
   
4. Use pictures!  This may be a picture of your memory layout for loading programs, your swapfile organization or the data structures defining your file system.  There are many places where you will be saying the 1000 words but a picture is what the audience needs to solidify understanding of your system.  Take the time and make those pictures.
   
5. State the limitations of the system. Tout your own work and state what you think are the system's highlights.
   
6. Get into a pre-planned demo to show the functioning of your system. Have a plan for what to run live. For some functionality, you might want run the test beforehand and only show the results. To make sure that your audience completely understands what they are seeing you might decide that a slide or two is warranted to back-up the demonstration.
   
7. A good rule of thumb for timing is 2 to 3 minutes per slide.  You'll have to subtract some for demonstration time.

TESTCASES file

For each assignment it will be your (or the team's) responsibility to create enough test programs to sufficiently document that the implementation has solved all aspects of the assignment.  The results of this testing will be submitted in a TESTCASES file that shows the output of all the tests run.  (The script program will be helpful to collect both the input and output generated while running your program.) This test output file should be annotated by the team to be sure to highlight all aspects of operation to your instructor.  You may also find it helpful to provide some introductory material before each test to guide your instructor through your test sequences.  The instructor will not attempt to decipher the operation of your program by reading raw test output. You must provide additional annotation that clearly highlights how your test output demonstrates that the program is working correctly.  This annotated test file may include some of the tests that you demonstrate directly to the instructor but it should stand on its own and provide a complete verification of the operation of your system.  Do not put this off until the last minute.  Generation of the tests and TESTCASES file should be clearly assigned to one or two team members.  A large part of the grade rests on the thoroughness of the tests and clarity of the descriptions provided.  Here is a good example and a poor example of a TESTCASES file.

You will submit your code according to the instructions provided at the end of each assignment.