Deadlock (교착 상태)

→ 두 개 이상의 프로세스나 스레드가 서로 상대방의 작업이 끝나기를 기다리며 무한히 대기하는 상황

발생 조건

상호 배제 (Mutual Exclusion)

: 리소스는 한 번에 하나의 프로세스만 사용할 수 있어야 한다. (동시에 여러 프로세스가 리소스 공유 불가능)

점유 대기 (Hold and Wait)

: 프로세스가 최소한 하나의 리소스를 보유하고 있으면서 다른 리소스를 얻기 위해 대기하고 있어야 한다.

비선점 (No Preemption)

: 프로세스가 어떤 리소스를 이미 보유하고 있을 때, 해당 리소스를 다른 프로세스로부터 선점할 수 없어야 한다. 다른 프로세스는 해당 프로세스가 리소스를 자발적으로 반납할 때까지 대기해야 한다.

순환 대기 (Circular Wait)

: 프로세스 간에 리소스 요청 순서가 사이클을 형성하도록 대기 관계가 형성되어야 한다. 한 프로세스가 다음 프로세스의 요청을 대기하고, 다음 프로세스는 그 다음 프로세스의 요청을 대기하며, 마지막 프로세스가 첫 번째 프로세스의 요청을 대기하는 상황

해결 방안

• 데드락이 발생하지 않도록 예방(prevention)
• 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance)
• 데드락 발생을 허용하지만 데드락을 탐지(detection)하여 데드락 회복(recovery)

예방

• 상호배제 부정 → 여러 프로세스가 한번에 한 공유 자원을 사용할 수 있도록
• 점유 대기 부정 → 프로세스 실행 전 필요한 모든 자원을 할당하여, 다른 프로세스에 점유 중인 자원을 대기하지 않도록
• 비선점 부정 → 자원 점유 중인 프로세스가 다른 프로세스에서 사용 중인 자원을 요구할 때 가진 자원 반납하게 하고 요구한 자원 사용하기 위해 대기하도록
• 순환 대기 부정 → 자원에 고유 번호를 할당하여 번호 순서대로 자원을 할당 받도록

회피

• 은행원 알고리즘 → 최소한 고객 한 명에게 대출해줄 금액은 항상 은행이 보유하고 있어야 한다
  : 교착 상태에 빠질 가능성이 있는지 판단하기 위해 상태를 안전 상태와 불안전 상태로 나누고, 안전 상태를 유지할 수 있는 요구만을 수락하고, 불안전 상태를 초래할 수 있는 사용자의 요구는 만족될 수 있을 때까지 계속해서 거절하는 방법.

회복

• 프로세스 종료

  • 교착 상태의 프로세스 모두 종료
  • 교착상태가 해결될 때까지 한 프로세스씩 중지

• 자원 선점

  • 프로세스들로부터 자원을 빼앗아 교착상태가 해결될 때까지 다른 프로세스들에게 자원을 할당

references
👉 https://chanhuiseok.github.io/posts/cs-2/
👉 https://velog.io/@smallcherry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-Deadlock%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C%EC%9D%98-%EC%A0%95%EC%9D%98%EC%99%80-%ED%95%84%EC%88%98%EC%A1%B0%EA%B1%B4-%EC%98%88%EB%B0%A9-%ED%9A%8C%ED%94%BC-%ED%9A%8C%EB%B3%B5-%EA%B8%B0%EB%B2%95 👉 https://jhnyang.tistory.com/102