threads-cv

Overview

This homework lets you explore some real code that uses locks and condition variables to implement various forms of the producer/consumer queue discussed in the chapter. You'll look at the real code, run it in various configurations, and use it to learn about what works and what doesn't, as well as other intricacies.

The different versions of the code correspond to different ways to "solve" the producer/consumer problem. Most are incorrect; one is correct. Read the chapter to learn more about what the producer/consumer problem is, and what the code generally does.

The first step is to download the code and type make to build all the variants. You should see four:

• main-one-cv-while.c: The producer/consumer problem solved with a single condition variable.
• main-two-cvs-if.c: Same but with two condition variables and using an if to check whether to sleep.
• main-two-cvs-while.c: Same but with two condition variables and while to check whether to sleep. This is the correct version.
• main-two-cvs-while-extra-unlock.c: Same but releasing the lock and then reacquiring it around the fill and get routines.

It's also useful to look at pc-header.h which contains common code for all of these different main programs, and the Makefile so as to build the code properly.

Each program takes the following flags:

• -l <number of items each producer produces>
• -m <size of the shared producer/consumer buffer>
• -p <number of producers>
• -c <number of consumers>
• -P <sleep string: how producer should sleep at various points>
• -C <sleep string: how consumer should sleep at various points>
• -v [verbose flag: trace what is happening and print it]
• -t [timing flag: time entire execution and print total time]

The first four arguments are relatively self-explanatory: -l specifies how many times each producer should loop (and thus how many data items each producer produces), -m controls the size of the shared buffer (greater than or equal to one), and -p and -c set how many producers and consumers there are, respectively.

What is more interesting are the two sleep strings, one for producers, and one for consumers. These flags allow you to make each thread sleep at certain points in an execution and thus switch to other threads; doing so allows you to play with each solution and perhaps pinpoint specific problems or study other facets of the producer/consumer problem.

The string is specified as follows. If there are three producers, for example, the string should specify sleep times for each producer separately, with a colon separator. The sleep string for these three producers would look something like this:

  sleep_string_for_p0:sleep_string_for_p1:sleep_string_for_p2

Each sleep string, in turn, is a comma-separated list, which is used to decide how much to sleep at each sleep point in the code. To understand this per-producer or per-consumer sleep string better, let's look at the code in main-two-cvs-while.c, specifically at the producer code. In this code snippet, a producer thread loops for a while, putting elements into the shared buffer via calls to do_fill(). Around this filling routine are some waiting and signaling code to ensure the buffer is not full when the producer tries to fill it. See the chapter for more details.

void *producer(void *arg) {
    int id = (int) arg;
    int i;
    for (i = 0; i < loops; i++) {   p0;
        Mutex_lock(&m);             p1;
        while (num_full == max) {   p2;
            Cond_wait(&empty, &m);  p3;
        }
        do_fill(i);                 p4;
        Cond_signal(&fill);         p5;
        Mutex_unlock(&m);           p6;
    }
    return NULL;
}

As you can see from the code, there are a number of points labeled p0, p1, etc. These points are where the code can be put to sleep. The consumer code (not shown here) has similar wait points (c0, etc.).

Specifying a sleep string for a producer is easy: just identify how long the producer should sleep at each point p0, p1, ..., p6. For example, the string 1,0,0,0,0,0,0 specifies that the producer should sleep for 1 second at marker p0 (before grabbing the lock), and then not at all each time through the loop.

Now let's show the output of running one of these programs. To begin, let's assume that the user runs with just one producer and one consumer. Let's not add any sleeping at all (this is the default behavior). The buffer size, in this example, is set to 2 (-m 2).

First, let's build the code:

prompt> make
gcc -o main-two-cvs-while main-two-cvs-while.c -Wall -pthread
gcc -o main-two-cvs-if main-two-cvs-if.c -Wall -pthread
gcc -o main-one-cv-while main-one-cv-while.c -Wall -pthread
gcc -o main-two-cvs-while-extra-unlock main-two-cvs-while-extra-unlock.c -Wall -pthread

Now we can run something:

prompt> ./main-two-cvs-while -l 3 -m 2 -p 1 -c 1 -v

