CS
3013 — Operating Systems
A-Term
2008
This is the 3000-level undergraduate course about computer operating systems. There are two major components to this course
- A general study of the principles and practices of modern
operating systems, and
- A brief but practical tour through the kernel of a major,
general purpose operating system using the recently upgraded Fossil
Laboratory (Free Open Source Software Laboratory).
A typical undergraduate operating system course would be require about 10-12
weeks, so not all of the essential material can be covered during this term. In
particular, the study of file systems is deferred to CS-4513, Distributed Systems, and the study of
network interfaces and protocols is deferred to CS-4514, Computer Networks: Architecture and
Implementation.
This web page is the official home page of CS-3013, Operating Systems, for the A-term of the 2008-2009 academic year. It will be updated throughout the course, and students are required to pay attention to all updates.
Contents
Course Information
Time and Place: Tuesdays and Fridays, 8:00am - 9:50am, Fuller
Labs 320, August 29-October 16, 2008
Professor:
Email:
<professor’s last name>@cs.wpi.edu
Office hours: preferably by appointment, or
(normally) 1 hour after each class and Fridays, noon–1:00 PM
Office:
Fuller Labs, room 137
Phone:
(508) 831-5493
Teaching Assistants and Student Assistant:
Li, Feng office hours:–
Tuesdays: 1:00 – 3:00 PM
Thursdays: 1:00 – 3:00 PM
Thangam Seenivasan office hours:–
Mondays: 2.00 – 4.00 PM
Wednesdays: 2.00 – 4.00 PM
Mondays: 1:00 – 2:00 PM
Wednesdays:
12:00 – 2:00 PM
Fridays: 1:00 – 2:00 PM
Office
hours will be held in the Fossil Lab (Fuller B17)
Required
Textbooks:
1.
Andrew S.
Tanenbaum, Modern Operating Systems, Third Edition, Pearson Prentice-Hall,
2008
2.
Robert Love, Linux Kernel Development, 2nd
edition, Novell Press, 2005
Note: – Earlier editions of Modern Operating Systems by Andrew Tanenbaum are not suitable for this course. Much has changed about operating systems since the previous edition was published in 2001.
Note: – 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.
Alternative
Linux Kernel book: Daniel P. Bovet
and Marco Cesari, Understanding the Linux
Kernel, Third edition, O’Reilly Media, 2006. This book is larger and more
encyclopedic than Robert Love’s book, but it is also more difficult to
penetrate by non-professionals of the Linux kernel field. Of special value is
the source code index in the back. Copies will be placed on reserve in the
Library.
Class e-mail lists: The e-mail list for this course is cs3013-all, and the e-mail list to reach the professor and TAs is cs3013-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.)
Reading
Assignment (pre-course)
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. There will be a 30-minute closed-book quiz on the material of this chapter on Friday, September 5, at 8:00 AM.
Practical matters
Prerequisites
You must have some knowledge of elementary data structures and some experience programming in C — for example, CS 2303 Systems Programming Concepts, or CS 2301 Systems Programming for Non-Majors.
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.
Exams and Quizzes
There will be:–
- One 30-minute closed-book, closed-notes quiz on the subject
matter of Chapter 1 of the Tanenbaum textbook on September 5
- One or more unannounced quizzes during the term on the subject
matter of (a) processes and threads, and (b) virtual memory and paging.
Quizzes will be closed book and closed notes.
- One final exam of approximately 90 minutes on October 14. You
may bring one 8½-by-11 inch page of prepared notes (two sides).
Each student
should have a calculator available for quizzes and exams.
Programming Projects
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.
Grading
Grades will be assessed approximately as follows:
- Exams and quizzes: (total ~40%)
- Programming Projects: (total ~40%)
- 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.
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.
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 at least one day 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. 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!
Absences
and/or Disabilities
If you need course adaptations or
accommodations because of a disability, or if you have medical information to
share with the professor, please make an appointment as soon as possible. Students
with disabilities who believe that they may need accommodations in this class
are encouraged to contact the Disability Services Office (DSO) as soon as
possible to ensure that such accommodations are implemented in a timely
fashion. The DSO is located in Daniels Hall, (508) 831-5235.
Students needing to be absent from class for any reason should notify the professor by e-mail as soon as possible. In particular, please plan ahead for religious holidays and/or projects that take you off campus.
Overview
and Outline
Overview
A requirement for both undergraduate and graduate degrees in Computer Science at WPI is that all students must have a solid understanding of how computer systems work. Successful completion of CS-3013 or CS-502 is a partial fulfillment of that requirement. CS-3013 this term is almost identical to the first half of CS-502, and students may not earn credit for both courses
During this term, we will introduce the notion of abstraction, and we will define the major abstractions provided by most modern operating systems. These abstractions are
- Processes and threads
- Virtual memory
- Files
- Sockets and connections
By the end of this term, you should have a thorough understanding of processes and threads and of virtual memory and paging. In depth coverage of files and persistent storage will be provided in CS-4313, Distributed Systems, and in depth coverage of sockets and connections will be provided in CS-4514, Computer Networks. This course will also include at least an overview of Input-Output subsystems and drivers.
You probably have encountered the terms process, virtual memory, and file before. 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 7 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.
Course
Outline
Week 0 (August 29):– Introduction, Chapter 1 of Tanenbaum.
- What is an operating system?
- Introduction to concurrency
Weeks 1-3 (September 2-18):– The process-thread abstraction, Chapter 2 of Tanenbaum.
- Processes and Threads
- Interprocess communication and synchronization
- Scheduling (including real-time scheduling, if time)
Weeks 4-5 (September 22-October 2):– The virtual-memory abstraction, Chapter 3 of Tanenbaum.
- Virtual Memory and Paging
- Page Replacement algorithms
- Caches and principles of caching
- Design and Implementation issues
Week 6 (October 7-10):– Input/Output, Chapter 5 of Tanenbaum.
- I/O hardware
- I/O software and drivers
- User interface support
Week 7 (October 14):– Conclusion.
- Final exam
Detailed lecture notes will be posted here shortly before or after each class.
Programming Projects
Project assignments are posted here. Projects involving the Linux kernel will be based on virtual machines running VMware Workstation or VMware Player. Information about setting up your virtual machine in the Fossil Lab is posted here.
Reference Material
The following papers are useful supplements to the material presented in class:–
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,
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)
Thompson, Ken, “Reflections on trusting trust,” Communications of ACM, vol.27, #8, August 1984, pp. 761-763 (.pdf)