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: Hugh C. Lauer

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.

top


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.

top


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!

top


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

top


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)

top


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:–

http://www.cs.wpi.edu/Account

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)

top


Lecture Slides

Electronic versions of slides will be posted here shortly before or after each class

Week 1

Course Introduction &
What is an Operating System

.ppt

html

 

Concurrency

.ppt

html

Week 2

Concurrency (continued) and Synchronization

.ppt

html

 

Processes in Unix, Linux, and Windows

.ppt

html

 

Threads

.ppt

html

Week 3

Digression on Stacks and Heaps

.ppt

html

 

Application Design in a Concurrent World

.ppt

html

 

Scheduling

.ppt

html

Week 4

Scheduling (continued)

.ppt

html

 

Linking & Loading

.ppt

html

 

Memory Management

.ppt

html

Week 5

Paging

.ppt

html

 

Virtual Memory

.ppt

html

Week 6

Virtual Memory (continued)

.ppt

html

 

Introduction to File Systems

.ppt

html

Week 7

Disks

.ppt

html

 

File System Implementations

.ppt

html

Week 8

More on File Systems

.ppt

html

 

Input and Output

.ppt

html

Week 9

Input and Output (continued)

.ppt

html

 

Computer Networks

.ppt

html

Week 10

Computer Networks (continued)

.ppt

html

 

Remote Procedure Call

.ppt

html

Week 11

Remote Procedure Call (continued)

.ppt

html

 

Distributed File Systems

.ppt

html

Week 12

Multiprocessing and Distributed Systems

.ppt

html

 

Atomic Transactions

.ppt

html

 

Virtualization

.ppt

html

Week 13

Protection and Security

.ppt

html

 

Security and Cryptography

.ppt

html

 

Multimedia Systems

.ppt

html

top


Reference Material                                  

The following papers are relevant to the material presented in class:–

Anderson, Ross, “An Update on the BMA Security Policy,” 1996. (.pdf)

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, D. D., “Experience with Processes and Monitors in Mesa,” Communications of ACM, vol. 23, Feb. 1980, pp. 105-117. (.pdf)

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, D. D. et al. “Pilot: An Operating System for a Personal Computer,” Communications of ACM, vol. 23, Feb. 1980, pp. 81-91. (.pdf)

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)