Locks

Locks are a simple concept that will become the building blocks for almost all your multithreaded programs. The idea of a lock is simple; only one thread can obtain a lock, and must release it when done. If another thread tries to obtain the lock which has already been obtained by another thread, it will wait until the thread releases the lock before obtaining it for itself and continuing.

You can use locks to create "mutual exclusion zones" -- areas of your code that only one thread will execute at a time. This removes the problem of multiple threads corrupting the shared data with unpredictable interleaving execution.

Below is the queue example modified so as to avoid interleaving problems.

class BlockingQueue {
      final Lock lock = new ReentrantLock();
      List< Integer > queue;

      public void Enqueue( Integer n ) {
             lock.lock(); // obtain the lock
             queue.add( n );
             lock.unlock(); // release the lock
      }

      public Integer Dequeue() {
             Integer result = null;
             while (result == null) {
                lock.lock();
                if (queue.size() > 0) {
                   result = queue.remove(0);
                }
                lock.unlock();
             }
             return result;
      }
}

The new variable "lock" has been introduced. "lock.lock()" means that the thread will try and obtain the lock and then release it with "lock.unlock()". If another thread tries to obtain a taken lock variable, it will wait until it is released. Only one thread can perform the size check and removal at once, so the problem of interleaving threads is removed. Notice I did not just turn the whole dequeue method into a mutual exclusion zone, this is because once the thread enters the loop, it would never release the lock to allow another thread to add something to the queue, hence causing an infinite loop and what's called a "deadlock" in threading jargon.

Condition Variables

Although it's safe for multiple threads to add and remove from the queue, there remains a performance issue. When a thread is removing from the queue, it will continually check the queue size, wasting precious CPU cycles. Ideally we want the thread to go to "sleep" until there is something to be taken from the queue, this is what condition variables are used to achieve.

Imagine Helen is waiting for Anthony to buy food and put it in the fridge. She goes to the fridge and opens it only to see there is nothing to eat. Now she can either stand at the fridge opening and closing it until Anthony manages to put food into it in between her checks, or she can go sleep on the couch and wait for Anthony to wake her up after he has put food into the fridge. Here Helen and Anthony are threads, and the couch is a condition variable which Helen sleeps on until Anthony signals her.

Using conditional variables, threads can be told to sleep until another thread signals it to wake up. Each condition variable is associated with a lock, when a thread is told to wait on a conditional variable, the associated lock is released, when the thread is signalled to wake up, the lock is obtained. You will very often use condition variables and locks in the following pattern:

foo() {
      lock.lock;
      while (condition is not true) {
         lock.conditional.wait()
      }
      do something;
      lock.unlock;
}

bar() {
      lock.lock
      modify state;
      lock.conditional.signal();
      lock.unlock;
}

Here threads will check a condition in foo() before performing some act, if the condition isn't true, it waits until signalled and then checks again. While the thread is waiting, it releases the lock such that another modifying thread can obtain it in bar() to modify the state. After the state is modified in bar(), the modifying thread signals the condition variable to notify a waiting thread that the state has changed. The waiting thread will then wake up, re-obtain the lock and perform the condition check again.

I have modified the queue example to use condition variables, such that the dequeue method does not waste CPU cycles in an infinite loop checking the queue size.

class BlockingQueue {
    final Lock lock = new ReentrantLock();
    final Condition cond  = lock.newCondition();

    List< Integer > queue;

    public void Enqueue( Integer n ) {
           lock.lock();
           queue.add(n);
           cond.signal();  // wake up a waiting thread
           lock.unlock();
    }

    public Integer Dequeue() {
           Integer result = null;
           lock.lock();
           while (queue.size() == 0) {
                 try { wait(); } // wait until signalled
                 catch (InterruptedException e) { }
           }
           result = queue.remove(0);
           lock.unlock();
           return result;
    }
}

Monitors

Monitors are a nice way of encapsulating the functionality of locks and condition variables into standard class design. A monitor is a class with an inbuilt lock and condition variable, when a method is called on the class, the lock is obtained and then released when the method returns. What this means is that no two threads can call a method on the same object at once, protecting its inner logic from race conditions and data corruption.

However, there are times when inside a monitor method, you want to wait for a certain state condition. Using our original infinite loop method would cause a dead lock, as the monitor's lock would remain acquired until the thread finishes the infinite loop, not allowing any other thread to access the monitor's methods to modify its state. To get around this, monitors also provide the functionality of a conditional variable.

Monitors in Java are simply created by adding the synchronised keyword before the declaration of the method that you wish to be a locking method. Java monitors provide protected methods to wait on and signal (notify) the monitor's condition variable. I have modified the queue example to make use of Java's monitor functionality, resulting in the most readable code yet.

class BlockingQueue {      
      List< Integer > queue;

      public synchronized void Enqueue( Integer n ) {
             queue.add(n);
             notify(); // signal a waiting thread
      }

      public synchronized Integer Dequeue() {
             while (queue.size() == 0) {
                try { wait(); } // wait until signalled
                catch (InterruptedException e) { } 
             }
             return queue.remove(0);
      }
}

So now you know the three basic tools for multithreading in languages such as Java and C/C++. For multithreaded programming in C++ using similar concepts and tools as Java, I highly recommend the boost threads library. However, multithreading is a lot more than the programming tools, the trick is learning the common patterns that occur in different applications. When designing a solution to a multithreading problem, research multithreading design patterns as nine times out of 10 you will be redesigning the wheel. In this tutorial the blocking queue is a simple implementation of the producer-consumer pattern. Another example of a pattern is the readers-writers problem that allows multiple threads access to a shared resource concurrently when only reading, but only one thread when writing.