polimd/Data Bases 2/lesson_05.md

DB2 - lesson 04

Paraboschi

19 October 2015

Concurrency Control pt.III

Hierarchical locking

Locking can be done upon objects at various level of granularity (tables, sets, whole database)

The objective is to:

• minimize the number of the locks
• recogniziung conflicts as soon as possible.

A typical hierarchy can be:

• table
• page
• tuple
• rule

The lower we put the lock, the higher is concurrency, but also lock manager load is higher.

Enhanced locking scheme

We have 5 lock modes:

• r_lock -> shared lock (SL)
• w_lock -> exclusive lock (XL)

Also intention of locking at lower levels of granularity is defined:

• ISL intention of locking in shared mode
• IXL intention of locking in exclusive mode
• SIXL lock in shared mode with intention of locking in exclusive mode

Conflicts in hierarchical locks

	ISL	IXL	SL	SIXL	XL
ISL	OK	OK	OK	OK	NO
IXL	OK	OK	NO	NO	NO
SL	OK	NO	OK	NO	NO
SIXL	OK	NO	NO	NO	NO
XL	NO	NO	NO	NO	NO

This way i can identify the conflicts based on the requests of the resources.

Hierarchical locking protocol

• Locks are requested starting from the root and going down in the hierarchy
• Locks are released starting from the leaves and then going up in the hierarchy
• To request an SL or ISL lock o a non-root node, a transaction must hold an ISL or IXL lock on its parent node . To request and IXL, XL, or SIXL lock on a non-root node, a transaction must hold a SIXL or IXL lock on its parent.

Example

Transaction 1: IXL(root)
read(P1) SIXL(P1)
write(t3) XL(t3)
read(t8) ISL(P2) SL(t8)

Page 1	Page 2
t1 read	t5
t2 read	t6
t3 write	t7
t4 read	t8 read

Transaction 2: IXL(root) ISL(P1)
read(t2) SL(t2)
read(t4) SL(t4)
write(t5) IXL(P2) XL(t5)
write(t6) XL(t6)

Page 1	Page 2
t1	t5 write
t2 read	t6 write
t3	t7
t4 read	t8

The two transactions (read and write operations) are compatible, in fact we have one type of lock for each resource.

Deadlock

Occurs because concurrent transactions hold and, in turn, require resources held by other transactions

A deadlock is represented by a cycle in the wait-for graph of the resources

Deadlock resolution techniques:

• Timeout: transactions killed after a long wait
• Deadlock prevention: transactions killed when they could be in deadlock
• Deadlock detection: transactions killed then they are in deadlock

Timeout method

A transaction is killed after given waiting, assuing it is involved in a deadlock.
Is the simplest, most used method

Timeout value is system-determined, the problem is choosing a proper value:

• too long: useless waits
• too short: unrequired kills

Deadlock prevention

A possible scheme is:

• Assigning transactions a number (an age)
• killing transactions when older transactions wait for younger transactions

Options for choosing the transaction to kill:

• pre-emptive (killing the waiting transaction)
• non-pre-emptive (killing the requesting transaction)

The problem: too many killings (waiting probability vs deadlock probability)

Deadlock prevention is not used because in any case it generates many killings.

Deadlock detection

Requires an algorithm to find real cycles in the wait-for graph It consumes resources but works well and is the solution used.