Using pthread_create and pthread_join calls, we can create concurrent tasks. These tasks work together to manipulate data and accomplish a given task. When multiple threads attempt to manipulate the same data item, the results can often be incoherent if proper care is not taken to synchronize them. Consider the following code fragment being executed by multiple threads. The variable my_cost is thread-local and best_cost is a global variable shared by all threads.

1   /* each thread tries to update variable best_cost as follows */ 
2   if (my_cost < best_cost) 
3       best_cost = my_cost; 

To understand the problem with shared data access, let us examine one execution instance of the above code fragment. Assume that there are two threads, the initial value of best_cost is 100, and the values of my_cost are 50 and 75 at threads t1 and t2, respectively. If both threads execute the condition inside the if statement concurrently, then both threads enter the then part of the statement. Depending on which thread executes first, the value of best_cost at the end could be either 50 or 75. There are two problems here: the first is the non-deterministic nature of the result; second, and more importantly, the value 75 of best_cost is inconsistent in the sense that no serialization of the two threads can possibly yield this result. This is an undesirable situation, sometimes also referred to as a race condition (so called because the result of the computation depends on the race between competing threads).

The aforementioned situation occurred because the test-and-update operation illustrated above is an atomic operation; i.e., the operation should not be broken into sub-operations. Furthermore, the code corresponds to a critical segment; i.e., a segment that must be executed by only one thread at any time. Many statements that seem atomic in higher level languages such as C may in fact be non-atomic; for example, a statement of the form global_count += 5 may comprise several assembler instructions and therefore must be handled carefully.

Threaded APIs provide support for implementing critical sections and atomic operations using mutex-locks (mutual exclusion locks). Mutex-locks have two states: locked and unlocked. At any point of time, only one thread can lock a mutex lock. A lock is an atomic operation generally associated with a piece of code that manipulates shared data. To access the shared data, a thread must first try to acquire a mutex-lock. If the mutex-lock is already locked, the process trying to acquire the lock is blocked. This is because a locked mutex-lock implies that there is another thread currently in the critical section and that no other thread must be allowed in. When a thread leaves a critical section, it must unlock the mutex-lock so that other threads can enter the critical section. All mutex-locks must be initialized to the unlocked state at the beginning of the program.

The Pthreads API provides a number of functions for handling mutex-locks. The function pthread_mutex_lock can be used to attempt a lock on a mutex-lock. The prototype of the function is:

1   int 
2   pthread_mutex_lock ( 
3       pthread_mutex_t *mutex_lock); 

A call to this function attempts a lock on the mutex-lock mutex_lock. (The data type of a mutex_lock is predefined to be pthread_mutex_t.) If the mutex-lock is already locked, the calling thread blocks; otherwise the mutex-lock is locked and the calling thread returns. A successful return from the function returns a value 0. Other values indicate error conditions such as deadlocks.

On leaving a critical section, a thread must unlock the mutex-lock associated with the section. If it does not do so, no other thread will be able to enter this section, typically resulting in a deadlock. The Pthreads function pthread_mutex_unlock is used to unlock a mutex-lock. The prototype of this function is:

1   int 
2   pthread_mutex_unlock ( 
3       pthread_mutex_t *mutex_lock); 

On calling this function, in the case of a normal mutex-lock, the lock is relinquished and one of the blocked threads is scheduled to enter the critical section. The specific thread is determined by the scheduling policy. There are other types of locks (other than normal locks), which are discussed in Section 7.6 along with the associated semantics of the function pthread_mutex_unlock. If a programmer attempts a pthread_mutex_unlock on a previously unlocked mutex or one that is locked by another thread, the effect is undefined.

We need one more function before we can start using mutex-locks, namely, a function to initialize a mutex-lock to its unlocked state. The Pthreads function for this is pthread_mutex_init. The prototype of this function is as follows:

1   int 
2   pthread_mutex_init ( 
3       pthread_mutex_t *mutex_lock, 
4       const pthread_mutexattr_t *lock_attr); 

This function initializes the mutex-lock mutex_lock to an unlocked state. The attributes of the mutex-lock are specified by lock_attr. If this argument is set to NULL, the default mutex-lock attributes are used (normal mutex-lock). Attributes objects for threads are discussed in greater detail in Section 7.6.

1   #include <pthread.h> 
2   void *find_min(void *list_ptr); 
3   pthread_mutex_t minimum_value_lock; 
4   int minimum_value, partial_list_size; 
5 
6   main() { 
7       /* declare and initialize data structures and list */ 
8       minimum_value = MIN_INT; 
9       pthread_init(); 
10      pthread_mutex_init(&minimum_value_lock, NULL); 
11 
12      /* initialize lists, list_ptr, and partial_list_size */ 
13      /* create and join threads here */ 
14  } 
15 
16  void *find_min(void *list_ptr) { 
17      int *partial_list_pointer, my_min, i; 
18      my_min = MIN_INT; 
19      partial_list_pointer = (int *) list_ptr; 
20      for (i = 0; i < partial_list_size; i++) 
21          if (partial_list_pointer[i] < my_min) 
22              my_min = partial_list_pointer[i]; 
23      /* lock the mutex associated with minimum_value and 
24      update the variable as required */ 
25      pthread_mutex_lock(&minimum_value_lock); 
26      if (my_min < minimum_value) 
27          minimum_value = my_min; 
28      /* and unlock the mutex */ 
29      pthread_mutex_unlock(&minimum_value_lock); 
30      pthread_exit(0); 
31  } 

1   pthread_mutex_t task_queue_lock; 
2   int task_available; 
3 
4   /* other shared data structures here */ 
5 
6   main() { 
7       /* declarations and initializations */ 
8       task_available = 0; 
9       pthread_init(); 
10      pthread_mutex_init(&task_queue_lock, NULL); 
11     /* create and join producer and consumer threads */ 
12  } 
13 
14  void *producer(void *producer_thread_data) { 
15      int inserted; 
16      struct task my_task; 
17      while (!done()) { 
18          inserted = 0; 
19          create_task(&my_task); 
20          while (inserted == 0) { 
21              pthread_mutex_lock(&task_queue_lock); 
22              if (task_available == 0) { 
23                  insert_into_queue(my_task); 
24                  task_available = 1; 
25                  inserted = 1; 
26              } 
27              pthread_mutex_unlock(&task_queue_lock); 
28          } 
29      } 
30  } 
31 
32  void *consumer(void *consumer_thread_data) { 
33      int extracted; 
34      struct task my_task; 
35      /* local data structure declarations */ 
36      while (!done()) { 
37          extracted = 0; 
38          while (extracted == 0) { 
39              pthread_mutex_lock(&task_queue_lock); 
40              if (task_available == 1) { 
41                  extract_from_queue(&my_task); 
42                  task_available = 0; 
43                  extracted = 1; 
44              } 
45              pthread_mutex_unlock(&task_queue_lock); 
46          } 
47          process_task(my_task); 
48      } 
49  } 

