Computer Science | School of Engineering | UC Santa Cruz
Home | Syllabus | Schedule | Reading List | Project

CMPS 221: Advanced Operating Systems
Fall 2011

Project Information

All students in CMPS 221 are required to complete a quarter-long project in the area of operating systems. The project may be the results of an implementation project, original research (preferred), or a strong survey of prior art. Reporting work done for another course is not acceptable.

Table of Contents

Project topics Project research Important dates

Project topics

You may choose any topic you like, as long as it is related to operating systems. For those who'd like suggestions, I would like to see the following projects implemented. Many of them may result in a paper being published (perhaps with some additional work after the quarter is over). If you are interested in one of the topics listed below, please see me before writing up your project description. I would prefer that everyone in class pick a different topic.

These topics are slanted towards file systems because that's my area of research. If you would prefer some other topic, I encourage you to pursue it.

  • Write a file system suitable for use with non-volatile magnetic FLASH or MRAM memory. Your file system can run at user level if you like, but should be adaptable (in the indefinite future) into an in-kernel file system. An interesting question is what form metadata structures should take if implemented in memory.
  • Trace and analyze system behavior. This could be process behavior (lifetimes, parent-child relationships), file system behavior, or network behavior. Tracing could be done on desktop machines, servers, or perhaps larger-scale computers. Compare your results with previously published results.
  • Explore the uses of single-address-space operating systems. Propose mechanisms that might make them feasible, along with possible uses.
  • Do research in real-time disk scheduling. Find out how much disk requests affect the performance of a real-time application such as a media player by profiling the performance with and without disk requests (by modifying the code). Propose a disk scheduler that satisfies both real-time and non-real-time process needs.
  • Develop a way to automatically synchronize files on two different computers (for example a home computer and a laptop) so that both "see" the same view of a shared file system.
  • Develop a search-based file system that does not have any directories.
  • Develop a way to run applications on the object stores in the Ceph object-based storage system.

Project research

Before you start your project, please read "An Evaluation of the Ninth SOSP Submissions" (full citation on the class reading list). This "paper" contains a lot of good advice about how to pick a research project and how to write it up.

References & background research

The background work for a research topic is very important, even though it often doesn't get the respect it deserves. Many people simply view a review of prior work as something they have to do. It's not. Rather, it's a survey of what others think about the project you're working on. Learn from what they did right as well as what they did wrong or didn't do at all. To do this, of course, you'll need to make sure you've read as many relevant papers as you can find. Good places to start include:

Of course, you can also use Google or other search engines to find papers as well. However, the inability to find a particular paper online is not an excuse for not getting a copy of the paper. You should use the library and your colleagues to get copies of papers that aren't online.

Simple searches aren't enough, though. You should also try to find papers by looking at the citation lists of papers you've already found. Often, these papers will be more relevant to your work than the paper whose bibliography you found them in.

Writing a research plan

Once you've read the Levin & Redell paper and done your background research, you're ready to come up with a research plan. Your plan should include your goals and the way that you will reach those goals. Your goal should be concrete, e.g. "Show that process arrival rates are Poisson." You will then need to come up with a plan for an experiment that will provide data that supports (or disproves!) your hypothesis. Your plan should state how your experiment will contribute to your goal as well as the program code, data gathering, and analysis that will be necessary. You should, if possible, estimate the amount of time you'll spend on your project ahead of time so that you can see if the project is realistic. You should also list external factors over which you have little (or no) control, e.g. "Get root priviliges on sundance to trace all user processes." This will enable you to set up a timeline for your project and stick to it. The biggest problem encountered with class research projects is poor time management.

Doing the research

Once you've got a good plan, you need to execute it. Do some work every week; don't wait until the end of the quarter. If you finish part of your plan early, go on to the next part. It's easy to take a break during the last week of the quarter, but much harder to do two weeks' work in a single week.

You should interleave doing the project research with the paper write-up as much as possible. Write your background section after you've read all of the papers in your bibliography. You can always go back and modify it later. Write the design section when your design is complete, and change it as your project design changes. This way, you'll only have a small amount of writing that has to be done at the last minute. Hurried writing shows, and it isn't pretty.

Final paper

As mentioned above, you'll need to write a final paper as part of your project. This report should be in the form of an academic paper—you'll be reading plenty of them this quarter—and should be about 12 pages (4000–5000 words) long (single spaced, 11–12 point font, two columns). Diagrams and graphs are strongly encouraged where appropriate. I'm not going to do an exact count of pages or words, but projects that are too lightweight will lose points.

Organization, bibliography, spelling, and grammar of the final report do count, as does (of course) the content itself.

I strongly urge you to use LaTeX in preparing your final paper, though you're welcome to use any software you like. Links that may be useful in learning LaTeX include:

The LaTeX book that I use is A Guide to LaTeX (Kopka & Daly). Amazon also has a list of LaTeX-related books that you can browse.

Important dates

There will be several checkpoints throughout the quarter. These are designed to ensure that your project stays on track to be completed at the end of the quarter. They are not intended to consume lots of time on their own. For example, a checkpoint with a status report should be a few paragraphs long, or a page at most. If you've been doing the project all along, the status report should be relatively easy. If you're behind, well, that's what checkpoints are for.

Your checkpoints should be turned in in ASCII (preferred) or PDF to scott@cs.ucsc.edu. The subject of the email should be "CMPS 221: {checkpoint}" where <checkpoint> is the name of the checkpoint you are submitting

The project checkpoints are:

Sep 29: Project pre-proposal
By this date you should submit to me a one-paragraph preliminary project idea. I will send you feedback that should be reflected in your final proposal.

Oct 6: Proposal
By this date, you should have chosen your project topic. You should hand in a one paragraph summary of your project topic. This should be your best idea about what you will do, but keep in mind that the actual project may evolve over the course of the quarter as you learn more.
 
Oct 18: Bibliography
Doing background research early is crucial. On this date, you should turn in a list of at least 10 references relevant to your project. They may include papers from the class reading list, but at least half of your bibliography must be papers not on the reading list.
 
Oct 27: Project plan
To do a good project, you need a good plan. On this date, you should submit your project plan. This should be in the form of an outline describing the goals of your project and how you plan to accomplish them. This will likely be the longest checkpoint, but it's a writeup you'll need to do for yourself anyway.
 
Nov 17: Progress report
For this checkpoint, turn in a 1–2 paragraph summary of your progress to this point. You should be nearly finished with implementation (if applicable), and should be starting your experiments. You should also have written parts of your final paper, such as the background and design sections.
 
Dec 8: Final paper
Your final paper is due on Wednesday, December 8th at 5 PM. Unlike the other checkpoints, your paper must be submitted in PDF. You can use ps2pdf or distill on any Unix system to convert PostScript to PDF.
 
Prof. Scott A. Brandt (scott@cs.ucsc.edu)