Dead lock(교착상태)

자바 쓰레드를 공부하던 중에 교착상태에 관한 내용을 정리했습니다.
운영체제에서도 마찬가지로 프로세스 관리 차원에서 교착상태를 주의 해야한다는 내용이 있었습니다.

Deadlock(교착상태)

• 두개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료하지 못하는 상태
  한정된 자원을 얻지 못해 다음 처리를 진행하지 못하는 상태를 말한다.

Deadlock 발생 조건

다음의 네가지 상황을 동시에 만족할 때 Deadlock 이 발생할 수 있다.

• 상호 배제(mutual exclusion)
  하나의 공유자원에 대해 두개 이상의 프로세스가 동시에 접근
• 점유 대기(hold and wait)
  하나의 자원을 점유하고 있는 프로세스가 있고, 해당 프로세스가 다른 프로세스에서 자원을 얻기 위해서는 요청 후 대기상태이다.
• 비선점(no preemptive)
  특정 프로세스가 자원을 사용하고 있는데 해당 자원 사용이 끝나기 전까지는 그 자원을 뺏을 수 없다.
• 순환대기(circular wait)
  프로세스들이 서로 사용하고 있는 자원에 대해서 순환적으로 대기하고 있는 형태이다.

Deadlock 예방

교착상태가 발생되지 않도록 사전에 예방하려면 네가지 발생 조건 중 하나를 제거함으로써 해결하는 방법이 있다.
but, 예방 방법으로는 일반적으로 자원 사용 효율성이 떨어지고 비용이 많이 드는 방법이기 때문에 많이 사용을 하지 않는다.

• 상호 배제 조건 제거
  하나의 공유자원에 대해 프로세스들이 동시에 접근할 수 있다? (불가능하다)
• 점유 대기 조건 제거
  특정 프로세스가 어떤 작업을 수행할 때 해당 작업에 필요한 리소스들을 먼저 요청하고, 할당 받은 다음에 작업을 수행한다. (자원의 효율성이 떨어지고, 프로세스들이 어떤 자원이 필요한지 확인하는 작업에서 추가적인 오버헤드가 발생한다.)
• 비선점 조건 제거
  프로세스가 다른 프로세스의 자원을 요청하기 위해서는 자신이 할당받았던 자원을 우선 반납을 한다.(현재까지 프로세스가 작업을 했던 상태를 잃어버릴 수도 있는등 다양한 문제점)
• 순환대기 조건 제거
  각각의 자원들에 대해 고유번호를 할당하고 특정 프로세스 내 자신이 할당받은 자원에 번호를 기준으로 오름차순이나 혹은 내림차순으로만 요청을 할 수 있도록 하는 방식)

Deadlock 회피

교착 상태 발생 가능성을 검사해서 발생 가능성이 있다면 사전에 회피하는 방식
ex) 자원할당 그래프 알고리즘, 은행원 알고리즘 (항상 os가 안전상태에 있도록 하는 알고리즘)
1. 프로세스가 자원 요청시 자원을 할당한 후에도 안정상태로 남아있는지 사전 검사
2. 안정 상태라면 자원을 할당
3. 불안정 상태라면 다른 프로세스가 자원을 해지할 때까지 대기
but, 회피 방법을 쓰더라도 자원을 요청할 때마다 시스템 상태를 검사하는 만큼 오버헤드가 크다. 은행원 알고리즘의 경우 전제조건이 많기 때문에 사용하기 어렵다.

Deadlock 탐지 및 회복

주로 많이 사용하는 방법으로 교착 상태를 허용하지만 상태를 탐지하고 회복하는 방식이다. 알고리즘을 주기적으로 실행함으로써 시스템에 발생한 Deadlock을 체크하고 데드락이 발생하게 되면 회복하는 과정의 반복이다.
(데드락이 발생하게 되면 자원을 뺏거나 process kill!)

• 자원할당 그래프 알고리즘
  : 프로세스들 간에 교착상태를 유발시키는 순환 사이클 들의 존재 유무 체크
  데드락의 탐지 방법 또한 알고리즘을 사용하게 되는데 이 주기를 너무 짧게 잡게 되면 회피와 다를것 없이 오버헤드가 커진다.
  시스템의 특성이나 비용적인 측면을 고려해서 어느 시점에 알고리즘을 실행하는 것이 좋을지를 결정해야한다.

교착상태에서 회복이란 교착 상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제 함으로써 회복한다.

• 프로세스 종료
  교착상태의 프로세스를 모두 중지
  교착상태가 제거될 떄까지 한 프로세스씩 중지
• 자원선점
  교착 상태가 제거될 때까지 프로세스가 점유한 자원을 선점해 다른 프로세스에게 할당

회복시 고려 사항

• 희생자 선택
  데드락 상태에서 어떤 프로세스를 선택해 종료나 자원을 회수할 것인지 선택한다. (비용측면, 가중치 고려)
• 후퇴(Rollback)
• starvation

Deadlock 무시

교착 상태 자체를 무시하고, 특별한 조치를 취하지 않는 방법이다. 교착 상태의 발생 확률이 낮은 상황에서 주로 사용한다. 예를들어 os중 UNIX와 윈도우가 취하는 방식인데, 교착상태가 발생했을 시 문제가 되는 프로세스를 죽이거나 재부팅을 통해 해결한다.

 

---

[참고] 우아한테크코스-Deadlock