dead.so

berkeley db 4.6.21的源码。berkeley db是一个简单的数据库管理系统

m4_comment([$Id: dead.so,v 10.21 2005/12/02 17:27:50 alanb Exp $])

m4_ref_title(Locking Subsystem,
    Deadlock detection, @deadlocks, lock/stdmode, lock/timeout)

m4_p([dnl
Practically any application that uses locking may deadlock.  The
exceptions to this rule are when all the threads of control accessing
the database are read-only or when the m4_cam product is used; the
m4_cam product guarantees deadlock-free operation at the expense of
reduced concurrency.  While there are data access patterns that are
deadlock free (for example, an application doing nothing but overwriting
fixed-length records in an already existing database), they are
extremely rare.])

m4_p([dnl
When a deadlock exists in the system, all the threads of control
involved in the deadlock are, by definition, waiting on a lock.  The
deadlock detector examines the state of the lock manager and identifies
a deadlock, and selects one of the lock requests to reject.  (See
m4_link(M4RELDIR/ref/lock/config, [Configuring locking]) for a
discussion of how a participant is selected).  The m4_ref(lock_get) or
m4_ref(lock_vec) call for which the selected participant is waiting then
returns a m4_ref(DB_LOCK_DEADLOCK) error.  When using the m4_db access
methods, this error return is propagated back through the m4_db database
handle method to the calling application.])

m4_p([dnl
The deadlock detector identifies deadlocks by looking for a cycle in
what is commonly referred to as its "waits-for" graph.  More precisely,
the deadlock detector reads through the lock table, and reviews each
lock object currently locked.  Each object has lockers that currently
hold locks on the object and possibly a list of lockers waiting for a
lock on the object.  Each object's list of waiting lockers defines a
partial ordering.  That is, for a particular object, every waiting
locker comes after every holding locker because that holding locker must
release its lock before the waiting locker can make forward progress.
Conceptually, after each object has been examined, the partial orderings
are topologically sorted.  If this topological sort reveals any cycles,
the lockers forming the cycle are involved in a deadlock.  One of the
lockers is selected for rejection.])

m4_p([dnl
It is possible that rejecting a single lock request involved in a
deadlock is not enough to allow other lockers to make forward progress.
Unfortunately, at the time a lock request is selected for rejection,
there is not enough information available to determine whether rejecting
that single lock request will allow forward progress or not.  Because
most applications have few deadlocks, m4_db takes the conservative
approach, rejecting as few requests as may be necessary to resolve the
existing deadlocks.  In particular, for each unique cycle found in the
waits-for graph described in the previous paragraph, only one lock
request is selected for rejection.  However, if there are multiple
cycles, one lock request from each cycle is selected for rejection.
Only after the enclosing transactions have received the lock request
rejection return and aborted their transactions can it be determined
whether it is necessary to reject additional lock requests in order to
allow forward progress.])

m4_p([dnl
The m4_ref(db_deadlock) utility performs deadlock detection by calling
the underlying m4_db m4_refT(lock_detect) at regular intervals
(m4_ref(lock_detect) runs a single iteration of the m4_db deadlock
detector).  Alternatively, applications can create their own deadlock
utility or thread by calling the m4_refT(lock_detect) directly, or by
using the m4_refT(dbenv_set_lk_detect) to configure m4_db to
automatically run the deadlock detector whenever there is a conflict
over a lock.  The tradeoffs between using the m4_ref(lock_detect) and
m4_refT(dbenv_set_lk_detect)s is that automatic deadlock detection will
resolve deadlocks more quickly (because the deadlock detector runs
as soon as the lock request blocks), however, automatic deadlock
detection often runs the deadlock detector when there is no need for
it, and for applications with large numbers of locks and/or where many
operations block temporarily on locks but are soon able to proceed,
automatic detection can decrease performance.])

m4_page_footer