[DB/2-1. Lock-based Protocols]

1️⃣ Lock-based Protocols

---

Lock-based Protocols

locking protocol : set of rules followed by all transactions while requesting and releasing locks

→ 동시성 제어를 위해 개발, 트랜잭션 스케줄을 제어하여 원하는 트랜잭션 스케줄만을 생성하도록 함

 

[ Lock modes ]

• exclusive (X) mode : Read or Write ⇒ lock-X()
• shared (S) mode : Read only ⇒ lock-S()

[ Lock 호환성 ]

	S	X
S	true	false
X	false	false

→ lock-S()끼리만 호환 가능 이외의 것들은 conflict 발생함

 

 

❓lock-X()가 호환되지 않는 이유?

→ lock-X가 호환된다면 write 과정에서 다른 더미 값 들어갈 수도 있기 때문에?

 

 

[ Lock-based Protocols의 특징 ]

• transactions can proceed only after request is granted
• A transaction may be granted a lock on an item if the requested lock is compatible with locks already held on the item by other transactions : compatible한 관계에서만 lock 확보 가능
  • any numbers of transactions can hold shared locks on an item
  • If any transaction holds an exclusive on the item, no other transaction may hold any lock on the item ⇒ lock-X는 호환 불가
• If a lock cannot be granted, the requesting transaction is made to wait till all incompatible locks held by other transactions have been released
  • The lock is then granted
• 모든 읽기/쓰기 연산에 대해 록 보유해야 함.
• 해당 데이터에 대한 록을 받지 못하여 기다리는 트랜잭션은 다른 트랜잭션에 부여된 충돌 록이 해제될 때까지 기다리고, 후에 트랜잭션이 해제되면 데이터에 대한 록을 받고 해당 연산을 수행함.

 

[ example ]

lock-S(A)

read(A)

unlock(A)

lock-S(B)

read(B)

unlock(B)

display(A+B)

⇒ 이러한 트랜잭션은 serializability 보장 X (read(A), read(B), display(A+B) 사이에 값이 바뀔 수 있기 때문)

 

---

Two-phase Locking Protocol (=2PL)

: 2단계 locking 규약

 

[ 2PL 과정 ]

1단계 : growing phase (→ lock 거는 것만)

• Transaction may obtain locks
• Transaction may not release locks

2단계 : shrinking phase (→ lock 푸는 것만)

• Transaction may release locks
• Transaction may not obtain locks

[ 2PL 특징 ]

• serializability 보장 ( Ensures to produce conflict serializable schedule)
• It can be proved that the transactions can be serialized in the order of their lock points
• 2PL does not ensure freedom from deadlocks
• Cascading rollback is possible under 2PL
  • 방지하기 위해? “strict 2PL” or “Rigorous 2PL” 사용
    • strict 2PL
    • : a transaction must hold all its exclusive locks till its commit/aborts (⇒ lock-X()를 unlock하는 시점? commit/abort 후에)
    • rigorous 2PL : all locks are held till commit / abort (모든 lock을 푸는 시점? commit/abort 후에)

---

Lock Conversions

: 2PL의 확장 (2PL with lock conversions)

First phase : upgrade(S→X)

• Can acquire a lock-S on item
• Can acquire a lock-X on item
• Can convert a lock-S to a lock-X (upgrade)

Second phase: downgrade (X→S)

• Can release a lock-S
• Can release a lock-X
• Can convert a lock-X to a lock-S (downgrade)

⇒ serializability 보장

---

Why 2PL ensures conflict serializability

“왜 2PL이 conflict serializability를 보장하는가”에 대한 증명

① 2PL이 serializability를 보장하지 않는다고 가정 → precedence graph 에 cycle 존재

② Cycle이 T0 → T1 → … → T1 → T0 이라고 가정 (ɑi가 Ti라는 트랜잭션이 last lock을 얻는 시점이라고 보자)

      Ti → Tj라는 트랜잭션에 대해 ɑi < ɑj가 성립함.

③ 따라서 T0 → T1 → … T1 → T0에 대해서 ɑ0 < ɑ1 < … < ɑ1 < ɑ2 성질을 가짐

④ ɑ0 < ɑ0은 모순적이기에, 상기 cycle은 존재

