| Thread 1 | Thread 2 |
|---|---|
| /* use resource 1 */ | /* use resource 2 */ |
| pthread_mutex_lock(&m1); | pthread_mutex_lock(&m2); |
| /* NOW use resources 2 + 1 */ | /* NOW use resources 1 + 2 */ |
| pthread_mutex_lock(&m2); | pthread_mutex_lock(&m1); |
| pthread_mutex_lock(&m1); | pthread_mutex_lock(&m2); |
The best way to avoid this problem is to make sure that whenever threads lock multiple mutexes, they do so in the same order. This technique is known as lock hierarchies: order the mutexes by logically assigning numbers to them. Also, honor the restriction that you cannot take a mutex that is assigned n when you are holding any mutex assigned a number greater than n.
Note: The lock_lint tool can detect the sort of deadlock problem shown in this example.
The best way to avoid such deadlock problems is to use lock hierarchies. When locks are always taken in a prescribed order, deadlock should not occur. However, this technique cannot always be used :
The idea of Conditional Locking use this approach:
Thread 1:
pthread_mutex_lock(&m1); pthread_mutex_lock(&m2); /* no processing */ pthread_mutex_unlock(&m2); pthread_mutex_unlock(&m1);
Thread 2:
for (; ;) {
pthread_mutex_lock(&m2);
if(pthread_mutex_trylock(&m1)==0)
/* got it! */
break;
/* didn't get it */
pthread_mutex_unlock(&m2);
}
/* get locks; no processing */
pthread_mutex_unlock(&m1);
pthread_mutex_unlock(&m2);
In the above example, thread 1 locks mutexes in the prescribed order, but thread 2 takes them out of order. To make certain that there is no deadlock, thread 2 has to take mutex 1 very carefully; if it were to block waiting for the mutex to be released, it is likely to have just entered into a deadlock with thread 1. To ensure this does not happen, thread 2 calls pthread_mutex_trylock(), which takes the mutex if it is available. If it is not, thread 2 returns immediately, reporting failure. At this point, thread 2 must release mutex 2, so that thread 1 can lock it, and then release both mutex 1 and mutex 2.
With met basic linked structues, when using threads which share a linked list structure the possibility of deadlock may arise.
By nesting mutex locks into the linked data structure and a simple ammendment of the link list code we can prevent deadlock by taking the locks in a prescribed order.
The modified linked is as follows:
typedef struct node1 {
int value;
struct node1 *link;
pthread_mutex_t lock;
} node1_t;
Note: we simply ammend a standard singly-linked list structure so that each node containing a mutex.
Assuming we have created a variable node1_t ListHead.
To remove a node from the list:
Because all searches start at ListHead, there is never a deadlock because the locks are always taken in list order.
Because the predecessor's lock is always taken first, you are again protected from deadlock.
The C code to remove an item from a singly linked list with nested locking is as follows:
node1_t *delete(int value)
{ node1_t *prev,
*current; prev = &ListHead;
pthread_mutex_lock(&prev->lock);
while ((current = prev->link) != NULL)
{ pthread_mutex_lock(¤t->lock);
if (current->value == value)
{ prev->link = current->link;
pthread_mutex_unlock(¤t->lock);
pthread_mutex_unlock(&prev->lock);
current->link = NULL; return(current);
}
pthread_mutex_unlock(&prev->lock);
prev = current;
}
pthread_mutex_unlock(&prev->lock);
return(NULL);
}
You should include the <synch.h> or <thread.h>libraries.
To initialize a mutex use int mutex_init(mutex_t *mp, int type, void *arg)). mutex_init() initializes the mutex pointed to by mp. The type can be one of the following (note that arg is currently ignored).
Mutexes can also be initialized by allocation in zeroed memory, in which case a type of USYNC_THREAD is assumed. Multiple threads must not initialize the same mutex simultaneously. A mutex lock must not be reinitialized while other threads might be using it.
The function int mutex_destroy (mutex_t *mp) destroys any state associated with the mutex pointed to by mp. Note that the space for storing the mutex is not freed.
To acquire a mutex lock use the function mutex_lock(mutex_t *mp) which locks the mutex pointed to by mp. When the mutex is already locked, the calling thread blocks until the mutex becomes available (blocked threads wait on a prioritized queue).
To release a mutex use mutex_unlock(mutex_t *mp) which unlocks the mutex pointed to by mp. The mutex must be locked and the calling thread must be the one that last locked the mutex (the owner).
To try to acquire a mutex use mutex_trylock(mutex_t *mp) to attempt to lock the mutex pointed to by mp. This function is a nonblocking version of mutex_lock()
Condition variables can be usedto atomically block threads until a particular condition is true. Condition variables are always used in conjunction with mutex locks:
Condition variables can be used to synchronize threads among processes when they are allocated in memory that can be written to and is shared by the cooperating processes.
The scheduling policy determines how blocking threads are awakened. For the default SCHED_OTHER, threads are awakened in priority order. The attributes for condition variables must be set and initialized before the condition variables can be used.
As with mutex locks, The condiotion variable attributes must be initialised and set (or set to NULL) before an actual condition variable may be initialise (with appropriat attributes) and then used.
The function pthread_condattr_init() initializes attributes associated with this object to their default values. It is prototyped by:
int pthread_condattr_init(pthread_condattr_t *cattr);
Storage for each attribute object, cattr, is allocated by the threads system during execution. cattr is an opaque data type that contains a system-allocated attribute object. The possible values of cattr's scope are PTHREAD_PROCESS_PRIVATE and PTHREAD_PROCESS_SHARED. The default value of the pshared attribute when this function is called is PTHREAD_PROCESS_PRIVATE, which means that the initialized condition variable can be used within a process.
Before a condition variable attribute can be reused, it must first be reinitialized by pthread_condattr_destroy(). The pthread_condattr_init() call returns a pointer to an opaque object. If the object is not destroyed, a memory leak will result.
pthread_condattr_init() returns zero after completing successfully. Any other returned value indicates that an error occurred. When either of the following conditions occurs, the function fails and returns the corresponding value.
A simple example call of this function is :
#include <pthread.h> pthread_condattr_t cattr; int ret; /* initialize an attribute to default value */ ret = pthread_condattr_init(&cattr);
The function pthread_condattr_destroy() removes storage and renders the attribute object invalid, it is prototyped by:
int pthread_condattr_destroy(pthread_condattr_t *cattr);
pthread_condattr_destroy() returns zero after completing successfully and destroying the condition variable pointed to by cattr. Any other returned value indicates that an error occurred. If the following condition occurs, the function fails and returns the corresponding value.
The scope of a condition variable can be either process private (intraprocess) or system wide (interprocess), as with mutex locks. If the condition variable is created with the pshared attribute set to the PTHREAD_PROCESS_SHARED state, and it exists in shared memory, it can be shared among threads from more than one process. This is equivalent to the USYNC_PROCESS flag in mutex_init() in the original Solaris threads. If the mutex pshared attribute is set to PTHREAD_PROCESS_PRIVATE (default value), only those threads created by the same process can operate on the mutex. Using PTHREAD_PROCESS_PRIVATE results in the same behavior as with the USYNC_THREAD flag in the original Solaris threads cond_init() call, which is that of a local condition variable. PTHREAD_PROCESS_SHARED is equivalent to a global condition variable.
The function pthread_condattr_setpshared() is used to set the scope of a condition variable, it is prototyped by:
int pthread_condattr_setpshared(pthread_condattr_t *cattr, int pshared);
The condition variable attribute cattr must be initialised first and the value of pshared is either PTHREAD_PROCESS_SHARED or PTHREAD_PROCESS_PRIVATE.
pthread_condattr_setpshared() returns zero after completing successfully. Any other returned value indicates that an error occurred.
A sample use of this function is as follows:
#include <pthread.h> pthread_condattr_t cattr; int ret; /* Scope: all processes */ ret = pthread_condattr_setpshared(&cattr, PTHREAD_PROCESS_SHARED); /* OR */ /* Scope: within a process */ ret = pthread_condattr_setpshared(&cattr, PTHREAD_PROCESS_PRIVATE);
The function int pthread_condattr_getpshared(const pthread_condattr_t *cattr, int *pshared) may be used to obtain the scope of a given condition variable.
The function pthread_cond_init() initializes the condition variable and is prototyped as follows:
int pthread_cond_init(pthread_cond_t *cv, const pthread_condattr_t *cattr);
The condition variable which is initialized is pointed at by cv and is set to its default value if cattr is NULL, or to specific cattr condition variable attributes that are already set with pthread_condattr_init(). The effect of cattr being NULL is the same as passing the address of a default condition variable attribute object, but without the memory overhead.
Statically-defined condition variables can be initialized directly to have default attributes with the macro PTHREAD_COND_INITIALIZER. This has the same effect as dynamically allocating pthread_cond_init() with null attributes. No error checking is done. Multiple threads must not simultaneously initialize or reinitialize the same condition variable. If a condition variable is reinitialized or destroyed, the application must be sure the condition variable is not in use.
pthread_cond_init() returns zero after completing successfully. Any other returned value indicates that an error occurred.
Sample calls of this function are:
#include <pthread.h> pthread_cond_t cv; pthread_condattr_t cattr; int ret; /* initialize a condition variable to its default value */ ret = pthread_cond_init(&cv, NULL); /* initialize a condition variable */ ret = pthread_cond_init(&cv, &cattr);
The function pthread_cond_wait() is used to atomically release a mutex and to cause the calling thread to block on the condition variable. It is protoyped by:
int pthread_cond_wait(pthread_cond_t *cv,pthread_mutex_t *mutex);
The mutex that is released is pointed to by mutex and the condition variable pointed to by cv is blocked.
pthread_cond_wait() returns zero after completing successfully. Any other returned value indicates that an error occurred. When the following condition occurs, the function fails and returns the corresponding value.
A simple example call is:
#include <pthread.h> pthread_cond_t cv; pthread_mutex_t mutex; int ret; /* wait on condition variable */ ret = pthread_cond_wait(&cv, &mutex);
The blocked thread can be awakened by a pthread_cond_signal(), a pthread_cond_broadcast(), or when interrupted by delivery of a signal. Any change in the value of a condition associated with the condition variable cannot be inferred by the return of pthread_cond_wait(), and any such condition must be reevaluated. The pthread_cond_wait() routine always returns with the mutex locked and owned by the calling thread, even when returning an error. This function blocks until the condition is signaled. It atomically releases the associated mutex lock before blocking, and atomically acquires it again before returning. In typical use, a condition expression is evaluated under the protection of a mutex lock. When the condition expression is false, the thread blocks on the condition variable. The condition variable is then signaled by another thread when it changes the condition value. This causes one or all of the threads waiting on the condition to unblock and to try to acquire the mutex lock again. Because the condition can change before an awakened thread returns from pthread_cond_wait(), the condition that caused the wait must be retested before the mutex lock is acquired.
The recommended test method is to write the condition check as a while loop that calls pthread_cond_wait(), as follows:
pthread_mutex_lock(); while(condition_is_false) pthread_cond_wait(); pthread_mutex_unlock();
No specific order of acquisition is guaranteed when more than one thread blocks on the condition variable. Note also that pthread_cond_wait() is a cancellation point. If a cancel is pending and the calling thread has cancellation enabled, the thread terminates and begins executing its cleanup handlers while continuing to hold the lock.
To unblock a specific thread use pthread_cond_signal() which is prototyped by:
int pthread_cond_signal(pthread_cond_t *cv);
This unblocks one thread that is blocked on the condition variable pointed to by cv. pthread_cond_signal() returns zero after completing successfully. Any other returned value indicates that an error occurred.
You should always call pthread_cond_signal() under the protection of the same mutex used with the condition variable being signaled. Otherwise, the condition variable could be signaled between the test of the associated condition and blocking in pthread_cond_wait(), which can cause an infinite wait. The scheduling policy determines the order in which blocked threads are awakened. For SCHED_OTHER, threads are awakened in priority order. When no threads are blocked on the condition variable, then calling pthread_cond_signal()l has no effect.
The folloowing code fragment illustrates how to avoid an infinite problem described above:
pthread_mutex_t count_lock;
pthread_cond_t count_nonzero;
unsigned count;
decrement_count()
{ pthread_mutex_lock(&count_lock);
while (count == 0)
pthread_cond_wait(&count_nonzero, &count_lock);
count = count - 1;
pthread_mutex_unlock(&count_lock);
}
increment_count()
{ pthread_mutex_lock(&count_lock);
if (count == 0)
pthread_cond_signal(&count_nonzero);
count = count + 1;
pthread_mutex_unlock(&count_lock);
}
You can also block until a specified event occurs. The function pthread_cond_timedwait() is used for this purpose. It is prototyped by:
int pthread_cond_timedwait(pthread_cond_t *cv,
pthread_mutex_t *mp, const struct timespec *abstime);
pthread_cond_timedwait() is used in a similar manner to pthread_cond_wait(): pthread_cond_timedwait() blocks until the condition is signaled or until the time of day, specified by abstime, has passed. pthread_cond_timedwait() always returns with the mutex, mp, locked and owned by the calling thread, even when it is returning an error. pthread_cond_timedwait() is also a cancellation point.
pthread_cond_timedwait() returns zero after completing successfully. Any other returned value indicates that an error occurred. When either of the following conditions occurs, the function fails and returns the corresponding value.
An examle call of this function is:
#include <pthread.h>
#include <time.h>
pthread_timestruc_t to;
pthread_cond_t cv;
pthread_mutex_t mp;
timestruct_t abstime;
int ret;
/* wait on condition variable */
ret = pthread_cond_timedwait(&cv, &mp, &abstime);
pthread_mutex_lock(&m);
to.tv_sec = time(NULL) + TIMEOUT;
to.tv_nsec = 0;
while (cond == FALSE)
{ err = pthread_cond_timedwait(&c, &m, &to);
if (err == ETIMEDOUT)
{ /* timeout, do something */
break;
}
}
pthread_mutex_unlock(&m);
All threads may be unblocked in one function: pthread_cond_broadcast(). This function is prototyped as follows:
int pthread_cond_broadcast(pthread_cond_t *cv);
pthread_cond_broadcast() unblocks all threads that are blocked on the condition variable pointed to by cv, specified by pthread_cond_wait(). When no threads are blocked on the condition variable, pthread_cond_broadcast() has no effect.
pthread_cond_broadcast() returns zero after completing successfully. Any other returned value indicates that an error occurred. When the following condition occurs, the function fails and returns the corresponding value.
Since pthread_cond_broadcast() causes all threads blocked on the condition to contend again for the mutex lock, use carefully. For example, use pthread_cond_broadcast() to allow threads to contend for varying resource amounts when resources are freed:
#include <pthread.h>
pthread_mutex_t rsrc_lock;
pthread_cond_t rsrc_add;
unsigned int resources;
get_resources(int amount)
{ pthread_mutex_lock(&rsrc_lock);
while (resources < amount)
pthread_cond_wait(&rsrc_add, &rsrc_lock);
resources -= amount;
pthread_mutex_unlock(&rsrc_lock);
}
add_resources(int amount)
{ pthread_mutex_lock(&rsrc_lock);
resources += amount;
pthread_cond_broadcast(&rsrc_add);
pthread_mutex_unlock(&rsrc_lock);
}
Note: that in add_resources it does not matter whether resources is updated first or if pthread_cond_broadcast() is called first inside the mutex lock. Call pthread_cond_broadcast() under the protection of the same mutex that is used with the condition variable being signaled. Otherwise, the condition variable could be signaled between the test of the associated condition and blocking in pthread_cond_wait(), which can cause an infinite wait.
The function pthread_cond_destroy() to destroy any state associated with the condition variable, it is prototyped by:
int pthread_cond_destroy(pthread_cond_t *cv);
The condition variable pointed to by cv will be destroyed by this call:
#include <pthread.h> pthread_cond_t cv; int ret; /* Condition variable is destroyed */ ret = pthread_cond_destroy(&cv);
Note that the space for storing the condition variable is not freed.
pthread_cond_destroy() returns zero after completing successfully. Any other returned value indicates that an error occurred. When any of the following conditions occur, the function fails and returns the corresponding value.
Similar condition variables exist in Solaris. The functions are prototyped in <thread.h>.
To initialize a condition variable use int cond_init(cond_t *cv, int type, int arg) which initializes the condition variable pointed to by cv. The type can be one of USYNC_PROCESS or USYNC_THREAD (See Solaris mutex (Section 30.1.9 for more details). Note that arg is currently ignored.
Condition variables can also be initialized by allocation in zeroed memory, in which case a type of USYNC_THREAD is assumed. Multiple threads must not initialize the same condition variable simultaneously. A condition variable must not be reinitialized while other threads might be using it.
To destroy a condition variable use int cond_destroy(cond_t *cv) which destroys a state associated with the condition variable pointed to by cv. The space for storing the condition variable is not freed.
To wait for a condition use int cond_wait(cond_t *cv, mutex_t *mp) which atomically releases the mutex pointed to by mp and to cause the calling thread to block on the condition variable pointed to by cv.
The blocked thread can be awakened by cond_signal(cond_t *cv), cond_broadcast(cond_t *cv), or when interrupted by delivery of a signal or a fork. Use cond_signal() to unblock one thread that is blocked on the condition variable pointed to by cv. Call this function under protection of the same mutex used with the condition variable being signaled. Otherwise, the condition could be signaled between its test and cond_wait(), causing an infinite wait. Use cond_broadcast() to unblock all threads that are blocked on the condition variable pointed to by cv. When no threads are blocked on the condition variable then cond_broadcast() has no effect.
Finally, to wait until the condition is signaled or for an absolute time use int cond_timedwait(cond_t *cv, mutex_t *mp, timestruct_t abstime) Use cond_timedwait() as you would use cond_wait(), except that cond_timedwait() does not block past the time of day specified by abstime. cond_timedwait() always returns with the mutex locked and owned by the calling thread even when returning an error.
(See Chapter IPC:Semaphores) has dealt with semaphore programming for POSIX and System V IPC semaphores.
Semaphore operations are the same in both POSIX and Solaris. The function names are changed from sema_ in Solaris to sem_ in pthreads. Solaris semaphore are defined in <thread.h>.
In this section we give a brief description of Solaris thread semaphores.
To initialize the function int sema_init(sema_t *sp, unsigned int count, int type, void *arg) is used. sema. type can be one of the following ):
arg is currently unused.
Multiple threads must not initialize the same semaphore simultaneously. A semaphore must not be reinitialized while other threads may be using it.
To increment a Semaphore use the function int sema_post(sema_t *sp). sema_post atomically increments the semaphore pointed to by sp. When any threads are blocked on the semaphore, one is unblocked.
To block on a Semaphore use int sema_wait(sema_t *sp). sema_wait() to block the calling thread until the count in the semaphore pointed to by sp becomes greater than zero, then atomically decrement it.
To decrement a Semaphore count use int sema_trywait(sema_t *sp). sema_trywait() atomically decrements the count in the semaphore pointed to by sp when the count is greater than zero. This function is a nonblocking version of sema_wait().
To destroy the Semaphore state call the function sema_destroy(sema_t *sp). sema_destroy() to destroy any state associated with the semaphore pointed to by sp. The space for storing the semaphore is not freed.