Deadlock.md

교착상태란?

Deadlock이라고 쓰며 두 개 이상의 트랜잭션이 특정 자원(테이블 또는 행)의 잠금(Lock)을 획득한채 다른 트랜잭션이 소유하고 있는 잠금을 요구하면서 아무리 기다려도 상황이 바뀌지 않는 상태

결과적으로 아무것도 완료되지 못하는 상태를 말한다.

흔히 발생할 수 있는 문제지만 일반적인 해결방법은 아직 없는 상태다.

• 잠금이란? 잠금(Lock)과 트랜잭션은 서로 비슷한 개념 같지만 사실 잠금은 동시성을 제어하기 위한 기능이고 트랜잭션은 데이터의 정합성을 보장하기 위한 기능이다. 잠금은 여러 커넥션에서 동시에 동일한 자원을 요청할 경우 순서대로 한 시점에는 하나의 커넥션만 변경할 수 있게 해주는 역할을 한다. 여기서 자원은 레코드나 테이블을 말한다. 이와는 조금 다르게 트랜잭션은 꼭 여러 개의 변경 작업을 수행하는 쿼리가 조합되었을 때만 의미있는 개념은 아니다. 트랜잭션은 하나의 논리적인 작업 셋 중 하나의 쿼리가 있든 두 개 이상의 쿼리가 있든 관계없이 논리적인 작업 셋 자체가 100% 적용되거나 아무것도 적용되지 않아야 함을 보장하는 것이다. 예를 들면 HW 에러 또는 SW 에러와 같은 문제로 인해 작업에 실패가 있을 경우, 특별한 대책이 필요하게 되는데 이러한 문제를 해결하는 것이다.

교착상태의 4가지 조건

• E.G 코프만 교수가 말하는 교착상태가 일어나기위한 4가지 필요 조건

