Syllabus for MCS-378: Operating Systems (Fall 2015)

Overview

This course covers the basics of operating systems as well as some material on concurrent programming, middleware, and networking. There are two principal reasons why a course on operating systems is practical to take (as opposed to just interesting), even if you never expect to be involved in the development of an operating system (which most of you won't):

Office hours

I welcome visitors to my office (OHS 306) on a drop-in basis as well as by appointment. You may send me electronic mail at max@gustavus.edu.

World Wide Web

All course materials will be available through my World Wide Web page. The URL for this course is https://gustavus.edu/+max/courses/F2015/MCS-378/. After this syllabus I will give hardcopy handouts only to those students who want them.

Text and readings

The primary text for the course is Operating Systems and Middleware: Supporting Controlled Interaction by Max Hailperin, the current version of which is available online. Recent conference papers serve as additional required readings; you have access to these through the syllabus on the web. Those conference papers will form the basis for the student presentations, described below.

Presentations

There will be eight times in the semester when I sit back and relax and let students teach the class instead. Each time, a pair of students will have 50 minutes to lead discussion on one of the papers we read from a conference. The whole class will be expected to read the paper at least casually, but the students leading the class will be expected to have read it more carefully and done whatever it takes to really understand it, which may involve additional background reading, talking with me, etc.

Each pair of students will be responsible for setting up a meeting with me the week before their presentation to go over it with me. (You are welcome to additional consultations as well.) At that meeting, you should also give me three straightforward questions about your reading. I will distribute these to the full class. All class members will submit their answers to these three questions by 10am the day of your presentation, as a way of making sure we all have a common starting point. I will look through them and alert you before your presentation if there are any common difficulties you might want to address. No late answers will be accepted for these questions because their point is to lay the groundwork for the presentation.

I will provide a list of attributes that good presentations have. For each presentation, each student in the audience will be asked to select two of these attributes that were particular strong points and two that particularly need work. I will summarize this feedback for the presenters. I will also use the same list of attributes to structure my own evaluation of the presentation, which will take place in a face-to-face “debriefing” with the presenters, with the grade generated as a summary of that meeting.

I'm going to ask you to express a preference ranking for the topics and will try to the extent possible to assign people to topics based on that. I suggest you read the abstracts of the papers to help determine your preferences; you can also take into account the timing of the presentations. I'll need to have you email me the rankings by noon Friday (September 11).

  1. September 24: "SKI: Exposing Kernel Concurrency Bugs through Systematic Schedule Exploration", Pedro Fonseca, Rodrigo Rodrigues, and Björn B. Brandenburg, 11th USENIX Symposium on Operating System Design and Implementation, October 2014, pages 415–431.
  2. September 29: "Self-Tuning Intel Transactional Synchronization Extensions", Nuno Diegues and Paolo Romano, 11th International Conference on Autonomic Computing, June 2014, pages 209–219.
  3. October 15: "NightWatch: Integrating Lightweight and Transparent Cache Pollution Control into Dynamic Memory Allocation Systems", Rentong Guo, Xiaofei Liao, Hai Jin, Jianhui Yue, and Guang Tan, 2015 USENIX Annual Technical Conference, July 2015, pages 307–318.
  4. October 22: "Shielding Applications from an Untrusted Cloud with Haven", Andrew Baumann, Marcus Peinado, and Galen Hunt, 11th USENIX Symposium on Operating System Design and Implementation, October 2014, pages 267–283.
  5. November 17: "Log-structured Memory for DRAM-based Storage", Stephen M. Rumble, Ankita Kejriwal, and John Ousterhout, 12th USENIX Conference on File and Storage Technologies, February 2014, pages 1–16.
  6. November 24: "The Design and Implementation of Open vSwitch", Ben Pfaff, Justin Pettit, Teemu Koponen, Ethan Jackson, Andy Zhou, Jarno Rajahalme, Jesse Gross, Alex Wang, Joe Stringer, Pravin Shelar, Keith Amidon, and Martín Casado, 12th USENIX Symposium on Networked Systems Design and Implementation, May 2015, pages 117–130.
  7. December 1: "In Search of an Understandable Consensus Algorithm", Diego Ongaro and John Ousterhout, 2014 USENIX Annual Technical Conference, June 2014, pages 305–319.
  8. December 15: "Mo(bile) Money, Mo(bile) Problems: Analysis of Branchless Banking Applications in the Developing World", Bradley Reaves, Nolen Scaife, Adam Bates, Patrick Traynor, and Kevin R.B. Butler, 24th USENIX Security Symposium, August 2015, pages 17–32.

Daily preparation assignment

Each class day that has a reading assignment, by 10am you are to enter on Moodle your preparation assignment for that day. (The first day of classes is excepted.) I will look these over in order to shape the class to meet your needs. As additional incentive, they provide an opportunity to earn Grade Points. No late preparation assignments are accepted, as that would undermine their real purpose.

For a conference paper, the preparation assignment will consist of questions provided by the presenters, as described in the section on presentations.

For readings from the textbook, your assignment is to send me an agenda for that day's class. Is there old business from prior days that you see as needing more time? In the new topics from that day's reading, what are the main points we should cover? What illustrations, programs, or other examples from the book would you like to go over? Are there exercises we should work? Are there topics beyond the reading we ought to cover?

Independent exploration and programming projects

You have the opportunity to take on independent exploration and programming projects and thereby earn Grade Points. Each chapter in the textbook ends with exercises, programming projects, and exploration projects. Of these three categories, the exercises are suitable for you to put on a class agenda as something we could talk about or work on together. The other two categories are available for your independent projects. For each of Chapters 2–11, you may submit via Moodle any programming or exploration project, subject to the restrictions listed below. If I indicate that your initial submission is inadequate, you can submit a revised version, as many times as are necessary to succeed.

Note that some projects in the text have fallen out of date relative to external software or resources. Be sure to ask for help if you are having trouble making adjustments to accommodate the present-day context.

Tests

There will be a midterm take-home test as shown on the schedule below and a final exam as scheduled by the registrar. If you have a conflict with a testing time, please contact me as soon as possible to make an alternative arrangement.

My default assumption is that students will take the final together. Therefore, I would ask you to please be respectful and quiet, even after completing your exam, so that your fellow students have a good test-taking environment. However, if you prefer to take the exam in a separate room, please contact me in advance and I will try to arrange it.

The midterm will be open-book and open-notes whereas the final will be closed-book and mostly closed-notes. You may, however, use a single 8 1/2 by 11 sheet of paper with hand-written notes for reference. (Both sides of the sheet are OK.)

Contribute to our open-source textbook

You can contribute to the further development of our textbook and earn Grade Points in the process. You will earn points for each new (or thoroughly rewritten) section you submit for inclusion in the book, up to a maximum of three sections. Each of the sections you submit may either be on a topic of your own choice that you have pre-cleared with me or may be chosen from the following list:

  1. Section 10.4, on web services, became so out of date that I effectively removed it, leaving just a place-holder. You could write a new section on web services.

  2. Section 11.3, on user authentication, really ought to have a subsection regarding single sign-on (SSO) and federated identity systems, including technologies such as SAML, OAuth, OpenID, and CAS. You could write such a subsection.

The best way for you to submit a contribution to the book is to make your own fork of the github repository, commit a revision into that fork, and then send me a "pull request" to ask me to incorporate it into the mainstream. Please don't let the mechanics stand in your way, though. I can help you with them or accept a contribution in some alternative form.

I will consider all submissions for inclusion into the book. In cases where two or more students write about the same topic (as is likely to happen with the two topics listed above), I may craft a composite version so as to include the best elements from each draft. If something derived from your work winds up in the book, I'll acknowledge your contribution in the Preface.

As an alternative to writing a section, you may create some new supplemental material such as an animation or screencast. As with a section on a topic of your own choice, you would need to pre-clear this with me.

Honor

Students are encouraged to discuss the course, including issues raised by the assignments. However, the solutions to assignments should be individual original work unless otherwise specified. If an assignment makes you realize you don't understand the material, ask a fellow student a question designed to improve your understanding, not one designed to get the assignment done. To do otherwise is to cheat yourself out of understanding as well as to be intolerably dishonorable.

Any substantive contribution to your solution by another person or taken from a publication should be properly acknowledged in writing. Failure to do so is plagiarism and will necessitate disciplinary action.

The same standards regarding plagiarism apply to team projects as to the work of individuals, except that the author is now the entire team rather than an individual. Anything taken from a source outside the team should be be properly cited.

One additional issue that arises from the team authorship of project reports is that all team members must stand behind all reports bearing their names. All team members have quality assurance responsibility for the entire project. If there is irreconcilable disagreement within the team it is necessary to indicate as much in the report.

You are expected to be familiar with the college academic honesty honor code policy and to comply with that policy. If you have any questions about it, please ask.

Late lab assignments

All lab assignments are due at the beginning of class on the day indicated. Late assignments will be penalized by one Grade Point for each weekday late or fraction thereof.

If you are too sick to complete an assignment on time, you will not be penalized. Simply notify me in writing that the lateness is due to illness. Other circumstances will be evaluated on a case-by-case basis.

Grade changes

Please point out any arithmetic or clerical error I make in grading, and I will gladly fix it. You may also request reconsideration if I have been especially unjust.

Grading

You will have the opportunity to earn up to 450 Grade Points (GP) throughout the semester as shown in the following table:

Category#GP eachGP possible
Lab42080
Lab extensions21020
Presentation12020
Preparation22122
Project2010200
Test22448
Text section32060
Total  450

Your course grade will be recorded as follows:

GPGrade
270–450A
260–269A−
250–259B+
240–249B
230–239B−
220–229C+
210–219C
200–209C−
190–199D+
170–189D
0–169F

Style guidelines

All project and lab reports should be readily readable and should not presuppose that I already know what you are trying to say. Use full English sentences where appropriate (namely almost everywhere) and clear diagrams, programs, etc. Remember that your goal is to communicate clearly and that the appearance of these technical items plays a role in this communication process. Be sure your assignments are either submitted online or stapled together with your name on them.

Accessibility

Gustavus Adolphus College is committed to ensuring the full participation of all students in its programs. If you have a documented disability (or you think you may have a disability of any nature) and, as a result, need reasonable academic accommodation to participate in class, take tests or benefit from the College’s services, then you should speak with the Disability Services staff, for a confidential discussion of your needs and appropriate plans. Course requirements cannot be waived, but reasonable accommodations may be provided based on disability documentation and course outcomes. Accommodations cannot be made retroactively; therefore, to maximize your academic success at Gustavus, please contact Disability Services as early as possible. Disability Services (gustavus.edu/advising/disability/) is located in the Academic Support Center. Disability Services Coordinator, Kelly Karstad, (kkarstad@gustavus.edu or x7138), can provide further information.

Support for English learners and multilingual students is available through the Academic Support Center’s Multilingual Learner Academic Specialist, Jody Bryant (jbryant2@gustavus.edu or x7197). The MLAS can meet individually with students for tutoring in writing, consulting about academic tasks, and helping students connect with the College’s support systems. When requested, the MLAS can consult with faculty regarding effective classroom strategies for English learners and multilingual students. The MLAS can provide students with a letter to a professor that explains and supports appropriate academic arrangements (e.g., additional time on tests, additional revisions for papers). Professors make decisions based on those recommendations at their own discretion. In addition, English learners and multilingual students can seek help from peer tutors in the Writing Center (gustavus.edu/writingcenter/). Please let me know if there is any accommodation in the course that would enable you to more fully show your abilities; for example, I would consider allowing extra time on tests, as well as allowing a dictionary in an otherwise closed-book test.

Schedule

The two topics or activities shown for each date correspond approximately to the two halves of the class period with a brief stretching break in between. However, we will divide the time to meet our needs rather than necessarily at the halfway point.

In the reading column, a single number with no decimal point indicates an entire chapter. A number with three decimal points in it, such as 8.5.1.1 or 8.5.1.2, refers to the material under the first or second heading within Section 8.5.1, even though those headings are not actually numbered.

DateReadingTopicDue
9/81Introduction
2Threads

9/103.1-3.3Scheduling Goals
3.4-3.7Scheduling Mechanisms

9/15Lab Preview
Lab 1: Scheduling

9/174.1-4.3Mutual Exclusion
4.4-4.6Other Synchronization Patterns

9/224.7-4.8,4.10Synchronization PathologiesLab 1
4.9Nonblocking Synchronization (and visitors)

9/24paper 1Exposing Kernel Concurrency Bugs (Andy, Dustin)
5.1-5.2Example Applications of Transactions

9/29paper 2Self-Tuning Intel's Transactional Synchronization (Andrew H., Caleb)
5.3-5.4Mechanisms for Atomicity and Durability

10/1No class

10/6No class (attend Nobel Conference)

10/86.1-6.2Uses for Virtual Memory
6.3Mechanisms for Virtual Memory

10/136.4-6.5Policies for Virtual Memory
Review of Chapters 1-6; take-home midterm out

10/15paper 3Cache Pollution Control (Elizabeth, Kenlong)
Lab Preview

10/207.1-7.2POSIX Process ManagementMidterm
7.3-7.6Protection

10/22paper 4Shielding Applications from an Untrusted Cloud (Sergio, Tyler)
Lab 2: Prepaging

10/298.1-8.3POSIX File API
Lab 2 (continued)

11/38.4-8.5.1.1Disk Space Allocation
Lab 2 (continued)

11/58.5.1.2-8.6Metadata, Directories, and Indexes
Lab 2 (continued)

11/108.7-8.9Metadata IntegrityLab 2
Lab 3: File Allocation

11/12Lab 3 (continued)

11/17paper 5Log-structured Memory (Dennis, Jake)
9.1-9.3.1Socket APIs

11/19Lab 3 (continued)

11/24paper 6Open vSwitch (Aaron, Tucker)Lab 3
10.1-10.3Messaging and Remote Method Invocation

12/1paper 7Consensus (Andrew R., Jacob)
Lab Preview

12/311.1-11.4Security Basics
Lab 4: Communication Middleware

12/8Lab 4 (continued)

12/1011.5-11.8More on Security
Lab 4 (continued)

12/15paper 8Mobile Money Vulnerabilities (Diana, Spencer)Lab 4
Review and evaluation


Course web site: https://gustavus.edu/+max/courses/F2015/MCS-378/
Instructor: Max Hailperin <max@gustavus.edu>