Berkeley DB Reference Guide: Transaction Protected Applications
Deadlock Detection
The first component of the infrastructure, deadlock detection, is not so much a requirement specific to transaction protected applications, but rather is necessary for almost all applications where more than a single thread of control will be accessing the database at one time. (It is not required by all such applications, as read-only applications cannot deadlock, however there are a very few applications where the access pattern to the data is sufficiently well structured that deadlock cannot occur.) Regardless, while Berkeley DB automatically handles database locking issues, it is normally possible for deadlock to occur.
When the deadlock actually occurs, what happens is that two (or more) processes (or threads, i.e., any thread of control) that hold locks request other locks that cannot be granted, and will never be granted because one of the processes now waiting holds the resource in question.
For example, consider two processes A and B. Let's say that A obtains an exclusive lock on item X, and B obtains an exclusive lock on item Y. Then, A requests a lock on Y and B requests a lock on X. A will wait until resource Y becomes available and B will wait until resource X becomes available. Unfortunately, since both A and B are waiting, neither will release the locks they hold and neither will ever obtain the resource on which it is waiting. In order to detect that deadlock has happened, a separate process or thread must review the locks currently held in the database. If deadlock has occurred, a victim must be selected, and that victim will then return the error EAGAIN from the database call it was making.
Berkeley DB provides a separate UNIX-style utility which can be used to perform this deadlock detection, named, cleverly enough, db_deadlock. Alternatively, applications can create their own deadlock utility or thread using the underlying lock_detect function, or specify that Berkeley DB run the deadlock detector internally whenever there is a conflict over a lock (see lk_detect for more information).
Deciding how often to run the deadlock detector and which of the deadlocked transactions will be forced to abort when the deadlock is detected is a common tuning parameter for Berkeley DB applications.
