CS
3013, A-Term 2011
This web page is the official home page of CS-3013, the undergraduate course in computer operating systems at Worcester Polytechnic Institute.
The pages of this web site contain materials needed by
students in the course, including lecture notes, programming assignments,
supplementary data and materials, and reference papers. These pages are updated
on a regular basis, and students are responsible for paying attention.
Some pages of this web site are protected and require users to log in with valid WPI user IDs and passwords. Such authentication is necessary to protect copyright material that is included under the fair use doctrine. Some materials may be further restricted to only members of the course.
Index
Testing, Grading, and Practical Matters
Lecture notes and details of the project assignments are found at the following URLs. These require your WPI userID and password to access.
Introduction
CS-3013 is intended for all students of the computational sciences — including traditional Computer Science, Robotics Engineering, Interactive Multimedia and Game Design, and Electrical and Computer Engineering. During the course, we will endeavor to introduce you to the fundamental concepts of computer operating systems and the kinds of things that you need to know about them, whether you intend to work inside of an operating system or not.
The course involves classroom lectures and project work. Both
components are equally important. However,
it is not possible to pass the course without a good faith attempt to complete
the project assignments.
Project work for this course will include two small projects to be undertaken by all students. After that, there are two alternatives:–
· For students interested in a “heavy duty” software engineering approach, the major project of the term will be to develop a kernel message system inside the Linux kernel.
· For students who envision themselves mostly as users of operating systems, the alternative project will be a non-trivial survey of the different kinds of operating systems and the facilities and feature that they offer to users and applications.
CS-3013 is the place in the WPI computing science curriculum where we introduce the notion of concurrency — that is, the design of applications, programs, and systems that have many activities executing at the same time. The mastery of concurrency is rapidly becoming an essential skill for all computing professionals, at all levels, and in all of the areas in which the computational sciences apply. Both project alternatives include serious amounts of concurrent programming.
Another important concept to be introduced in this course is abstraction. The major abstractions provided by most modern operating systems are processes and threads, virtual memory, files, and sockets and connections. You probably have encountered these terms before, either in previous 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 them that you did not know.
A cross-cutting concept that is encountered in operating systems and other areas of computing science and technology is caching. Caching is what makes virtual memory work at all, what makes modern computers fast, and what makes distributed games playable. Few operating system textbooks address the concept at all, and fewer attempt a quantitative analysis of it. This course introduces caching
A typical undergraduate operating system course requires
about 10-12 weeks, so not all of the essential material can be covered during
this term. In particular, the study of the implementation of file systems is
deferred to CS-4513,
Distributed Systems, and the
study of network interfaces and protocols is deferred to CS-3516,
Computer Networks.
Topics
The following table lists topics of the course and corresponding chapters in the course textbook, Modern Operating Systems, 3rd edition, by Andrew S. Tanenbaum. The order of presentation of topics varies from term to term.
|
Topics |
Text Chapters |
|
Introduction, History, Overview |
1 |
|
Concurrency
— Processes, Threads, Synchronization, |
2 |
|
Memory Management and Virtual Memory |
3 |
|
Files and Persistent Storage |
4 |
|
Input-Output Devices |
5 |
Course Information
This course meets for two 2-hour classes per week for a seven-week undergraduate term (28 hours).
Time and Place: Tuesdays and Fridays, 12:00 noon — 2:00 PM, Lower Fuller Auditorium, August 26 — October 11, 2011. There will be short break about half-way through each class.
Lecture Capture: Lectures will be automatically recorded by the Academic Technology Center. The recordings will include the lecture slides, any annotations made on the slides from the podium, and the spoken voice of the lecturer. Students may subscribe to these lectures at the following URL:–
http://echo360.wpi.edu/ess/feed?id=4d4e8dfb-c77a-49ae-8f0a-3b23fc91dbc2&type=M4V
Professor:
Hugh C. Lauer, Ph.D.
Email: <professor’s last name>@cs.wpi.edu
Office hours: 2:00–3:00 PM on Tuesdays, 10:00–11:00 AM on Fridays; and other
times by appointment
Office: Fuller Labs, Room 144
Teaching Assistants and Student Assistant:
Jia “Joe” Wang
times Mondays, 1-3 PM, Thursdays 4-6 PM
Can Tatar
(pronounced “John”)
times Tuesdays 3-5 PM, Fridays 3-5 PM
Taylor Andrews
(SA)
times Wednesdays 12-3 PM
Office hours will be held in Fuller A22.
Textbooks:
1. Andrew S. Tanenbaum, Modern Operating Systems. 3rd edition, Prentice Hall, 2008.
2. Robert Love, Linux Kernel Development, 3rd edition, Addison-Wesley, 2010.
Note 1:– Earlier editions of Modern Operating Systems by Andrew Tanenbaum are not suitable for this course. Much has changed about operating systems since the 2nd edition was published in 2001.
Note 2:– Undergraduate students planning to take CS-4513 (Distributed Systems) in a future term should retain their copies of the Tanenbaum textbook. It will be directly relevant to the file system topics covered in that course.
Note 3:– The second edition of Linux Kernel Design, by Robert Love, published by Novell Press in 2005, may be used as a substitute for the 3rd edition in this course. However, the Linux kernel has evolved considerably since that 2nd edition was published, and students will be responsible for understanding the differences. An electronic version of the 2nd edition has been placed on reserve in the Gordon Library.
Class e-mail
lists: The following list is in the domain cs.wpi.edu:–
cs3013-all — to reach all students in CS-3013, the
teaching assistants, and the professor
cs3013-staff — to reach just the
professor and teaching assistants assigned to this course
Course web
sites: The following URL points to the home page of the course web site for
the combined course:–
http://web.cs.wpi.edu/~cs3013/a11/
Discussion Board: During this term, we will use the class e-mail list as a discussion board. You are encouraged to check it regularly, and you are responsible for all official announcements sent to this list.
Absences: Students
needing to be absent from class should notify the professor by e-mail or in
person as soon as possible.
Testing, Grading, and Practical Matters
Testing
There will be no final exam in this course. Instead, there will be a short quiz each week. The dates of quizzes are:–
· September 2
· September 9
· September 16
· September 23
· September 30
· October 11
Each quiz will be approximately 20 minutes except the last one, which will be approximately 30 minutes. All quizzes are cumulative, in the sense that any topic at any time is the course may be asked on any subsequent quiz.
Each quiz will be graded separately. In determining the
final grade for the course, the quiz with the lowest score will be thrown out.
This is intended to accommodate unexpected absences, illnesses, or “bad days.” The final quiz is required in order to pass
the course; skipping the final quiz is equivalent to taking an NR for the
course.
Quizzes will be handed out either at the beginning of class or the end of the break. Because of the layout of the Fuller Auditorium, students completing quizzes early should remain in their seats so as not to disrupt students still working.
Reading Assignment (pre-term)
You are required to read and understand all of Chapter 1 of the Tanenbaum textbook by the end of the first week of the course. The quiz of Friday, September 2, will include the material of this chapter.
Essential Background
You should have some knowledge of computer organization and elementary data structures, and you need 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 coaching, help, and/or guidance outside of class.
Grading
Grades for the first seven weeks of this course will be assessed approximately as follows:–
· Quizzes: (total ~40%)
· Projects: (total ~40%)
· Class Participation: (~20%)
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.
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.
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 Corporate and Professional Education. More information can be found at
http://www.wpi.edu/Pubs/Policies/Honesty/policy.html
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 day on which it is due, 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 time indicated on the assignment. Projects must 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!
However, no late assignments will be accepted after the last day of class. There is not enough time between the last day of class and the date that grades are due to accommodate late assignments.
Project Work
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.
This course uses virtual machines to provide platforms on which students can build, modify, and debug the kernel of operating systems. A virtual machine is a simulation of computer hardware that has enough performance and fidelity to be indistinguishable from actual computer hardware. Each virtual machine runs on real hardware and a real operating system, together called the host system. Your experimental operating system is called the guest system.
By working in a virtual machine, you can 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.
All programming projects of this course will be carried out and graded on these virtual machines. The host system may VMware Workstation, VMware Player, or VMware Fusion on your own personal computer, or it may be the virtual Fossil server in the Computer Science Department. The guest system for all students is OpenSuse Linux 11.4. The virtual machine made available 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. All project grading is predicated on using this guest operating system.
To install your virtual machine and operating system, see instructions here (in doc format) or here (in pdf format).
Reference Material
The following papers are relevant to the material presented in class:–
Allman, Eric, “E-mail Authentication: what? Why? How?” ACM Queue, November 2006, pp 30-34. (.pdf)
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)
Dean, Jeffrey, and Ghemawat, Sanjay, “MapReduce: Simplified Data Processing on Large Clusters,” Communications of the ACM, vol 51, #1, January 2008, pp. 107-113. (.pdf)
Dean, J. and Ghemawat, S. “MapReduce: Simplified data processing on large clusters,”
In Proceedings of Operating Systems
Design and Implementation (OSDI). San Francisco, CA, 2004. pp. 137-150. (.pdf). Note: This paper is an earlier
version of the CACM paper above, but it contains some details not included in
the CACM paper.
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)
Ghemawat, Sanjay, Gobioff, Howard, and Leung, Shun-Tak, “The Google File System,” Proceedings of the 2003 Symposium on Operating System Principles, Bolton Landing (Lake George), NY, October 2003. (.pdf)
Gray, Jim, “Notes on Database Operating Systems,” in Operating Systems: an Advanced Course, vol 60 of Lecture Notes in Comp. Sci., Springer-Verlag, 1978, pp. 393-481 (.pdf)
Herlihy, Maurice, “Wait-Free Synchronization,” ACM Transactions on Programming Languages
and Systems, vol 11, #1, January 1992, pp.
124-149 (.pdf )
Hoare, C.A.R., “Monitors:
An Operating System Structuring Concept,” Communications of ACM, vol.
17, Oct. 1974, pp. 549-557. (.pdf);
correction (.pdf)
Howard, John H., Kazar, Michael L., Menees, Sherri G., Nichols, David A., Satyanarayanan, M., Sidebotham, Robert N., and West, Michael J., “Scale and Performance in a Distributed File System,” ACM Transactions on Computer Systems, Vol 6, #1, Feb 1988, pp. 51-81. (.pdf
Lampson, B.W., and Sturgis, H. E., “Crash
Recovery in a Distributed Data Storage System.”