1   int 
2   pthread_mutex_trylock ( 
3       pthread_mutex_t *mutex_lock); 

1   void *find_entries(void *start_pointer) { 
2 
3       /* This is the thread function */ 
4 
5       struct database_record *next_record; 
6       int count; 
7       current_pointer = start_pointer; 
8       do { 
9           next_record = find_next_entry(current_pointer); 
10          count = output_record(next_record); 
11      } while (count < requested_number_of_records); 
12  } 
13 
14  int output_record(struct database_record *record_ptr) { 
15      int count; 
16      pthread_mutex_lock(&output_count_lock); 
17      output_count ++; 
18      count = output_count; 
19      pthread_mutex_unlock(&output_count_lock); 
20 
21      if (count <= requested_number_of_records) 
22          print_record(record_ptr); 
23      return (count); 
24  } 

1   int output_record(struct database_record *record_ptr) { 
2       int count; 
3       int lock_status; 
4       lock_status = pthread_mutex_trylock(&output_count_lock); 
5       if (lock_status == EBUSY) { 
6           insert_into_local_list(record_ptr); 
7           return(0); 
8       } 
9       else { 
10          count = output_count; 
11          output_count += number_on_local_list + 1; 
12          pthread_mutex_unlock(&output_count_lock); 
13          print_records(record_ptr, local_list, 
14                requested_number_of_records - count); 
15          return(count + number_on_local_list + 1); 
16      } 
17  } 

As we noted in the previous section, indiscriminate use of locks can result in idling overhead from blocked threads. While the function pthread_mutex_trylock alleviates this overhead, it introduces the overhead of polling for availability of locks. For example, if the producer-consumer example is rewritten using pthread_mutex_trylock instead of pthread_mutex_lock, the producer and consumer threads would have to periodically poll for availability of lock (and subsequently availability of buffer space or tasks on queue). A natural solution to this problem is to suspend the execution of the producer until space becomes available (an interrupt driven mechanism as opposed to a polled mechanism). The availability of space is signaled by the consumer thread that consumes the task. The functionality to accomplish this is provided by a condition variable.

A condition variable is a data object used for synchronizing threads. This variable allows a thread to block itself until specified data reaches a predefined state. In the producer-consumer case, the shared variable task_available must become 1 before the consumer threads can be signaled. The boolean condition task_available == 1 is referred to as a predicate. A condition variable is associated with this predicate. When the predicate becomes true, the condition variable is used to signal one or more threads waiting on the condition. A single condition variable may be associated with more than one predicate. However, this is strongly discouraged since it makes the program difficult to debug.

A condition variable always has a mutex associated with it. A thread locks this mutex and tests the predicate defined on the shared variable (in this case task_available); if the predicate is not true, the thread waits on the condition variable associated with the predicate using the function pthread_cond_wait. The prototype of this function is:

1   int pthread_cond_wait(pthread_cond_t *cond, 
2       pthread_mutex_t *mutex); 

A call to this function blocks the execution of the thread until it receives a signal from another thread or is interrupted by an OS signal. In addition to blocking the thread, the pthread_cond_wait function releases the lock on mutex. This is important because otherwise no other thread will be able to work on the shared variable task_available and the predicate would never be satisfied. When the thread is released on a signal, it waits to reacquire the lock on mutex before resuming execution. It is convenient to think of each condition variable as being associated with a queue. Threads performing a condition wait on the variable relinquish their lock and enter the queue. When the condition is signaled (using pthread_cond_signal), one of these threads in the queue is unblocked, and when the mutex becomes available, it is handed to this thread (and the thread becomes runnable).

In the context of our producer-consumer example, the producer thread produces the task and, since the lock on mutex has been relinquished (by waiting consumers), it can insert its task on the queue and set task_available to 1 after locking mutex. Since the predicate has now been satisfied, the producer must wake up one of the consumer threads by signaling it. This is done using the function pthread_cond_signal, whose prototype is as follows:

1       int pthread_cond_signal(pthread_cond_t *cond); 

The function unblocks at least one thread that is currently waiting on the condition variable cond. The producer then relinquishes its lock on mutex by explicitly calling pthread_mutex_unlock, allowing one of the blocked consumer threads to consume the task.

Before we rewrite our producer-consumer example using condition variables, we need to introduce two more function calls for initializing and destroying condition variables, pthread_cond_init and pthread_cond_destroy respectively. The prototypes of these calls are as follows:

1   int pthread_cond_init(pthread_cond_t *cond, 
2       const pthread_condattr_t *attr); 
3   int pthread_cond_destroy(pthread_cond_t *cond); 

The function pthread_cond_init initializes a condition variable (pointed to by cond) whose attributes are defined in the attribute object attr. Setting this pointer to NULL assigns default attributes for condition variables. If at some point in a program a condition variable is no longer required, it can be discarded using the function pthread_cond_destroy. These functions for manipulating condition variables enable us to rewrite our producer-consumer segment as follows:

1   pthread_cond_t cond_queue_empty, cond_queue_full; 
2   pthread_mutex_t task_queue_cond_lock; 
3   int task_available; 
4 
5   /* other data structures here */ 
6 
7   main() { 
8       /* declarations and initializations */ 
9       task_available = 0; 
10      pthread_init(); 
11      pthread_cond_init(&cond_queue_empty, NULL); 
12      pthread_cond_init(&cond_queue_full, NULL); 
13      pthread_mutex_init(&task_queue_cond_lock, NULL); 
14      /* create and join producer and consumer threads */ 
15  } 
16 
17  void *producer(void *producer_thread_data) { 
18      int inserted; 
19      while (!done()) { 
20          create_task(); 
21          pthread_mutex_lock(&task_queue_cond_lock); 
22          while (task_available == 1) 
23              pthread_cond_wait(&cond_queue_empty, 
24                  &task_queue_cond_lock); 
25          insert_into_queue(); 
26          task_available = 1; 
27          pthread_cond_signal(&cond_queue_full); 
28          pthread_mutex_unlock(&task_queue_cond_lock); 
29      } 
30  } 
31 
32  void *consumer(void *consumer_thread_data) { 
33      while (!done()) { 
34          pthread_mutex_lock(&task_queue_cond_lock); 
35          while (task_available == 0) 
36              pthread_cond_wait(&cond_queue_full, 
37                  &task_queue_cond_lock); 
38          my_task = extract_from_queue(); 
39          task_available = 0; 
40          pthread_cond_signal(&cond_queue_empty); 
41          pthread_mutex_unlock(&task_queue_cond_lock); 
42          process_task(my_task); 
43      } 
44  } 

