CPSC 508: Graduate Operating Systems
Professor Margo Seltzer and Dr. Reto Achermann
Tu/Th 9:30 - 11:00
- 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
- 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
The course has five primary components:
- 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
In this homework, you will be asked to reproduce a research result
that you find in an operating systems research paper. You may select the
paper from those on our reading list or in the assignment or you may
propose a different one (but you'll need to get it OK'd).
The goals of the assignment are:
- To let you practice conducting research with a well-definied problem
- To give you a feel for how challenging it
can be to write up an experiment in a reproducible way
- To help you become both more critical and appreciative when you read papers
- 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.
- 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
- 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.
- 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.
- 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):
- Research Plan
- Project meetings with us
- First Draft
- Project Presentation
- Final Paper
- Quality of results
- Quality of presentation (both oral and written)
- Ability to place work in the context of existing work
No extensions (of course, if something truly out of the ordinary arises,
you should come talk to us)
We will post lecture notes on the web after class.
(We really want everyone to come to class with their own notes)
Actually, We really want people to come to class.
You are encouraged to discuss the papers before class if you wish.
A Computer Science Research Course According to Margo
Focus on what computer science systems research is using the area
of operating systems as the domain of discussion.
The following categories highlight what we view as some of the
most important aspects and characteristics of good research.
Others may disagree, and we won't claim that we am right, but this is how
we view it, so we encourage you to consider this viewpoint and take it
into account as you approach research in this course.
With luck, what you learn here will inform your research in other
endeavors as well.
Why do we read a lot of research papers?
How do we select papers to read?
- 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,
- 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
- Be able to be right in a gracious manner.
- Understand that there is likely to be no right or wrong answer.
- 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)
Good research often requires some engineering.
- 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.)
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
- If mousetraps were invisible, would they work better?
- How can we build invisible mouse traps?
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.
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?
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
- Measure again.
- Use real systems.
- Gather trace data.
- Instrument existing systems.
- Analytical investigation.
- Isolate small components.
- 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.
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).
- Retrospective or experience paper.
- 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?
- 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.
- 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:
- Introduce area (1 sentence)
- State problem/area (1-2 sentences)
- Explain approach or what you did (3-5 sentences)
- Summarize conclusions (be quantitative)
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
What you Did
- What does the reader need to know to understand the rest of this paper?
- This is where you describe your research
- Be thorough, but concise.
- 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)
- 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.
- 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.
Style check (passive voice, gendered writing)
Ideally, give yourself a few days to let a paper sit before you do
a final proofing pass
As you are conducting research, begin writing up
bits of the paper
Keep a notebook of everything that you do with
respect to the research
Make sure you can reconstruct how you got to
where you did.
Write Early -- Write Often
Check out the blog on how to write a dissertation
(a research paper is a mini dissertation) and the pet writing