CSC/ECE 517 Fall 2009/wiki2 14 conc patterns
Thread-Safe Programming and Concurrency Patterns
Thread-Safe Programming
In computer programming, a thread is an instance of the program running on behalf of some user or process.[1] Thread-safe describes a program portion or routine that functions correctly during simultaneous execution by multiple threads. A thread-safe piece of code can be called from multiple threads simultaneously without "clobbering" shared data or creating "race conditions".[2]
For example, suppose that an application creates several threads, each of which makes a call to the same library routine which, in turn, accesses/modifies a global structure or location in memory. As each thread calls this routine, it is possible that they may try to modify this global structure/memory location at the same time. If the routine does not employ some sort of synchronization constructs to prevent data corruption, then it is not thread-safe. This is depicted below:[2]
Consider the following method in Java:[3]
1 private Double pi = null;
2 public Double pi() {
3 if (pi == null) {
4 pi = new Double(22 / 7);
5 }
6 return pi;
7 }
This example is not thread-safe. Consider the case where pi is null and threads A and B enter the method and simultaneously execute line 4. They both test if pi is null and both tests return true. Next, consider thread A continues execution, returns the reference to the memory address that contains a object variable that contains the result of 22 divided by 7 and exits the method while thread B is suspended by the VM for some reason. When the execution of thread B continues later, a new object variable will be created on line 5 and the memory address held by the reference that has already been returned by the method will be overwritten with a new memory address. This is potentially very dangerous and could lead to nasty bugs.[3]
In order to ensure that a routine is thread-safe, one should make sure that concurrent threads use synchronized algorithms that cooperate with each other and confine the address of a shared object to one thread whenever an unsynchronized algorithm is active.[1]
Concurrency Patterns
In software engineering, a design pattern is a general reusable solution to a commonly occurring problem in software design. A design pattern is not a finished design that can be transformed directly into code. It is a description or template for how to solve a problem that can be used in many different situations. Design patterns can thus, speed up the development process by providing tested, proven development paradigms, help prevent subtle issues that can cause major problems and improve code readability for coders and architects familiar with the patterns.[4]
Developing multi-threaded applications is hard since incorrect use of locks can cause subtle and pernicious errors. Likewise, developing multi-threaded reusable components is hard since it can be time-consuming to customize components to support new, more efficient locking strategies.[7] Concurrency Patterns are design patterns that help developers avoid common problems when programming multi-threaded components and applications. The adjacent figure gives a list of concurrency design patterns that will be discussed below.
Read/Write Access Pattern
The Read/Write Access Pattern is one of the most common types of design patterns used to implement concurrency. This pattern allows concurrent read access to an object. However, it enforces exclusive write access to an object.[10]
Consider a program to implement reliability features offered by TCP/IP protocol in UDP protocol. When an acknowledgment is received from the recipient, _ack_count, a global variable counter, is incremented by one. Also, every time a UDP packet is sent from the sender, a new thread is started to monitor receipt of acknowledgment for that packet. If acknowledgment is not received, packet is retransmitted. Concurrent access to and increment of _ack_count can cause conflicts.
These can be resolved using Read/Write access mechanism. Following is the code in Java that implements this design pattern. Suppose there is a class called SpinLocks that has methods s_read_lock(), s_write_lock(), s_done().[5,6]
int _ack_count=0; //Global variable
public class Reliable_UDP {
private SpinLocks lock_manager = new SpinLocks();
public int get_increment_ack_count{
lock_manager.s_read_lock();
int _ack_count = this.Reliable_UDP;
lock_manger.s_done();
return _ack_count;
}
public int set_increment_ack_count{
lock_manager.s_write_lock();
_ack_count++;
lock_manger.s_done();
}
}
As can be observed from the above code sample, the methods of the Reliable_UDP class use a SpinLocks object to coordinate concurrent calls. They begin by calling the appropriate lock method before getting or setting values. When finished, they call the SpinLocks object's done method to release the lock. The Read/Write Lock pattern is a specialized form of the Scheduler pattern.
Double-Checked Locking Pattern
The Double-checked locking design pattern is used when an application has one or more critical sections of code that must execute sequentially; when multiple threads can potentially attempt to execute the critical section simultaneously; when the critical section is executed just once and when acquiring a lock on every access to the critical section causes excessive overhead.[8]
Many familiar design patterns such as Singleton that work well for sequential programs contain subtle assumptions that do not apply in the context of concurrency. Consider the following implementation of the Singleton pattern:[8]
class Singleton
{
public:
static Singleton *instance (void)
{
if (instance_ == 0)
// Critical section.
instance_ = new Singleton;
return instance_;
}
void method (void);
// Other methods and members omitted.
private:
static Singleton *instance_;
};
// ...
Singleton::instance ()->method ();
// ...
The above implementation does not work in the presence of preemptive multi-tasking or true parallelism. For instance, if multiple threads executing on a parallel machine invoke Singleton::instance simultaneously before it is initialized, the Singleton constructor can be called multiple times. This violates the properties of a critical section.
The Solution: Double-Checked Locking
A common way to implement a critical section is to add a static Mutex to the class which ensures that the allocation and initialization of the Singleton occurs atomically. A Guard class is used to ensure that every access to Singleton::instance will automatically acquire and release the lock as follows:[8]
class Singleton
{
public:
static Singleton *instance (void)
{
// First check
if (instance_ == 0)
{
// Ensure serialization (guard
// constructor acquires lock_).
Guard<Mutex> guard (lock_);
// Double check.
if (instance_ == 0)
instance_ = new Singleton;
}
return instance_;
// guard destructor releases lock_.
}
private:
static Mutex lock_;
static Singleton *instance_;
};
The first thread that acquires the lock will construct Singleton and assign the pointer to instance_. All threads that subsequently call instance will find instance_!= 0 and skip the initialization step. The second check prevents a race condition if multiple threads try to initialize the Singleton simultaneously. Thus, the Double-Checked Locking pattern provides advantages of minimized locking and prevention of race conditions.[8]
Thread-Specific Storage pattern
The Thread-Specific Storage pattern alleviates several problems with multi-threading performance such as the overhead of acquiring and releasing locks and programming complexity. It improves performance and simplifies multithreaded applications by allowing multiple threads to use one logically global access point to retrieve thread-specific data without incurring locking overhead for each access. This pattern should be applied to multi-threaded applications that frequently access objects that are logically global but physically specific to each thread.[9]
For instance, when an error occurs in a system call, operating systems like UNIX and Win32 use a standard variable errno to report the problem. Consider the following typical C code fragment that receives buffers from a non-blocking TCP socket:[9]
// One global errno per-process.
extern int errno;
void *worker (SOCKET socket)
{
// Read from the network connection
// and process the data until the connection
// is closed.
for (;;) {
char buffer[BUFSIZ];
int result = recv (socket, buffer, BUFSIZ, 0);
// Check to see if the recv() call failed.
if (result == -1) {
if (errno != EWOULDBLOCK)
// Record error result in thread-specific data.
printf ("recv failed, errno = %d", errno);
} else
// Perform the work on success.
process_buffer (buffer);
}
}
If recv returns -1 the code checks that errno != EWOULDBLOCK and prints an error message if this is not the case (e.g., if errno == EINTR), otherwise it processes the buffer it receives. When the “global error variable” approach shown above is used in multi-threaded systems, race conditions can cause an errno value set by a method in one thread to be interpreted erroneously by applications in other threads.[9]
Solution: Thread-Specific Storage
The Thread-specific storage pattern allows sequential methods within a thread to access thread-specific objects atomically without incurring locking overhead for each access. Also, system developers can make the use of thread-specific storage completely transparent at the source-code level via data abstraction or macros. It is also highly portable. For example, the following code illustrates how errno is defined on Solaris 2.x:[9]
// A thread-specific errno definition (typically defined in <sys/errno.h>).
#if defined (_REENTRANT)
// The _errno() function returns the
// thread-specific value of errno.
#define errno (*_errno())
#else
// Non-MT behavior is unchanged.
extern int errno;
#endif /* REENTRANT */
void *worker (SOCKET socket)
{
// Exactly the same implementation shown above.
}
When the REENTRANT flag is enabled the errno symbol is defined as a macro that invokes a helper function called errno, which returns a pointer to the thread-specific value of errno. This pointer is dereferenced by the macro so that it can appear on either the left or right side of an assignment operator.[9]
Balking Pattern
Consider the scenario when a call is made to an object's method when the object is not in a state to properly execute the method. If the method handles this situation by returning without performing its normal function, we say that the method "balked".[5]
Consider the following example in Java: There is a class AirPlane which can be operated in two modes - the autopilot mode and the normal mode. When the normal mode is active, it is desired to deactivate the autopilot mode. Also, when the air plane is in autopilot mode, any action performed manually by the pilot should be ignored. This raises some concurrency issues which can be resolved in Java as shown below:[5]
public class AirPlane{
private boolean _auto_pilot_mode = false;
public void _perform_some_action(){
synchronized(this){
if(_auto_pilot_mode){
return;
}
}
//Code to execute the action goes here
}
void _auto_pilot_mode_off() {
_auto_pilot_mode = false;
}
}
If the _perform_some_action is called while an action is in progress, the method balks. Note the use of synchronized statement in the _perform_some_action method. This ensures that if multiple calls to the _perform_some_action method occur at the same time, the result is predictable. Exactly one of the calls will proceed normally and others will balk. Also, note that _auto_pilot_mode_off method is not synchronized. This is because setting the _auto_pilot_mode variable to false never causes a problem. The _auto_pilot_mode_off method does not modify any other state information and hence, concurrent calls to the _auto_pilot_mode_off are safe.
Guarded Suspension and Single Threaded Execution design patterns provide an alternate way to handle method calls to objects that are not in an appropriate state to execute the method call.
Producer/Consumer Pattern
The Producer/Consumer design pattern can be used when the objects are produced and consumed asynchronously.[5]
Consider the example of websites that provide the "Talk to a Specialist" functionality which starts a chat session with an online representative. A number of people may attempt to initiate the chat session at any given time. There will be multiple representatives available online. If a representative is not busy when a chat session is initiated, he responds to the user. Otherwise, the user is placed in a queue. Consider the example when we have a class called User that pushes a user in Queue & class Dispatcher that pops out a user when an online representative is free to begin the chat session.
The above example can be implemented in Java using core Java API that includes the classes java.io.PipedInputStream and java.io.PipedOutputStream. Together, they implement a variant of the Producer-Consumer pattern called the Pipe pattern. This pattern includes only one Producer and Consumer object. The Pipe pattern usually refers to the Producer object as a data source and the Consumer object as a data sink.[5]
public class Specialist implements Runnable {
private Queue queue_users;
...
public Specialist(Queue queue_users){
this.queue_users = queue_users;
...
}
public void run(){
User new_user = null;
..
queue_users.push(new_user);
}
public class Dispatcher implements Runnable{
private Queue queue_users;
...
public Dispatcher(Queue queue_users){
this.queue_users = queue_users;
...
}
...
public void run(){
User new_user = queue_users.pull();
...
}
...
}
And, final "Queue" class listing.
public class Queue{
private ArrayList data = new ArrayList();
...
synchronized public void push(User new_user){
data.add(new_user)
notify();
}
...
synchronized public User pull(){
while(data.size()==0){
try {
wait();
} catch(InterruptedException e) {
}
User new_user = (User)data.get(0);
data.remove(0);
return new_user;
}
public int size(){
return data.size();
}
}
In the above example, Specialist class is a producer which produces objects that are consumed by Consumer objects asynchronously. A Producer object could produce an object when all Consumer objects are busy processing other objects. In this case, the objects are pushed in the queue which acts as a buffer for objects produced by Specialist class. The objects remain there until a Consumer object pulls them out of the queue. If the queue is empty, the Consumer object waits until the Producer adds new object to the queue. The relationship between Producer-Consumer and Queue is depicted in the diagram below:[5]
Conclusion
The concurrency patterns discussed above involve coordinating concurrent operations. They address two types of problems:[5]
Shared resources - When concurrent operations access the same data or another type of shared resource, operations may interfere with each other if they access the resource at the same time. To ensure that operations on shared resources execute correctly, the operations must be sufficiently constrained to access their shared resource one at a time. However, if the operations are overly constrained, then they may deadlock and not be able to finish executing.
Sequence of operations - If operations are constrained to access a shared resource one at a time, it may be necessary to ensure that they access the shared resource in a particular order. For example, an object cannot be removed from a data structure before it is added to the data structure.
See Also
- Monitor Object
- Active Object
- Thread pool pattern
- Reactor patter
- Double Buffering
- Scheduler
- Asynchronous Processing
References
[1] http://searchcio-midmarket.techtarget.com/sDefinition/0,,sid183_gci331590,00.html
[3] http://www.javalobby.org/articles/thread-safe/index.jsp
[4] Design Patterns: Simply by Steve Holzner
[5] Mark Grand, Patterns in Java, Volume 1, A Catalog of Reusable Design Patterns Illustrated with UML, http://www.wiley.com/legacy/compbooks/catalog/25839-3.htm
[6] http://gee.cs.oswego.edu/dl/cpj/
[7] Douglas C. Schmidt, Strategized Locking, Thread-safe Decorator, and Scoped Locking: Patterns and Idioms for Simplifying Multi-threaded C++ Components, http://www.cs.wustl.edu/~schmidt/PDF/locking-patterns.pdf
[8] Double-Checked Locking -- A Optimization Pattern for Efficiently Initializing and Accessing Thread-safe Objects. (updated October 15th, 1996).(with Tim Harrison) http://www.cs.wustl.edu/~schmidt/PDF/DC-Locking.pdf
[9] Thread-Specific Storage -- An Object Behavioral Pattern for Accessing per-Thread State Efficiently. (with Tim Harrison and Nat Pryce)http://www.cs.wustl.edu/~schmidt/PDF/TSS-pattern.pdf
[10] Paul E. McKenney, Selecting locking primitives for parallel programming, http://portal.acm.org/citation.cfm?doid=236156.236174