Chapter 30: Definition And Routines

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives

Explain the main ideas and vocabulary in Definition And Routines.
Work through the source examples for Definition And Routines without depending on raw chunk order.
Use Definition And Routines as selective reference when learner modules point back to Ostep.

Prerequisites

Earlier prerequisite concepts leading into Chapter 30: Definition And Routines.

Module targets

module-03-concurrency-synchronization

AI companion modes

Explain simply
Socratic tutor
Quiz me
Challenge my understanding
Diagnose my confusion
Generate extra practice
Revision mode
Connect forward / backward

Source-of-truth note

This unit is anchored to Ostep and the source chapter "Chapter 30: Definition And Routines". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance

Primary source: Ostep
Source chapter 30: Chapter 30: Definition And Routines
Raw source file: 142-30-1-definition-and-routines.md
Raw source file: 143-30-2-the-producer-consumer-bounded-buffer-problem.md
Raw source file: 144-30-2-the-producer-consumer-bounded-buffer-problem-part-2.md

Merged source

Definition And Routines

30.1 Definition and Routines

30 Condition Variables

Thus far we have developed the notion of a lock and seen how one can be properly built with the right combination of hardware and OS support.

Unfortunately, locks are not the only primitives that are needed to build concurrent programs.

In particular, there are many cases where a thread wishes to check whether aconditionis true before continuing its execution. For example, a parent thread might wish to check whether a child thread has completed before continuing (this is often called ajoin()); how should such a wait be implemented? Let's look at Figure 30.1.

void *child(void *arg) {
printf("child\n");

3 // XXX how to indicate we are done?

4 return NULL;

}
int main(int argc, char *argv[]) {
printf("parent: begin\n");
pthread_t c;
Pthread_create(&c, NULL, child, NULL); // create child
// XXX how to wait for child?
printf("parent: end\n");
return 0;
}

Figure 30.1:A Parent Waiting For Its Child

What we would like to see here is the following output:

parent: begin child parent: end

We could try using a shared variable, as you see in Figure 30.2. This

solution will generally work, but it is hugely inefficient as the parent spins and wastes CPU time. What we would like here instead is some way to put the parent to sleep until the condition we are waiting for (e.g., the child is done executing) comes true.

1 2

void *child(void *arg) {
printf("child\n");
done = 1;
return NULL;
}
int main(int argc, char *argv[]) {
printf("parent: begin\n");
pthread_t c;
Pthread_create(&c, NULL, child, NULL); // create child
while (done == 0)

14 ; // spin

printf("parent: end\n");
return 0;
}

Figure 30.2:Parent Waiting For Child: Spin-based Approach

THECRUX: HOWTOWAITFORA CONDITION

In multi-threaded programs, it is often useful for a thread to wait for some condition to become true before proceeding. The simple approach, of just spinning until the condition becomes true, is grossly inefficient and wastes CPU cycles, and in some cases, can be incorrect. Thus, how should a thread wait for a condition?

To wait for a condition to become true, a thread can make use of what is known as acondition variable. Acondition variable is an explicit queue that threads can put themselves on when some state of execution

(i.e., some condition) is not as desired (by waiting on the condition);

some other thread, when it changes said state, can then wake one (or more) of those waiting threads and thus allow them to continue (bysignalingon the condition). The idea goes back to Dijkstra's use of "private semaphores" [D68]; a similar idea was later named a "condition variable" by Hoare in his work on monitors [H74].

To declare such a condition variable, one simply writes something like this: pthreadcondt c;, which declarescas a condition variable (note: proper initialization is also required). A condition variable has two operations associated with it: wait()andsignal(). Thewait()call is executed when a thread wishes to put itself to sleep; thesignal()call is executed when a thread has changed something in the program and thus wants to wake a sleeping thread waiting on this condition. Specifically, the POSIX calls look like this:

pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
pthread_cond_signal(pthread_cond_t *c);
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;
void thr_exit() {
Pthread_mutex_lock(&m);
done = 1;
Pthread_cond_signal(&c);
Pthread_mutex_unlock(&m);
}
void *child(void *arg) {
printf("child\n");
thr_exit();
return NULL;
}
void thr_join() {
Pthread_mutex_lock(&m);
while (done == 0)
Pthread_cond_wait(&c, &m);
Pthread_mutex_unlock(&m);
}
int main(int argc, char *argv[]) {
printf("parent: begin\n");
pthread_t p;
Pthread_create(&p, NULL, child, NULL);
thr_join();
printf("parent: end\n");
return 0;
}

