DeadLock 발생과 해결 방안

DeadLock(교착 상태)

교착상태는 여러 프로세스나 스레드가 서로 자원을 기다리며 실행이 멈추는 상태를 말한다.
예를 들어 프로세스 A가 프로세스 B의 어떤 자원을 요청할 때 프로세스 B도 프로세스 A가 점유하고 있는 자원을 요청하는 것이다.

DeadLock 원인

교착 상태는 다음 네 가지 조건을 모두 만족할 때 발생한다

• 상호 배제(Mutual exclusion)
  자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다

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

• 비선점(No preemption)
  다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다

• 환형 대기(Circular wait)
  각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있어야 한다

DeadLock 해결방안

교착 상태 예방

• 교착 상태 발생 조건 중 하나를 제거함으로써 해결하는 방법
  • 상호 배제 부정
    • 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다
  • 점유 대기 부정
    • 프로세스가 실행되기 전 필요한 모든 자원을 할당한다
  • 비선점 부정
    • 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다
  • 순환 대기 부정
    • 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다
  • 교착 상태는 필요악
  • 조건 중 하나라도 제거할 경우 자원을 효율적으로 사용할 수 없다
• 현대 시스템에는 자주 사용하지 않음

교착 상태 회피

• 교착 상태를 인정하고 피해가자
• 대표적으로 은행원 알고리즘
• 자원을 요청할 때 마다 시스템의 상태를 판단하고 회피하는 알고리즘을 사용해 오버헤드가 심하게 발생
  -> 현대 시스템에 이러한 오버헤드를 감당할 시스템이 거의 존재하지 않음

은행원 알고리즘

• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법
• 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를 회피하는 기법
• 안정 상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기함
• 교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 이용하는 방법
  운영체제 만화로 알아보는 은행원 알고리즘, 교착상태, 회피 알고리즘

교착 상태 탐지 및 복구

• 교착 상태가 자주 발생하는 시스템에서 일반적으로 사용하는 방법
• 교착 상태 탐지
  • 자원 할당 그래프를 이용해 교착 상태 존재 여부 및 교착 상태에 연관된 프로세스와 자원을 알아냄
  • 순환 대기 존재 여부에 초점을 맞춤
• 교착 상태 복구
  • 순환 대기를 깨서 교착 상태로부터 회복
    1. 순환 대기가 깨질 때 까지 프로세스 종료
    2. 순환 대기에 포함된 프로세스의 제어권을 뺏고 롤백

교착 상태 무시

• 교착 상태가 드물게 발생하는 시스템에서 일반적으로 사용하는 방법
  • 교착 상태를 해결하는데 드는 비용이 더 효율적이지 못하다 판단
  • 만약, 교착 상태가 발생하면 사용자가 직접 프로세스를 죽이거나 재부팅 시켜 해결

Starvation(기아 상태)

• 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁하는 상태
• 우선순위에 의해 특정 프로세스가 영원히 자원을 할당 받지 못하는 상태

Starvation 해결방안

• 프로세스의 우선순위를 수시로 변경한다
• 대기 시간이 긴 프로세스에 우선순위를 부여한다
• 프로세스의 우선순위가 아니라 요청 순서대로 처리하는 FIFO 방식의 요청 Queue를 사용한다

참조한 사이트
https://devraphy.tistory.com/242
https://jwprogramming.tistory.com/12
https://www.youtube.com/watch?v=FXzBRD3CPlQ