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-&gt;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-&gt;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-&gt;set_errpfx(dbenv, "txnapp");
76	dbenv-&gt;set_errfile(dbenv, stderr);
77<p>
78<b>	/* Do deadlock detection internally. */
79	if ((ret = dbenv-&gt;set_lk_detect(dbenv, DB_LOCK_DEFAULT)) != 0) {
80		dbenv-&gt;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-&gt;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-&gt;err(dbenv, ret, "dbenv-&gt;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