Lock management
The lock manager is invoked by all the processes that want to access the database
requests:
r_lock(T,x,errcode,timeout) w_lock(T,x,errcode,timeout) unlock(T,x)
Copyright By Assignmentchef assignmentchef
if the timeout expires, errcode signals an error and, usually, the transaction rolls back and restarts
Lock tables
Store information for the lock
keep, for each object:
two status bits (to represent the three possible status) counter of transactions sharing the r_lock
counter of the number of waiting processes
being frequently accessed, are maintained in central memory
Hierarchical lock (1)
In many real systems, locks can be requested on objects at different granularity
object hierarcy
Fragment 2
Fragment 1
Fragment n
Hierarchical lock (2)
XL (exclusive lock)
corresponds to write lock of the traditional protocol
SL (shared lock)
corresponds to read lock of the traditional protocol
ISL (intentional shared lock)
expresses the willing of blocking, in a shared manner, one of the descendants of the
current node
IXL (intentional exclusive lock)
expresses the willing of exclusively blocking one of the descendants of the current node
SIXL (shared intentional-exclusive lock)
requests a shared lock on the current node and expresses the willing of exclusively blocking one of the descendants of the current node
Hierarchical lock: protocol
locks are requested from the root going down the tree
lock are released from the locked node going up the tree
a transaction can request a SL or ISL lock on a node, only if it has a ISL or IXL lock on its parent
a transaction can request a IXL, XL, or SIXL lock on a node, only if it already has a SIXL or IXL lock on its parent
Hierarchical lock: example
To request an exclusive lock XL on a tuple:
IXL on the database
IXL on the relation
IXL on the partition to which the tuple belongs (fragment) XL for the tuple
locks are then released in reverse order
Hierarchical lock: granularity
The choice of granularity at which locks are requested is left to application developers, trade-off
Too large
many resources are blocked limits parallelism
Too small
many locks are requested
more work for the lock manager
failure risk after having acquired many resources
Lock in SQL:1999 (1)
Transactions can be classified as:
read only
cannot modify the database content or schema cannot request exclusive locks
read write default
Lock in SQL:1999 (2)
For each transaction, we can indicate an isolation level: read uncommitted
read committed
repeatable read
serializable
All the levels
require strict 2PL for write operations prevent loss of updates
different approaches for read operations
Read uncommitted
No constraints
does not require lock for reading
does not respect exclusive locks of other transactions
can suffer from all the anomalies of concurrent transactions
Read committed
Requires shared locks for read operations
excludes reads of intermediate states does not read uncommitted data
prevents dirty reads
does not guarantee serializability
Repeatable read
Requests strict 2PL also for read operations
tuple-level lock
prevents all the anomalies but ghost insert
Serializable
Requests strict 2PL also for read operations and uses predicate locks
prevents all the anomalies default
Two concurrent transactions are waiting (directly or indirectly) for each other ti waits for tj to release a lock
tj waits for ti to release a lock
The deadlock can involve multiple transactions t1 waits for t2
t2 waits for t3
tn-1 waits for tn tn waits for t1
Deadlock: example
t1: r1(x) w1(y)
t2: r2(y) w2(x)
Sequence of requests: r_lock1(x)
r_lock2(y) r1(x)
w_lock1(y) w_lock2(x)
deadlock
Waiting graph
A node for each transaction
An edge from ti to tj if ti is waiting for a resource locked by tj
There is a deadlock when there is a cycle in the waiting graph
Waiting graph: example
t1: r1(x) w1(y)
t2: r2(y) w2(x)
Sequence of requests: r_lock1(x)
r_lock2(y) r1(x)
w_lock1(y) w_lock2(x)
deadlock
Deadlock: solutions
Three main techniques
deadlock detection deadlock prevention
The transactions wait only for a maximum pre-defined interval (timeout)
When the timer elapses, if the transaction is still waiting a negative answer is returned
the transaction is aborted
The choice of the timeout is a trade-off
too low causes too many unnecessary aborts too high causes delays
It is used by most of the commercial DBMSs because it is simple
Detection and resolution
Detects the presence of cycles in the waiting graph
Does not constraint the behavior of the system but controls lock
tables to detect deadlocks
Different choices for:
when to perform the control
which transaction to kill in case of deadlock?
Prevention
Prevents deadlocks
using prevention techniques that guarantee that there will never be mutual wait
killing transactions that would create cycles: different policies for victim choice
Techniques for preventing mutual wait
Conservative 2PL: allocate locks at the beginning of the transaction it could be not always possible
Ordering among objects: objects must be allocated, by each transaction, according to a predefined order
Kill transactions
Deadlock prevented killing one of the transactions that would generate a cycle
preemptive kill the transaction that has the resource
non-preemptive kill the transaction that asks for the resource
Kill transactions: timestamp (1)
ti requests lock for x tj has lock on x
Non-preemptive (wait-die)
If ts(ti) < ts(tj): ti waits otherwise: abort(ti), then relaunches ti with the same ts(ti) Preemptive (wound-wait) if ts(ti) > ts(tj): ti waits
otherise : abort(tj); then relaunches tj with the same ts(tj)
Kill transactions: timestamp (2)
Killed transactions must restart with the same timestamp they would otherwise risk of being always killed (starvation)
Usually not used by commercial DBMSs
the probability of deadlock is much lower than the probability of a conflict
Kill transactions: no timestamp
ti requests lock for x
tj has lock on x
no waiting
abort(ti), then relaunches ti
cautious waiting
if tj is not waiting: ti waits otherwise ti is aborted
other choices:
kill the transaction that performed less work
Livelock and starvation
A transaction always waits for a lock that is continuously granted to other transactions
Happens when the lock manager does not properly manage the allocation
Starvation
A transaction is always killed
Happens if timestamps are not properly managed
CS: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.