[혼공컴운] 13장. 교착 상태

https://www.boardinfinity.com/blog/deadlock-in-operating-system/

13. 교착 상태

• 교착 상태는 아래 이미지 한 장으로 설명 가능하다.

• 서로가 각자에게 필요한 것을 가지고 있다!
• 어떡하지?

---

13.1 교착 상태란

• OS, 프로세스, 자원의 관점으로 보자면 아래와 같은 상황이다.

출처: https://www.geeksforgeeks.org/introduction-of-deadlock-in-operating-system/

• 교착 상태(deadlock)가 성립하기 위한 조건은 네 가지가 있다.
• 1. 상호 배제: 하나의 자원은 한 번에 하나의 프로세스만 점유할 수 있다.
• 2. 점유와 대기: 프로세스가 자원 하나를 붙들고 다른 자원을 기다릴 수 있다.
• 3. 비선점: 프로세스가 다른 프로세스의 자원을 강제로 뺏을 수 없다.
• 4. 원형 대기: 위 그림처럼, 자원 할당 그래프가 루프를 만들 수 있다.

---

13.2 교착 상태 해결 방법

• 교착 상태는 분명히 프로세스들이 옴짝달싹 못하는 상황이다.
• 어떻게든 해결해야 한다.
• 그런데 어떻게?
• 가장 간단한 방법: 교착 상태 성립 조건을 풀면 되지 않을까?

---

13.2.1 교착 상태 예방

• 교착 상태 성립 조건을 하나씩 풀어보자.

---

• 상호 배제를 없애면?
• 하나의 자원을 여러 프로세스가 쓸 수 있게 하겠다...?
• 그거 하면 안된다고 12장에서 말했다.

---

• 점유와 대기를 없애면?
• 프로세스가 자원을 들고 대기를 못 하게 하겠다...?
• 즉 프로세스는 빈 손으로 무작정 대기하거나, 필요한 자원을 다 주거나, 둘 중 하나만 하겠다...?
• 비효율적일 것임이 너무 자명하다.

---

• 비선점을 없애면?
• 프로세스가 다른 프로세스의 자원을 뺏을 수 있게 하겠다...?
• 무슨 아침 드라마도 아니고...

---

• 원형 대기 조건을 없애면?
• 간단하게, 모든 프로세스에 우선순위를 주어서 자원을 몰빵해주면?
• 문제점: 수 백 개 프로세스에 언제 순위표 붙이고 앉아있나.
• 다 별로다!

---

13.2.2 교착 상태 회피

• 교착 상태를 원천적으로 불가능하게 하는 것은 단점이 많았다.
• 어쩔 수 없이, 일단 하던 대로 하되, 교착 상태가 안 되도록 조심조심 해야 한다.
• 우선 몇 가지 용어를 정의하자.
  • 안전 순서열(safe sequence): 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
    • 예를 들어, 웹 브라우저 -> 메모장 -> 게임 순으로 자원을 할당했을 때 교착 상태가 되지 않는다면,
    • 웹 브라우저 -> 메모장 -> 게임이 안전 순서열이 된다.
  • 안전 상태(safe state): 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
  • 불안전 상태(unsafe state): 교착 상태가 발생할 수 있는 상황, 즉 안전 순서열이 없는 상황
• 안전 순서열이 없는 상황은 예시를 보면 바로 이해된다.

---

• 어떤 컴퓨터에 자원이 12개 있고, 3개의 프로세스가 돌아가고 있다.
• 각 프로세스의 요구 자원, 현재 사용 자원은 아래와 같다.
• 괄호 안은 각각의 합이다.

• P2 -> P1 -> P3 순으로 자원을 할당해보자.
• P2에게 부족한 2개를 마저 준다.

• P2는 필요한 자원을 모두 받았으므로 작업을 끝내고 자원을 반환한다.

• 다음으로 P1에게 자원을 준다.

• P1도 필요한 자원을 모두 받았으므로 작업을 끝내고 자원을 반환한다.

• 이제 P3는 얼마든지 자원을 받을 수 있다.
• 이 경우 안전 순서열이 있으므로 안전 상태이다.

---

• 이번엔 교착 상태에 빠지는 상황이다.

• 애초에 프로세스 하나라도 끝내려면 P2에 먼저 자원을 줄 수밖에 없다.

• P2를 끝내고 자원을 돌려받았다.

• 이제 자원 4개를 P1에 주든 P3에 주든 교착 상태에 빠질 수밖에 없다.
• 따라서 OS는 안전 상태를 유지한 채로 자원을 할당해야 한다.

13.2.3 교착 상태 검출 후 회복

• 마지막 방법은, 피할 수 없으면 즐기...는게 아니고,
• 일단 되는대로 해보고, 문제 생기면 그때 가서 덕테이핑을 하겠다는 뜻이다.

출처: https://9gag.com/gag/axjvdx1

• 교착 상태가 발생했다면 다음 중 하나를 수행하여 교착 상태를 푼다.

---

• 선점을 통한 회복
  • 교착 상태가 회복될 때까지 한 프로세스씩 자원을 몰아준다.
  • 즉, 다른 프로세스로부터 강제로 자원을 뺐는다.
• 프로세스 강제 종료
  • 교착 상태에 놓인 프로세스 전체 또는 일부를 강제 종료시킨다.
  • 당연히 오버헤드가 발생한다.