Figure 30.3:Parent Waiting For Child: Use A Condition Variable

We will often refer to these aswait()andsignal()for simplicity.

One thing you might notice about thewait()call is that it also takes a mutex as a parameter; it assumes that this mutex is locked whenwait() is called. The responsibility ofwait()is to release the lock and put the calling thread to sleep (atomically); when the thread wakes up (after some other thread has signaled it), it must re-acquire the lock before returning to the caller. This complexity stems from the desire to prevent certain race conditions from occurring when a thread is trying to put itself to sleep. Let's take a look at the solution to the join problem (Figure 30.3) to understand this better.

There are two cases to consider. In the first, the parent creates the child thread but continues running itself (assume we have only a single processor) and thus immediately calls intothrjoin()to wait for the child thread to complete. In this case, it will acquire the lock, check if the child is done (it is not), and put itself to sleep by callingwait()(hence releasing the lock). The child will eventually run, print the message "child", and callthrexit()to wake the parent thread; this code just grabs the lock, sets the state variabledone, and signals the parent thus waking it.

Finally, the parent will run (returning fromwait()with the lock held), unlock the lock, and print the final message "parent: end".

In the second case, the child runs immediately upon creation, sets doneto 1, calls signal to wake a sleeping thread (but there is none, so it just returns), and is done. The parent then runs, callsthrjoin(), sees thatdoneis 1, and thus does not wait and returns.

One last note: you might observe the parent uses awhileloop instead of just anifstatement when deciding whether to wait on the condition.

While this does not seem strictly necessary per the logic of the program, it is always a good idea, as we will see below.

To make sure you understand the importance of each piece of the threxit()andthrjoin()code, let's try a few alternate implementations. First, you might be wondering if we need the state variabledone.

What if the code looked like the example below? Would this work?

void thr_exit() {
Pthread_mutex_lock(&m);
Pthread_cond_signal(&c);
Pthread_mutex_unlock(&m);
}
void thr_join() {
Pthread_mutex_lock(&m);
Pthread_cond_wait(&c, &m);
Pthread_mutex_unlock(&m);
}

Unfortunately this approach is broken. Imagine the case where the child runs immediately and callsthrexit()immediately; in this case, the child will signal, but there is no thread asleep on the condition. When the parent runs, it will simply call wait and be stuck; no thread will ever wake it. From this example, you should appreciate the importance of the state variabledone; it records the value the threads are interested in knowing. The sleeping, waking, and locking all are built around it.

Here is another poor implementation. In this example, we imagine that one does not need to hold a lock in order to signal and wait. What problem could occur here? Think about it!

void thr_exit() {
done = 1;
Pthread_cond_signal(&c);
}
void thr_join() {
if (done == 0)
Pthread_cond_wait(&c);
}

The issue here is a subtle race condition. Specifically, if the parent calls thrjoin()and then checks the value ofdone, it will see that it is 0 and thus try to go to sleep. But just before it calls wait to go to sleep, the parent is interrupted, and the child runs. The child changes the state variable doneto 1 and signals, but no thread is waiting and thus no thread is woken. When the parent runs again, it sleeps forever, which is sad.

TIP: ALWAYSHOLDTHELOCKWHILESIGNALING

Although it is strictly not necessary in all cases, it is likely simplest and best to hold the lock while signaling when using condition variables. The

example above shows a case where youmusthold the lock for correctness; however, there are some other cases where it is likely OK not to, but probably is something you should avoid. Thus, for simplicity,hold the lock when calling signal.

The converse of this tip, i.e., hold the lock when calling wait, is not just a tip, but rather mandated by the semantics of wait, because wait always (a) assumes the lock is held when you call it, (b) releases said lock when putting the caller to sleep, and (c) re-acquires the lock just before returning. Thus, the generalization of this tip is correct: hold the lock when calling signal or wait, and you will always be in good shape.

Hopefully, from this simple join example, you can see some of the basic requirements of using condition variables properly. To make sure you understand, we now go through a more complicated example: theproducer/consumerorbounded-bufferproblem.

The Producer Consumer Bounded Buffer Problem

30.2 The Producer/Consumer (Bounded Buffer) Problem

