|
ducer/consumer
or bounded-buffer problem.
30.2 The Producer/Consumer (Bound Buffer) Problem
The next synchronization problem we will confront in this chapter is
known as the producer/consumer problem, or sometimes as the bounded
buffer
problem, which was first posed by Dijkstra [D72]. Indeed, it was
this very producer/consumer problem that led Dijkstra and his co-workers
to invent the generalized semaphore (which can be used as either a lock
or a condition variable) [D01]; we will learn more about semaphores later.
Imagine one or more producer threads and one or more consumer
threads. Producers produce data items and wish to place them in a buffer;
consumers grab data items out of the buffer consume them in some way.
This arrangement occurs in many real systems. For example, in a
multi-threaded web server, a producer puts HTTP requests into a work
queue (i.e., the bounded buffer); consumer threads take requests out of
this queue and process them.
A bounded buffer is also used when you pipe the output of one pro-
gram into another, e.g., grep foo file.txt | wc -l. This example
runs two processes concurrently; grep writes lines from file.txt with
the string foo in them to what it thinks is standard output; the U
NIX
shell redirects the output to what is called a U
NIX
pipe (created by the
pipe
system call). The other end of this pipe is connected to the stan-
dard input of the process wc, which simply counts the number of lines in
the input stream and prints out the result. Thus, the grep process is the
producer; the wc process is the consumer; between them is an in-kernel
bounded buffer; you, in this example, are just the happy user.
c
2014, A
RPACI
-D
USSEAU
T
HREE
E
ASY
P
IECES
330
C
ONDITION
V
ARIABLES
1
int buffer;
2
int count = 0; // initially, empty
3
4
void put(int value) {
5
assert(count == 0);
6
count = 1;
7
buffer = value;
8
}
9
10
int get() {
11
assert(count == 1);
12
count = 0;
13
return buffer;
14
}
Figure 30.4: The Put and Get Routines (Version 1)
1
void *producer(void *arg) {
2
int i;
3
int loops = (int) arg;
4
for (i = 0; i < loops; i++) {
5
put(i);
6
}
7
}
8
9
void *consumer(void *arg) {
10
int i;
11
while (1) {
12
int tmp = get();
13
printf("%d\n", tmp);
14
}
15
}
Figure 30.5: Producer/Consumer Threads (Version 1)
Because the bounded buffer is a shared resource, we must of course
require synchronized access to it, lest
1
a race condition arise. To begin to
understand this problem better, let us examine some actual code.
The first thing we need is a shared buffer, into which a producer puts
data, and out of which a consumer takes data. Let’s just use a single
integer for simplicity (you can certainly imagine placing a pointer to a
data structure into this slot instead), and the two inner routines to put
a value into the shared buffer, and to get a value out of the buffer. See
Figure
30.4
for details.
Pretty simple, no? The put() routine assumes the buffer is empty
(and checks this with an assertion), and then simply puts a value into the
shared buffer and marks it full by setting count to 1. The get() routine
does the opposite, setting the buffer to empty (i.e., setting count to 0)
and returning the value. Don’t worry that this shared buffer has just a
single entry; later, we’ll generalize it to a queue that can hold multiple
entries, which will be even more fun than it sounds.
Now we need to write some routines that know when it is OK to access
the buffer to either put data into it or get data out of it. The conditions for
1
This is where we drop some serious Old English on you, and the subjunctive form.
O
PERATING
S
YSTEMS
[V
ERSION
0.80]
WWW
.
OSTEP
.
ORG
C
ONDITION
V
ARIABLES
331
1
cond_t
cond;
2
mutex_t mutex;
3
4
void *producer(void *arg) {
5
int i;
6
for (i = 0; i < loops; i++) {
7
Pthread_mutex_lock(&mutex);
// p1
8
if (count == 1)
// p2
9
Pthread_cond_wait(&cond, &mutex); // p3
10
put(i);
// p4
11
Pthread_cond_signal(&cond);
// p5
12
Pthread_mutex_unlock(&mutex);
// p6
13
}
14
}
15
16
void *consumer(void *arg) {
17
int i;
18
for (i = 0; i < loops; i++) {
19
Pthread_mutex_lock(&mutex);
// c1
20
if (count == 0)
// c2
21
Pthread_cond_wait(&cond, &mutex); // c3
22
int tmp = get();
// c4
23
Pthread_cond_signal(&cond);
// c5
24
Pthread_mutex_unlock(&mutex);
// c6
25
printf("%d\n", tmp);
26
}
27
}
Figure 30.6: Producer/Consumer: Single CV and If Statement
this should be obvious: only put data into the buffer when count is zero
(i.e., when the buffer is empty), and only get data from the buffer when
count
is one (i.e., when the buffer is full). If we write the synchronization
code such that a producer puts data into a full buffer, or a consumer gets
data from an empty one, we have done something wrong (and in this
code, an assertion will fire).
This work is going to be done by two types of threads, one set of which
we’ll call the producer threads, and the other set which we’ll call con-
sumer
threads. Figure
30.5
shows the code for a producer that puts an
integer into the shared buffer loops number of times, and a consumer
that gets the data out of that shared buffer (forever), each time printing
out the data item it pulled from the shared buffer.
Do'stlaringiz bilan baham: | 
