DATABASE CONTROL ISSUES: SECURITY, BACKUP AND RECOVERY, CONCURRENCY - Fundamentals of Database Management Systems - page 310

Time Mr. White Ms. Black

10:15 A.M. Gets and locks the

record for nuts

10:16 A.M. Gets and locks the

record for bolts

10:17 A.M. Tries to get (and lock)

the record for bolts
but finds it locked by
Ms. Black

10:18 A.M. Tries to get (and lock)

the record for nuts
but finds it locked by
Mr. White

F IGURE 11.8
Deadlock

DEADLOCK!

Proceeding with this scenario, suppose two clerks, Mr. White and Ms. Black, each
request a quantity of nuts and bolts. White happens to list the nuts before the bolts
in his query. At 10:15 AM, he accesses and locks the record for nuts. Ms. Black
happens to list the bolts before the nuts in her query. At 10:16 AM, she accesses
and locks the record for bolts. Then, at 10:17 AM, White tries to access the record
for bolts but finds it locked by Black. And 10:18 AM, Black tries to access the
record for nuts but finds it locked by White. Both queries then wait endlessly for
each other to release what they each need to proceed. This is called '' deadlock ''
or ''the deadly embrace.'' It actually bears a close relationship to the ''gridlock''
traffic problem that major cities worry about during rush hour.
Does the prospect of deadlock mean that locks should not be used? No, because
there are two sorts of techniques for handling deadlock: deadlock prevention and
deadlock detection. Outright deadlock prevention sounds desirable but turns out to
be difficult. Basically, a transaction would have to lock all the data it will need,
assuming it can even figure this out at the beginning of the transaction (often the
value of one piece of data that a program retrieves determines what other data it
needs). If the transaction finds that some of the data it will need is unavailable
because another transaction has it locked, all it can do is release whatever data it
has already locked and start all over again.
So the usual way to handle deadlock is to let it occur, detect it when it does, and
then abort one of the deadlocked transactions, allowing the other to finish. The one
that was backed out can then be run again. One way to detect deadlock is through
a timeout, meaning that a query has been waiting for so long that the assumption
is it must be deadlocked. Another way to detect deadlock is by maintaining a
resource usage matrix that dynamically keeps track of which transactions or users
are waiting for which pieces of data. Software can continuously monitor this matrix
and determine when deadlock has occurred.

Versioning
There is another way to deal with concurrent updates, known as '' versioning ,''
that does not involve locks at all. Basically, each transaction is given a copy or
''version'' of the data it needs for an update operation, regardless of whether any