[OS]교착상태와 교착상태 방지

교착상태(dead lock)이란?

---

• 첫 번째 스레드는 두 번째 스레드가 들고 있는 객체의 락이 풀리기 기다리고, 두 번째 스레드 역시 첫 번재 스레드의 락이 풀리기를 기다리는 상황을 말한다.
• 즉 모든 스레드가 락이 풀리기를 기다리고 있어 무한 대기중인 상태에 빠지는 것이다.

교착 상태에 빠지기 위한 네 가지 조건

---

• 상호 배재(mutual exclusion) : 한 번에 한 프로세스만 공유 자원을 사용할 수 있을 때
• 점유 대기(hold and wait) : 공유 자원에 대한 접근 권한을 갖고 있는 프로세스가, 그 접근 권한을 양보하지 않은 상태에서 다른 자원에 대한 접근 권한을 요구할 때
• 비선점(preemption) : 한 프로세스가 다른 프로세스의 자원 접근 권한을 강제로 취소할 수 없을 때
• 순환대기(circular wait) : 두 개 이상의 프로세스가 자원 접근을 기다리고 그 관계에 사이클이 존재할 때

교착 상태 예방

---

• 4가지 조건들 가운데 하나를 제거하면 되지만 1번 조건은 제거하기 어렵다.
  • 상호배제 : 모든 자원을 공유 가능하게 만들 수 없음(일부 자원은 애초에 공유가 불가능함)
  • 점유 대기 : 스레드가 자원을 요청할 때 다른 자원을 가지고 있지 않게 하면 starvation이 일어나고 자원효율이 떨어진다
  • 비선점 : 대기중인 스레드부터 자원을 선점하도록 설정(CPU 레지스터나 데이터베이스 트랜젝션처럼 상태가 쉽게 저장되고 복원되는 자원에는 적용 가능하지만 mutex 락이나 세마포어에는 적용 불가능)
  • 대부분의 교착상태 방지 알고리즘은 4번 조건, 대기 상태의 사이클이 발생하는 일을 막는 데 초점이 맞춰져 있다. 자원의 타입에 번호를 매기고(인덱싱), 번호순대로 자원을 요청하도록 요구. 점유 불가능한 자원이 있다면 모든 자원 방출. starvation이 발생할 수 있다.
• 예방을 하려면 자원을 효율적으로 사용하기 어려움으로 예방은 잘 사용하지 않는다(탐지 및 회복을 주로 사용)

교착 상태 무시

---

• 교착상태가 드물게 발생하는 시스템에서 일반적으로 사용
• 사용자가 프로세스를 죽이거나 시스템 자체를 재부팅

교착 상태 회피

---

교착 상태 예방은 장치 이용률도 저하시키고, throughput 도 감소시킨다. 교착상태 회피는 각 요청에 대해 교착 상태를 일으킬 가능성이 있으면 대기시킨다.

• 시스템이 교착 상태가 되는 것을 막기 위해 교착 상태를 방지하는(Banker 알고리즘- 안전 상태일때만 요구를 수락하고 불안전상태일때는 안전상태를 만족할때까지 수락하지 않음, 하지만 할당 자원 수 및 프로세스 할당 수 고정 등 현실적으로 제약이 많아 사용이 어려움) 프로토콜 사용
• 탐지 및 복구는 교착상태가 발생할 것 같을 때 동작하지만 회피 알고리즘은 자원 요청시마다 시스템의 상태를 판단해야 하기 때문에 오버헤드가 발생

교착 상태 탐지 및 복구

---

• 교착 상태 존재 여부 및 교착 상태에 연관된 프로세스와 자원을 알아냄 -> 순환 대기 존재 여부에 초점을 맞춤, 자원과 프로세스에 대한 그래프를 그리고 소거해 관계를 알아냄 -> 얼마나 자주 회피 알고리즘을 돌리느냐에 따라 오버헤드 발생이 다름(CPU 이용률, 교착상태 빈도율 등에 따라 적절히 결정)
• 순환대기를 깨서 교착상태로부터 회복, 순환대기가 깨질때까지 프로세스 종료, 순환대기에 포함된 프로세스의 제어권을 뺏고 롤백
• 운영자가 직접 처리하거나 시스템이 자동으로 회복
• 프로세스와 스레드를 모두 종료하거나 교착 상태 탐지 알고리즘을 돌려가며 하나씩 종료
• 교착 상태가 깨질때까지 자원을 선점하여 다른 프로세스에게 줌(어떤 자원을 선택할 것인지, 안전한 상태로 후퇴시키고 재시작, starvation을 방지하기 위해 victim이 되는 횟수 제한)

기타

---

• Starvation : 교착 상태가 자원을 자유롭게 할당한 자원 부족의 결과라면, 기아 상태(starvation)은 자원 적절히 할당하는 데서 소외될 때 발생하는 문제이다. 특정 프로세스가 자원을 할당받지 못하면 끝없이 기다리는 상태

• 참고링크