Deadlock(교착상태) 조건과 처리

교착상태(Deadlock)

일련의 프로세스들이 서로가 가진 자원(SW || HW)을 기다리며 block된 상태

 

자원이란?

• 하드웨어, 소프트웨어 등을 포함하는 개념
  • EX) I/O device, CPU cycle, memory space, semaphore 등
• 프로세스가 자원을 사용하는 절차
  • 요청(Request), 획득(Allocate), 사용(Use), 반납(Release)

 

발생 조건

Mutual exclusion(상호 배제)

매 순간 하나의 프로세스만이 자원을 사용할 수 있음

 

No preemption(비선점)

프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

 

Hold and wait(점유 대기)

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

 

Circular wait(순환 대기)

자원을 기다리는 프로세스 간에 사이클이 형성되어야 함
EX) 프로세스 $P_0$, $P_1$, ... , $P_n$ 이 있을 때

• $P_0$은 $P_1$이 가진 자원을 기다림
• $P_1$은 $P_2$가 가진 자원을 기다림
• $P_n-1$은 $P_n$이 가진 자원을 기다림
• $P_n$은 $P_0$이 가진 자원을 기다림

 

 

자원 할당 그래프(Resource-Allocation Graph)

출처: 운영체제 - 반효경

자원의 할당을 나타내는 그래프이다.

• $R(네모)$은 자원을 의미한다.
• $P(동그라미)$는 프로세스를 의미한다.
• $P -> R$ 은 자원을 요청하는 중이라는 의미이고 $R -> P$는 프로세스가 자원을 할당 받는 중이라는 의미이다.
• 그래프에 Cycle이 없으면 데드락이 아니다.
• 그래프에 Cycle이 있더라도 할당될 수 있는 자원의 인스턴스가 부족할 때 데드락이 된다.
  • 왼쪽 그래프는 데드락 상황이다.
  • 반면 오른쪽 그래프는 $P_2$와 $P_4$가 데드락과 관련이 없기 때문에 데드락 상황이 아니다.

 

데드락 처리 방법

4가지 방법이 있고 아래로 내려갈 수록 오버헤드가 줄어든다.

Prevention(예방)

자원 할당 시 데드락의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

 

Avoidance(회피)

• 자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원을 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

 

Detection and recovery(감지와 복구)

데드락 발생은 허용하되 그에 대한 detection 루틴을 두어 데드락 발견시 recover한다.

 

Ignorance(무시)

• 데드락을 시스템이 책임지지 않는다.
• UNIX를 포함한 현대의 대부분 OS가 채택

 

 

방법 상세

 

Prevention(예방)

Mutual exclusion(상호 배제)

공유해서는 안되는 자원의 경우 반드시 성립해야 함 <- 예방할 이유가 없음

Hold and wait(점유 대기)

• 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
• 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 <- 비효율적이다.
• 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고(자진 반납) 다시 자원을 요청

No preemption(비선점)

• 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
• 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
• state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)

Circular wait(순환 대기)

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
• 예를 들어서, 순서가 3인 자원 $R_i$ 를 보유 중인 프로세스가 순서가 1인 자원 $R_j$을 할당받기 위해서는 우선 $R_i$를 release해야 한다.

-> 불필요한 제약 조건으로 Utilization(이용률) 저하, Throughput(성능) 감소, Starvation 문제가 발생한다. 즉, 비효율적이다.

 

 

Avoidance(회피)

• 자원 요청에 대한 부가적인 정보를 이용해서 자원 할당이 데드락으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당한다.
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.

safe state?

시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

safe sequence

• 프로세스의 Sequence$<P_1, P_2,...,P_n>$이 safe하려면 $P_i(1≤i≤n)$의 자원 요청이 $가용\;자원\;+\;모든\;P_j(j < i)의\;보유\;자원$에 의해 충족되어야 한다.
• 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장한다.
  • $P_i$의 자원 요청이 즉시 충족될 수 없으면 모든 $P_i(j < i)$가 종료될 때까지 기다린다.
  • $P_{i-1}$이 종료되면 $P_i$의 자원요청을 만족시켜 수행한다.

 

데드락 회피란?

시스템이 unsafe state에 있으면 데드락의 가능성이 있는 것이고, 회피는 시스템이 unsafe state에 들어가지 않는 것을 보장해주는 것이다.

 

회피 알고리즘

 

자원의 인스턴스가 하나인 경우

자원 할당 그래프 알고리즘을 사용한다.

 

자원의 인스턴스가 여러 개인 경우

은행원 알고리즘(Banker's Algorithm)을 사용한다.

출처: 운영체제 - 반효경

• 각 자원의 인스턴스 수와 각 프로세스의 현재 할당량, 최대 할당량으로 현재 가용 자원 수, 최대 필요한 자원 수를 구해 비교한다.
• 가용자원보다 자원을 요청한 프로세스의 최대 필요한 자원수가 크다면 자원을 할당해주지 않는다.(보수적이다.)
• 예를 들어 $P_O$의 경우 최초 요청시 최대 필요한 자원 수$(7;4;3)$가 가용 자원 수$(3;3;2)$를 초과하기 때문에 자원을 할당하지 않는다.
• 반면, $P_1$의 경우 최대 필요한 자원 수$(1;2;2)$가 가용 자원수$(3;3;2)$ 이하이기 때문에 할당이 가능하다.

 

 

Detection and recovery(감지와 복구)

사실 데드락이 자주 발생하는 이벤트는 아니기 때문에 미연에 방지하기 위해서 비효율적인 방법을 쓰기보다 시스템에 오류가 생기거나 느려지면 그때서야 감지하고 복구하는 처리 방법이다.

 

탐지 방법

 

자원의 인스턴스가 하나인 경우

자원 할당 그래프(Resource-Allocation Graph) 알고리즘을 사용한다.

• Corresponding wait-for graph이란 자원 할당 그래프에서 자원을 제거하고 프로세스만 표시한 것

출처: 운영체제 - 반효경

 

자원의 인스턴스가 여러 개인 경우

은행원 알고리즘(Banker's Algorithm)을 사용한다.

출처: 운영체제 - 반효경

여기서는 각 자원별 최대 사용량이 필요 없으며 실제로 요청한 자원량을 토대로 detection한다.

 

복구 방법

Process termination(프로세스 제거)

1. 데드락에 연루된 모든 프로세스를 제거한다.
2. 데드락 사이클이 없어질 때까지 프로세스를 하나씩 제거한다.

 

Resource Preemption(자원 선점)

1. 비용을 최소화할 victim을 선정
2. safe state로 롤백하여 프로세스를 재시작한다.
3. Starvation 문제
   • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
   • cost factor에 롤백 횟수도 같이 고려

 

 

Ignorance(무시)

데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음

• 데드락이 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일 수도 있다.
• 만약 시스템에 데드락이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처
• UNIX, Windows 등 대부분의 범용 OS가 채택

 

 

 

 

출처

반효경, "운영체제 2014-1", KOCW, http://www.kocw.net/home/cview.do?cid=3646706b4347ef09