In the above example, each task could be consumed by only one consumer thread. Therefore, we choose to signal one blocked thread at a time. In some other computations, it may be beneficial to wake all threads that are waiting on the condition variable as opposed to a single thread. This can be done using the function pthread_cond_broadcast.

1   int pthread_cond_broadcast(pthread_cond_t *cond); 

An example of this is in the producer-consumer scenario with large work queues and multiple tasks being inserted into the work queue on each insertion cycle. This is left as an exercise for the reader (Exercise 7.2). Another example of the use of pthread_cond_broadcast is in the implementation of barriers illustrated in Section 7.8.2.

It is often useful to build time-outs into condition waits. Using the function pthread_cond_timedwait, a thread can perform a wait on a condition variable until a specified time expires. At this point, the thread wakes up by itself if it does not receive a signal or a broadcast. The prototype for this function is:

1   int pthread_cond_timedwait(pthread_cond_t *cond, 
2       pthread_mutex_t *mutex, 
3       const struct timespec *abstime); 

If the absolute time abstime specified expires before a signal or broadcast is received, the function returns an error message. It also reacquires the lock on mutex when it becomes available.

The function pthread_attr_init lets us create an attributes object for threads. The prototype of this function is

1   int 
2   pthread_attr_init ( 
3       pthread_attr_t *attr); 

This function initializes the attributes object attr to the default values. Upon successful completion, the function returns a 0, otherwise it returns an error code. The attributes object may be destroyed using the function pthread_attr_destroy. The prototype of this function is:

1   int 
2   pthread_attr_destroy ( 
3       pthread_attr_t *attr); 

The call returns a 0 on successful removal of the attributes object attr. Individual properties associated with the attributes object can be changed using the following functions: pthread_attr_setdetachstate, pthread_attr_setguardsize_np, pthread_attr_setstacksize, pthread_attr_setinheritsched, pthread_attr_setschedpolicy, and pthread_attr_setschedparam. These functions can be used to set the detach state in a thread attributes object, the stack guard size, the stack size, whether scheduling policy is inherited from the creating thread, the scheduling policy (in case it is not inherited), and scheduling parameters, respectively. We refer the reader to the Pthreads manuals for a detailed description of these functions. For most parallel programs, default thread properties are generally adequate.

The Pthreads API supports three different kinds of locks. All of these locks use the same functions for locking and unlocking; however, the type of lock is determined by the lock attribute. The mutex lock used in examples thus far is called a normal mutex. This is the default type of lock. Only a single thread is allowed to lock a normal mutex once at any point in time. If a thread with a lock attempts to lock it again, the second locking call results in a deadlock.

Consider the following example of a thread searching for an element in a binary tree. To ensure that other threads are not changing the tree during the search process, the thread locks the tree with a single mutex tree_lock. The search function is as follows:

