- Berkeley DB Reference Guide:
- Locking Subsystem
|
|
Practically any application that uses locking may deadlock. The only exception to this rule is 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.
The db_deadlock utility performs deadlock detection by calling lock_detect at regular intervals; the lock_detect function runs the Berkeley DB deadlock detector. 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 participants to abort. (See Configuring locking for a discussion of how a participant is selected). The lock_get or 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 interface 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 abortion.
It is possible that aborting a single transaction involved in a deadlock is not enough to allow other transactions to make forward progress. Unfortunately, at the time a transaction is selected for abortion, there is not enough information available to determine whether aborting that single transaction will allow forward progress or not. Because most applications have few deadlocks, Berkeley DB takes the conservative approach, aborting as few transactions 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 transaction is selected for abortion. However, if there are multiple cycles, one transaction from each cycle is selected for abortion. Only after the aborting transactions have received the deadlock return and aborted their transactions can it be determined whether it is necessary to abort additional transactions in order to allow forward progress.
|
|
Copyright Sleepycat Software @ 1.1 log @Initial revision @ text @d1 1 a1 1 @ 1.1.1.1 log @Import: RPM 4.0.3 @ text @@ 1.1.1.2 log @Import: RPM 4.0.4 @ text @d1 1 a1 1 d14 1 a14 1
d24 1
a24 1
DB_ENV->lock_detect at regular intervals; the DB_ENV->lock_detect function runs
d28 2
a29 2
manager and identifies a deadlock, and selects one of the lock requests
to reject. (See Configuring locking
d31 1
a31 1
DB_ENV->lock_get or DB_ENV->lock_vec call for which the selected
d47 16
a62 17
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.
|
@
1.1.1.3
log
@Import: RPM 4.0.5
@
text
@d1 2
a2 2
a3 1
d18 17
a34 18
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 interface database handle interface to the calling application. a62 15 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 as 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. @ 1.1.1.4 log @Import: RPM 4.1 @ text @d1 2 a2 2 d4 1 d19 18 a36 17 Practically any application that uses locking may deadlock. The only exception to this rule is 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. The db_deadlock utility performs deadlock detection by calling DB_ENV->lock_detect at regular intervals; the DB_ENV->lock_detect function runs the Berkeley DB deadlock detector. 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 interface to the calling application. d65 15 @ 1.1.1.5 log @Import: RPM 4.1.1 @ text @d1 2 a2 2 a3 1 d18 17 a34 18 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 interface database handle interface to the calling application. a62 15 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 as 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. @ |