Atomic Operations

Atomic operations are a simple form of synchronization that work on simple data types. The advantage of atomic operations is that they do not block competing threads. For simple operations, such as incrementing a counter variable, this can lead to much better performance than taking a lock.

OS X and iOS include numerous operations to perform basic mathematical and logical operations on 32-bit and 64-bit values. Among these operations are atomic versions of the compare-and-swap, test-and-set, and test-and-clear operations. For a list of supported atomic operations, see the /usr/include/libkern/OSAtomic.h header file or see the atomic man page.

Memory Barriers and Volatile Variables

In order to achieve optimal performance, compilers often reorder assembly-level instructions to keep the instruction pipeline for the processor as full as possible. As part of this optimization, the compiler may reorder instructions that access main memory when it thinks doing so would not generate incorrect data. Unfortunately, it is not always possible for the compiler to detect all memory-dependent operations. If seemingly separate variables actually influence each other, the compiler optimizations could update those variables in the wrong order, generating potentially incorrect results.

A memory barrier is a type of nonblocking synchronization tool used to ensure that memory operations occur in the correct order. A memory barrier acts like a fence, forcing the processor to complete any load and store operations positioned in front of the barrier before it is allowed to perform load and store operations positioned after the barrier. Memory barriers are typically used to ensure that memory operations by one thread (but visible to another) always occur in an expected order. The lack of a memory barrier in such a situation might allow other threads to see seemingly impossible results. (For an example, see the Wikipedia entry for memory barriers.) To employ a memory barrier, you simply call the OSMemoryBarrier function at the appropriate point in your code.

Volatile variables apply another type of memory constraint to individual variables. The compiler often optimizes code by loading the values for variables into registers. For local variables, this is usually not a problem. If the variable is visible from another thread however, such an optimization might prevent the other thread from noticing any changes to it. Applying the volatile keyword to a variable forces the compiler to load that variable from memory each time it is used. You might declare a variable as volatile if its value could be changed at any time by an external source that the compiler may not be able to detect.

Because both memory barriers and volatile variables decrease the number of optimizations the compiler can perform, they should be used sparingly and only where needed to ensure correctness. For information about using memory barriers, see the OSMemoryBarrier man page.

Locks

Locks are one of the most commonly used synchronization tools. You can use locks to protect a critical section of your code, which is a segment of code that only one thread at a time is allowed access. For example, a critical section might manipulate a particular data structure or use some resource that supports at most one client at a time. By placing a lock around this section, you exclude other threads from making changes that might affect the correctness of your code.

Table 4-1 lists some of the locks that are commonly used by programmers. OS X and iOS provide implementations for most of these lock types, but not all of them. For unsupported lock types, the description column explains the reasons why those locks are not implemented directly on the platform.

For information on how to use locks, see Using Locks.

Conditions

A condition is another type of semaphore that allows threads to signal each other when a certain condition is true. Conditions are typically used to indicate the availability of a resource or to ensure that tasks are performed in a specific order. When a thread tests a condition, it blocks unless that condition is already true. It remains blocked until some other thread explicitly changes and signals the condition. The difference between a condition and a mutex lock is that multiple threads may be permitted access to the condition at the same time. The condition is more of a gatekeeper that lets different threads through the gate depending on some specified criteria.

One way you might use a condition is to manage a pool of pending events. The event queue would use a condition variable to signal waiting threads when there were events in the queue. If one event arrives, the queue would signal the condition appropriately. If a thread were already waiting, it would be woken up whereupon it would pull the event from the queue and process it. If two events came in to the queue at roughly the same time, the queue would signal the condition twice to wake up two threads.

The system provides support for conditions in several different technologies. The correct implementation of conditions requires careful coding, however, so you should look at the examples in Using Conditions before using them in your own code.

Perform Selector Routines

Cocoa applications have a convenient way of delivering messages in a synchronized manner to a single thread. The NSObject class declares methods for performing a selector on one of the application’s active threads. These methods let your threads deliver messages asynchronously with the guarantee that they will be performed synchronously by the target thread. For example, you might use perform selector messages to deliver results from a distributed computation to your application’s main thread or to a designated coordinator thread. Each request to perform a selector is queued on the target thread’s run loop and the requests are then processed sequentially in the order in which they were received.

