Introduction to operating system : Operating Systems: Three Easy Pieces
After class exercises: Homework
The translation of the README part of the exercises after class in this chapter (easy to view later):
1. Introduction to exercises
This assignment allows you to explore some real code that uses locks and conditional variables to implement various forms of Producer / consumer queues discussed in this chapter. You'll look at the actual code, run it in various configurations, and use it to understand what works, what doesn't work, and other complexities.
Different versions of the code correspond to different ways to "solve" producer / consumer problems.
The first step is Download code And type make to build all variants. After decompression, you should see four files:
- main-one-cv-while.c: a conditional variable is used to solve the producer / consumer problem.
- main-two-cvs-if.c: the same as above, but there are two conditional variables, and use if to check whether to sleep.
- main-two-cvs-while.c: same as above, but there are two conditional variables and while to check whether you sleep. (correct version.
- main-two-cvs-while-extra-unlock.c: same as above, but release the lock and re acquire it around the filler and acquisition programs.
It is also useful to look at PC header. H, which contains the common code of all these different main programs, as well as the Makefile, in order to build the code correctly.
Each program has 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]
Here, the relationship between the first four parameters is clear: - l Specify how many times each producer should cycle (and how many data items each producer produces), -m Control the size of the shared buffer (greater than or equal to 1), - p and - c Set the number of producers and consumers respectively.
More interestingly, there are two sleep string s, one for the producer and the other for the consumer. These flags allow you to sleep each thread at some point of execution, so as to switch to other threads; in this way, you can try various solutions, maybe find out specific problems, or study other aspects of the Producer / consumer problem.
The string is as follows. For example, if there are three producers, the string should specify the sleep time of each producer with a colon separator. The sleep strings of the three producers look like this.
sleep_string_for_p0:sleep_string_for_p1:sleep_string_for_p2
Each sleep string is a comma separated list in turn, which is used to determine how long to sleep at each sleep point in the code. In order to better understand the sleep string of each producer or consumer, let's take a look at the code in main-two-cvs-while.c, especially the producer code. In this code fragment, the producer thread will cycle for a period of time by calling Put the element into the shared buffer with \ _fill(). There are some waiting and signaling code around this filling routine to ensure that the buffer is not filled when the producer tries to fill the buffer. See this chapter for 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 many points marked p0, p1, etc. these points are where the code can sleep. The consumer code (not shown here) has similar waiting points (c0, etc.).
Specifying a sleep string for a producer is simple: just make sure that the producer is in p0, p1,..., p6. For example, the string 1,0,0,0,0,0,0,0 specifies that the producer should sleep for 1 second at the tag p0 (before acquiring the lock), and then not sleep in each cycle.
2. Operation example
Now let's show the output of running one of the programs. First, let's assume that the user runs with only one producer and one consumer. Let's not add any sleep (this is the default behavior). In this example, the buffer size is set to 2 (-m 2).
First, let's build the following code:
homework/HW-Threads-RealCV$ 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 the following program:
homework/HW-Threads-RealCV$ ./main-two-cvs-while -l 3 -m 2 -p 1 -c 1 -v
In this case, if you trace the code (using the verbose flag - v), you will get the following output (or something similar) 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--- ] c1 1 [u 0 f--- ] p0 0 [ --- *--- ] c4 0 [ --- *--- ] c5 0 [ --- *--- ] c6 0 [ --- *--- ] p1 0 [ --- *--- ] c0 1 [f--- u 1 ] p4 1 [f--- u 1 ] p5 1 [f--- u 1 ] p6 1 [f--- u 1 ] c1 1 [f--- u 1 ] p0 0 [*--- --- ] c4 0 [*--- --- ] c5 0 [*--- --- ] c6 0 [*--- --- ] p1 0 [*--- --- ] c0 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 happened in this simple example, let's first understand the description of the shared buffer in the output, as shown on the left. It is empty at first (one empty slot is represented by -- and two empty slots are represented by [* ------]); the output also shows the number of entries in the buffer (num\_full), starting from 0.
Then, after P0 assigns a value to it, its state changes to [u 0 f -] (Num \ _fullchanges to 1). You may also notice that there are some additional tags here; the U tag shows the location of the use\_ptr (this is where the consumer of the next consumption value will get something); similarly, the f tag shows the location of the fill\_ptr (this is where the next producer will generate the value) . when you see the * mark, it just means that use \ _ptrand fill \ _ptrpoint to the same slot.
Along the right side, you can see the track of the steps to be performed by each producer and consumer. For example, the producer acquires the lock (p1), and then generates a value (p4) in it because the buffer has an empty slot. Then continue to execute until it releases the lock (p6), and then try to acquire the lock again. In this example, the user acquires the lock and uses the value (c1, c4) . further study tracking to understand how producer / consumer solutions work with single producers and consumers.
Now, let's add some pauses to change the tracking behavior. In this example, suppose we want the producer to sleep so that consumers can run first. We can do this
homework/HW-Threads-RealCV$ ./main-two-cvs-while -l 1 -m 2 -p 1 -c 1 -P 1,0,0,0,0,0,0 -C 0 -v 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--- ] c3 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 -> 1
As you can see, the generator clicks the p0 tag in the code and gets the first value from its sleep specification, which is 1 in this case, so each object will sleep for 1 second before trying to get the lock. Therefore, the consumer starts running, gets the lock, but finds that the queue is empty, so it enters the sleep state (releasing the lock). Then the producer runs (finally) , all the processes are as you expected.
Note: sleep specifications must be provided for each producer and consumer. Therefore, if you create two producers and three consumers (using - p 2 -c 3), you must specify a sleep string for each (for example, - p 0:1 or - C 0,1,2:0:3,3,3,1,1,1,1). The sleep string can be shorter than the number of sleep points in the code; the remaining sleep slots are initialized to zero.