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 PowCoder代写 加微信 powcoder
• 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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com