1<!--$Id: deadlock.so,v 10.20 2002/06/24 14:51:07 bostic 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>Berkeley DB Transactional Data Store Applications</dl></b></td> 14<td align=right><a href="../transapp/admin.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../toc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../transapp/checkpoint.html"><img src="../../images/next.gif" alt="Next"></a> 15</td></tr></table> 16<p align=center><b>Deadlock detection</b></p> 17<p>The first component of the infrastructure, <i>deadlock 18detection</i>, is not so much a requirement specific to 19transaction-protected applications, but instead is necessary for almost 20all applications in which more than a single thread of control will be 21accessing the database at one time. Even when Berkeley DB automatically 22handles database locking, it is normally possible for deadlock to occur. 23Because the underlying database access methods may update multiple pages 24during a single Berkeley DB API call, deadlock is possible even when threads 25of control are making only single update calls into the database. The 26exception to this rule is when all the threads of control accessing the 27database are read-only or when the Berkeley DB Concurrent Data Store product is used; the Berkeley DB Concurrent Data Store 28product guarantees deadlock-free operation at the expense of reduced 29concurrency.</p> 30<p>When the deadlock occurs, two (or more) threads of control each request 31additional locks that can never be granted because one of the threads 32of control waiting holds the requested resource. For example, consider 33two processes: A and B. Let's say that A obtains a write lock on item 34X, and B obtains a write lock on item Y. Then, A requests a lock on Y, 35and B requests a lock on X. A will wait until resource Y becomes 36available and B will wait until resource X becomes available. 37Unfortunately, because both A and B are waiting, neither will release 38the locks they hold and neither will ever obtain the resource on which 39it is waiting. For another example, consider two transactions, A and 40B, each of which may want to modify item X. Assume that transaction A 41obtains a read lock on X and confirms that a modification is needed. 42Then it is descheduled and the thread containing transaction B runs. 43At that time, transaction B obtains a read lock on X and confirms that 44it also wants to make a modification. Both transactions A and B will 45block when they attempt to upgrade their read locks to write locks 46because the other already holds a read lock. This is a deadlock. 47Transaction A cannot make forward progress until Transaction B releases 48its read lock on X, but Transaction B cannot make forward progress until 49Transaction A releases its read lock on X.</p> 50<p>In order to detect that deadlock has happened, a separate process or 51thread must review the locks currently held in the database. If 52deadlock has occurred, a victim must be selected, and that victim will 53then return the error <a href="../../ref/program/errorret.html#DB_LOCK_DEADLOCK">DB_LOCK_DEADLOCK</a> from whatever Berkeley DB call 54it was making. Berkeley DB provides a separate UNIX-style utility that can 55be used to perform this deadlock detection, named <a href="../../utility/db_deadlock.html">db_deadlock</a>. 56Alternatively, applications can create their own deadlock utility or 57thread using the underlying <a href="../../api_c/lock_detect.html">DB_ENV->lock_detect</a> function, or specify 58that Berkeley DB run the deadlock detector internally whenever there is a 59conflict over a lock (see <a href="../../api_c/env_set_lk_detect.html">DB_ENV->set_lk_detect</a> for more 60information). The following code fragment does the latter:</p> 61<blockquote><pre>void 62env_open(DB_ENV **dbenvp) 63{ 64 DB_ENV *dbenv; 65 int ret; 66<p> 67 /* Create the environment handle. */ 68 if ((ret = db_env_create(&dbenv, 0)) != 0) { 69 fprintf(stderr, 70 "txnapp: db_env_create: %s\n", db_strerror(ret)); 71 exit (1); 72 } 73<p> 74 /* Set up error handling. */ 75 dbenv->set_errpfx(dbenv, "txnapp"); 76 dbenv->set_errfile(dbenv, stderr); 77<p> 78<b> /* Do deadlock detection internally. */ 79 if ((ret = dbenv->set_lk_detect(dbenv, DB_LOCK_DEFAULT)) != 0) { 80 dbenv->err(dbenv, ret, "set_lk_detect: DB_LOCK_DEFAULT"); 81 exit (1); 82 }</b> 83<p> 84 /* 85 * Open a transactional environment: 86 * create if it doesn't exist 87 * free-threaded handle 88 * run recovery 89 * read/write owner only 90 */ 91 if ((ret = dbenv->open(dbenv, ENV_DIRECTORY, 92 DB_CREATE | DB_INIT_LOCK | DB_INIT_LOG | 93 DB_INIT_MPOOL | DB_INIT_TXN | DB_RECOVER | DB_THREAD, 94 S_IRUSR | S_IWUSR)) != 0) { 95 dbenv->err(dbenv, ret, "dbenv->open: %s", ENV_DIRECTORY); 96 exit (1); 97 } 98<p> 99 *dbenvp = dbenv; 100}</pre></blockquote> 101<p>Deciding how often to run the deadlock detector and which of the 102deadlocked transactions will be forced to abort when the deadlock is 103detected is a common tuning parameter for Berkeley DB applications.</p> 104<table width="100%"><tr><td><br></td><td align=right><a href="../transapp/admin.html"><img src="../../images/prev.gif" alt="Prev"></a><a href="../toc.html"><img src="../../images/ref.gif" alt="Ref"></a><a href="../transapp/checkpoint.html"><img src="../../images/next.gif" alt="Next"></a> 105</td></tr></table> 106<p><font size=1>Copyright (c) 1996,2008 Oracle. All rights reserved.</font> 107</body> 108</html> 109