교착상태 (Deadlock)

 

 

 

데드락(Deadlock)

 

 

시스템 자원에 대한 요구가 뒤엉킨 상태로

자세하게는, 둘 이상의 프로세스들이 자원을 점유한 상태에서

서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 말하며 데드락(Deadlock) 이라고도 말합니다.

데드락이 발생하지 않으려면 교착상태 발생의 필수총분조건을 인지해야 합니다.

 

 

---

 

 

예방기법(Prevention) 

= 데드락 발생조건 

 

 

☑  상호배제 

 

Mutual Exclusion

한 번에 여러 프로세스가 공유 자원을 사용할 수 없을 경우

적어도 하나의 자원은 비공유 모드로 유지되어야 합니다. 

즉, 한 번에 둘 이상의 프로세스에서 엑세스할 수 없다는 것을 말합니다.

 

 

 

☑  점유와 대기 

 

Hold and Wait

실행에 필요한 자원을 프로세스가 실행되기 전 한꺼번에 요구하고 작업을 보류해서,

자원이 점유되지 않은 상태에서만 자원을 요구하도록 합니다.

즉, 이미 자원을 사용중이면, 다른 프로세스가 사용중인 자원을 사용하기 위해 대기하고 있는 상태의 프로세스가 존재해야합니다.

 

 

 

☑  비선점 

 

Non-preemption

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 합니다.

자원을 사용하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고,

요구한 자원을 사용하기 위해 기다리게 합니다.

 

 

 

☑  순환 대기 

 

Circular Wait

자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 합니다.

즉,  자원을 선형 순서로 분류하여 고유 번호를 할당하고

각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 한쪽 방향으로만 자원을 요구하는 것입니다.

 

 

 

 

이러한 교착 상태 회피를 구현하는 데 사용할 수 있는 기법 또한 인지해야 합니다.

이러한 기법은 교착 상태에 필요한 조건 중 하나 이상이 충족되지 않도록 하여(최소한으로) 교착 상태가 발생하지 않도록 합니다.

 

 

---

 

 

 회피 기법(Avoidance) 

 

 

☑  자원 순서 지정  

 

각 자원에 고유한 번호 순서가 지정되며 프로세스는 오름차순으로 자원을 요청해야합니다. 

이렇게 하면 프로세스가 항상 다음으로 높은 번호의 자원을 대기하므로 순환 대기가 발생하지 않을 수 있습니다.

 

 

 

☑  Banker's algorithm 

 

회피 기법의 가장 대표적인 알고리즘으로 

이 알고리즘은 시스템이 안전한 상태인지 여부를 결정하고 안전하지 않은 경우 프로세스가 안전하지 않은 상태로 들어가는 것을 방지하는 데 사용됩니다. 자세하게는, 이 알고리즘은 은행에서 모든 고객의 요구를 충족할 수 있도록 현금을 대출해주는 것에서 유래하였습니다. 은행원 알고리즘은 자원 할당 결정전에 예상되는 모든 자원의 최대 할당량을 가지고 시뮬레이션을 하여 safe state에 들 수 있는지 여부를 검사하여 교착상태의 가능성을 미리 조사하는 알고리즘입니다.

[OS] 교착상태(Deadlock, 데드락)의 정의, 발생 조건, 해결 방법

 

 

 

☑  선제적 리소스 할당 

 

자원이 더 이상 필요하지 않을 때 프로세스에서 강제로 제거 할 수 있습니다.

즉, 프로세스가 잠재적으로 교착 상태를 유발할 수 있는 자원을 보유하는 것을 방지할 수 있습니다.

 

 

 

☑  자원의 인스턴스 할당

 

자원의 여러 인스턴스를 생성하여 단일 프로세스가 다른 프로세스에 필요한 자원을 보유하지 못하도록 합니다.

 

 

---

 

 

데드락 탐지(Detection) 및

회복(Recovery)

 

 

먼저 시스템이 데드락 예방이나 회피법을 사용하지 않았을 때, 데드락이 발생할 수 있으니 여기에서 회복하기 위해 데드락을 탐지하고, 회복하는 알고리즘을 사용합니다.

 

 

• 탐지 기법
  • Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색합니다. 즉, 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악합니다.
  • 이 외에도 자원 할당 그래프를 통해 탐지하는 방법도 있습니다.

 

 

• 회복 기법
  • 단순히 프로세스를 1개 이상 중단시키기
    • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있음
    • 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있음
  • 자원 선점하기
    • 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법
• 데드락을 탐지 기법을 통해 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용합니다.

 

 

---

 

Reference Path

[운영체제] 데드락(Deadlock, 교착 상태)이란?

 

---