	UNIVERSITY OF WISCONSIN-MADISON Computer Sciences Department
CS 736 Fall 2004		Barton Miller

Project List

(Project Assigned: Thursday, October 7)
(Project Proposal Due: Friday, October 15, 3pm)
(Midway Interviews: Monday, November 22)
(Draft Report to Referees: Monday, December 13, in class)
(Referee Reports to Authors: Wednesday, December 15)
(Final Report Due: Friday, December 17, 1pm)
(Poster Session: Monday, December 20, time TBA)

General Comments

The projects are intended to give you an opportunity to study a particular area related to operating systems. Your project will require a test implementation, measurement study or analysis, literature search, and evaluation.

The project suggestions below are briefly stated. They are intended to guide you into particular areas and you are expected to expand these suggestions into a full project descriptions. This gives you more freedom in selecting an area and more burden in defining your own project. There may be more issues listed for a project than you can cover. If you have a topic of your own that is not listed below, you should come and talk with me so we can work out a reasonable project description.

You will write a paper that reports on your project. This paper will structured as if you were going to submit it to a conference. I will provide more details on the project report later in the semester.

You should work in teams of two people (and, in certain cases three people) on the project and report.

Projects

Here are a few project suggestions. I have mentioned other ideas in class and I encourage you to develop an idea of your own.

(1) Dynamic Instrumentation API:

The Paradyn project has developed a library for patching code into running programs. This interface, called the DynInst API, allows programmers to write tools that can patch code into unmodified programs in a machine-independent way. So, a tool that uses DynInst can work on SPARC, x86, IA64, Power, MIPS, and Alpha. Many simple tools have been built using DynInst for tracing and debugging, and more complex tools for doing such things as checkpointing and process migration.

One idea for a project involves Security Avoidance. Software vendors often want to control access to a piece of software, with the goal of charging the user for each copy. To this end, many programs require a license key, either stored in a file or distributed from license servers. When you first start an application program, it will obtain the license to see if you have permission to run the program. Previous students have successfully used dyninst to bypass obtaining a license from a server. The goal of this project is to attempt this operation for programs that store their licenses locally. We will discuss a list of possible programs that might be appropriate.

(2) Random Testing of Programs:

Join a distinguished line of CS736 projects! In the past (1990, 1995, and 2000), we have used random input to test the reliability of application programs on UNIX and NT. These techniques have been quite effective in finding bugs, and have been widely cited; this work has become almost a cult in itself.

The goal of this project is to take the 1995 study of applications on various platforms and repeat the study on command-line and X-window applications. Especially interesting would be to compare the various free/open UNIX systems such as Linux, BSDi, and freeBSD). As a product of this project, we would like to provide: (1) an update of the tool set that can be used by other developers, (2) bug reports for the software vendors, and (3) bug fixes for these bugs.

(3) Improving Page Replacement in Linux:

The goal of this project is to study the the internals of Linux as they relate to page replace policies. The steps involved in this project are to: (a) search for current and previous work in this area, (b) examine the Linux kernel source code to familiarize yourself with its structure and paging mechanisms, (c) make changes to Linix to implement WSClock, and (d) design experiments to test the performance of the new and old page replacement mechanisms.

(4) Visualizing File System Layout: (thanks to Andrea Arpaci-Dusseau)

A file system can be viewed as a large, complex data structure (i.e., consisting of a superblock, i-nodes, indirect blocks, and data blocks). In this project, you will investigate how the layout of a local file system can be visualized. This will involve understanding the file system data structures of a particular OS (e.g., Linux or Windows), traversing those structures by reading from the raw disk device, determining what information is interesting, and innovating in how to display this complex information simply.

You may want to show which blocks on disk are dedicated to i-nodes vs. data blocks vs. unallocated, the layout of individual files across the disk (i.e., the amount of fragmentation), and the age of each block. In addition, you will want to present quantitative information about such things as grouping and fragmentation.

(5) Windows vs. Unix File System Performance:

NTFS and the Unix FFS are both designed to provide good performance. However each file system has been optimized to be good at different things. The goal of this project is to do a side-by-side comparison of the basic on-disk structures, performance strategies (e.g., memory caching of data and meta-data, pre-fetching, replication), and generate workloads to tests these features.

(6) Mobility and GPS:

This idea of this project is to combine a GPS navigation card with a mobile computer such as a laptop or PDA. Pick some locale, such as the CS building or UW campus, develop (or obtain) a map of coordinates in this locale, and provide a smart display of location with nearby resources. Examples of "smart" information might be the name of person in the office, nature of room (such as bathroom, conference room, or administrative office),

You might make such a system smarter by attempting to obtain vertical information, such as on which floor you are (might be obtained by inferring from which base station you are receiving, e.g.,).

If needed, I will help obtain the GPS receiver card; you need to provide the mobile device.

Project Proposal

The project descriptions listed above a intentionally brief. You will need to expand and refine these to develop your own project. Different groups may choose the same topic, but have significantly different emphases.

Your project proposal will describe your goals, methods, implementation outline, evaluation criteria, and resources needed. First, you should describe the basic problem that you will be addressing. Next, you should provide a more detailed description of how you will approach the problem. This description should be contain much more detail than the brief paragraphs given above. You will provide an outline of features that you project will include, an implementation plan, and an evaluation plan.

Project proposals will typically be 3 to 4 double-spaced pages.

Referee Report

Each of you will referee the paper from another group. I am providing you with a sample referee report form, that is similar to one that I used for a recent conference. I am also providing you with two sample referee reports, to give you an idea of what might appear in a real report.

In general, a referee report starts with a summary of the main idea(s) in the paper, and then has an overall statement of the quality. You should then review the main technical ideas. In addition, either a marked-up copy of the paper, with typos and related errors, or a summary of typos and related errors should be given to the authors.