교착 상태(Dead Lock)

✔︎ 교착상태(Dead Lock)

프로세스(스레드)가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태

✔︎ 교착 상태가 발생하는 경우

프로세스1(스레드1), 프로세스2(스레드2)

프로세스1(스레드1)은 프로세스2(스레드2)가 사용하고 있는 자원을 대기하고 있고 프로세스2(스레드2)는 프로세스1(스레드1)이 사용하고 있는 자원을 기다리는 경우 두 프로세스(스레드)는 무한정 대기 상태에 빠진다.

✔︎ 교착 상태 발생 조건

1. 상호배제(mutual exclusion)
   자원은 한번에 한 프로세스(스레드)만 사용할 수 있음

2. 점유 대기(hold and wait)
   최소한 하나의 자원을 점유하고 있으면서 다른 프로세스(스레드)에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스(스레드)가 존재해야 함

3. 비선점(no preemption)
   다른 프로세스(스레드)에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

4. 순환 대기(Circular wait)
   프로세스(스레드)의 집합에서 순환 형태로 자원을 대기하고 있어야함

✔︎ 교착 상태 해결 방법

예방 & 회피

• 예방(prevention)
  교착 상태 발생 조건 중 하나를 제거한다

  • 상호배제 부정: 여러 프로세스가 공유 자원 사용
  • 점유대기 부정: 프로세스 실행전 모든 자원을 할당
  • 비선점 부정: 자원 점유 중인 프로세스(스레드)가 다른 자원을 요구할 때 가진 자원을 반납
  • 순환대기 부정: 자원에 고유번호 할당 후 순서대로 자원 요구

• 회피(avoidance)
  교착 상태 발생 시 피해나가는 방법

  • 은행원 알고리즘
    • 프로세스(스레드)가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태를 회피한다
    • 안정상태이며 자원을 할당하고 그렇지 않으면 다른 프로세스(스레드)가 자원 해지까지 대기

탐지 & 회복

• 탐지(detection)
  교착 상태를 탐지한다(자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오베헤드 발생)

• 회복(recovery)
  교착 상태를 일으킨 프로세스(스레드)를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법

  • 프로세스 종료 방법
    • 교착 상태의 프로세스(스레드)를 모두 중지
    • 교착 상태가 제거될 때까지 하나씩 프로세스(스레드) 중지
  • 자원 선점 방법(선점: 자원을 강제로 뺏음)
    • 교착 상태의 프로세스(스레드)가 점유하고 있는 자원을 선점
    • 우선 순위 낮은 프로세스(스레드)나 수행 횟수가 적은 프로세스(스레드) 위주로 자원 선점

✔︎ 참고

• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/DeadLock.md
• https://github.com/WeareSoft/tech-interview/blob/master/contents/os.md