CSE 120 Spring 2002 Project 1

Due on Sunday, 28 April 2002

Project Demonstrations on Wednesday, 1 May 2002

Overview

This project examines the performance of some simple concurrent programs.

You will implement three programs:

A bogus mutual exclusion algorithm;
Peterson's algorithm;
A bounded buffer program that uses a monitor for synchronization.

For the second and third programs you will measure the throughput using the Unix time command.

The programs are not difficult, but it will take some time to familiarize yourself with the java thread abstraction.

Java Threads Abstraction

You will implement your programs using java and the thread abstraction that java provides. The java developers have done a excellent job of documenting their API's. All the documentation can be found on the java web site (http://java.sun.com/) under the title API Documentation. A direct link to the java 1.4 API documentation is http://java.sun.com/j2se/1.4/docs/api/index.html. The threads abstraction is documented in the java.lang.Thread class. You should also understand the notify() and related functions in java.lang.Object.

First Program: A bogus mutual exclusion algorithm

The following algorithm doesn't satisfy the safety property of the mutual exclusion problem. It is, nonetheless, the canonical algorithm that Unix shell scripts use to implement a critical section.

int lock = 0;
cobegin
    while (1) {
        while (lock) ;
        lock = 1;
        /* in critical section */
        lock = 0;
        }
||
    while (1) {
        while (lock) ;
        lock = 1;
        /* in critical section */
        lock = 0;
       }
coend;

First, convince yourself that this algorithm satisfies neither the safety nor liveness properties of mutual exclusion. Do this by coming up with two adversary schedules: one in which safety is violated and one in which liveness is violated.

Then, implement this bogus mutual excusion algorithm. Have each process enter the critical section max_entries times, where max_entries is specified as a parameter to the program.

In your program, implement a separate shared variable that estimates the number of times both processes are simultaneously in the critical section. Run this program with different values of max_entries, and tabulate for each value of max_entries the fraction of time mutual exclusion was not satisfied.

Explain in your writeup why you only estimate the number of times mutual exclusion is not satisfied: describe the situations in which it either overcounts or undercounts. Part of your grade will be based on how precisely you can estimate the number of times mutual exclusion is violated.

Second Program: Peterson's algorithm

The machine you will use to run this project, ieng9, is a multiprocessor that does not implement sequentially consistent memory. This means that shared memory won't behave as you might imagine it would. For example, consider two threads, both reading and writing a shared variable x. Let x have the value 0. If the first thread stores the value 1 to x, the second thread may not fetch this new value of x for some time; to the second thread, the value of x will remain to be 0. The first process, though, will see the value of x as 1. This behavior results when the two threads are running on different processors, and each processor maintains a cached value of x. When the first thread wrote the value 1 to x, it only updated it's cached value; the value is not immediately propogated to memory (and then to the second thread's cached value).

Implement Peterson's algorithm in java and verify that the safety property mutual exclusion can be violated.

In your writeup, give a behavior that illustrates why with this memory model, Peterson's algorithm is not safe.

Third Program: Bounded Buffer with a java monitor

Here's the pseudocode for a Hoare monitor-based version of a k-bounded buffer program. It uses two unspecified functions:

monitor BB {

private:

int buffers[k], in = 0, out = 0; values = 0;

condition canProduce, canConsume;

public:
entry void Produce (int v) {
if (values == k) canProduce.wait();
values = values + 1;
buffers[in] = v;
in = (in + 1) % k;
canConsume.signal();
}

int void Consume (void) {
int v;
if (values == 0) canConsume.wait();
values = values - 1;
v = buffers[out];
out = (out + 1) % k;
canProduce.signal();
return v;
}
}

Implement this monitor in java. This will require a good understanding of monitors and the notify() family of functions. The value of k should be a parameter specified as a command-line value. You will need to create a thread that repeatedly calls Produce and another thread that repeatedly calls Consume. The producer thread should produce some predictable sequence of values (say, produce the values 1, 2, 3, ...). After producing each value, it should spin, counting to some value prod_time which is specified as a command-line value. The Consumer thread should check that each value it consumes is the one it should be consuming. After consuming a value, it should also spin, counting to the value cons_time which is also specified as a command-line value. Thus, you'll have three command-line parameters: the number of buffers k, the production time prod_time, and the consumpion time cons_time. The total number of values produced need not be a command-line parameter, but it should be reasonably large (i.e., in the tens of thousands).

Run the program with two different speeds: one with prod_time = 50,000 and cons_time = 500,000, and one with prod_time =400,000 and cons_time = 4,000,000. For both of these two speeds, run the program with 2, 4, 8, 16 and 32 buffers. Thus, you will run the program ten times. Measure the execution time of the program for each of these ten experiments, and then compute the throughput (that is, the average number of consumptions per second) for each program.

Explain the relationship you find between the throughput and the program speeds and the relationship between the throughput and the number of buffers.

Using the Unix time command

The Unix time command is a useful tool for getting some idea how long a program takes to run. Some shells (like tcsh) have time as a built-in command, and there is a program time that can be used from other shells.

To use time, just prefix your command with time, e.g.

time javac foo.java

will not only create foo.class from foo.java, but will also tell you how long it took to do so. You will three times: the user time, the system time, and the elapsed time. For this experiments, you can use the reported elapsed time.

Turning In

You should hand in:

The three programs (written in Java and that run on ieng9);
A report (in ASCII, postscript or PDF) that contains:

Your name and e-mail address.
For the first program, the estimate you computed for the number of times mutual exclusion was violated and your explanation on why the value you report is only an estimate.
For the second program, the estimate you computed for the number of times mutual excusion was violated and your explanation on why Peterson's algorithm is not safe.
For the third program, the results of your experiments and the explanation for the behavior you observed..

These files should be turned into us by 11:59 PM PST on Sunday, 28 April 2002. Late projects will not be accepted. Details on how to turn in the project will be available on discus.

Grading

We will have a signup sheet in OSTL by 24 April for times that you can demonstrate your project to one of us. All demonstrations will be on Wednesday, 1 May. Each slot will be for 30 minutes and there will be slots throughout that day. All of your team members should be present at the project demonstration. You will be asked to show and explain your code, to run the programs, and to explain the results you give in your report. You will be graded on your clarity and correctness of your code, the clarity of your presentation, and the validity and reasoning you give for the behavior you report. This demonstration will account for 75% of your project grade.

We will also grade your report, which will account for the remaining 25% of your project grade.This report will be graded for clarity, honesty, and insight.Writing using correct and clear English is important. It is better to use simple English and be correct and clear rather than using complex English and be incorrect or unclear.

last edited 9 April 2002 by kam