If you want to stop two people using a single room
at the same time, an obvious technique is to provide the room with a lock, and the people with a single key. Locks in concurrent systems are a logical extension of this.
Locks are divided into two classes:
Shared (;SPM_quot;read;SPM_quot;) Locks
Shared locks are used to exclude updates, but allow shared read only access
to an object from a transaction. [Recall, in our print spooler example
there are no problems with concurrent ;SPM_quot;List;SPM_quot; operations, but ;SPM_quot;Add;SPM_quot;
should be exclusive of ;SPM_quot;List;SPM_quot;).
Exclusive (;SPM_quot;write;SPM_quot;) Locks
Exclusive locks exclude all other accesses and are used for write/update
access to an object from a transaction.
When a transaction starts, and then attempts to acquire appropriate
locks on the items/objects it is going to access. When it is done with these
items, it releases the locks.
This mechanism is known as <#641#> two phase locking<#641#>.
To maximize the concurrency in the system, the right locks must be used the right way:
Locks should apply to the smallest granularity of object sensible.
For instance, two processes accessing different records in a file should not
Locks should be released as early as possible.
For instance, when a read lock can be released as soon as the appropriate value
has been read, but a write lock cannot be released until the entire transaction
involving the write operation is complete. Otherwise, other transactions could
be affected by an intermediate state of this transaction. However, it
is safest to hold both read an write locks until the end (I
believe this is the usual practice). Consider the following#fnearlylock#643>:
Figure:Releasing Read Locks Early
If T1 releases an reclaims its read lock on y, there could be
Locks should be acquired in the same order when accessing the same object.
This last point is vital for avoiding deadlock.
As we saw in chapter two, deadlock is caused by two concurrent processes
acquiring resources that the other requires; in this case the resource is the
lock (right to access the object). Deadlock can be dealt with either by
avoidance or detection.
Deadlock avoidance involves imposing some ordering on the transactions in the
system This is problematic, as transactions may be data dependent; that is ,
it may not be known in advance what will be the set of transactions the system
Transactions or locks may be timed out. This will lead to failure/aborts and
retries, which may mean undue work, and may not stop the same situation
arising again (possibly immediately), although suitably randomized timeouts
Thirdly, one can allow deadlock to occur, and detect it, and then abort some
suitably random selection of transactions. Detection is based on keeping a list
of all the processes waiting for and holding each lock (or resource). By scanning
this list (;SPM_quot;Wait For Graph;SPM_quot;), we can detect deadlock by the presence of loops.
In a distributed transaction system, deadlock is very much harder to detect
since the processes executing transactions/locks are distributed, and no
single machine can reliably hold the Wait For Graph for the whole system.
If it is possible to choose sensible values, we can use the timeout mechanism
to abandon potentially deadlocked distributed transactions. However, as we have
discussed, the communications system often has effectively
unbounded delays in delivering a (correct) message, so we may abort successful
transactions unnecessarily. There is an engineering tradeoff to be decided by
measuring the values for an actual system. Some systems do not require
absolute consistency - it may be acceptable for different users to
perceive different levels of accuracy in the information they receive
[e.g. weather forecasts at sea are more important to ships than