💡교착상태(데드락, Deadlock)란?

둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황

---

✅자원 할당 그래프 : 교착 상태 상황 확인

교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다.
자원할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현하는 그래프이다.

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현

2. 사용할 수 있는 자원의 개수는 자원 사각형 내의 점으로 표현

3. 프로세스가 자원을 할당 받아 사용중이라면 자원에서 프로세스를 향해 화살표를 표시

• 하드디스크의 자원 하나는 프로세스 A에 할당
• CPU의 자원은 프로세스 B,C에 할당

4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

• 프로세스 D는 CPU의 할당을 기다리는 중

📌그렇다면 어느 경우에 교착 상태가 발생할까?

❗자원 할당 그래프가 원의 형태를 띠고 있을 때 교착상태가 발생한다

---

✅교착 상태 발생 원인

1️⃣상호 배제(mutual exclusion)

• 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

2️⃣점유와 대기(hold and wait)

• 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태

3️⃣비선점(nonpreemptive)

• 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태

4️⃣원형 대기(circularwait)

• 프로세스들이 원의 형태로 자원을 대기하는 형태

➡️ 위 네 가지 조건을 모두 만족할 때, 교착 상태가 발생할 수 있다.

---

✅교착 상태 해결 방법

☑️교착 상태 예방

• 애초에 교착 상태가 발생하지 않도록 하는 방식
• 교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 만족시키지 않는 방법으로 예방

1. 상호 배제를 없애보자

• 모든 자원을 프로세스들이 공유하도록 만들어야한다 → 현실적으로 불가능

2. 점유와 대기를 없애보자

• 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분 → 자원의 활용률 낮아짐

3. 비선점을 없애보자

• 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이나 모든 자원이 선점 가능한 것이 아니다.
• 대표적으로 선점이 가능한 자원 : CPU

4. 원형 대기 조건을 없애보자

• 자원에 번호를 붙이고 오름차순으로 할당하면 원형대기는 발생하지 않는다.
• 1번 포크 → 2번 포크 → 3번 포크 →...→5번 포크에서 다시 1번 포크는 잡지 못한다.
• 위 3가지 방식에 비해 현실적인 방식이지만 어떤 자원에 어떤 번호를 붙이느냐에 따라 자원 활용률이 달라지게 된다.
  

➡️교착 상태를 사전에 방지하는 예방 방식은 교착 상태가 발생하지 않음을 보장할 수는 있지만, 여러 부작용이 따르게 된다.

---

☑️교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 자원을 할당하는 방식

안전 순서열

• 교착 상태 없이 안전하게 모든 프로세스들에 자원을 할당할 수 있게 하는 순서

안전 상태

• 교착 상태없이 모든 프로세스가 자원을 할당받고 종료될 수 있는 상태
• 안전 순서열이 있는 상태

불안전 상태

• 교착 상태가 발생할 수도 있는 상태
• 안전 순서열이 없는 상태

➡️교착 상태 회피는 항시 안전 상태를 유지하며 자원을 할당하는 방식으로, 대표적인 알고리즘에는 은행원 알고리즘이 있다.

☑️교착 상태 검출 후 회복

• 교착 상태 발생을 인정하고 사후에 조치하는 방식
• 교착 상태를 회복하는 방식에는 두 가지가 있다.

1. 선점을 통한 회복

• 교착 상태가 해결이 될 때까지 한 프로세스씩 자원을 몰아주는 방식

2. 프로세스 강제 종료를 통한 회복

• 교착 상태에 놓인 프로세스를 모두 강제 종료 하는 방식
  → 단점 : 작업 내역을 잃을 위험성 존재
• 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료하는 방식
  → 단점 : 한 프로세스 종료 후 교촉 상태가 해결되었는지 확인하는 작업 반복 -> 오버헤드 발생