CSC/ECE 517 Fall 2009/wiki2 14 san

Thread-Safe Programming and Concurrency Patterns

Introduction to Thread-Safe Programming

In computer programming, thread-safe describes a program portion or routine that can be called from multiple programming threads without unwanted interaction between the threads [1]. A piece of code is thread-safe if it functions correctly during simultaneous execution by multiple threads and in particular, it must satisfy the need for multiple threads to access the same shared data, and the need for a shared piece of data to be accessed by only one thread at any given time [2].

Here's an illustration of a thread unsafe scenario. Suppose that your application creates several threads, each of which makes a call to the same library routine such that this library routine accesses/modifies a global structure or location in memory then as each thread calls this routine it is possible that they may try to modify this global structure/memory location at the same time [4].

Typical thread-unsafe scenario [4]

Two important questions arise:

• What are the consequences of running a thread-unsafe program? Thread programming errors may lead to unpredictable results like data errors possibly followed by fatal application exceptions or endless blocked threads (race-conditions and deadlocks) and these errors are especially difficult to find but easy to introduce by inexperienced programmers [3].
• How do we ensure that a particular multi-threaded code is thread safe? Some ways to unsure thread safety are that concurrent threads use synchronized algorithms that cooperate with each other and to confine the address of a shared object to one thread whenever an unasynchronized algorithm is active [1].

Here's an example of some thread safe code. In C language, local variables are dynamically allocated on the stack. Therefore, any function that does not use static data or other shared resources is trivially thread-safe, as in the following example [5]:

/* thread-safe function */
int diff(int x, int y)
{
       int delta;
       delta = y - x;
       if (delta < 0)
               delta = -delta;
       return delta;
}

Concurrency Patterns

Definitions

• Design Patterns

  In software engineering, a design pattern is a general reusable solution to a commonly occurring problem in software design and not a finished design that can be transformed directly into code [6]. It is a description or template for how to solve a problem that can be used in many different situations and typically shows relationships and interactions between classes or objects, without specifying the final application classes or objects that are involved [6].

• Concurrency Pattern

  To ensure the above discussed thread safe programming in a multi-threaded programming paradigm where the focus is on the interactions between tasks that execute in parallel, we need to design applications using design patterns called concurrency patterns [7].

Types of Concurrency Patterns

Active Object

The Active Object pattern decouples method execution from method invocation in order to simplify synchronized access to an object that resides in its own thread of control so that one or more independent threads can access data modeled as a single object [8]. This pattern is commonly used in distributed systems requiring multi-threaded servers and in client applications, such as windowing systems and network browsers which employ active objects to simplify concurrent, asynchronous network operations [8].

This pattern consists of certain important components and describes the interactions between these components [8]: The Proxy component provides interface for clients with publicly accessible methods. The Scheduler component schedules requests to decide which request will be executed next. There is another interface which defines the method request on an active object. There also exists a list of pending requests from clients along with the implementation of the active object method.

An example of the Scheduler component in Java [9]:

public class Scheduler
{
  private List act_list = new ArrayList();
  private synchronized IMethodRequest get()
  public synchronized void insert(IMethodRequest mr)
  private class Dispatcher extends Thread
}

Balking Pattern

The balking pattern only executes an action on an object when the object is in a particular state so if we are trying to access an object in a particular state which differs from the expected state, the object will "balk".

For example, in Java, an IllegalStateException might be thrown in this case [10]. To avoid such an error from occurring, the object can attempt to acquire write locks which will time out if the object is not in the right state. Also, if an object’s method is called when the object is not in an appropriate state to execute that method, have the method return without doing anything [11].

An example of the Balking pattern in Java [10]:

public class Example{
   private boolean jobInProgress = false; 
   public void job(){
       synchronized(this){
          if(jobInProgress){
              return;
          }
          jobInProgress = true;
       }
   }
}

Read/Write Lock Pattern

This pattern allows concurrent read access to an object but requires exclusive access for write operations [11]. This means that when an object is being written to, the object access will be blocked for all other read operations.