The next synchronization problem we will confront in this chapter is known as theproducer/consumerproblem, or sometimes as thebounded bufferproblem, 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 generate data items and place them in a buffer; consumers grab said items from the buffer and 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 program into another, e.g.,grep foo file.txt | wc -l. This example runs two processes concurrently;grepwrites lines fromfile.txtwith the string fooin them to what it thinks is standard output; the UNIX shell redirects the output to what is called a UNIXpipe (created by the pipesystem call). The other end of this pipe is connected to the standard input of the processwc, which simply counts the number of lines in the input stream and prints out the result. Thus, thegrepprocess is the producer; thewcprocess is the consumer; between them is an in-kernel bounded buffer; you, in this example, are just the happy user.

int count = 0; // initially, empty
void put(int value) {
assert(count == 0);
count = 1;
buffer = value;
}
int get() {
assert(count == 1);
count = 0;
return buffer;
}

Figure 30.4:The Put And Get Routines (Version 1)

void *producer(void *arg) {
int i;
int loops = (int) arg;
for (i = 0; i < loops; i++) {
put(i);
}
}
void *consumer(void *arg) {
int i;
while (1) {
int tmp = get();
printf("%d\n", tmp);
}
}

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, lest1 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? Theput()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 settingcountto 1. Theget()routine does the opposite, setting the buffer to empty (i.e., setting countto 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 1This is where we drop some serious Old English on you, and the subjunctive form.

void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex); // p1
if (count == 1) // p2
Pthread_cond_wait(&cond, &mutex); // p3
put(i); // p4
Pthread_cond_signal(&cond); // p5
Pthread_mutex_unlock(&mutex); // p6
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex); // c1
if (count == 0) // c2
Pthread_cond_wait(&cond, &mutex); // c3
int tmp = get(); // c4
Pthread_cond_signal(&cond); // c5
Pthread_mutex_unlock(&mutex); // c6
printf("%d\n", tmp);
}
}

Figure 30.6:Producer/Consumer: Single CV And If Statement this should be obvious: only put data into the buffer whencountis zero (i.e., when the buffer is empty), and only get data from the buffer when countis 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 producerthreads, and the other set which we'll call consumerthreads. Figure 30.5 shows the code for a producer that puts an integer into the shared bufferloopsnumber 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.

A Broken Solution

Now imagine that we have just a single producer and a single consumer.

Obviously theput()andget()routines have critical sections within them, asput()updates the buffer, andget()reads from it. However, putting a lock around the code doesn't work; we need something more.

Not surprisingly, that something more is some condition variables. In this (broken) first try (Figure 30.6), we have a single condition variablecond and associated lockmutex.

c2 Running Ready Ready c3 Sleep Ready Ready 0 Nothing to get

Sleep Ready p1 Running 0

Sleep Ready p2 Running 0

Sleep Ready p4 Running 1 Buffer now full

Ready Ready p5 Running 1 Tc1awoken

Ready Ready p6 Running 1

Ready Ready p1 Running 1

Ready Ready p2 Running 1

Ready Ready p3 Sleep 1 Buffer full; sleep

Ready c1 Running Sleep 1 Tc2sneaks in ...

Ready c2 Running Sleep 1

Ready c4 Running Sleep 0 ... and grabs data

Ready c5 Running Ready 0 Tpawoken

Ready c6 Running Ready 0 c4 Running Ready Ready 0 Oh oh! No data

Figure 30.7:Thread Trace: Broken Solution (Version 1)

Let's examine the signaling logic between producers and consumers.

When a producer wants to fill the buffer, it waits for it to be empty (p1p3). The consumer has the exact same logic, but waits for a different condition: fullness (c1-c3).

With just a single producer and a single consumer, the code in Figure 30.6 works. However, if we have more than one of these threads (e.g., two consumers), the solution has two critical problems. What are they?

... (pause here to think) ...

Let's understand the first problem, which has to do with theifstatement before the wait. Assume there are two consumers (Tc1andTc2) and one producer (Tp). First, a consumer (Tc1) runs; it acquires the lock (c1), checks if any buffers are ready for consumption (c2), and finding that none are, waits (c3) (which releases the lock).

Then the producer (Tp) runs. It acquires the lock (p1), checks if all buffers are full (p2), and finding that not to be the case, goes ahead and fills the buffer (p4). The producer then signals that a buffer has been filled (p5). Critically, this moves the first consumer (Tc1) from sleeping on a condition variable to the ready queue; Tc1 is now able to run (but not yet running). The producer then continues until realizing the buffer is full, at which point it sleeps (p6, p1-p3).