For a summary of perform selector routines and more information about how to use them, see Cocoa Perform Selector Sources.

Avoid Synchronization Altogether

For any new projects you work on, and even for existing projects, designing your code and data structures to avoid the need for synchronization is the best possible solution. Although locks and other synchronization tools are useful, they do impact the performance of any application. And if the overall design causes high contention among specific resources, your threads could be waiting even longer.

The best way to implement concurrency is to reduce the interactions and inter-dependencies between your concurrent tasks. If each task operates on its own private data set, it does not need to protect that data using locks. Even in situations where two tasks do share a common data set, you can look at ways of partitioning that set or providing each task with its own copy. Of course, copying data sets has its costs too, so you have to weigh those costs against the costs of synchronization before making your decision.

Understand the Limits of Synchronization

Synchronization tools are effective only when they are used consistently by all threads in an application. If you create a mutex to restrict access to a specific resource, all of your threads must acquire the same mutex before trying to manipulate the resource. Failure to do so defeats the protection offered by the mutex and is a programmer error.

Be Aware of Threats to Code Correctness

When using locks and memory barriers, you should always give careful thought to their placement in your code. Even locks that seem well placed can actually lull you into a false sense of security. The following series of examples attempt to illustrate this problem by pointing out the flaws in seemingly innocuous code. The basic premise is that you have a mutable array containing a set of immutable objects. Suppose you want to invoke a method of the first object in the array. You might do so using the following code:

NSLock* arrayLock = GetArrayLock();

NSMutableArray* myArray = GetSharedArray();

id anObject;

[arrayLock lock];

anObject = [myArray objectAtIndex:0];

[arrayLock unlock];

[anObject doSomething];

Because the array is mutable, the lock around the array prevents other threads from modifying the array until you get the desired object. And because the object you retrieve is itself immutable, a lock is not needed around the call to the doSomething method.

There is a problem with the preceding example, though. What happens if you release the lock and another thread comes in and removes all objects from the array before you have a chance to execute the doSomething method? In an application without garbage collection, the object your code is holding could be released, leaving anObject pointing to an invalid memory address. To fix the problem, you might decide to simply rearrange your existing code and release the lock after your call to doSomething, as shown here:

NSLock* arrayLock = GetArrayLock();

NSMutableArray* myArray = GetSharedArray();

id anObject;

[arrayLock lock];

anObject = [myArray objectAtIndex:0];

[anObject doSomething];

[arrayLock unlock];

By moving the doSomething call inside the lock, your code guarantees that the object is still valid when the method is called. Unfortunately, if the doSomething method takes a long time to execute, this could cause your code to hold the lock for a long time, which could create a performance bottleneck.

The problem with the code is not that the critical region was poorly defined, but that the actual problem was not understood. The real problem is a memory management issue that is triggered only by the presence of other threads. Because it can be released by another thread, a better solution would be to retain anObject before releasing the lock. This solution addresses the real problem of the object being released and does so without introducing a potential performance penalty.

NSLock* arrayLock = GetArrayLock();

NSMutableArray* myArray = GetSharedArray();

id anObject;

[arrayLock lock];

anObject = [myArray objectAtIndex:0];

[anObject retain];

[arrayLock unlock];

[anObject doSomething];

[anObject release];

Although the preceding examples are very simple in nature, they do illustrate a very important point. When it comes to correctness, you have to think beyond the obvious problems. Memory management and other aspects of your design may also be affected by the presence of multiple threads, so you have to think about those problems up front. In addition, you should always assume that the compiler will do the worst possible thing when it comes to safety. This kind of awareness and vigilance should help you avoid potential problems and ensure that your code behaves correctly.

For additional examples of how to make your program thread-safe, see Thread Safety Summary.

Watch Out for Deadlocks and Livelocks

Any time a thread tries to take more than one lock at the same time, there is a potential for a deadlock to occur. A deadlock occurs when two different threads hold a lock that the other one needs and then try to acquire the lock held by the other thread. The result is that each thread blocks permanently because it can never acquire the other lock.

