CS
3013 and CS
502
Summer 2011
This is a combined undergraduate and graduate level course during which you will study and compare the design and implementation of modern operating systems. Students registering for undergraduate credit will register for CS 3013 (seven weeks), and students registering for graduate credit will register for CS 502 (ten weeks).
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 CS-502 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. Many students find that they have to make adjustments to
their family lives for the duration of this course. If you are working in a
full-time job, is strongly recommended that you not attempt to take any other course this term in addition to this
one.
Index
Prerequisites and Essential Background
Lecture notes and Programming assignments are found at the following URLs. These require your WPI userID and password to access.
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-3013 is a partial fulfillment of that requirement for undergraduate students, and 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 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.
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 a very short summer, 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.
For graduate students, 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.
Topics
The following outlines the topics that will be covered and the corresponding readings from 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 |
|
Networks, Sockets, and Communications |
Not in Text |
Programming Projects
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 is VMware Workstation, VMware Player, or VMware Fusion, and the guest system is openSuse Linux 11.4. 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.
To install your virtual machine and operating system, see instructions here (in doc format) or here (in pdf format).
Term Project for CS-502
In addition to the other work of this course, each CS-502 student is required to complete a Term Project during this term. 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. Oral reports will be presented during the weeks of July 19, July 26, and (if necessary) August 2. 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 — i.e., August 4.
The Term Project description can be found here (doc
format) or here
(pdf format). The PowerPoint slides can be found here
in pptx format.
Course Information
This course meets for two 2-hour classes per week for a seven-week undergraduate term (28 hours) and a ten-week graduate term (40 hours).
Time and Place: Tuesdays and Thursdays, 6:00 pm — 8:00 PM, Fuller Labs 320, May 31 – July 14, 2011 (undergraduate) or May 31 – August 4, 2011 (graduate).
Professor:
Hugh C. Lauer, Ph.D.
Email: <professor’s last name>@cs.wpi.edu
Office hours: (normally) 1 hour before each class; or other times by
appointment
Office: Fuller Labs, Room 235
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. There will be some overlap of topics between the summer version of CS-3013 and the normal version of CS-4513.
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.
Class e-mail
lists: The following two lists are in the domain cs.wpi.edu:–
cs3013-all — to reach all students in both CS-3013 and CS-502 and the
professor
cs3013-staff — to reach just the
professor and any teaching assistants or graders that might be assigned to this
course
cs502-all — to reach just the CS-502 students (and the professor)
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/e11/
In order to comply with copyright regulations, portions of the course web site will require you to log in. Please use your regular WPI login ID and password.
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.
Practical matters
There will be one major exam at the end of the seventh week of the course, on July 14. This is the final exam for students registered for CS-3013. This will approximately one hour. If the class feels that it is worthwhile, we may arrange an interim quiz earlier in the term. For students registered for CS-502, there will be a second “mini-final” exam on August 4.
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.
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:–
· Exams and quizzes: (total ~40%)
· Programming Projects: (total ~40%)
· Class Participation: (~20%)
The final three weeks for CS-502 will be worth an additional 50%, allocated approximately as follows:–
· Term Project: (~25%)
· Additional Programming Project and mini-final: (~25%)
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 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!
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.
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 )
Lämmel, Ralf, “Google’s MapReduce Programming Model — Revisited,” Microsoft Corp., Redmond, WA. (.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)
Waldo, Jim, Wyant, Geoff, Wollrath, Ann, and Kendall, Sam, “A Note on Distributed Computting,” Sun Microsystems Laboratories, Inc., Technical Report SMLI TR-94-29, November 1994 (.pdf)