Programming with threads is very tricky because most threaded programs are concurrent programs. In particular, there's no way to know when the system will schedule one thread to run and when it will run another. One thread might run for a very long time, or the system might switch among threads very quickly. On a system with multiple processors, the system might even schedule multiple threads to run at literally the same time.
Debugging a threaded program is difficult because you cannot always easily reproduce the behavior that caused the problem. You might run the program once and have everything work fine; the next time you run it, it might crash. There's no way to make the system schedule the threads exactly the same way it did before.
The ultimate cause of most bugs involving threads is that the threads are accessing the same data. As mentioned previously, that's one of the powerful aspects of threads, but it can also be dangerous. If one thread is only partway through updating a data structure when another thread accesses the same data structure, chaos is likely to ensue. Often, buggy threaded programs contain a code that will work only if one thread gets scheduled more often—or sooner—than another thread. These bugs are called race conditions; the threads are racing one another to change the same data structure.
Suppose that your program has a series of queued jobs that are processed by several concurrent threads. The queue of jobs is represented by a linked list of struct job objects.
After each thread finishes an operation, it checks the queue to see if an additional job is available. If job_queue is non-null, the thread removes the head of the linked list and sets job_queue to the next job on the list.
The thread function that processes jobs in the queue might look like Listing 4.10.
#include <malloc.h> struct job { /* Link field for linked list. */ struct job* next; /* Other fields describing work to be done... */ }; /* A linked list of pending jobs. */ struct job* job_queue; /* Process queued jobs until the queue is empty. */ void* thread_function (void* arg) { while (job_queue != NULL) { /* Get the next available job. */ struct job* next_job = job_queue; /* Remove this job from the list. */ job_queue = job_queue->next; /* Carry out the work. */ process_job (next_job); /* Clean up. */ free (next_job); } return NULL; }
Now suppose that two threads happen to finish a job at about the same time, but only one job remains in the queue. The first thread checks whether job_queue is null; finding that it isn't, the thread enters the loop and stores the pointer to the job object in next_job. At this point, Linux happens to interrupt the first thread and schedules the second. The second thread also checks job_queue and finding it non-null, also assigns the same job pointer to next_job. By unfortunate coincidence, we now have two threads executing the same job.
To make matters worse, one thread will unlink the job object from the queue, leaving job_queue containing null. When the other thread evaluates job_queue->next, a segmentation fault will result.
This is an example of a race condition. Under "lucky" circumstances, this particular schedule of the two threads may never occur, and the race condition may never exhibit itself. Only under different circumstances, perhaps when running on a heavily loaded system (or on an important customer's new multiprocessor server!) may the bug exhibit itself.
To eliminate race conditions, you need a way to make operations atomic. An atomic operation is indivisible and uninterruptible; once the operation starts, it will not be paused or interrupted until it completes, and no other operation will take place meanwhile. In this particular example, you want to check job_queue; if it's not empty, remove the first job, all as a single atomic operation.
The solution to the job queue race condition problem is to let only one thread access the queue of jobs at a time. Once a thread starts looking at the queue, no other thread should be able to access it until the first thread has decided whether to process a job and, if so, has removed the job from the list.
Implementing this requires support from the operating system. GNU/Linux provides mutexes, short for MUTual EXclusion locks. A mutex is a special lock that only one thread may lock at a time. If a thread locks a mutex and then a second thread also tries to lock the same mutex, the second thread is blocked, or put on hold. Only when the first thread unlocks the mutex is the second thread unblocked—allowed to resume execution. GNU/Linux guarantees that race conditions do not occur among threads attempting to lock a mutex; only one thread will ever get the lock, and all other threads will be blocked.
Think of a mutex as the lock on a lavatory door. Whoever gets there first enters the lavatory and locks the door. If someone else attempts to enter the lavatory while it's occupied, that person will find the door locked and will be forced to wait outside until the occupant emerges.
To create a mutex, create a variable of type pthread_mutex_t and pass a pointer to it to pthread_mutex_init. The second argument to pthread_mutex_init is a pointer to a mutex attribute object, which specifies attributes of the mutex. As with pthread_create, if the attribute pointer is null, default attributes are assumed. The mutex variable should be initialized only once. This code fragment demonstrates the declaration and initialization of a mutex variable.
pthread_mutex_t mutex; pthread_mutex_init (&mutex, NULL);
Another simpler way to create a mutex with default attributes is to initialize it with the special value PTHREAD_MUTEX_INITIALIZER. No additional call to pthread_mutex_init is necessary. This is particularly convenient for global variables (and, in C++, static data members). The previous code fragment could equivalently have been written like this:
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
A thread may attempt to lock a mutex by calling pthread_mutex_lock on it. If the mutex was unlocked, it becomes locked and the function returns immediately. If the mutex was locked by another thread, pthread_mutex_lock blocks execution and returns only eventually when the mutex is unlocked by the other thread. More than one thread may be blocked on a locked mutex at one time. When the mutex is unlocked, only one of the blocked threads (chosen unpredictably) is unblocked and allowed to lock the mutex; the other threads stay blocked.
A call to pthread_mutex_unlock unlocks a mutex. This function should always be called from the same thread that locked the mutex.
Listing 4.11 shows another version of the job queue example. Now the queue is protected by a mutex. Before accessing the queue (either for read or write), each thread locks a mutex first. Only when the entire sequence of checking the queue and removing a job is complete is the mutex unlocked. This prevents the race condition previously described.
#include <malloc.h> #include <pthread.h> struct job {/* Link field for linked list. */
struct job* next;
/* Other fields describing work to be done... */
};
/* A linked list of pending jobs. */
struct job* job_queue;
/* A mutex protecting job_queue. */
pthread_mutex_t job_queue_mutex = PTHREAD_MUTEX_INITIALIZER;
/* Process queued jobs until the queue is empty. */
void* thread_function (void* arg)
{ while (1) {struct job* next_job;
/* Lock the mutex on the job queue. */
pthread_mutex_lock (&job_queue_mutex);
/* Now it's safe to check if the queue is empty. */
if (job_queue == NULL)
next_job = NULL;
else {/* Get the next available job. */
next_job = job_queue;
/* Remove this job from the list. */
job_queue = job_queue->next;
}
/* Unlock the mutex on the job queue because we're done with the
queue for now. */
pthread_mutex_unlock (&job_queue_mutex);
/* Was the queue empty? If so, end the thread. */
if (next_job == NULL)
break;
/* Carry out the work. */
process_job (next_job);
/* Clean up. */
free (next_job);
}
return NULL;
}
All accesses to job_queue, the shared data pointer, come between the call to pthread_mutex_lock and the call to pthread_mutex_unlock. A job object, stored in next_job, is accessed outside this region only after that object has been removed from the queue and is therefore inaccessible to other threads.
Note that if the queue is empty (that is, job_queue is null), we don't break out of the loop immediately because this would leave the mutex permanently locked and would prevent any other thread from accessing the job queue ever again. Instead, we remember this fact by setting next_job to null and breaking out only after unlocking the mutex.
Use of the mutex to lock job_queue is not automatic; it's up to you to add code to lock the mutex before accessing that variable and then to unlock it afterward. For example, a function to add a job to the job queue might look like this:
void enqueue_job (struct job* new_job)
{pthread_mutex_lock (&job_queue_mutex);
new_job->next = job_queue;
job_queue = new_job;
pthread_mutex_unlock (&job_queue_mutex);
}
Mutexes provide a mechanism for allowing one thread to block the execution of another. This opens up the possibility of a new class of bugs, called deadlocks. A deadlock occurs when one or more threads are stuck waiting for something that never will occur.
A simple type of deadlock may occur when the same thread attempts to lock a mutex twice in a row. The behavior in this case depends on what kind of mutex is being used. Three kinds of mutexes exist:
· Locking a fast mutex (the default kind) will cause a deadlock to occur. An attempt to lock the mutex blocks until the mutex is unlocked. But because the thread that locked the mutex is blocked on the same mutex, the lock cannot ever be released.
· Locking a recursive mutex does not cause a deadlock. A recursive mutex may safely be locked many times by the same thread. The mutex remembers how many times pthread_mutex_lock was called on it by the thread that holds the lock; that thread must make the same number of calls to pthread_mutex_unlock before the mutex is actually unlocked and another thread is allowed to lock it.
· GNU/Linux will detect and flag a double lock on an error-checking mutex that would otherwise cause a deadlock. The second consecutive call to pthread_mutex_lock returns the failure code EDEADLK.
By default, a GNU/Linux mutex is of the fast kind. To create a mutex of one of the other two kinds, first create a mutex attribute object by declaring a pthread_mutexattr_t variable and calling pthread_mutexattr_init on a pointer to it. Then set the mutex kind by calling pthread_mutexattr_setkind_np; the first argument is a pointer to the mutex attribute object, and the second is PTHREAD_MUTEX_RECURSIVE_NP for a recursive mutex, or PTHREAD_MUTEX_ERRORCHECK_NP for an error-checking mutex. Pass a pointer to this attribute object to pthread_mutex_init to create a mutex of this kind, and then destroy the attribute object with pthread_mutexattr_destroy.
This code sequence illustrates creation of an error-checking mutex, for instance:
pthread_mutexattr_t attr;
pthread_mutex_t mutex;
pthread_mutexattr_init (&attr);
pthread_mutexattr_setkind_np (&attr, PTHREAD_MUTEX_ERRORCHECK_NP);
pthread_mutex_init (&mutex, &attr);
pthread_mutexattr_destroy (&attr);
As suggested by the "np" suffix, the recursive and error-checking mutex kinds are specific to GNU/Linux and are not portable. Therefore, it is generally not advised to use them in programs. (Error-checking mutexes can be useful when debugging, though.)
Occasionally, it is useful to test whether a mutex is locked without actually blocking on it. For instance, a thread may need to lock a mutex but may have other work to do instead of blocking if the mutex is already locked. Because pthread_mutex_lock will not return until the mutex becomes unlocked, some other function is necessary.
GNU/Linux provides pthread_mutex_trylock for this purpose. If you call pthread_mutex_trylock on an unlocked mutex, you will lock the mutex as if you had called pthread_mutex_lock, and pthread_mutex_trylock will return zero. However, if the mutex is already locked by another thread, pthread_mutex_trylock will not block. Instead, it will return immediately with the error code EBUSY. The mutex lock held by the other thread is not affected. You may try again later to lock the mutex.
In the preceding example, in which several threads process jobs from a queue, the main thread function of the threads carries out the next job until no jobs are left and then exits the thread. This scheme works if all the jobs are queued in advance or if new jobs are queued at least as quickly as the threads process them. However, if the threads work too quickly, the queue of jobs will empty and the threads will exit. If new jobs are later enqueued, no threads may remain to process them. What we might like instead is a mechanism for blocking the threads when the queue empties until new jobs become available.
A semaphore provides a convenient method for doing this. A semaphore is a counter that can be used to synchronize multiple threads. As with a mutex, GNU/Linux guarantees that checking or modifying the value of a semaphore can be done safely, without creating a race condition.
Each semaphore has a counter value, which is a non-negative integer. A semaphore supports two basic operations:
· A wait operation decrements the value of the semaphore by 1. If the value is already zero, the operation blocks until the value of the semaphore becomes positive (due to the action of some other thread). When the semaphore's value becomes positive, it is decremented by 1 and the wait operation returns.
· A post operation increments the value of the semaphore by 1. If the semaphore was previously zero and other threads are blocked in a wait operation on that semaphore, one of those threads is unblocked and its wait operation completes (which brings the semaphore's value back to zero).
Note that GNU/Linux provides two slightly different semaphore implementations. The one we describe here is the POSIX standard semaphore implementation. Use these semaphores when communicating among threads The other implementation, used for communication among processes, is described in Section 5.2, "Process Semaphores." If you use semaphores, include Process <semaphore.h>.
A semaphore is represented by a sem_t variable. Before using it, you must initialize it using the sem_init function, passing a pointer to the sem_t variable. The second parameter should be zero, [2] and the third parameter is the semaphore's initial value. If you no longer need a semaphore, it's good to deallocate it with sem_destroy.
[2] A nonzero value would indicate a semaphore that can be shared across processes, which is not supported by GNU/Linux for this type of semaphore.
To wait on a semaphore, use sem_wait. To post to a semaphore, use sem_post. A nonblocking wait function, sem_trywait, is also provided. It's similar to pthread_mutex_trylock—if the wait would have blocked because the semaphore's value was zero, the function returns immediately, with error value EAGAIN, instead of blocking.
GNU/Linux also provides a function to retrieve the current value of a semaphore, sem_getvalue, which places the value in the int variable pointed to by its second argument. You should not use the semaphore value you get from this function to make a decision whether to post to or wait on the semaphore, though. To do this could lead to a race condition: Another thread could change the semaphore's value between the call to sem_getvalue and the call to another semaphore function. Use the atomic post and wait functions instead.
Returning to our job queue example, we can use a semaphore to count the number of jobs waiting in the queue. Listing 4.12 controls the queue with a semaphore. The function enqueue_job adds a new job to the queue.
#include <malloc.h>
#include <pthread.h>
#include <semaphore.h>
struct job {/* Link field for linked list. */
struct job* next;
/* Other fields describing work to be done... */
};
/* A linked list of pending jobs. */
struct job* job_queue;
/* A mutex protecting job_queue. */
pthread_mutex_t job_queue_mutex = PTHREAD_MUTEX_INITIALIZER;
/* A semaphore counting the number of jobs in the queue. */
sem_t job_queue_count;
/* Perform one-time initialization of the job queue. */
void initialize_job_queue ()
{/* The queue is initially empty. */
job_queue = NULL;
/* Initialize the semaphore which counts jobs in the queue. Its
initial value should be zero. */
sem_init (&job_queue_count, 0, 0);
}
/* Process queued jobs until the queue is empty. */
void* thread_function (void* arg)
{ while (1) {struct job* next_job;
/* Wait on the job queue semaphore. If its value is positive,
indicating that the queue is not empty, decrement the count by
1. If the queue is empty, block until a new job is enqueued. */
sem_wait (&job_queue_count);
/* Lock the mutex on the job queue. */
pthread_mutex_lock (&job_queue_mutex);
/* Because of the semaphore, we know the queue is not empty. Get
the next available job. */
next_job = job_queue;
/* Remove this job from the list. */
job_queue = job_queue->next;
/* Unlock the mutex on the job queue because we're done with the
queue for now. */
pthread_mutex_unlock (&job_queue_mutex);
/* Carry out the work. */
process_job (next_job);
/* Clean up. */
free (next_job);
}
return NULL;
}
/* Add a new job to the front of the job queue. */
void enqueue_job (/* Pass job-specific data here... */)
{struct job* new_job;
/* Allocate a new job object. */
new_job = (struct job*) malloc (sizeof (struct job));
/* Set the other fields of the job struct here... */
/* Lock the mutex on the job queue before accessing it. */
pthread_mutex_lock (&job_queue_mutex);
/* Place the new job at the head of the queue. */
new_job->next = job_queue;
job_queue = new_job;
/* Post to the semaphore to indicate that another job is available. If
threads are blocked, waiting on the semaphore, one will become
unblocked so it can process the job. */
sem_post (&job_queue_count);
/* Unlock the job queue mutex. */
pthread_mutex_unlock (&job_queue_mutex);
}
Before taking a job from the front of the queue, each thread will first wait on the semaphore. If the semaphore's value is zero, indicating that the queue is empty, the thread will simply block until the semaphore's value becomes positive, indicating that a job has been added to the queue.
The enqueue_job function adds a job to the queue. Just like thread_function, it needs to lock the queue mutex before modifying the queue. After adding a job to the queue, it posts to the semaphore, indicating that a new job is available. In the version shown in Listing 4.12, the threads that process the jobs never exit; if no jobs are available for a while, all the threads simply block in sem_wait.
We've shown how to use a mutex to protect a variable against simultaneous access by two threads and how to use semaphores to implement a shared counter. A condition variable is a third synchronization device that GNU/Linux provides; with it, you can implement more complex conditions under which threads execute.
Suppose that you write a thread function that executes a loop infinitely, performing some work on each iteration. The thread loop, however, needs to be controlled by a flag: The loop runs only when the flag is set; when the flag is not set, the loop pauses.
Listing 4.13 shows how you might implement this by spinning in a loop. During each iteration of the loop, the thread function checks that the flag is set. Because the flag is accessed by multiple threads, it is protected by a mutex. This implementation may be correct, but it is not efficient. The thread function will spend lots of CPU whenever the flag is not set, checking and rechecking the flag, each time locking and unlocking the mutex. What you really want is a way to put the thread to sleep when the flag is not set, until some circumstance changes that might cause the flag to become set.
#include <pthread.h>
int thread_flag;
pthread_mutex_t thread_flag_mutex;
void initialize_flag ()
{pthread_mutex_init (&thread_flag_mutex, NULL);
thread_flag = 0;
}
/* Calls do_work repeatedly while the thread flag is set; otherwise
spins. */
void* thread_function (void* thread_arg)
{ while (1) {int flag_is_set;
/* Protect the flag with a mutex lock. */
pthread_mutex_lock (&thread_flag_mutex);
flag_is_set = thread_flag;
pthread_mutex_unlock (&thread_flag_mutex);
if (flag_is_set)
do_work ();
/* Else don't do anything. Just loop again. */
}
return NULL;
}
/* Sets the value of the thread flag to FLAG_VALUE. */
void set_thread_flag (int flag_value)
{/* Protect the flag with a mutex lock. */
pthread_mutex_lock (&thread_flag_mutex);
thread_flag = flag_value;
pthread_mutex_unlock (&thread_flag_mutex);
}
A condition variable enables you to implement a condition under which a thread executes and, inversely, the condition under which the thread is blocked. As long as every thread that potentially changes the sense of the condition uses the condition variable properly, Linux guarantees that threads blocked on the condition will be unblocked when the condition changes.
As with a semaphore, a thread may wait on a condition variable. If thread A waits on a condition variable, it is blocked until some other thread, thread B, signals the same condition variable. Unlike a semaphore, a condition variable has no counter or memory; thread A must wait on the condition variable before thread B signals it. If thread B signals the condition variable before thread A waits on it, the signal is lost, and thread A blocks until some other thread signals the condition variable again.
This is how you would use a condition variable to make the previous sample more efficient:
· The loop in thread_function checks the flag. If the flag is not set, the thread waits on the condition variable.
· The set_thread_flag function signals the condition variable after changing the flag value. That way, if thread_function is blocked on the condition variable, it will be unblocked and will check the condition again.
There's one problem with this: There's a race condition between checking the flag value and signaling or waiting on the condition variable. Suppose that thread_function checked the flag and found that it was not set. At that moment, the Linux scheduler paused that thread and resumed the main one. By some coincidence, the main thread is in set_thread_flag. It sets the flag and then signals the condition variable. Because no thread is waiting on the condition variable at the time (remember that thread_function was paused before it could wait on the condition variable), the signal is lost. Now, when Linux reschedules the other thread, it starts waiting on the condition variable and may end up blocked forever.
To solve this problem, we need a way to lock the flag and the condition variable together with a single mutex. Fortunately, GNU/Linux provides exactly this mechanism. Each condition variable must be used in conjunction with a mutex, to prevent this sort of race condition. Using this scheme, the thread function follows these steps:
1. The loop in thread_function locks the mutex and reads the flag value.
2. If the flag is set, it unlocks the mutex and executes the work function.
3. If the flag is not set, it atomically unlocks the mutex and waits on the condition variable.
The critical feature here is in step 3, in which GNU/Linux allows you to unlock the mutex and wait on the condition variable atomically, without the possibility of another thread intervening. This eliminates the possibility that another thread may change the flag value and signal the condition variable in between thread_function's test of the flag value and wait on the condition variable.
A condition variable is represented by an instance of pthread_cond_t. Remember that each condition variable should be accompanied by a mutex. These are the functions that manipulate condition variables:
· pthread_cond_init initializes a condition variable. The first argument is a pointer to a pthread_cond_t instance. The second argument, a pointer to a condition variable attribute object, is ignored under GNU/Linux.
The mutex must be initialized separately, as described in Section 4.4.2, "Mutexes."
· pthread_cond_signal signals a condition variable. A single thread that is blocked on the condition variable will be unblocked. If no other thread is blocked on the condition variable, the signal is ignored. The argument is a pointer to the pthread_cond_t instance.
A similar call, pthread_cond_broadcast, unblocks all threads that are blocked on the condition variable, instead of just one.
· pthread_cond_wait blocks the calling thread until the condition variable is signaled. The argument is a pointer to the pthread_cond_t instance. The second argument is a pointer to the pthread_mutex_t mutex instance.
When pthread_cond_wait is called, the mutex must already be locked by the calling thread. That function atomically unlocks the mutex and blocks on the condition variable. When the condition variable is signaled and the calling thread unblocks, pthread_cond_wait automatically reacquires a lock on the mutex.
Whenever your program performs an action that may change the sense of the condition you're protecting with the condition variable, it should perform these steps. (In our example, the condition is the state of the thread flag, so these steps must be taken whenever the flag is changed.)
1. Lock the mutex accompanying the condition variable.
2. Take the action that may change the sense of the condition (in our example, set the flag).
3. Signal or broadcast the condition variable, depending on the desired behavior.
4. Unlock the mutex accompanying the condition variable.
Listing 4.14 shows the previous example again, now using a condition variable to protect the thread flag. Note that in thread_function, a lock on the mutex is held before checking the value of thread_flag. That lock is automatically released by pthread_cond_wait before blocking and is automatically reacquired afterward. Also note that set_thread_flag locks the mutex before setting the value of thread_flag and signaling the mutex.
#include <pthread.h>
int thread_flag;
pthread_cond_t thread_flag_cv;
pthread_mutex_t thread_flag_mutex;
void initialize_flag ()
{/* Initialize the mutex and condition variable. */
pthread_mutex_init (&thread_flag_mutex, NULL);
pthread_cond_init (&thread_flag_cv, NULL);
/* Initialize the flag value. */
thread_flag = 0;
}
/* Calls do_work repeatedly while the thread flag is set; blocks if
the flag is clear. */
void* thread_function (void* thread_arg)
{/* Loop infinitely. */
while (1) {/* Lock the mutex before accessing the flag value. */
pthread_mutex_lock (&thread_flag_mutex);
while (!thread_flag)
/* The flag is clear. Wait for a signal on the condition
variable, indicating that the flag value has changed. When the
signal arrives and this thread unblocks, loop and check the
flag again. */
pthread_cond_wait (&thread_flag_cv, &thread_flag_mutex);
/* When we've gotten here, we know the flag must be set. Unlock
the mutex. */
pthread_mutex_unlock (&thread_flag_mutex);
/* Do some work. */
do_work ();
}
return NULL;
}
/* Sets the value of the thread flag to FLAG_VALUE. */
void set_thread_flag (int flag_value)
{/* Lock the mutex before accessing the flag value. */
pthread_mutex_lock (&thread_flag_mutex);
/* Set the flag value, and then signal in case thread_function is
blocked, waiting for the flag to become set. However,
thread_function can't actually check the flag until the mutex is
unlocked. */
thread_flag = flag_value;
pthread_cond_signal (&thread_flag_cv);
/* Unlock the mutex. */
pthread_mutex_unlock (&thread_flag_mutex);
}
The condition protected by a condition variable can be arbitrarily complex. However, before performing any operation that may change the sense of the condition, a mutex lock should be required, and the condition variable should be signaled afterward.
A condition variable may also be used without a condition, simply as a mechanism for blocking a thread until another thread "wakes it up." A semaphore may also be used for that purpose. The principal difference is that a semaphore "remembers" the wake-up call even if no thread was blocked on it at the time, while a condition variable discards the wake-up call unless some thread is actually blocked on it at the time. Also, a semaphore delivers only a single wake-up per post; with pthread_cond_broadcast, an arbitrary and unknown number of blocked threads may be awoken at the same time.
Deadlocks can occur when two (or more) threads are each blocked, waiting for a condition to occur that only the other one can cause. For instance, if thread A is blocked on a condition variable waiting for thread B to signal it, and thread B is blocked on a condition variable waiting for thread A to signal it, a deadlock has occurred because neither thread will ever signal the other. You should take care to avoid the possibility of such situations because they are quite difficult to detect.
One common error that can cause a deadlock involves a problem in which more than one thread is trying to lock the same set of objects. For example, consider a program in which two different threads, running two different thread functions, need to lock the same two mutexes. Suppose that thread A locks mutex 1 and then mutex 2, and thread B happens to lock mutex 2 before mutex 1. In a sufficiently unfortunate scheduling scenario, Linux may schedule thread A long enough to lock mutex 1, and then schedule thread B, which promptly locks mutex 2. Now neither thread can progress because each is blocked on a mutex that the other thread holds locked.
This is an example of a more general deadlock problem, which can involve not only synchronization objects such as mutexes, but also other resources, such as locks on files or devices. The problem occurs when multiple threads try to lock the same set of resources in different orders. The solution is to make sure that all threads that lock more than one resource lock them in the same order.