When a thread needs exclusive access to code or some other resource, it requests a lock. If it can, Windows responds by giving this lock to the thread. At this point, nothing else in the system can access the locked code. This happens all the time and is a normal part of any well-written multithreaded application. Although a particular code segment can only have one lock on it at a time, multiple code segments can each have their own lock.
A deadlock arises when two or more threads have requested locks on two or more resources, in an incompatible sequence. For instance, suppose that Thread One has acquired a lock on Resource A and then requests access to Resource B. Meanwhile, Thread Two has acquired a lock on Resource B and then requests access to Resource A. Neither thread can proceed until the other thread's lock is relinquished, and, therefore, neither thread can proceed.
User-mode deadlocks arise when multiple threads, usually of a single application, have blocked each other's access to the same resource. However, multiple threads of multiple applications can also block each other's access to a global/shared resource, such as a global event, or semaphore.
A deadlock is a situation where an application locks up because two or more activities are waiting for each other to finish. This occurs in multithreading software where a shared resource is locked by one thread and another thread is waiting to access it and something occurs so that the thread holding the locked item is waiting for the other thread to execute. A deadlock is a situation where an application locks up because two or more activities are waiting for each other to finish. This occurs in multithreading software where a shared resource is locked by one thread and another thread is waiting to access it and something occurs so that the thread holding the locked item is waiting for the other thread to execute. Addressing deadlocks requires tuning of applications, databases, and systems. When deadlocks are a persistent problem, changes in the design of applications and databases may be needed. Monitor, alert, diagnose, and report on deadlocks with SQL Diagnostic Manager for SQL Server.
Application deadlock example. Some developers simulate cursors by using two or more connections from DB-Library™. One connection performs a select and the other connection performs updates or deletes on the same tables. This can create application deadlocks. For example: Connection A holds a shared lock on a page. WinDbg can be used for native C programs or for managed.NET programs with the SOS debugging extension. I’ll show you how to use WinDbg to debug the Nested-Lock deadlock from Part 1. We’ll use an additional extension called SOSEX, which allows to automatically find deadlocks. Here are the steps to take to debug with WinDbg: 1.
Kernel-mode deadlocks arise when multiple threads (from the same process or from distinct processes) have blocked each others' access to the same kernel resource.
The procedure used to debug a deadlock depends on whether the deadlock occurs in user mode or in kernel mode.
Debugging a User-Mode Deadlock
When a deadlock occurs in user mode, use the following procedure to debug it:
Millionth visitor to this page 11/5/01-Karen Webb!2 Millionth 6/16/20023 Millionth 4 Millionth 5/2/20035 Millionth 9/26/20036 Millionth 2/10/20047 Millionth 6/14/20048 Millionth 9 Millionth 3/10/200510 Millionth 7/25/200511Millionth 12/8/200512 Millionth 4/2/200613 Millionth 8/11/200614 Millionth 15 Millionth 3/23/200716 Millionth 17 Millionth 6/25/200818 Millionth 3/14/200919 Millionth 20 Millionth 8/4/201021 Millionth 3/12/201122 Millionth 1/20/201223 Millionth 24 Millionth 25 Millionth 1/13/201526 Millionth 8/20/2017.
Issue the !ntsdexts.locks extension. In user mode, you can just type !locks at the debugger prompt; the ntsdexts prefix is assumed.
This extension displays all the critical sections associated with the current process, along with the ID for the owning thread and the lock count for each critical section. If a critical section has a lock count of zero, it is not locked. Use the ~ (Thread Status) command to see information about the threads that own the other critical sections.
Use the kb (Display Stack Backtrace) command for each of these threads to determine whether they are waiting on other critical sections.
Using the output of these kb commands, you can find the deadlock: two threads that are each waiting on a lock held by the other thread. In rare cases, a deadlock could be caused by more than two threads holding locks in a circular pattern, but most deadlocks involve only two threads.
Here is an illustration of this procedure. You begin with the !ntdexts.locks extension:
The first critical section displayed has no locks and, therefore, can be ignored.
The second critical section displayed has a lock count of 2 and is, therefore, a possible cause of a deadlock. The owning thread has a thread ID of 0xA3.
You can find this thread by listing all threads with the ~ (Thread Status) command, and looking for the thread with this ID:
In this display, the first item is the debugger's internal thread number. The second item (the
Id field) contains two hexadecimal numbers separated by a decimal point. The number before the decimal point is the process ID; the number after the decimal point is the thread ID. In this example, you see that thread ID 0xA3 corresponds to thread number 4.
You then use the kb (Display Stack Backtrace) command to display the stack that corresponds to thread number 4:
Notice that this thread has a call to the WaitForCriticalSection function, which means that not only does it have a lock, it is waiting for code that is locked by something else. We can find out which critical section we are waiting on by looking at the first parameter of the call to WaitForCriticalSection. This is the first address under Args to Child: '24e750'. So this thread is waiting on the critical section at address 0x24E750. This was the third critical section listed by the !locks extension that you used earlier.
In other words, thread 4, which owns the second critical section, is waiting on the third critical section. Now turn your attention to the third critical section, which is also locked. The owning thread has thread ID 0xA9. Returning to the output of the ~ command that you saw previously, note that the thread with this ID is thread number 6. Display the stack backtrace for this thread:
This thread, too, is waiting for a critical section to be freed. In this case, it is waiting on the critical section at 0x68629100. This was the second critical section in the list generated earlier by the !locks extension.
This is the deadlock. Thread 4, which owns the second critical section, is waiting on the third critical section. Thread 6, which owns the third critical section, is waiting on the second critical section.
Having confirmed the nature of this deadlock, you can use the usual debugging techniques to analyze threads 4 and 6.
Debugging a Kernel-Mode Deadlock
There are several debugger extensions that are useful for debugging deadlocks in kernel mode:
The !kdexts.locks extension displays information about all locks held on kernel resources and the threads holding these locks. (In kernel mode, you can just type !locks at the debugger prompt; the kdexts prefix is assumed.)
The !qlocks extension displays the state of all queued spin locks.
The !wdfkd.wdfspinlock extension displays information about a Kernel-Mode Driver Framework (KMDF) spin-lock object.
The !deadlock extension is used in conjunction with Driver Verifier to detect inconsistent use of locks in your code that have the potential to cause deadlocks.
When a deadlock occurs in kernel mode, use the !kdexts.locks extension to list all the locks currently acquired by threads.
You can usually pinpoint the deadlock by finding one non-executing thread that holds an exclusive lock on a resource that is required by an executing thread. Most of the locks are shared.-->
Deadlock Detection monitors the driver's use of resources which need to be locked -- spin locks, mutexes, and fast mutexes. This Driver Verifier option will detect code logic that has the potential to cause a deadlock at some future point.
The Deadlock Detection option of Driver Verifier, along with the !deadlock kernel debugger extension, is an effective tool for making sure your code avoids poor use of these resources.
Deadlock Detection is supported only in Windows XP and later versions of Windows.
Causes of Deadlocks
A deadlock is caused when two or more threads come into conflict over some resource, in such a way that no execution is possible.
The most common form of deadlock occurs when two or more threads wait for a resource that is owned by the other thread. This is illustrated as follows:
|Thread 1||Thread 2|
Takes Lock A
Takes Lock B
Requests Lock B
Requests Lock A
If both sequences happen at the same time, Thread 1 will never get Lock B because it is owned by Thread 2, and Thread 2 will never get Lock A because it is owned by Thread 1. At best this causes the threads involved to halt, and at worst causes the system to stop responding.
Deadlocks are not limited to two threads and two resources. Three-way deadlocks between three threads and three locks are common -- and even five-part or six-part deadlocks occur occasionally. These deadlocks require a certain degree of 'bad luck' since they rely on a number of things happening simultaneously. However, the farther apart the lock acquisitions are, the more likely these become.
Single-thread deadlocks can occur when a thread attempts to take a lock that it already owns.
The common denominator among all deadlocks is that lock hierarchy is not respected. Whenever it is necessary to have more than one lock acquired at a time, each lock should have a clear precedence. If A is taken before B at one point and B before C at another, the hierarchy is A-B-C. This means that A must never be acquired after B or C, and B must not be acquired after C.
Lock hierarchy should be followed even when there is no possibility of a deadlock, since in the process of maintaining the code it will be easy for a deadlock to be accidentally introduced.
Resources That Can Cause Deadlocks
The most unambiguous deadlocks are the result of owned resources. These include spin locks, mutexes, fast mutexes, and ERESOURCEs.
Resources that are signaled rather than acquired (such as events and LPC ports) tend to cause much more ambiguous deadlocks. It is of course possible, and all too common, for code to misuse these resources in such a way that two threads will end up waiting indefinitely for each other to complete. However, since these resources are not actually owned by any one thread, it is not possible to identify the delinquent thread with any degree of certainty.
The Deadlock Detection option of Driver Verifier looks for potential deadlocks involving spin locks, mutexes, and fast mutexes. It does not monitor the use of ERESOURCEs, nor does it monitor the use of nonowned resources.
Effects of Deadlock Detection
Driver Verifier's Deadlock Detection routines find lock hierarchy violations that are not necessarily simultaneous. Most of the time, these violations identify code paths that will deadlock when given the chance.
To find potential deadlocks, Driver Verifier builds a graph of resource acquisition order and checks for loops. If you were to create a node for each resource, and draw an arrow any time one lock is acquired before another, then path loops would represent lock hierarchy violations.
Driver Verifier will issue a bug check when one of these violations is discovered. This will happen before any actual deadlocks occur.
Note Even if the conflicting code paths can never happen simultaneously, they should still be rewritten if they involve lock hierarchy violations. Such code is a 'deadlock waiting to happen' that could cause real deadlocks if the code is rewritten slightly.
When Deadlock Detection finds a violation, it will issue bug check 0xC4. The first parameter of this bug check will indicate the exact violation. Possible violations include:
Two or more threads involved in a lock hierarchy violation
A resource that is released out of sequence
A thread that tries to acquire the same resource twice (a self-deadlock)
A resource that is released without having been acquired first
A resource that is released by a different thread than the one that acquired it
A resource that is initialized more than once, or not initialized at all
A thread that is deleted while still owning resources
Starting in Windows 7, Driver Verifier can predict possible deadlocks. For example, trying to use the same KSPIN_LOCK data structure both as a regular spin lock and as a stack queued spin lock.
See Bug Check 0xC4 (DRIVER_VERIFIER_DETECTED_VIOLATION) for a list of the bug check parameters.
Monitoring Deadlock Detection
Once Deadlock Detection finds a violation, the !deadlock kernel debugger extension can be used to investigate exactly what has occurred. It can display the lock hierarchy topology as well as the call stacks for each thread at the time the locks were originally acquired.
For best results, the driver in question should be running on a checked build of Windows, since that allows the kernel to obtain more complete run-time stack traces.
There is a detailed example of the !deadlock extension, as well as general information about debugger extensions, in the documentation in the Debugging Tools for Windows package. See Windows Debugging for details.
Activating This Option
You can activate the Deadlock Detection feature for one or more drivers by using Driver Verifier Manager or the Verifier.exe command line. For details, see Selecting Driver Verifier Options.
Application That Can Deadlock Go
At the command line
At the command line, the Deadlock Detection option is represented by Bit 5 (0x20). To activate Deadlock Detection, use a flag value of 0x20 or add 0x20 to the flag value. For example:
The feature will be active after the next boot.
On Windows Vista and later versions of Windows, you can also activate and deactivate Deadlock Detection without rebooting the computer by adding the /volatile parameter to the command. For example:
This setting is effective immediately, but is lost when you shut down or reboot the computer. For details, see Using Volatile Settings.
The Deadlock Detection feature is also included in the standard settings. For example:
Using Driver Verifier Manager
- Select Create custom settings (for code developers) and then click Next.
- Select Select individual settings from a full list.
- Select (check) Deadlock detection.
The Deadlock Detection feature is also included in the standard settings. To use this feature, in Driver Verifier Manager, click Create Standard Settings.