CPSC 508: Graduate Operating Systems

Topics:

• What this course is about?
• Course administrivia.
• A Computer Science Research Course according to Margo.
• An Overview of Operating Systems Research.
• Reading Research Papers
• Writing Research Papers

What is this course about?

Operating Systems research literature Why do we read a lot of papers, including very old ones?

• How has the role of the operating system evolved over time?
• What are the principles that underly the field of operating systems
• How has the past informed the present?
• What are the current trends in operating systems?
• What might the future hold?

Reading and Critiquing many papers What does it mean to critique a paper?

• Read many, many papers
• Discuss the papers, their methodology, the questions they ask
• Critique papers (assignment 1 and the mock program committee)
• Determine what makes a good research paper

Conducting Operating Systems Research

• Learn to produce quality research.
• Learn to identify a research problem.
• Designing an experimental setup.
• Building, measuring, analyzing, and questioning.
• Presenting research results orally and in written form

Course Administrivia

• One "homework" (Research reproduction)
• Reading research papers (44 or 45 papers/articles)
• Mock Program Committee: try your hand at reviewing papers
• Exam(s): 3 quizzes on the reading.
• Final project: research proposal, research plan, extended abstract, oral presentation, written report

Homework: A Research Reproduction

1. To let you practice conducting research with a well-definied problem
2. To give you a feel for how challenging it can be to write up an experiment in a reproducible way
3. To help you become both more critical and appreciative when you read papers
4. To introduce you to a real operating systems research problem

The homework assignment is to be completed independently. The assignment is already linked off the web site; you will want to do some reading to help you select a suitable paper to use.

The goal of this assignment is to learn how to write good research papers and present research results; the process is as important as the final outcome. This will be a frustrating assignment.

Reading

• The reading list is reasonably long.
• There are hundreds of good papers we are not reading.
• In general, we will cover two papers per lecture.
• Classes will be discussions.
• Everyone is expected to do all the reading.
• You will be asked to engage in group discussion about each paper using Piazza.
• Everyone is expected to participate in discussions (notice that 20% of class grade is participation).
• For each paper, we will have a class scribe -- someone who takes notes on the conversation, summarizing our discussion.
• Participation includes participation in the online discussion, participation in class, and the notes you take in class. If you are uncomfortable speaking up in class, you can participate by sending comments/questions to us via email before lecture.
• We will put our notes on the papers on the web after class. My notes summarize the paper (i.e., what you should have gotten out of reading the paper); the scribe notes will summarize our discussion, which should be much deeper and should focus on the research approach and the strength of the ideas and the work.

Mock Program Committee

• Read the extended abstracts that your classmates have turned in for their final projects.
• Write comprehensive, constructive reviews of the work.
• Participate in a meeting where we decide which papers we will "accept" for the CPSC conference.

Quizzes

• Short (one-half class period)
• Easy (if you have done the reading)
• Impossible (if you have not done the reading)
• Questions are likely to ask you to synthesize information from multiple papers. we try to avoid brute memorization of the papers and also to ask questions that you can't answer simply from having been in class.

Final project

• The real meat of the course.
• The goals of the project are:
• Let you try your hand at conducting systems research.
• Provide a lot of feedback on writing, posing a question, designing an experiment, presenting research.
• Help you become better systems researchers.
• About the size of a conference paper.
• May be completed in groups -- size of project should reflect the size of the group
• Every paper should pose and answer a research question.
• Six phases (note that phases 1 and 2 are due at the same time):
1. Proposal
2. Research Plan
3. Project meetings with us
4. First Draft
5. Project Presentation
6. Final Paper
• Evaluated on:
1. Methodology
2. Quality of results
3. Quality of presentation (both oral and written)
4. Ability to place work in the context of existing work

Random Stuff

A Computer Science Research Course According to Margo

Become familiar with existing research -- reading

• Establish a common language.
• Establish a common history.
• Know what is known.
• Critique what is known.
• Explore what is unknown.
• Become experts -- as the semester progresses, the class dialogue will become more sophisticated and each of you will bring more background and context to the class.

• Classic historical papers
• Important papers
• Papers that demonstrate excellence in research
• Papers that help demonstrate how the field is changing through time
• Current topics
• Areas in which I'm particularly interested

Discussion -- classes

• Assumption is that everyone has read the paper, so we will not rehash the contents of the paper (although we are always happy to discuss parts of a paper that people find confusing or that they did not understand).
• Be willing to question the paper -- its assumptions, its methodology, its conclusions.
• Be willing to take a position -- don't agree with everything
• Be willing to be wrong -- it's OK to change your position if others persuade you; it's OK to try to persuade others; it's also OK to agree to disagree.
• Be able to be right in a gracious manner.
• Understand that there is likely to be no right or wrong answer.

Do Research.

• Goal is to contribute knowledge to the field.
• Challenge is finding a question that can be reasonably answered in several weeks.
• One of the greatest challenges in experimental computer science is distinguishing research from engineering.
• We hope you will develop the skills to do the following:
  • Dig into the details of an evaluation to determine if the results are statistically significant and if they are believable.
  • Identify when there are simpler solutions that the authors overlooked.
  • Understand why the authors couldn't find a simpler solution (if none existed).
  • Decide if the results are what you expect or are surprising. If they are surprising, check that the authors explained that the results were, in fact, not expected and why the results were as they were.