1. 상호배제(Mutual Exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.
2. 점유대기(Hold and Wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
3. 비선점(Non-preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때 까지 그 자원을 뺏을 수 없다.
4. 순환대기(Circular Wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

• 여기서 4. 순환대기 조건은 2. 점유대기 조건과 3. 비선점 조건을 만족해야 성립하므로 위 4가지 조건들은 서로 완전히 독립적인 형태는 아니다.

교착상태의 해결방안

교착상태는 일어나기위한 4가지 필요조건을 모두 충족해야하기 때문에 위의 4가지 조건중 하나를 막음으로써 교착상태에 대응하게 된다.

1. 예방

   1. 상호배제 조건 부정(제거) : 한번에 여러개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
   2. 점유대기 조건 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구하도록 한다.
   3. 비선점 조건 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고 요구한 자원을 사용하기 위해 기다리게 한다.
   4. 순환대기 조건 부정 : 자원을 선형 순서로 분류하여 고유번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 한다.

2. 회피 교착 상태가 발생하기 전 교착 상태를 예상하여 안전상태에서만 자원 요청을 허용함

   Safe state(안전상태) : Safe sequence가 존재하여 모든 프로세스가 정상적으로 종료할 수 있는 상태

   Safe sequence(안전순서) : 교착 상태를 발생시키지 않고 자원을 할당하는 순서

   1. 자원할당 그래프 알고리즘 : 자원 유형마다 인스턴스가 있는 경우 사용가능하다.

      방법

      • 자원 할당 그래프에 예약 간선을 추가합니다.
        • 예약 간선(claim edge) : 향후 요청할 수 있는 자원을 가리키는 점선으로 표시된 간선
      • 프로세스 시작 전에 모든 예약 간선들을 자원할당 그래프에 표시합니다.
      • 프로세스는 예약 간선으로 설정한 자원에 대해서만 요청할 수 있고 주기가 형성되지 않을 때에만 자원을 할당 받습니다.

      예)

      다음 그래프에서 프로세스 P2가 자원 R2를 요청하여 자원을 할당받는다면

      

      다음과 같이 주기(cycle)가 발생하므로 자원을 요청을 승인할 수 없습니다.

      

      반대로 프로세스 P1이 자원 R2를 요청하여 자원을 할당받는다면 주기가 발생하지 않아 자원을 요청하여 할당받을 수 있습니다.

      • 요청선 : 프로세스에서 자원으로 연결 된 섬 (나 저 자원 쓰고 싶다~라고 요청한다고 보면 됨)
      • 할당선 : 자원에서 프로세스로 연결 된 섬 (이 자원은 이 프로세서가 쓰고 있음을 나타냄)

      참고자료 : https://wannabe-gosu.tistory.com/26

   2. 은행원 알고리즘 : 각 자원 유형마다 다수의 인스턴스를 갖는 경우 사용가능하다.

      방법

      • 프로세스 시작시 자신이 필요한 각 자원의 최대(Max) 개수를 미리 선언합니다.
      • 각 프로세스에서 자원요청이 있을때 요청을 승인하면 시스템이 안전한 상태(safe state)로 유지되는 경우에만 자원을 할당합니다.
      • 불안정 상태(unsafe state)가 예상되면 다른 프로세스가 끝날 때까지 대기를 합니다.

      참고자료 : https://chanhuiseok.github.io/posts/cs-2/

   • 사실 이 같은 방법은 최대 자원 요구량도 알아야하고 할당할 수 있는 자원수가 일정하는 등 제약조건이 많고 자원이용도 하락같은 단점이 존재한다.

3. 발견 (및 회복)

   먼저 시스템이 교착상태 예방이나 회피법을 사용하지 않았을 때, 교착상태가 발생할 수 있으니 여기에서 탐지하고 회복하는 알고리즘을 사용한다.

   • 탐지기법(발견) : Allocation, Request, Available 등으로 시스템에 교착상태가 발생했는지 여부를 탐지합니다. (은행원 알고리즘 방식과 유사하다고 함)
   • 회복기법
     • 교착상태에 빠진 모든 프로세스를 중단시키기 : 부분 결과가 폐기될수있는 부작용 존재
     • 프로세스를 하나씩 중단시킬 때 마다 탐지 알고리즘으로 교착상태를 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이되는 작업일 수 있음

4. 무시

   예방이나 회피 기법을 사용하면 성능에 영향을 미칠 수 있기 때문에 교착상태 발생 확률이 비교적 낮은 경우 별다른 조치를 취하지 않는다.

교착상태의 예(MySQL)

MySQL MVCC에 따른 특성 때문에 트랜잭션에서 갱신 연산(Insert, Update, Delete)를 실행하면 잠금을 획득한다. (기본은 행에 대한 잠금)

트랜잭션 1이 테이블 B의 첫번째 행의 잠금을 얻고 트랜잭션 2도 테이블 A의 첫번째 행의 잠금을 얻었다고 하자.

`Transaction 1> create table B (i1 int not null primary key) engine = innodb; Transaction 2> create table A (i1 int not null primary key) engine = innodb;

Transaction 1> start transaction; insert into B values(1); Transaction 2> start transaction; insert into A values(1);`

트랜잭션을 commit 하지 않은채 서로의 첫번째 행에 대한 잠금을 요청하면

Transaction 1> insert into A values(1); Transaction 2> insert into B values(1); ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

Deadlock 이 발생한다. 일반적인 DBMS는 교착상태를 독자적으로 검출해 보고한다.

교착 상태의 빈도를 낮추는 방법

• 트랜잭션을 자주 커밋한다.
• 정해진 순서로 테이블에 접근한다. 위에서 트랜잭션 1 이 테이블 B -> A 의 순으로 접근했고, 트랜잭션 2 는 테이블 A -> B의 순으로 접근했다. 트랜잭션들이 동일한 테이블 순으로 접근하게 한다.
• 읽기 잠금 획득 (SELECT ~ FOR UPDATE)의 사용을 피한다.
• 한 테이블의 복수 행을 복수의 연결에서 순서 없이 갱신하면 교착상태가 발생하기 쉽다, 이 경우에는 테이블 단위의 잠금을 획득해 갱신을 직렬화 하면 동시성을 떨어지지만 교착상태를 회피할 수 있다.