할 수 없음.

∴ 2PL은 serializability 보장함

---

Automatic Acquisition of Locks

A transaction Ti issues the standard read/write instruction without explicit locking calls

-> lock에 대한 획득/철회는 사용자의 요구에 의해 운영되는 것이 아니라 시스템 내부에서 자동으로 운영됨

 

ex. read()에 대한 lock 획득 과정

 

 

ex. write()에 대한 lock 획득 과정

 

• write lock은 호환성이 없으므로 반드시 배타적으로 lock 획득해야 한다.
• 트랜잭션이 쓰기 록을 획득하고자 할 때 타트랜잭션이 동일 데이터에 대하여 록을 보유하고 있거나 또는 타트랜잭션이 록을 기다리고 있으면, 록 획득을 요구하는 트랜잭션은 기다려야 한다. (waiting queue에서 기다림)

---

Implementation of Locking

• lock manager는 트랜잭션이 잠금 및 잠금 해제 요청을 보내는 별도의 프로세스로 구현될 수 있음
• The lock manager는 lock grant message를 보내며 lock 요청에 대해 응답
• 요청한 트랜잭션은 응답될 때까지 기다림
• lock manager은 granted lock과 pending request를 기록하기 위해 lock table이라는 자료구조를 가지고 있음 (→ in-memory hash table)
  • • A lock manager can be implemented as a separate process to which transactions send lock and unlock requests
    • The lock manager replies to a lock request by sending a lock grant messages (or a message asking the transaction to roll back in case of a deadlock)
    • The requesting transaction waits until its request is answered
    • The lock manager maintains a data structure called a lock table to record granted locks and pending requests
    • The lock table is usually implemented as an in-memory hash table indexed on the name of the data item being locked

---

Lock Table

• - 검은색 : lock 할당, 흰색 : 요청 대기 중

ex. 첫번째 칸은 hash[0]임 → hash값이 0인 모든 트랜잭션의 lock 정보를 가지고 있음.

I7이라는 data에 대해 T23 Transaction이 lock 정보를 갖고 잇음

I23 data는 T1, T8에 lock-S가 허용되어 있고, 응답을 기다리는 T2가 있음. (T2가 요구하는 것은 lock-X여야 함)

---

Deadlock

• T3, T4 둘 다 실행되지 않음
• : executing lock-S(B) causes T4 to wait for T3 to release its lock on B, while executing lock-X(A) causes T3 to wait for T4 to release its lock on A

⇒ 해결책

: T3 or T4 중 하나 선택해서 Roll Back 시킴 (victim_희생자)

 

 

lock을 사용하는 concurrency control에서는 deadlock 발생 가능

2개 이상의 트랜잭션이 무한정 기다리는 상태 → deadlock

---

Starvation

Starvation is also possible if concurrency control manager is badly designed (기아 상태)

(ex. 앞서 선정한 victim만 계속 선정되어 roll back하게 되면 → starvartion 발생)

⇒ deadlock은 방지할 수 없지만 starvation은 방지해야 함!

---

Graph-based Protocol

2PL의 대안? graph-based Protocol

• 한방향으로 접근하면 cycle이 생기지 않는다는 것 이용
• ex. tree-based protocol

[ Graph-based Protocol의 특징 ]

• conflict serializability & freedom from deadlock 보장
• 2PL과 비교해서
  • 짧은 대기 시간 (바로 unlock할 수 있기 때문)
  • 동시성 증가
  • deadlock free (→ no rollbacks are required)

---

Tree-based Protocol

• Only exclusive locks are allowed
• The first lock by Ti may be on any data item
• Subsequently, a data Q can be locked by Ti only if the parent of Q is currently locked by Ti
• Data items may be unlocked at any time
• A data item that has been locked and unlocked by Ti cannot subsequently be relocked by Ti
• 록 해제는 제약 없이 가능하여 록 해제하고 다시 록을 요구할 수 있음
  • 다만, 한번 록을 획득하고 해제한 데이터 항목에 대해서는 다시 록을 잡을 수 없음
• 트리 기반 규약은 트랜잭션이 록을 해제하였다가도 후에 새로운 록을 획득할 수 있음