Engineering vs. Research (the most valuable part of this lecture)

1. Golden rule #1: The engineering is not the research.
• "I want to build mouse trap?" is not research.
• "Is my new-fangled high-tech mouse trap better at trapping mice than a conventional one?" is possibly a research project. ("And why is that so," makes it even better.)
2. Golden rule #2: Research requires a question (hypothesis).
• Is my mousetrap better and is it statistically significant?
• Why is my mousetrap better?
• Why is Adi's mousetrap not as good as Jan's mousetrap?
• Does there exist a material that is better at building mousetraps than those conventionally used?
• If mousetraps were invisible, would they work better?
• How can we build invisible mouse traps?
3. Golden rule #3: The engineering helps you ask the question.
• Create a prototype mousetrap.
• Build a framework in which to evaluate the efficacy of mousetraps.
• Designing experiments is a combination of engineering and research.
• Conducting the experiments is often engineering.
• Analyzing the results of the experiments is the research.
4. Golden rule #4: Tolerate no sloppiness when conducting the research.
• Write down everything.
• Understand the numbers!
• Question yourself constantly.
• Understand the numbers!
• Remind yourself of the question you are asking.
• Understand the numbers!
• Are your numbers stable?
5. Golden rule #5: Reproducability
• Write down exactly how you obtained the numbers: revision of your (clean!) code, data, machine configuration (e.g. git commit hashes)
• Ensure a clean build / checkout before running the experiment. (you can include the revision in your binary and print it)
• ideally: have a script that builds, configures and runs your workload on your machine/cluster of machines with the right configuration
• Include your configuration in your obtained data (e.g., file name, metadata, comment, etc. -- from the produced graph / table, you should be able to find the right settings/versions and reproduce the same graph)
• If you observe change in your numbers, you want to be able to look at the diff between two revisions to figure out what changed, does your diff explain the change in measured numbers?. (e.g., replaced a list with a hashmap)

What is Operating Systems Research?

Identification of a problem/phenomenon

• Applications are changing; demands change.
• I/O performance is not increasing as rapidly as is CPU performance.
• Processors now have multiple cores and/or multiple threads.
• Networking is king.
• Everything is moving to the cloud.

Hypothesize a solution or better mousetrap

Evaluate hypothesis

• Measure.
• Measure.
• Measure again.
• Use real systems.
• Gather trace data.
• Instrument existing systems.
• Simulation.
• Analytical investigation.
• Isolate small components.

Draw Conclusions

• Use results to suggest new hypotheses.
• Compare results against others' results.

Toughest things to Grok

• There are not necessarily any right answers.
• No one can tell you with certainty that you are right.
• You are never done.
• Understanding large systems is difficult.

Reading Research Papers

Identify what kind of paper you are reading

• Big idea (famous people write these).
• Unifying theme (again, mostly famous people).
• Small idea with evaluation (most papers).
• Measurement.
• Comparison.
• Retrospective or experience paper.

Take notes

• Create on-line bibliography with comments.
• Create outline.
• Record big ideas.
• Jot down buzz words.

Put paper in context

• What other papers are like this one?
• How is this one different/the same as others?
• What are the new ideas?
• Did the authors read the literature?

Critique

• The ideas
• Do the ideas make sense?
• Are the ideas well-motivated?
• Does this paper make a difference?
• Is this an LPU (least publishable unit)?
• The methodology
• What are they trying to measure/prove/demonstrate?
• Do they attempt this in a significant way?
• Do you believe their results? (why/why not)
• Do they present their results well?

After you have finished reading the paper

• Summarize paper in 1-3 sentences.
• Put paper in one of three categories.
• Classic
• Important
• Useless
• Is the paper well-written?
• What did you learn from the paper?
• How would you have conducted the research?
• Does the paper suggest any future work?

Writing Research Papers

The parts of a research paper:

1. Abstract
   • Introduce area (1 sentence)
   • State problem/area (1-2 sentences)
   • Explain approach or what you did (3-5 sentences)
   • Summarize conclusions (be quantitative)
2. Introduction
The introduction must help readers along the journey from a standing start to the list of contributions -- when they get to the contributions, they must understand why the contributions are important.
• Complete description of the problem
• A framework that convinces readers that you've done something new and important (may require some related work)
• Why is this work important?
• What horrible things will happen if this work isn't done?
• What good will happen if this work is done?
• Why is now the right time to be doing the work?
• State contributions (higher level than specific results)
• Road map of the rest of the paper
3. Background
• What does the reader need to know to understand the rest of this paper?
4. What you Did
• This is where you describe your research
• Be thorough, but concise.
5. The Results
• Describe experimental setup (make your work reproducible).
• Explain expected results (why are they expected).
• Explain surprising results and explain why they are as they are; what does the difference mean?
• Present results clearly (Tufte: Visual Presentation of Data)
6. Related Work
• Do a thorough literature search -- know what others have done
• Laundry lists of references aren't very useful
• Relate your work to existing work
• Identify work upon which you build
• Identify ways in which your work differs from previous work.
• Demonstrate how your work fits in to the grand scheme of things.
7. Conclusions
• State results again.
• State significance of results.
• Tell people what they should have learned.
• Future Work
• What questions still remain?
• What new questions have arisen?
• How can your work be extended.

General Tips