Library Version 11.2.5.3

Library Version 12.1.6.1

@@ -22,9 +22,7 @@ - +

Prev	Chapter 16. - The Locking Subsystem -	Chapter 16. The Locking Subsystem	Next

@@ -38,67 +36,85 @@

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 Berkeley DB Concurrent Data Store product is used; the -Berkeley DB Concurrent Data Store 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.

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 -Configuring locking for a -discussion of how a participant is selected). The DB_ENV->lock_get() or -DB_ENV->lock_vec() call for which the selected participant is waiting then -returns a DB_LOCK_DEADLOCK error. When using the Berkeley DB access -methods, this error return is propagated back through the Berkeley DB database -handle method to the calling application.

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.

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, Berkeley 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.

The db_deadlock utility performs deadlock detection by calling -the underlying Berkeley DB DB_ENV->lock_detect() method at regular intervals -(DB_ENV->lock_detect() runs a single iteration of the Berkeley DB deadlock -detector). Alternatively, applications can create their own deadlock -utility or thread by calling the DB_ENV->lock_detect() method directly, or by -using the DB_ENV->set_lk_detect() method to configure Berkeley DB to -automatically run the deadlock detector whenever there is a conflict -over a lock. The tradeoffs between using the DB_ENV->lock_detect() and -DB_ENV->set_lk_detect() methods 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.

+ 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 + Berkeley DB Concurrent Data Store product is used; the + Berkeley DB Concurrent Data Store 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. +

+ 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 Configuring locking for a discussion of how a + participant is selected). The DB_ENV->lock_get() or DB_ENV->lock_vec() call for + which the selected participant is waiting then returns a DB_LOCK_DEADLOCK error. + When using the Berkeley DB access methods, this error return is propagated + back through the Berkeley DB database handle method to the calling + application. +

+ 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. +

+ 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, Berkeley 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. +

+ The db_deadlock utility performs deadlock detection by calling the + underlying Berkeley DB DB_ENV->lock_detect() method at regular + intervals (DB_ENV->lock_detect() runs a single iteration of the + Berkeley DB deadlock detector). Alternatively, applications + can create their own deadlock utility or thread by calling the + DB_ENV->lock_detect() method directly, or by using the + DB_ENV->set_lk_detect() method to configure Berkeley DB to + automatically run the deadlock detector whenever there is a + conflict over a lock. The tradeoffs between using the + DB_ENV->lock_detect() and DB_ENV->set_lk_detect() methods 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. +

@@ -115,7 +131,8 @@ automatic detection can decrease performance.

Home - Deadlock detection using timers + Deadlock detection using + timers