2장 연습문제

2.1.

반대로 생성할 수 없다고 가정하자.

T0->Tm->...Tn->T0로 사이클이 존재한다고 가정하자.

일단 2PL의 정의에 의해 

Ti<Tj이면 ai<aj이다.

이때 그렇다면 위 가정에서 시간은 a0<am<...<an<a0이고

a0<a0인 모순이 생기기에 사이클이 생길 수 없다.

∴2PL은 충돌 직렬 가능 스케줄만을 생성한다.

 

2.2.

(a)

T1

locs-s(A)

read(A)

lock-x(B)

read(B)

if A=0 then B:= B+1

write(B)

unlock(A)/unlock(B)

unlock(B)/unlock(A)

 

T2

locs-s(B)

read(B)

lock-x(A)

read(A)

if B=0 then A:= A+1

write(A)

unlock(B)/unlock(A)

unlock(A)/unlock(B)

 

이런 식으로 일부 transaction 실행 순서를 잡으면 deadlock이 발생할 수 있다.

 

2.3. Rigorous 2PL의 장점?

Rigorous 2PL은 일반 2PL과 달리 recoverable하면서 cascadeless함을 보장한다.

 

2.4. 

다음 트리 구조가 주어졌다고 가정하자.

2PL(O) tree(X) 스케줄 예시

2PL(X) tree(O) 스케줄 예시

2.5.

MGL(Multiple Granuarity Locking)에서 어떤 노드에 explicit하게 lock을 걸면 자식 노드에도 lock이 걸리는데

이걸 implicit lock이라 한다.

 

2.6.

X lock이 부모 노드에 걸리고 하위 자식 노드들 중 하나 이상에서 S lock을 거는 것이 XIS인데 이는 충돌이

발생하므로 사용할 가치가 없다.

 

2.7.

dataase에...

S나 SIX가 걸리면 tableA에서 굳이 'S', 'S'IX를 할 필요가 없었으니 적절하지 않고,

IS가 걸리면 row 단계에서 S와 X가 겹칠 수 있기에 안되고,

X가 걸리면 tableA에서 S와 X가 겹치므로 안된다.

IX의 경우엔 row단계에 X가 등장하니 필요하다.

 

∴ IX

 

2.8.

이단계 일치성을 사용하면 isolation을 보장할 수 있게 되어 cascading을 피하고 동시성을 향상시킬 수 있다.

하지만 직렬가능성이 보장되지 않기에 프로그래머가 이를 보장해야 한다.

 

2.9.

팬텀현상은 Insert나 delete로 인해 같은 SQL 쿼리문이나 트랜잭션끼리 서로 도출한 결과 값이 다르거나 논리적으로 불가능한 상황을 의미한다.

2PL 프로토콜을 씀에도 불구하고 옳지 않은 동시성 실행으로 이끄는 이유는 2PL이 데이터의 page가 아닌 tuple에 lock을 걸기 때문이다.

lock이 걸린 tuple에 대해서만 2PL이 적용되고 이외에 insert나 delete 된 tuple은 lock이 걸려있지 않아서 다른 결과를 초래하기 때문이다.

 

2.10.

read-committed 방식은 write lock에 대해서는 트랜잭션이 종료될 때까지 갖고 있기에 cascadeless를 보장한다.

 

2.11.

 

2.12.

 

(1) X, unlock 다음에 lock이 나오므로 

(2) X, A노드 록을 잡은 후 C노드 록을 잡기 전에 C의 부모노드인 B노드 록을 잡아야 하므로

 

2.13.

(a) T2가 T1보다 young하기 때문에 die.

(b) T2가 T3보다 old하기 때문에 T3가 롤백이 되고 T2가 실행된다.

(c) livelock을 방지하기 위해 restart하는 트랜잭션은 원래의 timestamp를 가지고서 실행된다.

 

2.14.

(a) T1이 T3보다 old하기 때문에 wait을 하고 T3는 계속 진행한다.

(b) T2가 T3보다 old하기 때문에 wound를 하고 실행이 되고 T3는 롤백된다.

(c) T1-->T2<--T3

wait-for 그래프에 cycle이 존재하지 않기 때문에 deadlock이 발생하지 않는다.

 

2.15.

(a) 중간중간에 lock을 풀고 값을 read 해와야 하므로 Read uncommitted or Read committed

(b) 결과 값이 보장되려면 Serializable과 Repeatable Read

 

 

2.17.

(1) Rigorous 2PL을 사용하는 동시성 제어 환경에서 트랜잭션의 동일한 직렬 스케줄은 트랜잭션의 완료 순서로 결정됨.

(2) 2PL에서 lock downgrade는 shrinking phase에서만 발생할 수 있다.

(3) record-level lockin을 하는 경우에 phantom 현상이 발생한다.

(4) 팬텀현상은 serializable을 제외한 나머지 3 방식에서 발생한다.

(5) 멀티버젼 타임스탬프 ordering을 이용하여 동시성 제어를 하는 경우, read 연산은 기다림없이 수행이 된다.

(6) Timeout 기법을 쓴다면 deadlock이 발생하지 않는다.

(7) T2가 죽지는 않는다.

(8) 트랜잭션을 재수행 시에는 기존 타임스탬프 값을 사용하고 이를 통해 starvation을 방지한다.

(9) 2PL은 Serializability를 보장하지 Recoverable을 보장하지는 않는다.

 

4가지 실행방식