Here is where the problem occurs: another consumer (Tc2) sneaks in and consumes the one existing value in the buffer (c1, c2, c4, c5, c6, skipping the wait at c3 because the buffer is full). Now assumeTc1runs; just before returning from the wait, it re-acquires the lock and then returns. It then callsget()(c4), but there are no buffers to consume! An assertion triggers, and the code has not functioned as desired. Clearly, we should have somehow preventedTc1from trying to consume becauseTc2snuck in and consumed the one value in the buffer that had been produced. Figure 30.7 shows the action each thread takes, as well as its scheduler state (Ready, Running, or Sleeping) over time.

void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex); // p1
while (count == 1) // p2
Pthread_cond_wait(&cond, &mutex); // p3
put(i); // p4
Pthread_cond_signal(&cond); // p5
Pthread_mutex_unlock(&mutex); // p6

The Producer Consumer Bounded Buffer Problem Part 2

30.2 The Producer/Consumer (Bounded Buffer) Problem (Part 2)

}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex); // c1
while (count == 0) // c2
Pthread_cond_wait(&cond, &mutex); // c3
int tmp = get(); // c4
Pthread_cond_signal(&cond); // c5
Pthread_mutex_unlock(&mutex); // c6
printf("%d\n", tmp);
}
}

Figure 30.8:Producer/Consumer: Single CV And While

The problem arises for a simple reason: after the producer wokeTc1, butbeforeTc1ever ran, the state of the bounded buffer changed (thanks to

Tc2). Signaling a thread only wakes them up; it is thus ahintthat the state of the world has changed (in this case, that a value has been placed in the buffer), but there is no guarantee that when the woken thread runs, the state will still be as desired. This interpretation of what a signal means is often referred to asMesa semantics, after the first research that built a condition variable in such a manner [LR80]; the contrast, referred to as

Hoare semantics, is harder to build but provides a stronger guarantee that the woken thread will run immediately upon being woken [H74].

Virtually every system ever built employs Mesa semantics.

Better, But Still Broken: While, Not If

Fortunately, this fix is easy (Figure 30.8): change theifto awhile. Think about why this works; now consumerTc1 wakes up and (with the lock held) immediately re-checks the state of the shared variable (c2). If the buffer is empty at that point, the consumer simply goes back to sleep (c3). The corollaryifis also changed to awhilein the producer (p2).

Thanks to Mesa semantics, a simple rule to remember with condition variables is toalways use while loops. Sometimes you don't have to recheck the condition, but it is always safe to do so; just do it and be happy.

c2 Running Ready Ready c3 Sleep Ready Ready 0 Nothing to get

Sleep c1 Running Ready 0

Sleep c2 Running Ready 0

Sleep c3 Sleep Ready 0 Nothing to get

Sleep Sleep p1 Running 0

Sleep Sleep p2 Running 0

Sleep Sleep p4 Running 1 Buffer now full

Ready Sleep p5 Running 1 Tc1awoken

Ready Sleep p6 Running 1

Ready Sleep p1 Running 1

Ready Sleep p2 Running 1

Ready Sleep p3 Sleep 1 Must sleep (full) c2 Running Sleep Sleep 1 Recheck condition c4 Running Sleep Sleep 0 Tc1grabs data c5 Running Ready Sleep 0 Oops! Woke Tc2 c6 Running Ready Sleep 0 c1 Running Ready Sleep 0 c2 Running Ready Sleep 0 c3 Sleep Ready Sleep 0 Nothing to get

Sleep c2 Running Sleep 0

Sleep c3 Sleep Sleep 0 Everyone asleep...

Figure 30.9:Thread Trace: Broken Solution (Version 2)

However, this code still has a bug, the second of two problems mentioned above. Can you see it? It has something to do with the fact that there is only one condition variable. Try to figure out what the problem is, before reading ahead. DO IT!

... (another pause for you to think, or close your eyes for a bit) ...

Let's confirm you figured it out correctly, or perhaps let's confirm that you are now awake and reading this part of the book. The problem occurs when two consumers run first (Tc1 andTc2), and both go to sleep (c3). Then, a producer runs, put a value in the buffer, wakes one of the consumers (sayTc1), and goes back to sleep. Now we have one consumer ready to run (Tc1), and two threads sleeping on a condition (Tc2andTp).

And we are about to cause a problem to occur: things are getting exciting!

