CSE 120 Winter 2001 Project 1

Due 30 January 2001

Overview

This project examines some issues of the performance of some simple concurrent programs.

You will implement three programs:

Peterson's algorithm;
A bounded buffer program that uses atomic read/write shared variables for synchronization;
A bounded buffer program that uses semaphores for synchronization.

For each program you will measure the throughput using the Unix time command.

A Simple Process Abstraction

You will implement your programs using the Unix process, shared memory, and semaphore abstractions. The last two abstractions are somewhat complex, and so we've packaged the three abstractions into a single header file that simplifies their use.

The header file is called CSprocesses.h and the file you include is CSprocesses.o. It provides a function cobegin that creates a set of processes, all sharing some memory and an array of semaphores.

The code that a process executes is defined by a function with type CSprocess. This function takes two parameters: an integer, which is unique for each process, and a pointer to the shared memory segment. The semaphores that these processes share are named by indices into a hidden semaphore array. The processes are created via the cobegin function which also manages the shared memory segment and the semaphore array for the processes. The size of the shared memory segment and the number of semaphores are specified as parameters to cobegin.

Here's the definition of cobegin:

int cobegin (int sizeSM, int numSems, void (*init)(void *),
void (*final)(void *), ...);

The first two parameters specify the size of the shared memory segment and the number of semaphores respectively. The third parameter is a function that is invoked after the shared memory and the semaphores are created and before the processes are created. This function can be used to initialize the shared memory and semaphores for the processes. Similarly, the fourth parameter names a function that is invoked when all of the processes complete and before the shared memory is deallocated.

The remaining parameters are a list of functions, each specifying the code for a process to run.The list is terminated by NULL. If you forget to include the NULL, then cobegin will trundle off forking who know what, so don't forget that NULL...

The semaphores are manipulated by SemInit, SemP and SemV. The last two functions are the classic P and V operations, and the first function initializes the value of a semaphore. SemInit can be invoked only by the initializing routine init; otherwise an assert failure is raised.

Here's a complete example of the use of CSprocesses. It uses a single semaphore to implement the critical section problem for three processes. Each process increments a shared variable count each time one enters the critical section. Each process executes the same code (defined by the function Process), and each will have a distinct value of the parameter me. The function Init initializes count and the semaphore, and Final prints out the final value of count.

Some points worth noting about this example:

Init and Final are defined as parameters to cobegin, and so their parameter needs to be cast to point to the structure shared_mem to keep the compiler from complaining. The cast isn't needed for the functions defining the processes because their type isn't statically declared in the definition of cobegin.
I didn't need to wrap count with a struct. I did this to remind you of how the C struct abstraction is used.
The CSprocesses abstraction hides the array of semaphore from you (in an effort to simplify their use. Take a look at CSprocesses.c if you'd like to see how they are actually used). Semaphores are just named by indices into this array. This is the same technique that Unix uses to name open files - a file descriptor is just an index into a hidden open file array. Here, I named the single semaphore MUTEX using a define statement.

#include "CSprocesses.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#define MUTEX 0
long max_entries;
struct shared_mem { long count; };
void Init (void * sm) {
    struct shared_mem *shared = (struct shared_mem *) sm;
    shared->count = 0;
    SemInit(MUTEX, 1);
    }
void Final (void * sm) {
    struct shared_mem *shared = (struct shared_mem *) sm;
    printf("Processes entered %d times\n", shared->count);
    }
void Process (int me, struct shared_mem *shared) {
    int stop = 0;
    while (! stop) {
        SemP(MUTEX);
        stop = (++ shared->count >= max_entries);
        SemV(MUTEX);
        }
    }
int main (int argc, int** argv) {
    assert (argc == 2);
    max_entries = atol(argv[1]);
    assert (max_entries >= 0);
    cobegin(sizeof(struct shared_mem), 1, Init, Final,
        Process, Process, Process, NULL);
    exit(0);
}

Program 1: Peterson's Algorithm

Implement the standard two process Peterson's Algorithm using the CSprocesses abstraction. Like the example code given above, have the two processes together enter the critical section max_entries times, where max_entries is specified as a parameter to the program.

Run and time the program's execution for several values of max_entries ranging from 10 to 100,000. How is the running time related to the value of max_entries? Is the relation linear? If not, then explain why it isn't.

Program 2: Bounded Buffer using Semaphores

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

prod_func that produces an integer;
cons_func that consumes an integer.

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

semaphore produce = k, consume = 0;

cobegin

while (1) {

int v = prod_func();

P(produce);

buffers[in] = v;

in = (in + 1) % k;

V(consume);

}

||

while (1) {

int v;

P(consume);

v = buffers[out];

out = (out + 1) % k;

V(produce);

cons_func(v);

}

coend;

Implement this program using CSprocesses. The value of k should be a parameter specified as a command-line value. The function prod_value should produce some predictable value (say, produce the values 1, 2, 3, ...) and then loop counting to some value prod_time which is specified as a command-line value. The function cons_value should check that the value it consumes is the one it should be consuming and then loop counting to some value cons_time which is also specified as a command-line value. Thus, you'll have three command-line parameters: the number of buffers, the production time, and the consumption time. The total number of values produced need not be a command-line parameter, but it should be reasonably large (i.e., at least in the 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.

Program 3: Bounded Buffer using Atomic Read/Write Shared Variable for Synchronization

The previous program used semaphores to synchronize the producer and consumer. One doesn't need semaphores, just like one doesn't need semaphores to implement mutual exclusion. Instead, one can simply use busy waiting and the atomic read/write properties of shared variables. For this program, you first need to devise such a shared variable version of the k-bounded buffer problem. As before, use CSprocesses.h, but the second parameter to cobegin will be zero.

First, write a pseudocode version of your program using a syntax like the pseudocode example for the semaphore-based k-bounded buffer program given above. Then, give an informal argument showing the correctness (safety and liveness) of your solution.

Translate the pseudocode into C and CSprocesses. Run the same ten experiments that you ran for the semaphore-based version. Explain the relationship you find between the throughput and the program speeds and the relationship between the throughput and the number of buffers.

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 gcc foo.c

will not only create a.out from foo.c, 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 C and that run on the Linux machines in OSTL);
A report (either in postscript, PDF or ASCII) that contains:

