1<!--$Id: dead.so,v 10.21 2005/12/02 17:27:50 alanb Exp $--> 2<!--Copyright (c) 1997,2008 Oracle. All rights reserved.--> 3<!--See the file LICENSE for redistribution information.--> 4<html> 5<head> 6<title>Berkeley DB Reference Guide: Deadlock detection</title> 7<meta name="description" content="Berkeley DB: An embedded database programmatic toolkit."> 8<meta name="keywords" content="embedded,database,programmatic,toolkit,btree,hash,hashing,transaction,transactions,locking,logging,access method,access methods,Java,C,C++"> 9</head> 10<body bgcolor=white> 11<a name="2"><!--meow--></a> 12<table width="100%"><tr valign=top> 13<td><b><dl><dt>Berkeley DB Reference Guide:<dd>Locking Subsystem</dl></b></td> 14<td align=right><a href="/lock/stdmode.html"><img src="/images/prev.gif" alt="Prev"></a><a href="/toc.html"><img src="/images/ref.gif" alt="Ref"></a><a href="/lock/timeout.html"><img src="/images/next.gif" alt="Next"></a> 15</td></tr></table> 16<p align=center><b>Deadlock detection</b></p> 17<p>Practically any application that uses locking may deadlock. The 18exceptions to this rule are when all the threads of control accessing 19the database are read-only or when the Berkeley DB Concurrent Data Store product is used; the 20Berkeley DB Concurrent Data Store product guarantees deadlock-free operation at the expense of 21reduced concurrency. While there are data access patterns that are 22deadlock free (for example, an application doing nothing but overwriting 23fixed-length records in an already existing database), they are 24extremely rare.</p> 25<p>When a deadlock exists in the system, all the threads of control 26involved in the deadlock are, by definition, waiting on a lock. The 27deadlock detector examines the state of the lock manager and identifies 28a deadlock, and selects one of the lock requests to reject. (See 29<a href="/ref/lock/config.html">Configuring locking</a> for a 30discussion of how a participant is selected). The <a href="/api_c/lock_get.html">DB_ENV->lock_get</a> or 31<a href="/api_c/lock_vec.html">DB_ENV->lock_vec</a> call for which the selected participant is waiting then 32returns a <a href="/ref/program/errorret.html#DB_LOCK_DEADLOCK">DB_LOCK_DEADLOCK</a> error. When using the Berkeley DB access 33methods, this error return is propagated back through the Berkeley DB database 34handle method to the calling application.</p> 35<p>The deadlock detector identifies deadlocks by looking for a cycle in 36what is commonly referred to as its "waits-for" graph. More precisely, 37the deadlock detector reads through the lock table, and reviews each 38lock object currently locked. Each object has lockers that currently 39hold locks on the object and possibly a list of lockers waiting for a 40lock on the object. Each object's list of waiting lockers defines a 41partial ordering. That is, for a particular object, every waiting 42locker comes after every holding locker because that holding locker must 43release its lock before the waiting locker can make forward progress. 44Conceptually, after each object has been examined, the partial orderings 45are topologically sorted. If this topological sort reveals any cycles, 46the lockers forming the cycle are involved in a deadlock. One of the 47lockers is selected for rejection.</p> 48<p>It is possible that rejecting a single lock request involved in a 49deadlock is not enough to allow other lockers to make forward progress. 50Unfortunately, at the time a lock request is selected for rejection, 51there is not enough information available to determine whether rejecting 52that single lock request will allow forward progress or not. Because 53most applications have few deadlocks, Berkeley DB takes the conservative 54approach, rejecting as few requests as may be necessary to resolve the 55existing deadlocks. In particular, for each unique cycle found in the 56waits-for graph described in the previous paragraph, only one lock 57request is selected for rejection. However, if there are multiple 58cycles, one lock request from each cycle is selected for rejection. 59Only after the enclosing transactions have received the lock request 60rejection return and aborted their transactions can it be determined 61whether it is necessary to reject additional lock requests in order to 62allow forward progress.</p> 63<p>The <a href="/utility/db_deadlock.html">db_deadlock</a> utility performs deadlock detection by calling 64the underlying Berkeley DB <a href="/api_c/lock_detect.html">DB_ENV->lock_detect</a> method at regular intervals 65(<a href="/api_c/lock_detect.html">DB_ENV->lock_detect</a> runs a single iteration of the Berkeley DB deadlock 66detector). Alternatively, applications can create their own deadlock 67utility or thread by calling the <a href="/api_c/lock_detect.html">DB_ENV->lock_detect</a> method directly, or by 68using the <a href="/api_c/env_set_lk_detect.html">DB_ENV->set_lk_detect</a> method to configure Berkeley DB to 69automatically run the deadlock detector whenever there is a conflict 70over a lock. The tradeoffs between using the <a href="/api_c/lock_detect.html">DB_ENV->lock_detect</a> and 71<a href="/api_c/env_set_lk_detect.html">DB_ENV->set_lk_detect</a> methods is that automatic deadlock detection will 72resolve deadlocks more quickly (because the deadlock detector runs 73as soon as the lock request blocks), however, automatic deadlock 74detection often runs the deadlock detector when there is no need for 75it, and for applications with large numbers of locks and/or where many 76operations block temporarily on locks but are soon able to proceed, 77automatic detection can decrease performance.</p> 78<table width="100%"><tr><td><br></td><td align=right><a href="/lock/stdmode.html"><img src="/images/prev.gif" alt="Prev"></a><a href="/toc.html"><img src="/images/ref.gif" alt="Ref"></a><a href="/lock/timeout.html"><img src="/images/next.gif" alt="Next"></a> 79</td></tr></table> 80<p><font size=1>Copyright (c) 1996,2008 Oracle. All rights reserved.</font> 81</body> 82</html> 83