CS 736 - Fall '94 Project List

(Project Proposal Due: Friday, October 21)
(Midway Interviews: Monday/Tuesday, November 10/11)
(Draft Report to Referees: Tuesday, December 6)
(Referee Reports to Authors: Friday, December 9)
(Final Report Due: Thursday, December 15)

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 can work in teams of two people (and, in certain cases three people) on the project and report.


(1) Operating System Kernel Size Study:

Last year, several CS736 students studied the size of code, static data, and dynamic data in the Mach 3.x ``micro'' kernel. They did a detailed study of code and data size, broken down by OS module and function.

This semester's project involves doing a similar study on our UNIX kernel source code. This includes dividing the kernel into to its main functions, and finding the size of each one. Size of code, static tables, buffer pools, and dynamic memory all should be included in the evaluation. We can use these results to compare to the results from the Mach study.

(2) Parallel Job Control in a Workstation Cluster:

In your first paper assignment, you explored the design of scheduling and control of parallel jobs in a Cluster of Workstations (COW). The goal of this project is to build some basic tools to execute and monitor jobs in a COW environment. A COW is characterized by using commodity (standard) workstations connected by commodity networks.

Specifically, you will need to include the following features: (1) launching (starting) a parallel job, (2) monitoring the job's status, (3) detecting the job's completion, and (4) controlling the job, including suspending, resuming, and killing. If you want to do a three-person project, you can include a graphic interface to these functions (otherwise, a simple line-oriented interface is fine).

You also need to evaluate your features, testing the cost (performance) of each function. You will have to find or develop some parallel jobs to test your software.

(3) Distributed Shared Memory:

In a study started last Fall, we (Burger, Hyder, Miller, and Wood) studied the behavior of paging and scheduling policies for fine-grained distributed shared-memory systems. One question is: what do you do when you get a page fault on one node? Three reasonable choices are (1) gang-context switch, (2) just wait for the page on the local processors, but don't schedule anything else (``spin''), or (3) let a sequential program run on that faulting node until the page fault is satisfied. Our study was done by using and modifying the Wisconsin Wind Tunnel on the TMC CM-5 parallel computer.

We evaluated the gang-context switch and spin policies, but did not evaluate the local context switch policy (called ``Local Under Gang'', or LUG). LUG is attractive because it allows the system to use wasted cycles, but may not be beneficial if memory, cache, and TLB pollution excessively degrade the parallel job's performance. The goal of this project would be to extend the study to include LUG.

(4) Distributed Debugging:

How do we debug processes on different machines? Distributed programs may have processes executing on more than one machine. A difficult problem is to be able halt a distributed program. There are delays associated with any communication and this makes it difficult to promptly and reasonably halt a distributed program. Breakpoint detection is another hard problem. How do you detect a breakpoint that includes processes running on different machines.

A paper written by Jong Choi and I describes several ideas for solving these problems. The goal of this project is to implement some of these ideas to better understand the problems.

(5) Fuzz Revisited:

The goal of this project is to evaluate the robustness of various UNIX utility programs, given an unpredictable input stream. Several years ago, we built tools to generate and test programs by feeding them random input. The result of this study was that we were able to crash 25-33% of the standard UNIX utilities. Almost every UNIX manufacturer adopted our Fuzz testing tools as part of their release process. The goal of this project is to update the Fuzz testing tools and see if reliability has improved several years later.

The first tool is called the fuzz generator. This is a program that generates a random character stream. You will take the fuzz generator and use it to attack as many UNIX utilities as possible, with the goal of trying to break them. For the utilities that break, you will try to determine what type of input cause the break. There is also an tool called ptyjig that allows random input to be fed to interactive programs.

A major extension to these tools would be to figure out a way to generate random input to graphic interface programs.

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.

Last modified: Fri Oct 7 12:14:54 CDT 1994