Your name and e-mail address.
For the first program, the results of your experiments and the explanation for the behavior you observed.
For the second program, the results of your experiments and the explanation for the behavior you observed.
For the third program, the pseudocode and correctness argument for the shared variable version of the k-bounded buffer program, the results of your experiments and the explanation for the behavior you observed.

These files should be encoded as a uuencoded compressed tar file and e-mailed to cs120w@sdcc7.ucsd.edu by 11:59 PM PST on 30 January 2001. We will not accept late projects. The way to mail a uuencoded compressed tar file file is as follows: assume that your programs are called p1peterson.c, p1busy.c and p1sem.c, and your report is called p1report.ps. Ensure that these four files are all in the same directory on a Lunux machine. Type the following commands:

    tar -cf p1.tar p1peterson.c p1busy.c p1sem.c p1report.ps
    compress p1.tar
    uuencode p1.tar.Z p1.tar.Z | mail cs120w@sdcc7.ucsd.edu

If you wish, you can then remove the compressed tar file:

rm p1.tar.Z

Grading

Your project will be graded on

The quality of your programs. Points that lend quality to your program include correctness, clarity, elegance, and performance. A correct program, of course, is best, but an incorrect program with the bugs detailed in your report is better than an incorrect program with the bugs not detailed in the report.
Writing a program clearly (so that it can be read and understood by humans as well as computers) is a skill worth developing. Using small functions, using good modularity, and commenting unclear code are all well-known techniques for writing code clearly. Sometimes people use blank lines or short lines to show the structure of a program (some program editors enforce this style), but doing so can expand the length of a code segment significantly thereby reducing the clarity of the code. For the same reason, having too many comments in your program can hurt clarity as much as having too few comments; use comment with caution. Every now and then, one will find a program in which the comments disagree with the code (and, of course, the code has precedence!). If you do this, then your project grade will be docked severely.
The discussion on your algorithm for k-bounded buffer with shared variables. This should be clear, correct, and written in English that would not cause an English teacher to despair. I won't worry about things like the breadth of your vocabulary or whether you use parallel construction, but I would like you to take some time in planning how to present your discussion.
The quality of your experiments. For each experiment you choose some values for the independent variable (for example, the number of times mutex is to be attained, or the speed and number of buffers) and measure the value of a dependent variable (the throughput). How accurate are your measurements? How well have you isolated the experiment so that the impact other variables that can affect the dependent variable is minimized? For example, if you run your experiments on a heavily loaded machine, then the resulting competition may make your experiments not very useful. (Note that you may wish to choose some off-hours time to run the experiments on an isolated machine in OSTL).
The discussion and analyses of your experiments. Like the discussion on your algorithm, this material should also be clear, correct, and written in proper English. You will also be graded on the depth of your analyses.

last edited 4 January 2001 by kam