The consumerTc1then wakes by returning fromwait()(c3), re-checks the condition (c2), and finding the buffer full, consumes the value (c4).

This consumer then, critically, signals on the condition (c5), waking one thread that is sleeping. However, which thread should it wake?

Because the consumer has emptied the buffer, it clearly should wake the producer. However, if it wakes the consumerTc2(which is definitely possible, depending on how the wait queue is managed), we have a problem. Specifically, the consumer Tc2 will wake up and find the buffer empty (c2), and go back to sleep (c3). The producerTp, which has a value to put into the buffer, is left sleeping. The other consumer thread, Tc1, also goes back to sleep. All three threads are left sleeping, a clear bug; see

Figure 30.9 for the brutal step-by-step of this terrible calamity.

Signaling is clearly needed, but must be more directed. A consumer should not wake other consumers, only producers, and vice-versa.

void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex);
while (count == 1)
Pthread_cond_wait(&empty, &mutex);
put(i);
Pthread_cond_signal(&fill);
Pthread_mutex_unlock(&mutex);
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex);
while (count == 0)
Pthread_cond_wait(&fill, &mutex);
int tmp = get();
Pthread_cond_signal(&empty);
Pthread_mutex_unlock(&mutex);
printf("%d\n", tmp);
}
}

Figure 30.10:Producer/Consumer: Two CVs And While

The Single Buffer Producer/Consumer Solution

The solution here is once again a small one: usetwocondition variables, instead of one, in order to properly signal which type of thread should wake up when the state of the system changes. Figure 30.10 shows the resulting code.

In the code above, producer threads wait on the conditionempty, and signalsfill. Conversely, consumer threads wait onfill and signalempty.

By doing so, the second problem above is avoided by design: a consumer can never accidentally wake a consumer, and a producer can never accidentally wake a producer.

The Final Producer/Consumer Solution

We now have a working producer/consumer solution, albeit not a fully general one. The last change we make is to enable more concurrency and efficiency; specifically, we add more buffer slots, so that multiple values can be produced before sleeping, and similarly multiple values can be consumed before sleeping. With just a single producer and consumer, this approach is more efficient as it reduces context switches; with multiple producers or consumers (or both), it even allows concurrent producing or consuming to take place, thus increasing concurrency. Fortunately, it is a small change from our current solution.

int fill_ptr = 0;
int use_ptr = 0;
int count = 0;
void put(int value) {
buffer[fill_ptr] = value;
fill_ptr = (fill_ptr + 1) % MAX;

9 count++;

}
int get() {
int tmp = buffer[use_ptr];
use_ptr = (use_ptr + 1) % MAX;

15 count--; 16 return tmp;

Figure 30.11:The Final Put And Get Routines 1 cond_t empty, fill; 2 mutex_t mutex; 3

void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex); // p1
while (count == MAX) // p2
Pthread_cond_wait(&empty, &mutex); // p3
put(i); // p4
Pthread_cond_signal(&fill); // p5
Pthread_mutex_unlock(&mutex); // p6
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex); // c1
while (count == 0) // c2
Pthread_cond_wait(&fill, &mutex); // c3
int tmp = get(); // c4
Pthread_cond_signal(&empty); // c5
Pthread_mutex_unlock(&mutex); // c6
printf("%d\n", tmp);
}
}

Figure 30.12:The Final Working Solution

The first change for this final solution is within the buffer structure itself and the correspondingput()andget()(Figure 30.11). We also slightly change the conditions that producers and consumers check in order to determine whether to sleep or not. Figure 30.12 shows the final waiting and signaling logic. A producer only sleeps if all buffers are currently filled (p2); similarly, a consumer only sleeps if all buffers are currently empty (c2). And thus we solve the producer/consumer problem.

TIP: USEWHILE(NOTIF) FORCONDITIONS

When checking for a condition in a multi-threaded program, using awhileloop is always correct; using an ifstatement only might be, depending on the semantics of signaling. Thus, always usewhileand your code will behave as expected.

Using while loops around conditional checks also handles the case wherespurious wakeupsoccur. In some thread packages, due to details of the implementation, it is possible that two threads get woken up though just a single signal has taken place [L11]. Spurious wakeups are further reason to re-check the condition a thread is waiting on.

Learning objectives​

Prerequisites​

Module targets​

AI companion modes​

Source-of-truth note​

External enrichment​

Source provenance​

Merged source​

Definition And Routines​