A livelock is similar to a deadlock and occurs when two threads compete for the same set of resources. In a livelock situation, a thread gives up its first lock in an attempt to acquire its second lock. Once it acquires the second lock, it goes back and tries to acquire the first lock again. It locks up because it spends all its time releasing one lock and trying to acquire the other lock rather than doing any real work.

The best way to avoid both deadlock and livelock situations is to take only one lock at a time. If you must acquire more than one lock at a time, you should make sure that other threads do not try to do something similar.

Use Volatile Variables Correctly

If you are already using a mutex to protect a section of code, do not automatically assume you need to use the volatile keyword to protect important variables inside that section. A mutex includes a memory barrier to ensure the proper ordering of load and store operations. Adding the volatile keyword to a variable within a critical section forces the value to be loaded from memory each time it is accessed. The combination of the two synchronization techniques may be necessary in specific cases but also leads to a significant performance penalty. If the mutex alone is enough to protect the variable, omit the volatile keyword.

It is also important that you do not use volatile variables in an attempt to avoid the use of mutexes. In general, mutexes and other synchronization mechanisms are a better way to protect the integrity of your data structures than volatile variables. The volatile keyword only ensures that a variable is loaded from memory rather than stored in a register. It does not ensure that the variable is accessed correctly by your code.

Using a POSIX Mutex Lock

POSIX mutex locks are extremely easy to use from any application. To create the mutex lock, you declare and initialize a pthread_mutex_t structure. To lock and unlock the mutex lock, you use the pthread_mutex_lock and pthread_mutex_unlock functions. Listing 4-2 shows the basic code required to initialize and use a POSIX thread mutex lock. When you are done with the lock, simply call pthread_mutex_destroy to free up the lock data structures.

Listing 4-2  Using a mutex lock

pthread_mutex_t mutex;

void MyInitFunction()

{

    pthread_mutex_init(&mutex, NULL);

}

void MyLockingFunction()

{

    pthread_mutex_lock(&mutex);

    // Do work.

    pthread_mutex_unlock(&mutex);

}

Using the NSLock Class

An NSLock object implements a basic mutex for Cocoa applications. The interface for all locks (including NSLock) is actually defined by the NSLocking protocol, which defines the lock and unlock methods. You use these methods to acquire and release the lock just as you would any mutex.

In addition to the standard locking behavior, the NSLock class adds the tryLock and lockBeforeDate: methods. The tryLock method attempts to acquire the lock but does not block if the lock is unavailable; instead, the method simply returns NO. The lockBeforeDate: method attempts to acquire the lock but unblocks the thread (and returns NO) if the lock is not acquired within the specified time limit.

The following example shows how you could use an NSLock object to coordinate the updating of a visual display, whose data is being calculated by several threads. If the thread cannot acquire the lock immediately, it simply continues its calculations until it can acquire the lock and update the display.

BOOL moreToDo = YES;

NSLock *theLock = [[NSLock alloc] init];

...

while (moreToDo) {

    /* Do another increment of calculation */

    /* until there’s no more to do. */

    if ([theLock tryLock]) {

        /* Update display used by all threads. */

        [theLock unlock];

    }

}

Using the @synchronized Directive

The @synchronized directive is a convenient way to create mutex locks on the fly in Objective-C code. The @synchronized directive does what any other mutex lock would do—it prevents different threads from acquiring the same lock at the same time. In this case, however, you do not have to create the mutex or lock object directly. Instead, you simply use any Objective-C object as a lock token, as shown in the following example:

- (void)myMethod:(id)anObj

{

    @synchronized(anObj)

    {

        // Everything between the braces is protected by the @synchronized directive.

    }

}

The object passed to the @synchronized directive is a unique identifier used to distinguish the protected block. If you execute the preceding method in two different threads, passing a different object for the anObj parameter on each thread, each would take its lock and continue processing without being blocked by the other. If you pass the same object in both cases, however, one of the threads would acquire the lock first and the other would block until the first thread completed the critical section.