1   search_tree(void *tree_ptr) 
2   { 
3       struct node *node_pointer; 
4       node_pointer = (struct node *) tree_ptr; 
5       pthread_mutex_lock(&tree_lock); 
6       if (is_search_node(node_pointer) == 1) { 
7           /* solution is found here */ 
8           print_node(node_pointer); 
9           pthread_mutex_unlock(&tree_lock); 
10          return(1); 
11      } 
12      else { 
13          if (tree_ptr -> left != NULL) 
14              search_tree((void *) tree_ptr -> left); 
15          if (tree_ptr -> right != NULL) 
16              search_tree((void *) tree_ptr -> right); 
17      } 
18      printf("Search unsuccessful
"); 
19      pthread_mutex_unlock(&tree_lock); 
20  } 

If tree_lock is a normal mutex, the first recursive call to the function search_tree ends in a deadlock since a thread attempts to lock a mutex that it holds a lock on. For addressing such situations, the Pthreads API supports a recursive mutex. A recursive mutex allows a single thread to lock a mutex multiple times. Each time a thread locks the mutex, a lock counter is incremented. Each unlock decrements the counter. For any other thread to be able to successfully lock a recursive mutex, the lock counter must be zero (i.e., each lock by another thread must have a corresponding unlock). A recursive mutex is useful when a thread function needs to call itself recursively.

In addition to normal and recursive mutexes, a third kind of mutex called an errorcheck mutex is also supported. The operation of an errorcheck mutex is similar to a normal mutex in that a thread can lock a mutex only once. However, unlike a normal mutex, when a thread attempts a lock on a mutex it has already locked, instead of deadlocking it returns an error. Therefore, an errorcheck mutex is more useful for debugging purposes.

The type of mutex can be specified using a mutex attribute object. To create and initialize a mutex attribute object to default values, Pthreads provides the function pthread_mutexattr_init. The prototype of the function is:

1   int 
2   pthread_mutexattr_init ( 
3       pthread_mutexattr_t   *attr); 

This creates and initializes a mutex attributes object attr. The default type of mutex is a normal mutex. Pthreads provides the function pthread_mutexattr_settype_np for setting the type of mutex specified by the mutex attributes object. The prototype for this function is:

1   int 
2   pthread_mutexattr_settype_np ( 
3       pthread_mutexattr_t   *attr, 
4       int type); 

Here, type specifies the type of the mutex and can take one of the following values corresponding to the three mutex types – normal, recursive, or errorcheck:

A mutex-attributes object can be destroyed using the pthread_attr_destroy that takes the mutex attributes object attr as its only argument.

In many applications, a data structure is read frequently but written infrequently. For such scenarios, it is useful to note that multiple reads can proceed without any coherence problems. However, writes must be serialized. This points to an alternate structure called a read-write lock. A thread reading a shared data item acquires a read lock on the variable. A read lock is granted when there are other threads that may already have read locks. If there is a write lock on the data (or if there are queued write locks), the thread performs a condition wait. Similarly, if there are multiple threads requesting a write lock, they must perform a condition wait. Using this principle, we design functions for read locks mylib_rwlock_rlock, write locks mylib_rwlock_wlock, and unlocking mylib_rwlock_unlock.

The read-write locks illustrated are based on a data structure called mylib_rwlock_t. This structure maintains a count of the number of readers, the writer (a 0/1 integer specifying whether a writer is present), a condition variable readers_proceed that is signaled when readers can proceed, a condition variable writer_proceed that is signaled when one of the writers can proceed, a count pending_writers of pending writers, and a mutex read_write_lock associated with the shared data structure. The function mylib_rwlock_init is used to initialize various components of this data structure.

The function mylib rwlock rlock attempts a read lock on the data structure. It checks to see if there is a write lock or pending writers. If so, it performs a condition wait on the condition variable readers proceed, otherwise it increments the count of readers and proceeds to grant a read lock. The function mylib_rwlock_wlock attempts a write lock on the data structure. It checks to see if there are readers or writers; if so, it increments the count of pending writers and performs a condition wait on the condition variable writer_proceed. If there are no readers or writer, it grants a write lock and proceeds.

The function mylib_rwlock_unlock unlocks a read or write lock. It checks to see if there is a write lock, and if so, it unlocks the data structure by setting the writer field to 0. If there are readers, it decrements the number of readers readers. If there are no readers left and there are pending writers, it signals one of the writers to proceed (by signaling writer_proceed). If there are no pending writers but there are pending readers, it signals all the reader threads to proceed. The code for initializing and locking/unlocking is as follows:

1   typedef struct { 
2       int readers; 
3       int writer; 
4       pthread_cond_t readers_proceed; 
5       pthread_cond_t writer_proceed; 
6       int pending_writers; 
7       pthread_mutex_t read_write_lock; 
8   } mylib_rwlock_t; 
9 
10 
11  void mylib_rwlock_init (mylib_rwlock_t *l) { 
12     l -> readers = l -> writer = l -> pending_writers = 0; 
13     pthread_mutex_init(&(l -> read_write_lock), NULL); 
14     pthread_cond_init(&(l -> readers_proceed), NULL); 
15     pthread_cond_init(&(l -> writer_proceed), NULL); 
16  } 
17 
18  void mylib_rwlock_rlock(mylib_rwlock_t *l) { 
19     /* if there is a write lock or pending writers, perform condition 
20     wait.. else increment count of readers and grant read lock */ 
21 
22     pthread_mutex_lock(&(l -> read_write_lock)); 
23     while ((l -> pending_writers > 0) || (l -> writer > 0)) 
24         pthread_cond_wait(&(l -> readers_proceed), 
25            &(l -> read_write_lock)); 
26     l -> readers ++; 
27     pthread_mutex_unlock(&(l -> read_write_lock)); 
28  } 
29 
30 
31  void mylib_rwlock_wlock(mylib_rwlock_t *l) { 
32     /* if there are readers or writers, increment pending writers 
33     count and wait. On being woken, decrement pending writers 
34     count and increment writer count */ 
35 
36     pthread_mutex_lock(&(l -> read_write_lock)); 
37     while ((l -> writer > 0) || (l -> readers > 0)) { 
38         l -> pending_writers ++; 
39         pthread_cond_wait(&(l -> writer_proceed), 
40            &(l -> read_write_lock)); 
41     } 
42     l -> pending_writers --; 
43     l -> writer ++ 
44     pthread_mutex_unlock(&(l -> read_write_lock)); 
45  } 
46 
47 
48  void mylib_rwlock_unlock(mylib_rwlock_t *l) { 
49     /* if there is a write lock then unlock, else if there are 
50     read locks, decrement count of read locks. If the count 
51     is 0 and there is a pending writer, let it through, else 
52     if there are pending readers, let them all go through */ 
53 
54     pthread_mutex_lock(&(l -> read_write_lock)); 
55     if (l -> writer > 0) 
56        l -> writer = 0; 
57     else if (l -> readers > 0) 
58        l -> readers --; 
59     pthread_mutex_unlock(&(l -> read_write_lock)); 
60     if ((l -> readers == 0) && (l -> pending_writers > 0)) 
61        pthread_cond_signal(&(l -> writer_proceed)); 
62     else if (l -> readers > 0) 
63        pthread_cond_broadcast(&(l -> readers_proceed)); 
64  } 

We now illustrate the use of read-write locks with some examples.

1   void *find_min_rw(void *list_ptr) { 
2       int *partial_list_pointer, my_min, i; 
3       my_min = MIN_INT; 
4       partial_list_pointer = (int *) list_ptr; 
5       for (i = 0; i < partial_list_size; i++) 
6           if (partial_list_pointer[i] < my_min) 
7               my_min = partial_list_pointer[i]; 
8       /* lock the mutex associated with minimum_value and 
9       update the variable as required */ 
10      mylib_rwlock_rlock(&read_write_lock); 
11      if (my_min < minimum_value) { 
12          mylib_rwlock_unlock(&read_write_lock); 
13          mylib_rwlock_wlock(&read_write_lock); 
14          minimum_value = my_min; 
15      } 
16      /* and unlock the mutex */ 
17      mylib_rwlock_unlock(&read_write_lock); 
18      pthread_exit(0); 
19  } 

1   manipulate_hash_table(int entry) { 
2       int table_index, found; 
3       struct list_entry *node, *new_node; 
4 
5       table_index = hash(entry); 
6       pthread_mutex_lock(&hash_table[table_index].list_lock); 
7       found = 0; 
8       node = hash_table[table_index].next; 
9       while ((node != NULL) && (!found)) { 
10          if (node -> value == entry) 
11              found = 1; 
12          else 
13              node = node -> next; 
14      } 
15      pthread_mutex_unlock(&hash_table[table_index].list_lock); 
16      if (found) 
17          return(1); 
18      else 
19          insert_into_hash_table(entry); 
20  } 

1   manipulate_hash_table(int entry) 
2   { 
3       int table_index, found; 
4       struct list_entry *node, *new_node; 
5 
6       table_index = hash(entry); 
7       mylib_rwlock_rlock(&hash_table[table_index].list_lock); 
8       found = 0; 
9       node = hash_table[table_index].next; 
10      while ((node != NULL) && (!found)) { 
11          if (node -> value == entry) 
12              found = 1; 
13          else 
14              node = node -> next; 
15      } 
16      mylib_rwlock_rlock(&hash_table[table_index].list_lock); 
17      if (found) 
18          return(1); 
19      else 
20          insert_into_hash_table(entry); 
21  } 

It is important to identify situations where read-write locks offer advantages over normal locks. Since read-write locks offer no advantage over normal mutexes for writes, they are beneficial only when there are a significant number of read operations. Furthermore, as the critical section becomes larger, read-write locks offer more advantages. This is because the serialization overhead paid by normal mutexes is higher. Finally, since read-write locks rely on condition variables, the underlying thread system must provide fast condition wait, signal, and broadcast functions. It is possible to do a simple analysis to understand the relative merits of read-write locks (Exercise 7.7).

An important and often used construct in threaded (as well as other parallel) programs is a barrier. A barrier call is used to hold a thread until all other threads participating in the barrier have reached the barrier. Barriers can be implemented using a counter, a mutex and a condition variable. (They can also be implemented simply using mutexes; however, such implementations suffer from the overhead of busy-wait.) A single integer is used to keep track of the number of threads that have reached the barrier. If the count is less than the total number of threads, the threads execute a condition wait. The last thread entering (and setting the count to the number of threads) wakes up all the threads using a condition broadcast. The code for accomplishing this is as follows:

1   typedef struct { 
2       pthread_mutex_t count_lock; 
3       pthread_cond_t ok_to_proceed; 
4       int count; 
5   } mylib_barrier_t; 
6 
7   void mylib_init_barrier(mylib_barrier_t *b) { 
8       b -> count = 0; 
9       pthread_mutex_init(&(b -> count_lock), NULL); 
10      pthread_cond_init(&(b -> ok_to_proceed), NULL); 
11  } 
12 
13  void mylib_barrier (mylib_barrier_t *b, int num_threads) { 
14      pthread_mutex_lock(&(b -> count_lock)); 
15      b -> count ++; 
16      if (b -> count == num_threads) { 
17          b -> count = 0; 
18          pthread_cond_broadcast(&(b -> ok_to_proceed)); 
19      } 
20      else 
21          while (pthread_cond_wait(&(b -> ok_to_proceed), 
22              &(b -> count_lock)) != 0); 
23      pthread_mutex_unlock(&(b -> count_lock)); 
24  } 

In the above implementation of a barrier, threads enter the barrier and stay until the broadcast signal releases them. The threads are released one by one since the mutex count_lock is passed among them one after the other. The trivial lower bound on execution time of this function is therefore O (n) for n threads. This implementation of a barrier can be speeded up using multiple barrier variables.

Let us consider an alternate barrier implementation in which there are n/2 condition variable-mutex pairs for implementing a barrier for n threads. The barrier works as follows: at the first level, threads are paired up and each pair of threads shares a single condition variable-mutex pair. A designated member of the pair waits for both threads to arrive at the pairwise barrier. Once this happens, all the designated members are organized into pairs, and this process continues until there is only one thread. At this point, we know that all threads have reached the barrier point. We must release all threads at this point. However, releasing them requires signaling all n/2 condition variables. We use the same hierarchical strategy for doing this. The designated thread in a pair signals the respective condition variables.

1   typedef struct barrier_node { 
2       pthread_mutex_t count_lock; 
3       pthread_cond_t ok_to_proceed_up; 
4       pthread_cond_t ok_to_proceed_down; 
5       int count; 
6   } mylib_barrier_t_internal; 
7 
8   typedef struct barrier_node mylog_logbarrier_t[MAX_THREADS]; 
9   pthread_t p_threads[MAX_THREADS]; 
10  pthread_attr_t attr; 
11 
12  void mylib_init_barrier(mylog_logbarrier_t b) { 
13      int i; 
14      for (i = 0; i < MAX_THREADS; i++) { 
15          b[i].count = 0; 
16          pthread_mutex_init(&(b[i].count_lock), NULL); 
17          pthread_cond_init(&(b[i].ok_to_proceed_up), NULL); 
18          pthread_cond_init(&(b[i].ok_to_proceed_down), NULL); 
19      } 
20  } 
21 
22  void mylib_logbarrier (mylog_logbarrier_t b, int num_threads, 
23             int thread_id) { 
24      int i, base, index; 
25      i=2; 
26      base = 0; 
27 
28      do { 
29          index = base + thread_id / i; 
30          if (thread_id % i == 0) { 
31              pthread_mutex_lock(&(b[index].count_lock)); 
32              b[index].count ++; 
33              while (b[index].count < 2) 
34                  pthread_cond_wait(&(b[index].ok_to_proceed_up), 
35                      &(b[index].count_lock)); 
36                  pthread_mutex_unlock(&(b[index].count_lock)); 
37              } 
38              else { 
39                  pthread_mutex_lock(&(b[index].count_lock)); 
40                  b[index].count ++; 
41                  if (b[index].count == 2) 
42                      pthread_cond_signal(&(b[index].ok_to_proceed_up)); 
43                  while (pthread_cond_wait(&(b[index].ok_to_proceed_down), 
44                      &(b[index].count_lock)) != 0); 
45                  pthread_mutex_unlock(&(b[index].count_lock)); 
46                  break; 
47              } 
48              base = base + num_threads/i; 
49              i=i*2; 
50      } while (i <= num_threads); 
51      i=i/2; 
52      for (; i > 1; i = i / 2) { 
53          base = base - num_threads/i; 
54          index = base + thread_id / i; 
55          pthread_mutex_lock(&(b[index].count_lock)); 
56          b[index].count = 0; 
57          pthread_cond_signal(&(b[index].ok_to_proceed_down)); 
58          pthread_mutex_unlock(&(b[index].count_lock)); 
59      } 
60  } 

In this implementation of a barrier, we visualize the barrier as a binary tree. Threads arrive at the leaf nodes of this tree. Consider an instance of a barrier with eight threads. Threads 0 and 1 are paired up on a single leaf node. One of these threads is designated as the representative of the pair at the next level in the tree. In the above example, thread 0 is considered the representative and it waits on the condition variable ok_to_proceed_up for thread 1 to catch up. All even numbered threads proceed to the next level in the tree. Now thread 0 is paired up with thread 2 and thread 4 with thread 6. Finally thread 0 and 4 are paired. At this point, thread 0 realizes that all threads have reached the desired barrier point and releases threads by signaling the condition ok_to_proceed_down. When all threads are released, the barrier is complete.

It is easy to see that there are n − 1 nodes in the tree for an n thread barrier. Each node corresponds to two condition variables, one for releasing the thread up and one for releasing it down, one lock, and a count of number of threads reaching the node. The tree nodes are linearly laid out in the array mylog_logbarrier_t with the n/2 leaf nodes taking the first n/2 elements, the n/4 tree nodes at the next higher level taking the next n/4 nodes and so on.

It is interesting to study the performance of this program. Since threads in the linear barrier are released one after the other, it is reasonable to expect runtime to be linear in the number of threads even on multiple processors. In Figure 7.3, we plot the runtime of 1000 barriers in a sequence on a 32 processor SGI Origin 2000. The linear runtime of the sequential barrier is clearly reflected in the runtime. The logarithmic barrier executing on a single processor does just as much work asymptotically as a sequential barrier (albeit with a higher constant). However, on a parallel machine, in an ideal case when threads are assigned so that subtrees of the binary barrier tree are assigned to different processors, the time grows as O(n/p + log p). While this is difficult to achieve without being able to examine or assign blocks of threads corresponding to subtrees to individual processors, the logarithmic barrier displays significantly better performance than the serial barrier. Its performance tends to be linear in n as n becomes large for a given number of processors. This is because the n/p term starts to dominate the log p term in the execution time. This is observed both from observations as well as from analytical intuition.

Figure 7.3. Execution time of 1000 sequential and logarithmic barriers as a function of number of threads on a 32 processor SGI Origin 2000.

We initiate the OpenMP programming model with the aid of a simple program. OpenMP directives in C and C++ are based on the #pragma compiler directives. The directive itself consists of a directive name followed by clauses.

1   #pragma omp directive [clause list] 

OpenMP programs execute serially until they encounter the parallel directive. This directive is responsible for creating a group of threads. The exact number of threads can be specified in the directive, set using an environment variable, or at runtime using OpenMP functions. The main thread that encounters the parallel directive becomes the master of this group of threads and is assigned the thread id 0 within the group. The parallel directive has the following prototype:

1   #pragma omp parallel [clause list] 
2   /* structured block */ 
3 

Each thread created by this directive executes the structured block specified by the parallel directive. The clause list is used to specify conditional parallelization, number of threads, and data handling.

It is easy to understand the concurrency model of OpenMP when viewed in the context of the corresponding Pthreads translation. In Figure 7.4, we show one possible translation of an OpenMP program to a Pthreads program. The interested reader may note that such a translation can easily be automated through a Yacc or CUP script.

Figure 7.4. A sample OpenMP program along with its Pthreads translation that might be performed by an OpenMP compiler.

1   #pragma omp parallel if (is_parallel == 1) num_threads(8)  
2                        private (a) shared (b) firstprivate(c) 
3   { 
4       /* structured block */ 
5   } 

The default state of a variable is specified by the clause default (shared) or default (none). The clause default (shared) implies that, by default, a variable is shared by all the threads. The clause default (none) implies that the state of each variable used in a thread must be explicitly specified. This is generally recommended, to guard against errors arising from unintentional concurrent access to shared data.

Just as firstprivate specifies how multiple local copies of a variable are initialized inside a thread, the reduction clause specifies how multiple local copies of a variable at different threads are combined into a single copy at the master when threads exit. The usage of the reduction clause is reduction (operator: variable list). This clause performs a reduction on the scalar variables specified in the list using the operator. The variables in the list are implicitly specified as being private to threads. The operator can be one of +, *, -, &, |, ^, &&, and ||.

1       #pragma omp parallel reduction(+: sum) num_threads(8) 
2       { 
3           /* compute local sums here */ 
4       } 
5       /* sum here contains sum of all local instances of sums */ 

In addition to these data handling clauses, there is one other clause, copyin. We will describe this clause in Section 7.10.4 after we discuss data scope in greater detail.

We can now use the parallel directive along with the clauses to write our first OpenMP program. We introduce two functions to facilitate this. The omp_get_num_threads() function returns the number of threads in the parallel region and the omp_get_thread_num() function returns the integer i.d. of each thread (recall that the master thread has an i.d. 0).

1   /* ****************************************************** 
2      An OpenMP version of a threaded program to compute PI. 
3      ****************************************************** */ 
4 
5       #pragma omp parallel default(private) shared (npoints)  
6                            reduction(+: sum) num_threads(8) 
7       { 
8         num_threads = omp_get_num_threads(); 
9         sample_points_per_thread = npoints / num_threads; 
10        sum = 0; 
11        for (i = 0; i < sample_points_per_thread; i++) { 
12          rand_no_x =(double)(rand_r(&seed))/(double)((2<<14)-1); 
13          rand_no_y =(double)(rand_r(&seed))/(double)((2<<14)-1); 
14          if (((rand_no_x - 0.5) * (rand_no_x - 0.5) + 
15              (rand_no_y - 0.5) * (rand_no_y - 0.5)) < 0.25) 
16              sum ++; 
17        } 
18      } 

Note that this program is much easier to write in terms of specifying creation and termination of threads compared to the corresponding POSIX threaded program.

The parallel directive can be used in conjunction with other directives to specify concurrency across iterations and tasks. OpenMP provides two directives – for and sections – to specify concurrent iterations and tasks.

1       #pragma omp for [clause list] 
2           /* for loop */ 
3 

1     #pragma omp parallel default(private) shared (npoints)  
2                          reduction(+: sum) num_threads(8) 
3     { 
4       sum=0; 
5       #pragma omp for 
6       for (i = 0; i < npoints; i++) { 
7         rand_no_x =(double)(rand_r(&seed))/(double)((2<<14)-1); 
8         rand_no_y =(double)(rand_r(&seed))/(double)((2<<14)-1); 
9         if (((rand_no_x - 0.5) * (rand_no_x - 0.5) + 
10            (rand_no_y - 0.5) * (rand_no_y - 0.5)) < 0.25) 
11            sum ++; 
12      } 
13    } 

Assigning Iterations to Threads

The schedule clause of the for directive deals with the assignment of iterations to threads. The general form of the schedule directive is schedule(scheduling_class[, parameter]). OpenMP supports four scheduling classes: static, dynamic, guided, and runtime.

Example 7.13 Scheduling classes in OpenMP – matrix multiplication.

We explore various scheduling classes in the context of dense matrix multiplication. The code for multiplying two matrices a and b to yield matrix c is as follows:

1       for (i = 0; i < dim; i++) { 
2           for (j = 0; j < dim; j++) { 
3               c(i,j) = 0; 
4               for (k = 0; k < dim; k++) { 
5                   c(i,j) += a(i, k) * b(k, j); 
6               } 
7           } 
8       } 

The code segment above specifies a three-dimensional iteration space providing us with an ideal example for studying various scheduling classes in OpenMP. ▪

Static. The general form of the static scheduling class is schedule(static[, chunk-size]). This technique splits the iteration space into equal chunks of size chunk-size and assigns them to threads in a round-robin fashion. When no chunk-size is specified, the iteration space is split into as many chunks as there are threads and one chunk is assigned to each thread.

Example 7.14 Static scheduling of loops in matrix multiplication

The following modification of the matrix-multiplication program causes the outermost iteration to be split statically across threads as illustrated in Figure 7.5(a).

1   #pragma omp parallel default(private) shared (a, b, c, dim)  
2                        num_threads(4) 
3       #pragma omp for schedule(static) 
4       for (i = 0; i < dim; i++) { 
5           for (j = 0; j < dim; j++) { 
6               c(i,j) = 0; 
7               for (k = 0; k < dim; k++) { 
8                   c(i,j) += a(i, k) * b(k, j); 
9               } 
10          } 
11      } 

Figure 7.5. Three different schedules using the static scheduling class of OpenMP.

Since there are four threads in all, if dim = 128, the size of each partition is 32 columns, since we have not specified the chunk size. Using schedule(static, 16) results in the partitioning of the iteration space illustrated in Figure 7.5(b). Another example of the split illustrated in Figure 7.5(c) results when each for loop in the program in Example 7.13 is parallelized across threads with a schedule(static) and nested parallelism is enabled (see Section 7.10.6). ▪

Dynamic. Often, because of a number of reasons, ranging from heterogeneous computing resources to non-uniform processor loads, equally partitioned workloads take widely varying execution times. For this reason, OpenMP has a dynamic scheduling class. The general form of this class is schedule(dynamic[, chunk-size]). The iteration space is partitioned into chunks given by chunk-size. However, these are assigned to threads as they become idle. This takes care of the temporal imbalances resulting from static scheduling. If no chunk-size is specified, it defaults to a single iteration per chunk.

Guided. Consider the partitioning of an iteration space of 100 iterations with a chunk size of 5. This corresponds to 20 chunks. If there are 16 threads, in the best case, 12 threads get one chunk each and the remaining four threads get two chunks. Consequently, if there are as many processors as threads, this assignment results in considerable idling. The solution to this problem (also referred to as an edge effect) is to reduce the chunk size as we proceed through the computation. This is the principle of the guided scheduling class. The general form of this class is schedule(guided[, chunk-size]).In this class, the chunk size is reduced exponentially as each chunk is dispatched to a thread. The chunk-size refers to the smallest chunk that should be dispatched. Therefore, when the number of iterations left is less than chunk-size, the entire set of iterations is dispatched at once. The value of chunk-size defaults to one if none is specified.

Runtime. Often it is desirable to delay scheduling decisions until runtime. For example, if one would like to see the impact of various scheduling strategies to select the best one, the scheduling can be set to runtime. In this case the environment variable OMP_SCHEDULE determines the scheduling class and the chunk size.

When no scheduling class is specified with the omp for directive, the actual scheduling technique is not specified and is implementation dependent. The for directive places additional restrictions on the for loop that follows. For example, it must not have a break statement, the loop control variable must be an integer, the initialization expression of the for loop must be an integer assignment, the logical expression must be one of <, ≤, >, or ≥, and the increment expression must have integer increments or decrements only. For more details on these restrictions, we refer the reader to the OpenMP manuals.

1       #pragma omp parallel 
2       { 
3           #pragma omp for nowait 
4               for (i = 0; i < nmax; i++) 
5                   if (isEqual(name, current_list[i]) 
6                       processCurrentName(name); 
7           #pragma omp for 
8               for (i = 0; i < mmax; i++) 
9                   if (isEqual(name, past_list[i]) 
10                      processPastName(name); 
11      } 

1   #pragma omp sections [clause list] 
2   { 
3       [#pragma omp section 
4           /* structured block */ 
5       ] 
6       [#pragma omp section 
7           /* structured block */ 
8       ] 
9       ... 
10  } 

1       #pragma omp parallel 
2       { 
3           #pragma omp sections 
4           { 
5               #pragma omp section 
6               { 
7                   taskA(); 
8               } 
9               #pragma omp section 
10              { 
11                  taskB(); 
12              } 
13              #pragma omp section 
14              { 
15                  taskC(); 
16              } 
17          } 
18      } 

1       #pragma omp parallel default (private) shared (n) 
2       { 
3           #pragma omp for 
4           for (i = 0 < i < n; i++) { 
5           /* body of parallel for loop */ 
6           } 
7       } 

1   #pragma omp parallel for default (private) shared (n) 
2   { 
3       for (i = 0 < i < n; i++) { 
4       /* body of parallel for loop */ 
5       } 
6   } 
7 

1       #pragma omp parallel 
2       { 
3           #pragma omp sections 
4           { 
5               #pragma omp section 
6               { 
7                   taskA(); 
8               } 
9               #pragma omp section 
10              { 
11                 taskB(); 
12              } 
13              /* other sections here */ 
14          } 
15      } 

1       #pragma omp parallel sections 
2       { 
3           #pragma omp section 
4           { 
5               taskA(); 
6           } 
7           #pragma omp section 
8           { 
9               taskB(); 
10          } 
11          /* other sections here */ 
12      } 

1   #pragma omp parallel for default(private) shared (a, b, c, dim)  
2                        num_threads(2) 
3       for (i = 0; i < dim; i++) { 
4       #pragma omp parallel for default(private) shared (a, b, c, dim)  
5                        num_threads(2) 
6           for (j = 0; j < dim; j++) { 
7               c(i,j) = 0; 
8               #pragma omp parallel for default(private)  
9                        shared (a, b, c, dim) num_threads(2) 
10              for (k = 0; k < dim; k++) { 
11                  c(i,j) += a(i, k) * b(k, j); 
12              } 
13          } 
14      } 

In Section 7.5, we described the need for coordinating the execution of multiple threads. This may be the result of a desired execution order, the atomicity of a set of instructions, or the need for serial execution of code segments. The Pthreads API supports mutexes and condition variables. Using these we implemented a range of higher level functionality in the form of read-write locks, barriers, monitors, etc. The OpenMP standard provides this high-level functionality in an easy-to-use API. In this section, we will explore these directives and their use.

1       #pragma omp barrier 

1   #pragma omp single [clause list] 
2            structured block 

1   #pragma omp master 
2            structured block 

1   #pragma omp critical [(name)] 
2            structured block 

1       #pragma omp parallel sections 
2       { 
3           #pragma parallel section 
4           { 
5               /* producer thread */ 
6               task = produce_task(); 
7               #pragma omp critical ( task_queue) 
8               { 
9                   insert_into_queue(task); 
10              } 
11          } 
12          #pragma parallel section 
13          { 
14              /* consumer thread */ 
15              #pragma omp critical ( task_queue) 
16              { 
17                  task = extract_from_queue(task); 
18              } 
19              consume_task(task); 
20          } 
21      } 

1   x binary_operation = expr 
2   x++ 
3   ++x 
4   x--
5   --x 

1   #pragma omp ordered 
2       structured block 

1       cumul_sum[0] = list[0]; 
2       #pragma omp parallel for private (i)  
3                   shared (cumul_sum, list, n) ordered 
4       for (i = 1; i < n; i++) 
5       { 
6           /* other processing on list[i] if needed */ 
7 
8           #pragma omp ordered 
9           { 
10              cumul_sum[i] = cumul_sum[i-1] + list[i]; 
11          } 
12      } 

1   #pragma omp flush[(list)] 

One of the critical factors influencing program performance is the manipulation of data by threads. We have briefly discussed OpenMP support for various data classes such as private, shared, firstprivate, and lastprivate. We now examine these in greater detail, with a view to understanding how these classes should be used. We identify the following heuristics to guide the process:

In addition to private, shared, firstprivate, and lastprivate, OpenMP supports one additional data class called threadprivate.

The threadprivate and copyin Directives. Often, it is useful to make a set of objects locally available to a thread in such a way that these objects persist through parallel and serial blocks provided the number of threads remains the same. In contrast to private variables, these variables are useful for maintaining persistent objects across parallel regions, which would otherwise have to be copied into the master thread’s data space and reinitialized at the next parallel block. This class of variables is supported in OpenMP using the threadprivate directive. The syntax of the directive is as follows:

1   #pragma omp threadprivate(variable_list) 

This directive implies that all variables in variable_list are local to each thread and are initialized once before they are accessed in a parallel region. Furthermore, these variables persist across different parallel regions provided dynamic adjustment of the number of threads is disabled and the number of threads is the same.

Similar to firstprivate, OpenMP provides a mechanism for assigning the same value to threadprivate variables across all threads in a parallel region. The syntax of the clause, which can be used with parallel directives, is copyin(variable_list).

In addition to directives, OpenMP also supports a number of functions that allow a programmer to control the execution of threaded programs. As we shall notice, these functions are similar to corresponding Pthreads functions; however, they are generally at a higher level of abstraction, making them easier to use.

1   #include <omp.h> 
2 
3   void omp_set_num_threads (int num_threads); 
4   int omp_get_num_threads (); 
5   int omp_get_max_threads (); 
6   int omp_get_thread_num (); 
7   int omp_get_num_procs (); 
8   int omp_in_parallel(); 

1   #include <omp.h> 
2 
3   void omp_set_dynamic (int dynamic_threads); 
4   int omp_get_dynamic (); 
5   void omp_set_nested (int nested); 
6   int omp_get_nested (); 

1   #include <omp.h> 
2 
3   void omp_init_lock (omp_lock_t *lock); 
4   void omp_destroy_lock (omp_lock_t *lock); 
5   void omp_set_lock (omp_lock_t *lock); 
6   void omp_unset_lock (omp_lock_t *lock); 
7   int omp_test_lock (omp_lock_t *lock); 

1   #include <omp.h> 
2 
3   void omp_init_nest_lock (omp_nest_lock_t *lock); 
4   void omp_destroy_nest_lock (omp_nest_lock_t *lock); 
5   void omp_set_nest_lock (omp_nest_lock_t *lock); 
6   void omp_unset_nest_lock (omp_nest_lock_t *lock); 
7   int omp_test_nest_lock (omp_nest_lock_t *lock); 

OpenMP provides additional environment variables that help control execution of parallel programs. These environment variables include the following.

OMP_NUM_THREADS. This environment variable specifies the default number of threads created upon entering a parallel region. The number of threads can be changed using either the omp_set_num_threads function or the num_threads clause in the parallel directive. Note that the number of threads can be changed dynamically only if the variable OMP_SET_DYNAMIC is set to TRUE or if the function omp_set_dynamic has been called with a non-zero argument. For example, the following command, when typed into csh prior to execution of the program, sets the default number of threads to 8.

1   setenv OMP_NUM_THREADS 8 

OMP_DYNAMIC. This variable, when set to TRUE, allows the number of threads to be controlled at runtime using the omp_set_num threads function or the num_threads clause. Dynamic control of number of threads can be disabled by calling the omp_set_dynamic function with a zero argument.

OMP_NESTED. This variable, when set to TRUE, enables nested parallelism, unless it is disabled by calling the omp_set_nested function with a zero argument.

OMP_SCHEDULE. This environment variable controls the assignment of iteration spaces associated with for directives that use the runtime scheduling class. The variable can take values static, dynamic, and guided along with optional chunk size. For example, the following assignment:

1   setenv OMP_SCHEDULE "static,4" 

specifies that by default, all for directives use static scheduling with a chunk size of 4. Other examples of assignments include:

1   setenv OMP_SCHEDULE "dynamic" 
2   setenv OMP_SCHEDULE "guided" 

In each of these cases, a default chunk size of 1 is used.

OpenMP provides a layer on top of native threads to facilitate a variety of thread-related tasks. Using directives provided by OpenMP, a programmer is rid of the tasks of initializing attributes objects, setting up arguments to threads, partitioning iteration spaces, etc. This convenience is especially useful when the underlying problem has a static and/or regular task graph. The overheads associated with automated generation of threaded code from directives have been shown to be minimal in the context of a variety of applications.

However, there are some drawbacks to using directives as well. An artifact of explicit threading is that data exchange is more apparent. This helps in alleviating some of the overheads from data movement, false sharing, and contention. Explicit threading also provides a richer API in the form of condition waits, locks of different types, and increased flexibility for building composite synchronization operations as illustrated in Section 7.8. Finally, since explicit threading is used more widely than OpenMP, tools and support for Pthreads programs is easier to find.

A programmer must weigh all these considerations before deciding on an API for programming.