교착상태 처리, 예방

# Dead handling 교착상태 처리 

- 트랜잭션이 서로 기다리는 상태

- 교착상태 예방 프로토콜은 교착상태에 절대 들어갈 수 없는 것을 보장한다. - 교착상태에 빠진 트랜잭션의 일부를 롤백시키는 과감한 조치

- 방법1 : 교착상태 예방 규약) 각 트랜잭션이 실행되기전에 데이터들을 미리 준비한다. (predeclaration), 데이터들의 접근 순서 등을 정한다 -> 세세하게 요구하기가 힘들다

- 방법2 : 교착상태 탐지 & 복구기법) 고유성 손실 부담이 있음

 

## 교착상태 예방 액세스 기법

1) 락 요청 순서에 있어서 대기 사이클이 일어나지 않도록, 혹은 필요한 락을 한꺼번에 요청

- * 각 트랜잭션이 실행 전 필요한 모든 락을 요청

단점 : 트랜잭션이 시작하기 전 어떤 데이터 항목에 락이 걸려야 하는지 미리 알기 어려움, 데이터 항목의 이용률이 떨어짐

- * 모든 데이터 항복에 순서를 매긴 다음 트랜잭션이 순서와 동일하게 락을 요청하기

단점 : 트랜잭션이 특정 항목에 락을 걸면 순위 상에 그 항목보다 앞에 있는 항목에는 락을 요청할 수 없도록 하는 것

 

2) 교착상태 복구와 밀접함, 락을 대기하는 것이 교착상태 될 것 같으면, 락을 대기시키고 그 대신 트랜잭션을 롤백

- 선점, 트랜잭션 롤백

- 선점을 제어하기 위해서는 트랜잭션이 유일한 스탬프를 부여한다.

 

  ## 타임스탬프 사용하는 두 가지 교착상태 예방 기법

  상황) Ti 가 Tj에게 주어진 락을 요청

  1. 대기-롤백(wait-die) : 비선점 기법, Ti가 Tj의 타임스탬프보다 작은 경우 ti는 대기, 대기 안하면 Ti롤백

young 라인 Read가 끝날때까지 Old 라인이 기다린다

(a)

(a) young 라인 Read가 끝날때까지 Old 라인이 기다린다 (중간에 Read 동작 다시 하면 일관성이 깨지므로)

(b)

(b) Young라인에서 Write 과정에서 취소(abort)해서 Die

Write(다른값) 을 하게 되면 Old라인에서 Read(다른값)이 되므로 일관성이 깨진다

 

  2. 롤백-대기(wound-wait)

  - 선점 기법. 대기-롤백 기법의 다른 한 부분. Ti의 타임스탬프가 Tj보다 더 큰 경우에만 Ti는 대기. 그렇지 않다면 Tj 롤백

(c)의 경우

(c) : 일관성 유지 위해 Write 시점에서 Die

(d)의 경우

(d) :  Old 트랜잭션이 끝날때까지 Young라인 Waiting

 

하지만, 대기-롤백과 롤백-대기 방법은 불필요한 롤백이 발생한다. 

 

3) 시간 초과 (lock timeout) 기법

- 락을 요청한 트랜잭션이 최대로 지정한 시간만큼만 대기

- 시간안에 락을 얻지 못한다면 해당 트랜잭션은 시간초과로 롤백된 다음 다시 시작

- 대기시간이 길 때 유용한 방법.

- 그러나 시간 설정 기준, 불필요한 지연, 기아현상, 따라서 제한적인 용도로 사용

 

# 교착상태 탐지   

- union find 알고리즘 사용된다