In this case, if you trace the code (with the verbose flag, -v), you will get the following output (or something like it) on the screen:

 NF             P0 C0
  0 [*---  --- ] p0
  0 [*---  --- ]    c0
  0 [*---  --- ] p1
  1 [u  0 f--- ] p4
  1 [u  0 f--- ] p5
  1 [u  0 f--- ] p6
  1 [u  0 f--- ] p0
  1 [u  0 f--- ]    c1
  0 [ --- *--- ]    c4
  0 [ --- *--- ]    c5
  0 [ --- *--- ]    c6
  0 [ --- *--- ]    c0
  0 [ --- *--- ] p1
  1 [f--- u  1 ] p4
  1 [f--- u  1 ] p5
  1 [f--- u  1 ] p6
  1 [f--- u  1 ] p0
  1 [f--- u  1 ]    c1
  0 [*---  --- ]    c4
  0 [*---  --- ]    c5
  0 [*---  --- ]    c6
  0 [*---  --- ]    c0
  0 [*---  --- ] p1
  1 [u  2 f--- ] p4
  1 [u  2 f--- ] p5
  1 [u  2 f--- ] p6
  1 [u  2 f--- ]    c1
  0 [ --- *--- ]    c4
  0 [ --- *--- ]    c5
  0 [ --- *--- ]    c6
  1 [f--- uEOS ] [main: added end-of-stream marker]
  1 [f--- uEOS ]    c0
  1 [f--- uEOS ]    c1
  0 [*---  --- ]    c4
  0 [*---  --- ]    c5
  0 [*---  --- ]    c6

Consumer consumption:
  C0 -> 3

Before describing what is happening in this simple example, let's understand the depiction of the shared buffer in the output, as is shown on the left. At first it is empty (an empty slot indicated by ---, and the two empty slots shown as [*--- --- ]); the output also shows the number of entries in the buffer (num_full), which starts at 0. Then, after P0 puts a value in it, its state changes to [u 0 f--- ] (and num_full changes to 1). You might also notice a few additional markers here; the u marker shows where the use_ptr is (this is where the next consumer to consume a value will get something from); similarly, the f marker shows where the fill_ptr is (this is where the next producer will produce a value). When you see the * marker, it just means the use_ptr and fill_ptr are pointing to the same slot.

Along the right you can see the trace of which step each producer and consumer is about to execute. For example, the producer grabs the lock (p1), and then, because the buffer has an empty slot, produces a value into it (p4). It then continues until the point where it releases the lock (p6) and then tries to reacquire it. In this example, the consumer acquires the lock instead and consumes the value (c1, c4). Study the trace further to understand how the producer/consumer solution works with a single producer and consumer.

Now let's add some pauses to change the behavior of the trace. In this case, let's say we want to make the producer sleep so that the consumer can run first. We can accomplish this as follows:

prompt> ./main-two-cvs-while -l 1 -m 2 -p 1 -c 1 -P 1,0,0,0,0,0,0 -C 0 -v

The results:
 NF             P0 C0
  0 [*---  --- ] p0
  0 [*---  --- ]    c0
  0 [*---  --- ]    c1
  0 [*---  --- ]    c2
  0 [*---  --- ] p1
  1 [u  0 f--- ] p4
  1 [u  0 f--- ] p5
  1 [u  0 f--- ] p6
  1 [u  0 f--- ] p0
  1 [u  0 f--- ]    c3
  0 [ --- *--- ]    c4
  0 [ --- *--- ]    c5
  0 [ --- *--- ]    c6
  0 [ --- *--- ]    c0
  0 [ --- *--- ]    c1
  0 [ --- *--- ]    c2
 ...

As you can see, the producer hits the p0 marker in the code and then grabs the first value from its sleep specification, which in this case is 1, and thus each sleeps for 1 second before even trying to grab the lock. Thus, the consumer gets to run, grabs the lock, but finds the queue empty, and thus sleeps (releasing the lock). The producer then runs (eventually), and all proceeds as you might expect.

Do note: a sleep specification must be given for each producer and consumer. Thus, if you create two producers and three consumers (with -p 2 -c 3), you must specify sleep strings for each (e.g., -P 0:1 or -C 0,1,2:0:3,3,3,1,1,1). Sleep strings can be shorter than the number of sleep points in the code; the remaining sleep slots are initialized to be zero.