락을 써서 동기화를 수행하다 보면 필연적으로 데드락이라는 부작용이 생길 수 있습니다. 이번 영상에서는 데드락이 무엇이고, 발생하는 이유와 해결 방법을 배우게 됩니다. 개발자가 데드락을 알아야 하는 이유는 데드락에 빠지면 더 이상 프로세스나 스레드가 진행하지 못하기 때문입니다.
참고로, 데드락은 OS에서 등장하는 개념이기도 하지만 DB에서도 등장하는 개념이라서 잘 알고 계시는 것이 좋습니다.

데드락(Deadlock)

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

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

Mutual exclusion

리소스(resource)를 공유해서 사용할 수 없다. 즉, 하나의 스레드의 동작이 끝난 후 리소스를 사용한다.

Hold and wait

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

No preemption

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

Circular wait

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

OS의 데드락 해결 방법

1. 데드락 방지

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

1. Mutual exclusion 방지 : 리소스를 공유 가능하게 한다.(현실적으로 불가능하다. race condition의 위험)

2. Hold and wait 방지 : 사용할 리소스들을 모두 획득한 뒤에 시작, 리소스를 전혀 가지지 않은 상태에서만 리소스 요청(리소스 사용 효율이 떨어진다. 리소스를 모두 획득하지 못하면 계속해서 대기 하는 상황이 발생한다.(starvation))

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

4. circular wait 방지 : 모든 리소스에 순서 체계를 부여해서 오름차순으로 리소스를 요청. 1번을 획득하고 4번을 획득해야 한다.

2. 데드락 회피

실행 환경에서 추가적인 정보를 활용해서 데드락이 발생할 것 같은 상황을 회피한다.
=> 추가적 정보(현재 사용 가능한 리소스, 이미 누군가에게 할당된 리소스, 미래에 있을 리소스 요청 정보)

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

3. 데드락 감지와 복구

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

복구 전략

1. 데드락이 발생하면 프로세스를 종료한다.(모든 프로세스 종료 or 프로세스 한개씩 종료)

2. 데드락이 발생하면 다른 프로세스가 리소스의 일시적인 선점을 허용한다.

4. 데드락 무시

데드락이 발생해도 운영체제는 관여하지 않고, 개발자가 해결한다.

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

예제

lock1과 lock2는 별도의 락(리소스)이며 t1이 lock1을 획득한 후 lock2를 획득해야 하고 t2는 lock2를 획득한 후 lock1을 획득해야한다.

t1이 lock1를 획득하고 lock2를 획득하려할 때 이미 t2에의해 lock2를 획득할 수가 없는 상태이며, t2도 lock1을 획득할 수 없는 상태이다.
=> Deadlock, 교착상태

생각해보자. 프로그래밍 단계에서 반드시 mutual exclusion을 확보해야하는가? mutual exclusion 없이도 해결할 수 있는가?

Mutual exclusion이 반드시 필요하다.

t2도 t1처럼 lock1을 획득하고 lock2를 획득하게 하면 어떻게 될까? circular wait를 방지한다. lock1를 먼저 획득한 스레드가 리소스를 사용하며 데드락을 방지 할 수 있다.

반드시 중첩, hold and wait가 필요한가?

Thread t1 = new Thread(()->{
	synchronized(lock1){
    	System.out.println("[t1] get lock1");
    }
    
    synchronized(lock2){
    	System.out.println("[t1] get lock2");
    }
});
// lock1을 획득한 후 lock2를 획득하는게 아닌,
// 별도로 분리하여 서로에게 영향을 받지 않게 한다.

출처 : 쉬운코드 유튜브