Overview

CS 3204 provides an in-depth introduction to the principles and practices of operating systems. Particular emphasis is given to the topics of multiprogramming, process and thread management, memory management, including virtual memory, concurrency, including synchronization and deadlock, resource allocation and management, including scheduling, and storage management and file systems. Additional topics include inter-process communication, networking, and device management.

Rather than learning what an OS looks like from the outside and how to use its facilities, this course will show you what an operating system looks like from the inside.

The topics will be accompanied by a series of programming projects that will give you hands-on experience in building significant parts of a real operating system. Most projects will be done in groups, which gives you the added benefit of learning how to work in a team.

Course information

Instructor: E-mail: Phone: Office Hours: Teaching Assistant: Email: Meeting Time: Class Web Page: Discussion Forum:

Dr. Ali R. Butt butta@cs.vt.edu 1-0489 Tuesday/Thursday 11:00am -- 12 pm in 637 McBryde Please email for appointments outside these hours Xiaomo Liu (xiaomliu@cs.vt.edu) Jaishankar Sundararaman (jaisunda@cs.vt.edu) See class website for office hours and location cs3204-staff@cs.vt.edu TTh 9:30am - 10:45pm in 204 McBryde http://courses.cs.vt.edu/~cs3204/spring2008/butta/ Available @ http://forum.cs.vt.edu

Prerequisites

The formal prerequisites for this class consist of CS2604: Data Structures and File Processing and ECE/CS 2504: Intro to Computer Organization. Each student must prove that they have obtained a grade of C or better in those classes. Students who fail to meet the prerequisite requirements should drop the class or will be dropped. Students who meet the requirements must submit a Computer Science Prerequisite Form as soon as possible, but no later than January 25, 2008 for verification.

The most important informal prerequisite consists of strong C/C++ programming skills. In particular, the projects in this class will require a solid understanding of pointer-based data structures.

A user-level understanding of the Linux operating system is required as well, as would be provided in CS 2204: UNIX.

Objectives

Upon completion of the course, students should be able to

1. Understand the basic structure and organization of a multi-programmed computer system, including the distinction between user and kernel mode, the use of interrupts and context switches, runtime organization, application-binary interfaces and system calls, program linking and loading.

2. Understand the principles underlying concurrency and know how to use proper synchronization and deadlock avoidance techniques.

3. Understand the principles behind memory management, including user-level memory management, virtual memory management and paging.

4. Understand the principles behind CPU scheduling, including round-robin, priority-based, and multi-level feedback queue based scheduling algorithms.

5. Understand how an OS provides protection to its applications and how it manages and virtualizes resources.

6. Understand how file and storage systems are constructed and what factors influence their performance.

At a higher level, I would like for you to take away an appreciation for the complexity of operating systems, and view this class as an example of how to learn managing complexity.

Textbook

Silberschatz, Galvin, Gagne. Operating System Concepts. 7th Edition.

John Wiley & Sons, Inc. ISBN 0-471-69466-5

Optional reference:

William Stallings. Operating Systems: Internals and Design Principles. 5th Edition.

Pearson Prentice Hall, 2005.

In addition to the textbook, lecture notes as well as link to external resources will be posted on the class website.

Format

The course work consists of lectures, exams, quizzes, and programming projects.

Midterm: There will be one in-class midterm. The midterm will cover material from the lectures and textbook. The midterm will also include questions related to the programming projects.

Quizzes: There will be several unannounced quizzes throughout the semester.

Final: There will be a final exam. The final exam will be comprehensive and include material from the lectures, textbook, and programming projects.

Projects: There will be 5 projects. You will do the first project individually; the remaining four projects will be done in a group, except as noted in the project description. Some of the group projects will have an individual component.

Projects will be submitted electronically via the Curator system.

Projects

For the Fifth semester now we are using Pintos, an educational operating system developed by Ben Pfaff at Stanford University. Pintos is used at a number of universities in undergraduate OS courses. We provide a baseline version of Pintos, and you will add various features to Pintos through the course of the semester. Pintos runs on the x86, and could boot on any PC, but we will use a virtual machine simulator to run it on the Linux lab machines. (We do not provide support to run Pintos anywhere else and we will grade your submissions on those machines.)

The CS 3204 projects are probably different from the projects you have encountered in the undergraduate classes you took so far.

First, they are probably harder than what you have done so far. Although a correct solution can be implemented in a total of about 2,500 lines of C code, getting your projects to actually pass the tests will require intense coding and debugging. We will provide you with tools and help.

Second, unlike most assignments you've done so far, you will work in a group. Working in a group more closely resembles what you will encounter outside academia, but it requires trust and cooperation among group members. Note that your grade will be determined by the performance of your group. All group members will receive the same score for a project, unless otherwise specified. Do not expect to farm out work and receive credit for a partial solution. For more details, read the collaboration policy outlined later in this document.

Third, you will have to read a substantial amount of code before you can start writing the first line of code in your solution. We will guide you to the parts of the code you have to study, but do not expect to start coding right away. We believe this to be beneficial in two ways: first, this mirrors what you encounter outside academia. Second, we believe you will pick up good programming practices by reading well-written and well-documented code.

Fourth, only 50% of your grade in those projects is determined by passing the test cases we provide (all of which are public). The other 50% of your score comes from the design documents you are required to submit with your solution. Again, this mirrors an industrial setting where you have to provide a rationale for your design and create documentation that makes your code maintainable.

