데드락

🎈 Deadlock?

두 개 이상의 프로세스 혹은 스레드가 서로가 가진 리소스를 기다리는 상태

 

 

🎈 데드락을 만드는 네 가지 조건

1. Mutual exclusion

    리소스(resource)를 공유해서 사용할 수 없다.

2. Hold and Wait

    프로세스가 이미 하나 이상의 리소스를 취득한(hold) 상태에서 다른 프로세스가 사용하고 있는 리소스를 추가로 기다린다(wait).

3. No preemption

    리소스 반환(relase)은 오직 그 리소스를 취득한 프로세스만 할 수 있다. 

4. Circular wait

    프로세스들이 순환(circular) 형태로 서로의 리소스를 기다린다.

 

 

🎈 OS의 데드락 해결 방법

1. 데드락 방지

   네 가지 조건 중 하나가 충족되지 않게 시스템을 디자인

#1. Mutual exclusion 방지: 리소스를 공유 가능하게 함. 현실적으로 불가능. 

#2. Hold and wait 방지:

- 사용할 리소스들을 모두 획득한 뒤에 시작

- 리소스를 전혀 가지지 않은 상태에서만 리소스를 요청

#3. No preemption

- 추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 한다. 

#4. Circular wait

- 모든 리소스에 순서 체계를 부여해서 오름차순으로 리소스를 부여. 데드락 방지 방법 중 가장 많이 사용되는 방식.

 

2. 데드락 회피

실행 환경에서 추가적인 정보를 활용해서 데드락이 발생할 것 같은 상황을 회피하는 것

Banker algorithm

: 리소스 요청을 허락해줬을 때 데드락이 발생할 가능성이 있으면 리소스를 할당해도 안전할 때 까지 계속 요청을 거절하는 알고리즘. 

 

3. 데드락 감지와 복구

데드락을 허용하고 데드락이 발생하면 복구하는 전략

복구 전략 1. 프로세스를 종료한다. 

복구 전략 2. 리소스의 일시적인 선점을 허용한다. 

 

4. 데드락 무시

 

 

 

🎈 프로그래밍 레벨에서 데드락

public class Main {
    public static void main(String[] args) {
        Object lock1 = new Object();
        Object lock2 = new Object();
        
        Thread t1 = new Thread(() -> {...});
        
        Thread t2 = new Thread(() -> {...});
        
        t1.start();
        t2.start();
    }
}


Thread t1 = new Thread(() -> {
    synchronized(lock1) {
    	System.out.println("[t1] get lock1");
        synchronized(lock2) {
        	System.out.println("[t1] get lock2");
        }
    }
});


Thread t2 = new Thread(() -> {
    synchronized(lock2) {
    	System.out.println("[t2] get lock2");
        synchronized(lock1) {
        	System.out.println("[t2] get lock1");
        }
    }
});

 

- mutual exclusion을 남발하지 않았는지 확인

mutual exclusion이 반드시 필요한 상황이라면

- lock 취득 순서를 변경하면 circular wait를 방지

- 중첩해서 lock을 취득하려 해서 hold and wait가 발생하므로, 중첩해서 취득하지 않도록하여 데드락 방지