Home > Concurrent programming > Condition variables

Condition variables

While reading excellent book about IPC by Richard Stevens, I’ve learned about “condition variables” in POSIX threads, which provide a way to send a signal from one thread to another. A similar feature present in Java. Every object can become condition variable because it has methods wait() and notify().

However, reading the book made me curious. Why condition variables are needed ? They have simple semantics: wait() blocks the thread, notify() wakes it up. But common implementation of “locks” (called “mutexes” in POSIX) have similar semantics: if lock is held, then get() will block the thread, and releasing the lock will wake up waiting thread. So, maybe all condition variables could be replaced by locks ?

To answer this question, I’ve used producer-consumer task as an example and tried to replace condition variables with locks. Here is what I got (in pseudo-code):


var data;
lock signal;
lock protector;

proc init() {get(signal);}

proc produce(arg newdata) {
  get(protector);
  data = newdata;
  release(protector);
  release(signal);
  get(signal);
}

proc consume() {
  get(signal);
  release(signal);
  get(protector);
  var localdata = data;
  release(protector);
  return localdata;
}

This code uses lock named “signal” to block consumer thread until producer will put some data. However, this code has two problems.

First problem is that the time between releasing and acqusition of “signal” lock in “produce” is very small. The threading system must start a blocked thread immediatelly then the lock is released. Otherwise a producer thread will get the “signal” lock again, and there are chances that a consumer thread will block forever. With conditional variables it is also possible that a notification will not be delivered because there are no threads waiting, but in that case locking is usually designed in a way that a consumer thread will be scheduled with very high probability.

Second problem is that this code will not work if there are several producer threads. All invocations of produce() by threads other than thread which invoked init() will block. To solve this problem, we need our lock to be special. Same as with common lock, an attempt to acquire a lock which is already held by another thread should lead to blocking. But non-owner thread should be able to release the lock.

Even if we will have this “special lock”, there is still probability that produce() procedure will block, if another producing thread will grab the lock just then it was released. But, let us think that this is a minor problem.

Let’s analyze this new type of lock. Let’s call it “s_lock” (“special lock”). Its behaviour is very similar to semaphore: release/get sequence is like “post”, and get/release sequence is like “wait”.

Another interesting idea is to try and implement s_lock using usual locks (which must be released by thread which owns them). Let’s try (in pseudo-code):


struct s_lock {bool held, lock atomic, lock blocker};

proc s_get(s_lock arg) {
  get(atomic);
  while (arg.held) {
    release(arg.atomic);
    get(arg.blocker);
  }
  arg.held = true;
  release(arg.atomic);
}

proc s_release(s_lock arg) {
  get(arg.atomic);
  arg.held = false;
  release(arg.atomic);
  release(blocker);
}

To implement semantics of s_lock, we use two locks: one for performing atomic operations on flag, and another for blocking the thread which will try to get a busy lock. It is clear that this code will not work: s_release() should work correctly if invoked by any thread, but it will unable to release “blocker” lock if it is held by another thread. This means that we need s_locks to implement s_locks! So, the only options are either to have s_locks as primitives, or to implement them using condition variables (which we are trying to replace).

So, our attempt has failed. We definetelly need two separate things: one for atomicity (lock), and another for blocking and waking up. In fact, main source of confusion is a semantics of lock. Blocking on busy is not nesessary. If get() will just immediatelly return with unsuccesfull result if lock is already held, then all concurrent programs are still possible. It will just require usage of conditional variables in some cases there they are currently don’t needed.

To summarize things up. There are two tasks in multi-threaded programming: to perform some tasks in “atomic” way, and to avoid busy waiting (spinning). Those tasks could be acomplished by separate primitives (non-blocking locks and condition variables), or by single primitive (semaphore).

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: