둘 이상의 프로세스들이 자원을 점유한 상태로 서로 다른 프로세스(스레드)가 점유하는 자원을 요구하면서 기다리는 현상을 말한다.
이 교착상태는 아무렇게 발생하는 것이 아니라 발생하는 조건이 있는데 이 조건을 간단하게 알아보자
상호배제(Mutual Exclusion)
: 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.
점유와 대기(Hold and Wait)
: 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 있는 자원을 추가로 점유하기 위해서 대기하는 프로세스가 있어야 한다.
순환 대기(Circular Wait)
: 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서(사이클) 다른 프로세스의 자원을 요구해야 한다.
비선점(Non-preemption)
: 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.
발생 조건 중에 한 가지 이상을 제거하는 방법
자원의 효율적으로 사용할 수 없기 때문에 잘 사용하지 않는다.
교착상태가 발생할지 체크 후에 발생할 가능성(불완전 상태)이 있다면 자원을 할당하지 않고 데드락을 피해 가는 방법
자원을 빌릴 때마다 시스템을 상태를 파악하기 때문에 오버헤드 발생
자원의 수가 일정해야 한다
따라서 잘 사용하지 않음
현재 시스템에 데드락이 발생했는지를 탐색하는 방법
탐 생하는 은 여러 가지가 있는데 이 중에 가장 대표적인 알고리즘으로는 자원 할당 그래프가 있다.
일반적으로 복구와 함께 사용하며 교착상태가 자주 발생하는 시스템은 대부분 이 방식을 일반적으로 사용함
데드락 상태일 때 교착상태에서 벗어나는 방법
교착 상태의 프로세스를 종료시키거나 자원을 재할당해서 해결한다.
프로세스를 종료시키는 방법을 사용할 경우 종료시키는 프로세스의 기준은 시스템마다 다다르다
각각의 스레드가 위와 같이 자원을 요구하며 대기하는 상태이다.
public class test {
public static void main(String[] args) throws InterruptedException {
Object obj1 = new Object(); //자원1
Object obj2 = new Object(); //자원2
Object obj3 = new Object(); //자원3
Thread t1 = new Thread(new ThreadSync(obj1, obj2), "t1"); //스레드1 -> 자원 1 점유 자원 2 요청
Thread t2 = new Thread(new ThreadSync(obj2, obj3), "t2"); //스레드2 -> 자원 2 점유 자원 3 요청
Thread t3 = new Thread(new ThreadSync(obj3, obj1), "t3"); //스레드3 -> 자원 3 점유 자원 2 요청
t1.start();
Thread.sleep(1000);
t2.start();
Thread.sleep(1000);
t3.start();
}
}
class ThreadSync implements Runnable{
private final Object obj1;
private final Object obj2;
public ThreadSync(Object o1, Object o2){
this.obj1=o1;
this.obj2=o2;
}
@Override
public void run() {
String name = Thread.currentThread().getName();
System.out.println("스레드 "+name + "이 "+obj1+"락 획득 시도");
synchronized (obj1) {
System.out.println("스레드 "+name + "이 "+obj1+"락 획득 성공");
work();
System.out.println("스레드 "+name + "이 "+obj2+"락 획득 시도");
synchronized (obj2) {
System.out.println("스레드 "+name + "이 "+obj2+"락 획득 성공");
work();
}
System.out.println("스레드 "+name + "이 "+obj2+"락 반납");
}
System.out.println("스레드 "+name + "이 "+obj1+"락 반납");
System.out.println(name + "스레드 종료");
}
private void work() {
try {
Thread.sleep(5000); // 한번에 서로의 자원을 요청하기 위한 대기시간
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
스레드 t1이 java.lang.Object@216335a9 자원 획득 시도
스레드 t1이 java.lang.Object@216335a9 자원 획득 성공
스레드 t2이 java.lang.Object@c3d0ec0 자원 획득 시도
스레드 t2이 java.lang.Object@c3d0ec0 자원 획득 성공
스레드 t3이 java.lang.Object@7b3fb7f0 자원 획득 시도
스레드 t3이 java.lang.Object@7b3fb7f0 자원 획득 성공
스레드 t1이 java.lang.Object@c3d0ec0 자원 획득 시도
스레드 t2이 java.lang.Object@7b3fb7f0 자원 획득 시도
스레드 t3이 java.lang.Object@216335a9 자원 획득 시도
다음과 같이 테스트는 종료되지 않고 계속 서로의 자원을 요구하면서 대기한다.
한 개의 행에 여러 클라이언트가 lock을 얻기 위해 대기중 되는 상태
아래의 순서로 쿼리 진행
mysql> START TRANSACTION;
Query OK, 0 rows affected (0.00 sec)
mysql> SELECT * FROM t WHERE i = 1 LOCK IN SHARE MODE;
mysql> START TRANSACTION;
Query OK, 0 rows affected (0.00 sec)
mysql> DELETE FROM t WHERE i = 1;
mysql> DELETE FROM t WHERE i = 1;
client 1의 트랜잭션이 종료되어야(share lock 반납) client 2의 delete와 client 3의 delete가 실행된다.
하지만 client 1의 트랜잭션이 종료되려 먼 client 1의 delete가 실행돼야 하는데 client 1의 delete는 먼저 요청한 client 2의 트랜잭션이 종료되길 기다리고 있다. (lock 획득 대기 중)
즉 끝나지 않는 대기를 계속하게 된다.
결국은 db가 deadlock 해결하기 위해 트랜잭션을 rollback 시키고 아래의 메시지를 준다.
Ref
https://dev.mysql.com/doc/refman/5.7/en/innodb-deadlock-example.html