Computer Science An Overview _J. Glenn *shear _11th Edition
To solve such problems, a DBMS could force transactions to execute in
their entirety on a one-at-a-time basis by holding each new transaction in a
queue until those preceding it have completed. But a transaction often spends
a lot of time waiting for mass storage operations to be performed. By inter-
weaving the execution of transactions, the time during which one transaction
is waiting can be used by another transaction to process data it has already
retrieved. Most large database management systems therefore contain a
scheduler to coordinate time-sharing among transactions in much the same
way that a multiprogramming operating system coordinates interweaving of
processes (Section 3.3).
To guard against such anomalies as the incorrect summary problem and the
lost update problem, these schedulers incorporate a locking protocol in which
the items within a database that are currently being used by some transaction
are marked as such. These marks are called locks; marked items are said to be
locked. Two types of locks are common—shared locks and exclusive locks.
They correspond to the two types of access to data that a transaction might
require—shared access and exclusive access. If a transaction is not going to alter
a data item, then it requires shared access, meaning that other transactions are
also allowed to view the data. However, if the transaction is going to alter the
item, it must have exclusive access, meaning that it must be the only transaction
with access to that data.
In a locking protocol, each time a transaction requests access to a data
item, it must also tell the DBMS the type of access it requires. If a transaction
requests shared access to an item that is either unlocked or locked with a
shared lock, that access is granted and the item is marked with a shared lock.
If, however, the requested item is already marked with an exclusive lock, the
additional access is denied. If a transaction requests exclusive access to an
item, that request is granted only if the item has no lock associated with it. In
this manner, a transaction that is going to alter data protects that data from
other transactions by obtaining exclusive access, whereas several transactions
can share access to an item if none of them are going to change it. Of course,
once a transaction is finished with an item, it notifies the DBMS, and the asso-
ciated lock is removed.
Various algorithms are used to handle the case in which a transaction’s
access request is rejected. One algorithm is that the transaction is merely
forced to wait until the requested item becomes available. This approach, how-
ever, can lead to deadlock, since two transactions that require exclusive access
to the same two data items could block each other’s progress if each obtains
exclusive access to one of the items and then insists on waiting for the other. To
avoid such deadlocks, some database management systems give priority to
older transactions. That is, if an older transaction requires access to an item
that is locked by a younger transaction, the younger transaction is forced to
release all of its data items, and its activities are rolled back (based on the log).
Then, the older transaction is given access to the item it required, and the
younger transaction is forced to start again. If a younger transaction is repeat-
edly preempted, it will grow older in the process and ultimately become one
of the older transactions with high priority. This protocol, known as the
wound-wait protocol (old transactions wound young transactions, young
transactions wait for old ones), ensures that every transaction will ultimately
be allowed to complete its task.