As a precautionary measure, the @synchronized block implicitly adds an exception handler to the protected code. This handler automatically releases the mutex in the event that an exception is thrown. This means that in order to use the @synchronized directive, you must also enable Objective-C exception handling in your code. If you do not want the additional overhead caused by the implicit exception handler, you should consider using the lock classes.

For more information about the @synchronized directive, see The Objective-C Programming Language.

Using Other Cocoa Locks

The following sections describe the process for using several other types of Cocoa locks.

NSRecursiveLock *theLock = [[NSRecursiveLock alloc] init];

void MyRecursiveFunction(int value)

{

    [theLock lock];

    if (value != 0)

    {

        --value;

        MyRecursiveFunction(value);

    }

    [theLock unlock];

}

MyRecursiveFunction(5);

id condLock = [[NSConditionLock alloc] initWithCondition:NO_DATA];

while(true)

{

    [condLock lock];

    /* Add data to the queue. */

    [condLock unlockWithCondition:HAS_DATA];

}

while (true)

{

    [condLock lockWhenCondition:HAS_DATA];

    /* Remove data from the queue. */

    [condLock unlockWithCondition:(isEmpty ? NO_DATA : HAS_DATA)];

    // Process the data locally.

}

Using the NSCondition Class

The NSCondition class provides the same semantics as POSIX conditions, but wraps both the required lock and condition data structures in a single object. The result is an object that you can lock like a mutex and then wait on like a condition.

Listing 4-3 shows a code snippet demonstrating the sequence of events for waiting on an NSCondition object. The cocoaCondition variable contains an NSCondition object and the timeToDoWork variable is an integer that is incremented from another thread immediately prior to signaling the condition.

Listing 4-3  Using a Cocoa condition

[cocoaCondition lock];

while (timeToDoWork <= 0)

    [cocoaCondition wait];

timeToDoWork--;

// Do real work here.

[cocoaCondition unlock];

Listing 4-4 shows the code used to signal the Cocoa condition and increment the predicate variable. You should always lock the condition before signaling it.

Listing 4-4  Signaling a Cocoa condition

[cocoaCondition lock];

timeToDoWork++;

[cocoaCondition signal];

[cocoaCondition unlock];

Using POSIX Conditions

POSIX thread condition locks require the use of both a condition data structure and a mutex. Although the two lock structures are separate, the mutex lock is intimately tied to the condition structure at runtime. Threads waiting on a signal should always use the same mutex lock and condition structures together. Changing the pairing can cause errors.

Listing 4-5 shows the basic initialization and usage of a condition and predicate. After initializing both the condition and the mutex lock, the waiting thread enters a while loop using the ready_to_go variable as its predicate. Only when the predicate is set and the condition subsequently signaled does the waiting thread wake up and start doing its work.

Listing 4-5  Using a POSIX condition

pthread_mutex_t mutex;

pthread_cond_t condition;

Boolean     ready_to_go = true;

void MyCondInitFunction()

{

    pthread_mutex_init(&mutex);

    pthread_cond_init(&condition, NULL);

}

void MyWaitOnConditionFunction()

{

    // Lock the mutex.

    pthread_mutex_lock(&mutex);

    // If the predicate is already set, then the while loop is bypassed;

    // otherwise, the thread sleeps until the predicate is set.

    while(ready_to_go == false)

    {

        pthread_cond_wait(&condition, &mutex);

    }

    // Do work. (The mutex should stay locked.)

    // Reset the predicate and release the mutex.

    ready_to_go = false;

    pthread_mutex_unlock(&mutex);

}

The signaling thread is responsible both for setting the predicate and for sending the signal to the condition lock. Listing 4-6 shows the code for implementing this behavior. In this example, the condition is signaled inside of the mutex to prevent race conditions from occurring between the threads waiting on the condition.

Listing 4-6  Signaling a condition lock

void SignalThreadUsingCondition()

{

    // At this point, there should be work for the other thread to do.

    pthread_mutex_lock(&mutex);

    ready_to_go = true;

    // Signal the other thread to begin work.

    pthread_cond_signal(&condition);

    pthread_mutex_unlock(&mutex);

}