The Java module ReadWriteLock is a good example of this pattern. It maintains a pair of associated locks, one for read-only operations and one for writing so that the read lock may be held simultaneously by multiple reader threads, so long as there are no writer but the write lock is exclusive [12].

An example of the read/write locking in Java [13]:

public void setWriteLock(boolean lock) {
       if (lock) {
               rwLock.writeLock().lock();
               WaitTimerTask job = new WaitTimerTask(Thread.currentThread(),false);
               waitTimer.schedule(job, maxWait);
       } else {
               rwLock.writeLock().unlock();
               WaitTimerTask job = lockTaskStack.get().pop();
               job.cancel();
       }
}

Guarded Suspension Pattern

In this pattern, an operation on an object required not only a lock but also a condition to be met before the operation is executed [14]. So as the name suggests, the execution is "suspended" until the "guard" or condition is satisfied. Because it is blocking, the guarded suspension pattern is generally only used when the developer knows that a method call will be suspended for a finite and reasonable period of time. If a method call is suspended for too long, then the overall program will slow down or stop, waiting for the precondition to be satisfied. If the developer knows that the method call suspension will be indefinite or for an unacceptably long period, then the balking pattern may be preferred [14].

An example of an actual implementation would be a queue object with a get method that has a guard to detect when there are no items in the queue. Once the "put" method notifies the other methods (for example, a get() method), then the get() method can exit its guarded state and proceed with a call. Once the queue is empty, then the get() method will enter a guarded state once again [14].

An example of Guarded Suspension [15]:

synchronized void guardedMethod () {
   while (! precondition) { wait (); }
       ... // code requiring precondition
}

Monitor Pattern

In this pattern, an object may be used by multiple threads using mutual exclusion such that at any time only a single thread will be executing on that object [16]. This simplifies the code complexity by removing the need to parallelize the code between the multiple threads. Monitors also provide a mechanism for threads to temporarily give up exclusive access, in order to wait for some condition to be met, before regaining exclusive access and resuming their task or have a mechanism for signaling other threads that such conditions have been met [16].

As a simple example, consider a monitor for performing transactions on a bank account [16]:

monitor class Account {
 private int balance := 0
 invariant balance >= 0  
 public method boolean withdraw(int amount)
 {
   if amount < 0 then error "Amount may not be negative"
   else if balance < amount then return false
   else { balance := balance - amount ; return true }
 }
 public method deposit(int amount) {
   if amount < 0 then error "Amount may not be negative"
   else balance := balance + amount
 }
}

References

[1] http://searchcio-midmarket.techtarget.com/sDefinition/0,,sid183_gci331590,00.html
[2] http://en.wikipedia.org/wiki/Thread_safety
[3] http://www.multicoreinfo.com/2009/03/thread-safe/
[4] http://www.cdac.in/html/events/beta-test/PEEP-2008-web-page/peep-2008-handson-webpage-mode-1/pthreads-peep-2008/pthreads-peep-2008-overview.html
[5] http://publib.boulder.ibm.com/infocenter/systems/index.jsp?topic=/com.ibm.aix.genprogc/doc/genprogc/writing_reentrant_thread_safe_code.htm
[6] http://en.wikipedia.org/wiki/Design_pattern_%28computer_science%29
[7] http://en.wikipedia.org/wiki/Concurrency_pattern
[8] http://www.cs.wustl.edu/~schmidt/PDF/Act-Obj.pdf
[9] http://www.cs.uu.nl/docs/vakken/no/active_object_pattern.pdf
[10] http://en.wikipedia.org/wiki/Balking_pattern
[11] http://www.mindspring.com/~mgrand/pattern_synopses.htm
[12] http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/locks/ReadWriteLock.html
[13] http://today.java.net/pub/a/today/2007/06/28/extending-reentrantreadwritelock.html
[14] http://en.wikipedia.org/wiki/Guarded_suspension
[15] http://web.cecs.pdx.edu/~antoy/Courses/Patterns/slides/GuardedSuspension.html
[16] http://en.wikipedia.org/wiki/Monitor_%28synchronization%29