Fifth, you will be using the C language, rather than C++, for these projects. This mirrors most current OS, which are written in C rather than C++. Using C instead of C++ means that you cannot use certain language constructs, such as classes or templates, or runtime features such as RTTI. Nevertheless, your code will be written in an object-based style with encapsulation that is similar to how a C++ program would be structured.

The original Pintos series was designed for a 10-week quarter. This allows us to add a "warm-up" project at the beginning, and to relax the schedule for the projects somewhat. Nonetheless, you do not have the option to procrastinate.

We encourage you to start asking questions early and often.

Late Policy

No extensions for the projects will be granted, except in extremely excruciating circumstances. Instead, each student will have a budget of 4 late days that can be used to submit projects late without penalty. You decide when you want to use your late days -- there is no need to contact the instructor or GTA beforehand. Late days are granted in whole integer multiples of days: if your assignment is 5 minutes late, you will have used up an entire late day. Submissions received after you have used up your late days will receive a zero score. For some assignments, you may work in a team. If you are working in a team, late submissions will count against the budgets of all team members, so make sure that all of you have enough late days left or the team member with insufficient days risks getting a zero. These late days are intended to account for various minor emergencies, such as network outages, snow or flood days, or lab downtime: please contact the instructor for extensions only if you have truly extraordinary circumstances that would prevent you from completing the assignments on time.

Late Drop and Incomplete Policy

Less-than-hoped-for performance, or realizing you have taken on too much work this semester, are not permissible reasons to grant course withdrawal requests after Feb 25, 2008. (This policy applies only to drop requests that have to be approved by the instructor; in particular, it does not apply to the course withdrawals for six credit hours to which you are entitled according to college policy.) I will not grant incompletes for this course unless extraordinary, unforeseen circumstances outside of your control are to blame.

Grading

The contributions of the different course components to your final grade are as follows:

Midterm	15%
Quizzes	5%
Final Exam	25%
Projects	55%

Auto-Fail Rules

You fail the class, unless:

• You produce a working Project 2 by the end of the semester. "Working" means for your project deliverable to pass a to-be defined set of tests.
• You show "reasonable effort" on Projects 3 and 4. A zero score on any of these two projects clearly fails the "reasonable effort" test -- otherwise, we will use our judgment as to what constitutes reasonable effort.

Note that meeting these requirements forms a necessary, not a sufficient condition for passing. "Passing the class" means a grade that is not an F.

Modes of Communication

Website: The class website and the forum are the primary means of communication from us to you. We will post announcements there, which are binding. There is no mailing list for this class.

Email: Class-related email should be sent to cs3204-staff@cs.vt.edu, with the exception of project-related questions, which should be posted in the forum. The email alias ensures that it reaches both the instructor and TA, and ensures that it will be archived separately. I will answer questions posted in the forum before answering questions I receive by email.

Blackboard: We will use Blackboard for the sole purpose of posting grades. Please double-check that we have the correct grades for you on file.

Collaboration Policy and Honor Code

On the class website you will find links to the following policies applying to this class: University Policy of Class Attendance, the The Virginia Tech Undergraduate Honor System, the ACM and IEEE Code of Ethics, and the Departmental Policy on Koofers.

The tenets of the honor code will be strictly enforced in this course, and all assignments shall be subject to the stipulations of the Undergraduate Honor Code. For more information on the Honor Code, please refer to the Undergraduate Honor System Constitution, located online at http://www.honorsystem.vt.edu/

In addition, we will enforce the Departmental Policy on Koofers, Old Programs, Cheating, and Computer Use, available at http://www.cs.vt.edu/site_pages/undergraduates/Koofer.pdf

The following policies regarding collaboration apply in this class.

• All submitted work is expected to be the original work of the individual student unless otherwise directed by the instructor. Note the emphasis on "submitted" work -- this includes work that is explicitly graded and work that may not be.

• Projects are to be the work of the individual student or team as specified. You may discuss general concepts, such as software libraries, Internet resources, or class and text topics, with others outside your team. However, discussion of project solutions, specific code, or detailed report content is an honor code violation. All source material used in project code and reports must be properly cited.

• For all the projects except the first, you will team up in groups of 3 students. While teaming up is voluntary, we strongly recommend that you work with a full group. You may switch teams or form new teams, but only between projects. You may work with at most one group on a given project. Students must contribute equally to the project within a team. It is not acceptable for students to either not contribute to the project or not to let the other group members contribute equally to the project. Please bring any problems in this regard to the instructor's attention early on.

• You are required to read-protect your work on shared file space so students outside of your team will not have access. Failing to do so is an honor code violation.

• Borrowing code or hiring someone to perform the work for you is an egregious violation of the honor code. We will use plagiarism detection software such as MOSS to screen out students attempting to do this. We have access to project solutions that were created and submitted outside of Virginia Tech, as well as solutions that were submitted in past quarters.

• Forum rules: you are not allowed to post code that is part of your solution on the forum. An exception is a single line if it causes a compile-time or runtime error. Posting debug output, including backtraces, is ok.

• You may not post detailed descriptions of your design or solution on the forum. You may not post answers to design document questions on the forum. If in doubt, ask beforehand.

• Not having read the honor code and its stipulations is no excuse for violating it.

• If you have any doubt about what is and is not allowed, it is your obligation to ask the instructor beforehand.

Students with Disabilities

If you need adaptations or accommodations because of a disability (learning disability, attention deficit disorder, psychological, or physical), if you have emergency medical information to share with the instructor, or if you need special arrangements in case the building must be evacuated, please meet with the instructor as soon as possible.