교착 상태(Dead Lock)

• 2개 이상의 프로세스/스레드가 서로가 가진 리소스를 기다림
• 더이상 진행이 안됨

교착 상태 발생 조건

• Mutual Exclusion : 리소스가 공유해서 사용할 수 없는 리소스이다.
• Hold and Wait : 프로세스가 자원을 가지고 있으면서 다른 자원을 기다린다.
• No Preemption : 프로세스가 소유한 리소스를 다른 프로세스는 빼앗을 수 없다.
• Circular Wait : 프로세스가 자원을 기다리는 것이 사이클을 이룬다.

OS의 데드락 해결 방법

데드락 방지

4가지 조건 중 하나가 충족되지 않도록 시스템을 디자인

Mutual Exclusion 방지

• 리소스를 공유할 수 있도록 설계
• 프린터 같이 실제 한번에 사용 못하는 자원 존재
• 값에 대하여 오류 발생
• 사실상 불가능

Hold and Wait 방지

• 사용할 리소스를 모두 획득하고 시작
• 리소스를 전혀 가지지 않은 상태에서만 다른 리소스 요청
• 리소스 사용이 비효율적

No Preemption 방지

• 추가적인 리소스를 기다려야 한다면, 소유한 리소스를 다른 프로세스가 뺏을 수 있도록

Circular Wait 방지

• 모든 리소스에 순서 체계를 부여, 오름차순으로 리소스 요청
• 리소스1과 리소스2가 필요할 때, 리소스1 -> 리소스2 순으로 요청

데드락 회피

실행 환경에서 추가적인 정보로 데드락 발생할 것 같은 상황을 회피

Banker’s Algorithm

• 리소스 요청을 허락했을 때, 데드락 발생 가능성이 있다면 거절
• 데드락 발생 가능성이 없을 때 까지 계속 리소스 요청 거절

데드락 감지와 복구

데드락을 허용하고 발생시 복구

프로세스 종료

• 데드락 발생 시 프로세스 종료
• 데드락이 종료될 때까지 프로세스를 하나씩 종료
• 프로세스 종료 시 할당된 모든 자원 반납

리소스의 일시적인 선점 허용

• 데드락 발생 시 일시적으로 리소스를 뺏을 수 있도록

프로그래밍밍의 데드락 해결 방법

데드락 발생 예시

public class Main {
  public static void main(String[] args) {
    Object lock1 = new Object();
    Object lock2 = new Object();

    Thread t1 = new Thread(() -> {
      synchronized (lock1) {
        // critical section1
        synchronized (lock2) {
          // critical section2
        }
      }
    });
    
    Thread t2 = new Thread(() -> {
      synchronized (lock2) {
        // critical section2
        synchronized (lock1) {
          // critical section1
        }
      }
    });

    t1.start();
    t2.start();
  }
}

데드락 해결 방법

• Mutual Exclusion 사용하지 않고 해결가능 한지
• lock1, lock2이 중첩이 필요한지
• t1, t2 모두 lock1, lock2을 똑같은 순서로 요청하도록