# 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.