CS
502
— Operating Systems
Fall
2007
This is the first year graduate-level
course about computer operating systems. During this course, we will address
the four major abstractions provided by most operating systems — namely,
threads and processes, virtual memory, files, and sockets and connections. We
will also carry out programming projects that involve building and modifying
the kernel of a major, general purpose operating system. Finally, each student
will study and report on one of the lesser known operating systems.
Most students find the programming project work
for this course time consuming. If you
are working at full-time job, it is strongly recommended that you NOT
attempt to take any other course this term in addition to this one.
Contents
Course Information
Time and Place: Mondays, 6:00pm - 8:50pm, Fuller Labs 320
September 10 — December 10, 2007
Professor:
Email:
<professor’s last name> at cs.wpi.edu
Office hours: (by appointment) but I will try to
be in my office at least by 5:00 PM on class days
Office:
Fuller Labs, room 239
Required
Textbooks:
1.
Silberschatz,
Galvin, and Gagne, Operating Systems Concepts, Seventh Edition, John
Wiley and Sons, 2005.
2.
Robert Love, Linux Kernel Development, 2nd
edition, Novell Press, 2005
Students will be expected to be familiar
with and to discuss the relevant sections of the textbook and other reading
material assigned during the term.
Supplementary
textbook: Andrew S. Tanenbaum,
Modern Operating Systems. 2nd edition, Prentice Hall, 2001.
Class e-mail lists: The e-mail list for this course is cs502-all, and the e-mail list to reach
the professor and TAs (if any) is cs502-staff.
Both lists are in the e-mail domain cs.wpi.edu.
(To reduce spam, we don’t publish full e-mail addresses on course web sites.)
Students needing to be absent from class
should notify the professor by e-mail as soon as possible. Please plan ahead
for religious holidays.
Overview
and Objectives
As a requirement for both undergraduate
and graduate degrees in Computer Science at WPI, all students must have a solid
understanding of how computer systems work. Successful completion of CS-502 is
a partial fulfillment of that requirement for graduate students.
During this term, we will introduce the
notion of abstraction and will
explore the major abstractions provided by most modern operating systems. This
will involve lectures, reading material, and programming projects. By the end
of the term, you should understand processes and threads, virtual memory and
paging, files and persistent storage, sockets and connections, and other
principal abstractions.
You probably have encountered these terms
before, either in your undergraduate studies, your professional work, or your
general computer literacy. However, it is likely that we will go into these
topics in considerably more depth than you have previously done. For example,
you may think you know what a process
or a file is, but you will probably
discover a lot more about both that did not know.
An important part of this course is for
each student to develop an appreciation of the depth, breadth, and scope of
modern operating systems and why they are so large and complex. To experience
this first hand, I know of no better way than to take a journey into the kernel
of one of them. We will dive directly into the Linux kernel and make
non-trivial modifications to it. In 14 very short weeks, you will get a glimpse
of the vast forest that supports a huge number of applications and machine
architectures. I hope that you will also gain the satisfaction of knowing that
it is not a mystery and that you would, indeed, be capable of mastering it,
should ever need to do so in your professional career.
The third component of this course is the
Term Project. During this project, each student will identify, investigate,
study, and report on one of the lesser known operating systems that are in
regular use today. “Lesser known” means not
Windows, not Linux, not Unix, and not the Macintosh operating systems.
Practical matters
There will be one “final” exam on
December 10. This will be 1.5–2.0 hours, and it may include lecture material
introduced earlier the same evening. In addition, there will be one or more unannounced quizzes during the term;
these would be approximately 30 minutes.
There will be approximately four
programming projects during the term. The duration of a project assignment is
based on the amount of time it is expected to take. For example, a two-week
assignment means that you should have completed half by the end of the first
week. There won’t be enough time to do it all in the second week.
Class
participation is an essential
part of the grade for the course. If you attend lectures but never say anything
or never engage in class discussions and the class e-mail list, it will be
enough to reduce your grade by one full letter or more.
Prerequisites
You should have
some knowledge of computer organization and elementary data structures and a
strong programming background. Neither C++ nor Java can be used inside the
Linux kernel, so programming projects within the kernel must be done in the C
programming language. If you have never programmed in a low-level language like
C, please arrange for tutorial help and guidance outside of class.
Grading
Grades will be
assessed approximately as follows:
·
Exams and
quizzes: (total ~30%)
·
Programming
Projects: (total ~30%)
·
Term Project
(~20%)
·
Class
Participation: (~20%)
Final grades
will reflect the extent to which you have demonstrated understanding of the
material, and completed the assigned projects. The base level grade will be a
“B,” which indicates that the basic objectives on assignments and exams have
been met. A grade of “A” will indicate significant achievement beyond the basic
objectives and a grade of “C” will indicate not all basic objectives were met,
but work was satisfactory for credit. No incomplete grades will be assigned
unless exceptional, extenuating circumstances exist.
If there are
any circumstances that limit or restrict your participation in the class or the
completion of assignments, please contact the professor as soon as possible so
that we can work something out.
Testing
In-class exams
and quizzes will be closed book. For the announced final exam on December 10,
students may bring one two-sided, 8.5-by-11 inch sheet of prepared notes. For
unannounced quizzes, no notes will be permitted.
Each student should have a calculator available
for quizzes and exams.
Academic
Honesty
Unless
explicitly noted, all work is to be done on an individual basis. Any violation
of the WPI guidelines for academic honesty will result in no credit for the
course and referral to the Student Affairs Office. More information can be
found at
http://www.wpi.edu/Pubs/Policies/Honesty/policy.html
All of that
being said, you are strongly encouraged to discuss with each other about ideas,
course material, and especially the challenges you encounter in working with
the Linux kernel.
Late Policy
Unless you have
contacted the professor prior to the due date, late submissions will be
penalized 10% of total assignment value per day (with the weekend counting as
one day) or partial day, and no assignments will be accepted after seven days
beyond the due date. All assignments are due at the start of class on the due
date. Projects will be submitted as directed in class.
Although this
policy may seem stringent, the professor is usually willing to make exceptions
to students to address specific circumstances, provided that they contact him well before the assignment is due!
Topics
The following outlines the topics that
will be covered and the corresponding readings from Silbershatz, et. al. The order of presentation of
topics varies from term to term.
|
Topics |
Text Chapters |
|
Introduction, History,
Overview |
1 |
|
General Organization of
an Operating System |
2 |
|
Concurrency and
synchronization |
6 |
|
Processes, Unix and
Windows processes, Threads |
3, 4 |
|
Scheduling |
5 |
|
Memory Management |
8 |
|
Virtual Memory and
Paging |
9 |
|
Monitors and
Interprocess Communication (IPC) |
6 (again) |
|
Input and Output |
13 |
|
Disks |
12 |
|
File Systems and
persistent storage |
10, 11 |
|
Networks |
16 |
|
Multiprocessor and
Distributed Systems |
16-18 |
|
Real-Time Systems |
19 |
|
Multimedia Systems |
20 |
|
Protection, security,
and encryption |
14-15 |
|
Virtual Machine Systems
|
2.8 |
Term Project
The
purpose of the term project is to expose students to operating systems other than the familiar ones — i.e.,
Windows, MacOS, Linux, and Unix. Each student will research on the web,
libraries, or other resources to discover and identify at least five different
operating systems that are in use today and will write one short paragraph
about each one. From all of the operating systems identified by the students,
the instructor will assign one to each student for in-depth research. You will
be responsible for giving a 10-minute oral report to the rest of the class of
your assigned operating system. In addition, a written report of up to ten
pages of that operating system will be due at the start of the final class of
the term.
Term Project Description
(.doc, .html)
Term Project Overview Slides (.ppt,
.html)
Programming Projects
Virtual Machines
To provide a
platform on which each student can build, modify, and debug the kernel of an
operating system, we will use virtual
machines. A virtual machine is a simulated computer implemented on a real
machine running some other operating system (called the host operating system). You can install your experimental operating
system (called the guest operating
system) in the virtual machine, modify it, debug it, and crash it, all without
harming the host system. If the guest
operating system crashes or things go bad, you can roll back to a previously
stable state or replace it entirely with a known good one. All in all, this is
a safe place in which to work on the most sensitive part of the operating system
without harming your other work or anyone else.
[Our
use of virtual machines mirrors a capability has been provided for a number of
years to undergraduate students taking CS-3013. In that course, students use
the Fossil Lab (see fossil.wpi.edu), a
laboratory with dedicated PCs on an isolated network for building and testing
Linux kernels. The Fossil Lab is not practical for CS-502 because (a) it
requires students to be physically present on campus to reboot or restore
machines after crashes, etc., and (b) the machines and operating systems are
out of date and require substantial support on the part of teaching assistants.
Since many students in CS-502 live far from campus and/or hold full-time jobs
in the Greater Boston region, they are unable to be physically present.]
The particular
operating system we will use for this course is OpenSuse 10.2. The virtual machine distributed to each member of
the class will contain this preinstalled and updated with a recent kernel. Do
not attempt to use a different operating system or to update it to a later
version than distributed in class.
There are three
ways to set up your virtual machine:–
·
You may
install and use the free VMware Player
application on your own PC (or on a Macintosh that supports Windows programs).
To choose, see the following instructions:– (.doc,
.html).
·
You may run
your virtual machine on the Computer Science Department server csopt4.wpi.edu using an application called VMware Server. To choose this option, see instructions here:– (.doc, .html).
·
You may also
set up an OpenSUSE Linux 10.2 environment directly on a computer that you
control or on a Macintosh Parallels
system. You may also experiment with VMware
Fusion on the Macintosh. See the instructor if you wish to do any of these.
Students
planning to use the CS Department server should have CS department accounts. If
you do not already have such an account, you can apply for one by visiting the
following web page:–
If it asks you
for a “certificate,” simply click “Okay.” Fill in the form, giving your CCC
account, student ID, etc. Where is asks what CS systems for which you need an
account, click “Other” and type in the box “VMware.” In the Notes section,
specify “Professor Lauer, for CS-502.”
General Requirements for
Submitting Programming Assignments
Each
programming project submitted by a student will be compiled and tested by the
professor or a grader. In order to make the grading process reasonable, a
certain uniformity of project submissions and reasonable standard of
programming practice are expected.
Programming
projects this term will be compiled and tested on OpenSUSE Linux 10.2 running
on a VMware virtual machine. Projects that are machine independent could be
graded on either a Pentium (i386
architecture) or csopt4 in the Computer Science Department (x86_64 architecture). Most kernel
projects have a machine dependent component and will therefore be graded on the
architecture that the student specifies.
All student programs should compile without
warnings. It is, however,
inevitable that some other parts of the Linux kernel may generate warnings; you
are not responsible for those parts. For user-space programs, the use of the “-Wno_deprecated” switch is strongly discouraged without prior
permission from the instructor.
Kernel
components will be submitted in the form of patch
files (to be explained). The grader will start with a previously built kernel
and, working in the grader’s own kernel directory, will execute the following
commands in a shell to build the student’s kernel.
patch –p1 <
{student’s patch file}
make O={grader’s build directory} oldconfig
make O={grader’s build directory}
make O={grader’s build directory} modules_install install
User-space
project submissions (including test programs for kernel projects) must include
code, header files, a Makefile, a write-up, and test output or any other
supporting information. The grader will expect to type
cd {directory
containing student’s submission}
make
to compile the
components of the project submission and
make clean
to erase all
compiled components. User-space submissions must include copies of all
non-standard include files. Programs that depend upon kernel .h files must
provide separate copies as part of the user-space submission.
Submitting Your Projects
Projects are to
be submitted using the web-based version of the Turnin system. The instructor will provide accounts to students at
the start of term. When an account is set up, each student will receive an
e-mail message with a password for the Turnin
system. Students should log into Turnin
and change their passwords to something they can remember. In the event that a
password is forgotten, the instructor or grader can reset it. The web-based Turnin system can be accessed from
within a virtual machine or from anywhere on the Internet by visiting
http://web.cs.wpi.edu/~kfisler/turnin.html
http://turnin.cs.wpi.edu:8088/servlets/turnin.ss
Project
components should not be zipped together or be partitioned into folders for different
parts of the project. The reason is that the Turnin system already zips them together.
When
you submit an assignment, your submission must include not only the solution,
but also the test code or test cases and it must be well commented and easy to
read by others. Similarly, any output must be cleanly formatted and easy to
read by others.
Be sure to put your name at the top of every file
submitted as part of a programming project. You would be surprised at how
often students forget this!
The instructor
or grader will typically compile your program and test it with other test cases
developed separately. Your submission must include a patch file for kernel modifications (to be explained), a makefile for non-kernel
code (you should know what this is), and instructions for running test cases.
You should also include a narrative description, preferably in Microsoft Word
format or in PDF format.
“Getting the
correct answer” on a programming project is not sufficient to meet the objectives
of the assignment. Since operating systems are typically long-lived, frequently
revised, complex programs that are used (and maybe abused) by a diverse
population of programmers and users, successfully meeting the objectives of a
programming project includes testing and paying attention to its robustness.
Programming Project Assignments
Links to
programming project assignments will be posted here shortly before or after the
classed in which they are assigned:–
Project #0 – Linux
and Virtual Machine Dabbling (.doc,
.html)
Slides for assignment of project (.ppt,
.html)
Project #1 –
Linux Kernel Hacking (.doc,
.html)
Slides for assignment of project (.ppt,
.html)
Project #2 –
Kernel Message Handling System (.doc,
.html)
Slides for assignment of project (.ppt,
.html)
Project #3 –
Page Replacement in Linux (.doc,
.html)
Slides for assignment of project (.ppt,
.html)
Project #4 –
Discovery (multiple options) (.doc,
.html)
Slides for assignment of project (.ppt,
html)
Lecture Slides
Electronic
versions of slides will be posted here shortly before or after each class
|
Week 1 |
Course Introduction & |
.ppt |
|
|
|
Concurrency |
||
|
Week 2 |
Concurrency (continued) and Synchronization |
.ppt |
|
|
|
Processes in Unix, Linux, and Windows |
.ppt |
|
|
|
Threads |
||
|
Week 3 |
Digression on Stacks and Heaps |
||
|
|
Application Design in a Concurrent World |
||
|
|
Scheduling |
||
|
Week 4 |
Scheduling (continued) |
||
|
|
Linking & Loading |
||
|
|
Memory Management |
||
|
Week 5 |
Paging |
||
|
|
Virtual Memory |
||
|
Week 6 |
Virtual Memory (continued) |
||
|
|
Introduction to File Systems |
||
|
Week 7 |
Disks |
||
|
|
File System Implementations |
||
|
Week 8 |
More on File Systems |
||
|
|
Input and Output |
||
|
Week 9 |
Input and Output (continued) |
||
|
|
Computer Networks |
||
|
Week 10 |
Computer Networks (continued) |
||
|
|
Remote Procedure Call |
||
|
Week 11 |
Remote Procedure Call (continued) |
||
|
|
Distributed File Systems |
||
|
Week 12 |
Multiprocessing and Distributed Systems |
||
|
|
Atomic Transactions |
||
|
|
Virtualization |
||
|
Week 13 |
Protection and Security |
||
|
|
Security and Cryptography |
||
|
|
Multimedia Systems |
Reference
Material
The
following papers are relevant to the material presented in class:–
Birrell, Andrew D., and Nelson, Bruce
Jay, “Implementing Remote Procedure Calls,” ACM
Transactions on Computer Systems, vol. 2, #1, February 1984, pp 39-59. (.pdf)
Dijkstra, E. W., “Solution of a Problem in Concurrent Programming Control,” Communications of the ACM, vol. 8, #9,
Sept. 1965, p 569. (.pdf)
Dijkstra, E. W., “The Structure of the
‘THE’-Multiprogramming System,” Communications
of the ACM, vol 11, #5, May 1968, pp.341-346 (.pdf)
Hoare, C.A.R.,
“Monitors: An Operating System Structuring Concept,” Communications of ACM,
vol. 17, Oct. 1974, pp. 549-557. (.pdf);
correction (.pdf)
Lampson, B.W.,
and Redell,
Lampson, B.W., and
Sturgis, H. E., “Crash Recovery in a Distributed Data Storage System.”
This widely referenced paper was not published anywhere. A copy of an
original Xerox PARC report dated April 27, 1979 is here (.pdf).
A later version dated June 1, 1979 appears here (.pdf). This
later version carries the following footnote:– “This paper was circulated in several drafts, but
it was never published. Much of the material appeared in Distributed
Systems—Architecture and Implementation, ed. Lampson, Paul, and Siegert,
Lecture Notes in Computer Science 105, Springer, 1981, pp 246-265 and pp
357-370.
Lauer, H.C. and
Needham, R.M., “On the Duality of Operating System Structures,” Operating
Systems Review, vol 13, #2, April 1979, pp. 3-19. (.pdf)
Liu,
C. L. and Layland, James W., “Scheduling Algorithms for Multiprogramming in a
Hard-Real-Time Environment,” Journal of
the Association for Computing Machinery (JACM), vol. 20, #1, January 1973,
pp-46-61. (.pdf)
Redell,
Ritchie, D. M.
and Thompson, K., “The UNIX Time-Sharing System,” Communications of ACM, vol 17, #7, July 1974, pp. 365-375. (.pdf)
Rosenblum, M,
and Ousterhout, J. K., “The Design and Implementation of a Log-Structured File
System,” Proceedings of 13th
ACM Symposium on Operating Systems Principles, Pacific Grove, California,
October 1991, pp. 1-15. (.pdf)
Thompson, Ken,
“Reflections on trusting trust,” Communications
of ACM, vol.27, #8, August 1984, pp. 761-763 (.pdf)