Computer Science

COS 318: Operating Systems

An introduction to operating systems. Emphasis is on the fundamentals of how to design and implement an operating system. Topics include operating system structure, processes, threads, synchronizations, concurrent programming, interprocess communications, virtual memory, I/O device management, and file systems.

Textbook: Andrew S. Tanenbaum, Modern Operating Systems, 3rd edition, Prentice Hall., 2008.

Administrative Information

Course Mailing List: cos318[at] @ lists.cs.prince.ton.edu [subscription settings]

Lectures	Tue & Thu 13:30 – 14:50	COS 105
Precept	Tue 19:30 – 20:30	COS 105

	Name	Office	Office Hours	Email	Phone
Professor	Kai Li	COS 321	Tue 15:00 -17:00 in room COS 321	li @ cs	258-4637
AI	Nick Johnson	COS 213	Friday 15:00 – 17:00 in Lab 010	npjohnso at cs
AI	Shi Li	COS 216	Monday15:00 -17:00 in Lab 010	shili at cs
AI	Lars A. Bongo	LSI 227	Monday 15:00-17:00 in Lab 010	lars at cs

Schedule and Lecture Notes

You are expected to complete the readings and submit your reading notes before the corresponding lecture.

Date	Topic	Professors	Reading Assignments
9/17	Introduction	J.P. Singh	MOS 1.1-1.3
9/22	Overview	B. Kernighan	MOS 1.4-1.5, submit
9/24	OS Structure	B. Kernighan	MOS 1.6-1.7, submit
9/29	Processes & Threads	E. Felten	MOS 2.1, 2.2.1-2.2.3, submit
10/1	Threads Implementation (Non-preemptive & Preemptive)	E. Felten	MOS 2.2.4-2.2.9, submit
10/6	Mutex Implementation	JP. Singh	MOS 2.3.3, 2.3.6, submit
10/8	CPU Scheduling	JP. Singh	MOS 2.4, submit
10/13	Semaphores, Monitors, & Condition Variables	A. Appel	MOS 2.3.5, 2.3.7, Birrell's paper, submit
10/15	Deadlocks	J.P. Singh	MOS 6, submit
10/20	I/O Devices and Drivers	J.P. Singh	MOS 5.1-5.3, 5.5-5.9, submit
10/22	Message Passing	J.P. Singh	MOS 2.3.8, 8.2.1-8.2.4, submit
10/27	Midterm		Suggested solutions
10/29	Security and protection	E. Felten	MOS 9
11/10	Virtual Memory Address Translation	J.P. Singh	MOS 3.1-3.3, submit
11/12	Virtual Memory Paging and Replacement	J.P. Singh	MOS 3.4, submit
11/17	Virtual Memory Design Issues	K. Li	MOS 3.5-3.6, submit
11/19	Storage Devices	J.P. Singh	MOS 5.4, submit
11/24	Internetworking	J. Rexford	DARPA Internet Protocols, submit
12/1	File Systems	J.P. Singh	MOS 4.1, 9.3.1-9.3.3, submit
12/3	File Layout and Directories	J.P. Singh	MOS 4.2,4.3.1-4.3.3, 4.5.2-4.5.3 , submit
12/8	File System Reliability and Performance	J.P. Singh	MOS 4.4.2-4.4.4, 4.3.5,4.3.6, submit
12/10	NFS and Snapshot	K. Li	MOS 10.6.3-10.6.4, NetApp paper, submit
12/15	Virtual Machine Monitors	M. Fiuczynski	Virtual Machine Monitor, paper, submit
12/17	Deduplication file system and review	K. Li	Deduplication, paper , submit

Projects

We believe that the only way to master the knowledge of operating systems is to build a real operating system kernel. The six projects in this course are designed to do exactly that. At the end of the class, you will have a small, real operating system kernel. This set of projects were co-developed with colleagues at University of Tromso in Norway and have been used in other institutions such as Yale.

Students will be paired as working groups for the first five projects. You will be regrouped after three projects in order to give you a chance to work with another person for the next two projects. You will be working alone on the last project.

Each project has two grading phases: design review and final submission. Design reviews are discussed here. 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.

You will be using the Linux PCs in the 010 lab in Friends Center (so called Fishbowl). All the projects will be done on a USB flash memory stick or using Bochs, so please do not write your kernel to the hard disk. The lab in Friend 010 is reserved for COS 318 students during the whole semester. When working on the projects, it is helpful to test your implementation using a simulator such as Bochs or Qemu during the development phase. After your projects run successfully on a simulator, you should test it on a real PC. Please share test machines if the lab is full.

Due Date	Number	Project
10/5	1	Bootloader
10/19	2	Non-preemptive Kernel
11/10	3	Preemptive Kernel
11/23	4	Interprocess Communication & Process Management
12/14	5	Virtual Memory
1/12	6	File Systems

Policies

Grading

The course grades will be determined roughly as follows:

Course projects (50%)
Midterm (20%)
Final project (20%)
Reading and Participation (10%)

The course will not be graded on a curve, so students are not competing against each other. Most projects contain extra credits. The midterm is tentatively scheduled on the Thursday of the midterm week.

Late Submissions

Project submissions are due at 11:59PM on the due date. Late submissions are marked down using a popular function. In this way, an assignment which is only a few hours late doesn't get penalized that much. A late grade is computed as follows:

grade = original_grade * exp(-time_late/three_days)

Examples: work turned in five minutes late gets 99.9% credit, one hour late gets 98.6% credit, six hours late gets 92.0% credit, one day late gets 71.7% credit, three days late gets 36.8%, and one week late gets 9.7%.

Exceptions will be made only in extreme circumstances and only in advance.

Exams

The midterm exam will be designed to test how well students understand the materials taught in the lectures as well as in the projects. Please watch the schedule of this web page for the times and the locations of the exams.

Reading & Participation

It is strongly recommended that students read the suggested reading materials before the class. A number of discussion topics will be provided on the course web page before each class starts. Refer here for details.

The participation grades will be based on the students' understanding of the discussion topics shown in their submitted questions and their contributions in the class discussions. Student can earn up 1 point for participation (0 for no participation) and 0.5 extra point for active participation.

Collaboration

We believe that students can learn quite a bit from each other. We encourage you to help each other understand the materials in the course and in particular, to learn from each other in doing the operating system projects. In order to encourage such cooperation, we will give you the opportunity to tell us those students who helped you the most in understanding the material. Such information will be turned into extra points for the helpers at the end of the class.

You can also earn extra credits by developing useful tools for the projects that can be used by others. To do so, you need to discuss your ideas first with the instructor and the TAs.

There is a clear distinction between cooperation and cheating. Copying other's code or designs are strictly prohibited. We will punish transgressors severely.

COS 318: Operating Systems
Princeton University
Department of Computer Science