Title: COSC330/530 - Lecture 11

COSC330/530 - Parallel and Distributed Computing

Lecture 11 - Thread Synchronization

Dr. Mitchell Welch

Reading

• Chapter 11 from Advanced Programming in the UNIX environment
• Assignment 2 Description

Summary

• Conditional Variables
• Synchronization Templates
• Synchronization Examples
• Producer-Consumer Problem Resolved

Conditional Variables

• Condition variables allow you to do three things:
  1. wait, by blocking or sleeping, for a condition to come true
  2. signal, i.e. wake up, another thread that may be waiting for some condition
  3. broadcast, i.e. wake up, every thread that may be waiting for some condition

Lets take each operation in turn!

Conditional Variables

The wait function prototype is:

#include <pthread.h>
int pthread_cond_wait(pthread_cond_t  *cond, pthread_mutex_t *mutex);

• This routine causes a thread to wait for a condition variable to be signaled or broadcast.
• The mutex should be protecting some shared data upon which your predicate depends.
• Call this routine only after you have locked the mutex specified in mutex.
• This routine atomically releases the mutex and causes the calling thread to wait on the condition.
• The atomicity is important, because it means the thread cannot miss a wakeup while the mutex is unlocked.

Conditional Variables

• When the wait is satisfied as a result of some thread calling:

pthread_cond_signal

or

pthread_cond_broadcast,

the mutex is reacquired before returning to the caller.

• So the wait on the variable becomes a wait on the mutex.
• Thus signaling a thread that is waiting does not wake it up! It merely means that it is now waiting on the mutex, it is no longer waiting on the condition variable.

Conditional Variables

The signal function prototype is:

#include <pthread.h>
int pthread_cond_signal(pthread_cond_t *cond);

• This routine unblocks at least one thread waiting on the specified condition variable cond.
• Calling this routine implies that data guarded by the associated mutex has changed, so that it might be possible for one of the waiting threads to proceed.
• In general, only one will be awakened.
• If no threads are waiting on the specified condition variable, then this routine takes no action.

Conditional Variables

• The signal does not propagate to the next condition variable wait.
• This routine should be called when any thread waiting on the specified condition variable might find its predicate true, but only one thread should proceed. If more than one thread can proceed then you must use pthread_cond_broadcast.

Conditional Variables

The broadcast prototype is:

#include <pthread.h>
int pthread_cond_broadcast(pthread_cond_t  *cond);

• This routine unblocks all threads waiting on the specified condition variable.
• Calling this routine implies that data guarded by the associated mutex has changed, so that it might be possible for one or more waiting threads to proceed.
• The threads that are unblocked shall contend for the mutex according to the scheduling policy (if applicable).

Synchronization Templates

• To correctly wait on some condition to become true, you must follow the following steps:
  1. acquire the mutex (thus preventing the data on which the condition depends from being changed)
  2. test the predicate (see if action can be taken)
  3. if the predicate is true do some work and then release the mutex
  4. if the predicate is false call pthread_cond_wait and then go back to the second step when it returns.

Synchronization Templates

• This is summed up by the following template:

pthread_mutex_lock(&mutex);

while(!test_condition(...))
  pthread_cond_wait(&condvar, &mutex);

do_stuff(...);

pthread_mutex_unlock(&mutex);

Synchronization Templates

• To correctly signal or broadcast you should follow the following steps:
  1. acquire the mutex (thus preventing the data on which the condition depends from being changed by some other thread)
  2. do whatever you need to do to the data
  3. signal or broadcast on the conditional variable
  4. release the mutex

Synchronization Templates

• This is summed up by the following template:

pthread_mutex_lock(&mutex);
do_stuff(...);
pthread_cond_signal(&condvar);
pthread_mutex_unlock(&mutex);

Synchronization Examples

• Lets start with a really trivial example and imitate a join with a single spawned thread.
• Thus our main should create a thread and then wait until that thread has finished.
• Review Example01.c

Synchronization Examples

• It is important to understand why the main thread must lock the mutex before spawning the thread.
• If it didn't then it would create a race condition.
• In other words the spawned thread could signal before the main thread had gotten around to waiting.
• The signal would be lost (since it is not remembered) and thus the program could hang.
• It can get even subtler as we shall soon see.

Synchronization Examples

• OK now lets spawn some number of threads and wait until they are all finished.
• This will mean that we need to keep track of the number of times we have been woken up. Here is a first attempt: example02.c

Synchronization Examples

• There are two things wrong with this program:

  1. The threads all write to standard error, a shared resource and so this critical section needs some protection!
  2. More importantly is that signals can get lost!!! This is how:

• When a thread signals the main thread, the main thread then has to obtain the mutex.

• However in this state it is not actually waiting anymore on the condition variable.
• Suppose one of the other threads gets to the mutex first. It will then signal but that signal will get lost!! Since no one is waiting for it. Thus what will happen is that the main thread won't wake up enough times.

Synchronization Examples

• Try it for small delays, and a larger number of threads.
• It will never wake up.
• How can we solve this problem?
• To solve this we can let the threads do the counting rather than the main thread!
• example03.c

Producer-Consumer Problem Resolved

• Recall the buggy version of the producer consumer flawed_pc.c

Producer-Consumer Problem Resolved

• We keep track of two numbers:
  1. slots the number of empty (or at least usable) slots.
  2. items the number of items ready for consuming.
• Each number has an associated condition variable:
  1. slots_cond is associated with slots
  2. items_cond is associated with items
• Each condition variable has an associated mutex:
  1. slots_lock is associated with slots_cond
  2. items_lock is associated with items_cond
• The producer must wait for slots to be non-zero!
• The consumer must wait for items to be non-zero!

Producer-Consumer Problem Resolved

• The Rules of the Game
  1. A thread should not touch or look at slots without holding its mutex.
  2. A thread should not touch or look a items without holding its mutex.
  3. The consumer waits for items to be non-zero.
  4. The producer waits for slots to be non-zero.
  5. If a thread alters a variable that the other thread may be waiting on, then it must signal it after the change has been made.

Producer-Consumer Problem Resolved

• The producer should:
  • Wait until there are some empty slots then put an item, and decrement the number of slots available then increment the number of items ready for consuming then signal the consumer
• The consumer should:
  • Wait until there are some items to consume then take an item, and decrement the number of items ready for consuming then increment the number of slots available then signal the producer.

Producer-Consumer Problem Resolved

• We can now solve the producer consumer:
• good_pc.c

Questions?

Summary

• Conditional Variables
• Synchronization Templates
• Synchronization Examples
• Producer-Consumer Problem Resolved

Reading

• Chapter 11 from Advanced Programming in the UNIX environment
• Assignment 2 Description