[운영체제] 교착 상태 (Deadlock)

본 게시글은 KOCW 이화여자대학교 반효경 교수님의 <운영체제> 강의를 듣고,
<혼자 공부하는 컴퓨터구조 + 운영체제> 책을 참고하여 정리한 내용입니다.
게시글에 포함되는 이미지 자료는 <운영체제> 강의에 포함된 강의 자료입니다.

교착 상태(Deadlock)란?

일련의 프로세스들이 서로가 가진 자원(resource)을 기다리며 block된 상태를 교착상태(deadlock)이라고 합니다.

 

자원(resource)

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

Deadlock 발생의 4가지 조건

교착 상태가 발생할 조건에는 네 가지가 있습니다. 네 가지 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 아래의 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생깁니다.

 

Mutual exclution (상호 배제)

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

한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 것입니다.

 

No preemption (비선점)

프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않습니다.

 

Hold and Wait (점유와 대기)

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

어떤 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있습니다.

 

Circular wait (원형 대기)

자원을 기다리는 프로세스 간에 사이클이 형성됩니다.

ex) 프로세스 P0, P1, ..., Pn이 있을 때

P0은 P1이 가진 자원을 기다림

P1은 P2가 가진 자원을 기다림

Pn은 P0이 가진 자원을 기다림

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

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

 

자원 할당 그래프

• 원: 프로세스(process), 사각형: 자원(resource), 점(사각형 내): 자원의 개수
• 화살표 방향
  • 프로세스(원) -> 자원(사각형): 프로세스가 자원을 기다리고 있는 상태
  • 자원(사각형) -> 프로세스(원): 프로세스가 자원을 할당받아 사용 중

 

• 그래프에 cycle이 없으면 deadlock이 아님
• 그래프에 cycle이 있으면 - deadlock 가능성 (무조건 deadlock은 아님)
  • 1번 그림: deadlock O
  • 2번 그림: deadlock X - cycle이 1개 있으나 자원이 2개씩이고 P2와 P4는 관련없기 때문(P2 or P4 자원 반납 시 사이클 사라짐)

Deadlock의 처리 방법

Deadlock Prevention (교착 상태 예방)

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

 

Deadlock Avoidance (교착 상태 회피)

- 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당

- 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

 

Deadlock Detection and recovery (교착 상태 검출 후 회복)

- deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover

 

Deadlock Ignorance

- deadlock을 시스템이 책임지지 않음

- UNIX를 포함한 대부분의 OS가 채택

Deadlock Prevention

deadlock 발생조건 4가지 중 어느 하나를 원천적으로 차단해서 deadlock에 들어가지 못하게 하는 방법

 

1. Mutual Exclusion (상호배제)

공유해서는 안되는 자원의 경우 배제할 수 있는 조건은 아님 (현실적으로 무리)

 

2. Hold and Wait (점유와 대기)

프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 함

방법 1) 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 (비효율적)

방법 2) 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청

 

3. No Preemption (비선점)

- 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨

- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다

- 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있음

- State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용. 즉, 일부 자원에 대해서는 효과적(CPU, memory)

 

4. Circular Wait (원형 대기)

모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당

ex) 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release해야 함

 

deadlock 발생 조건을 원천적으로 제거하여 deadlock을 사전에 방지하는 예방 방식은 교착 상태가 발생하지 않음을 보장할 수 있지만 자원 이용률(utilization)이 낮아지기 때문에 전체 성능(throughput) 또한 감소하며, starvation 문제가 생긴다는 부작용이 있습니다.

Deadlock Avoidance

교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 조심 조심 자원을 할당하는 방식입니다. 교착 상태 회피 방식에서는 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주합니다.

 

• 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로 부터 안전한지를 동적으로 조사해서 안전한 경우(safe state)에만 할당
• 프로세스가 자원 요청했을 때 데드락 가능성이 있다면 여분의 자원이 있더라도 할당 X
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
• 시스템이 safe state에 있으면 -> no deadlock
• 시스템이 unsafe state에 있으면 -> possibility of deadlock
• Deadlock Avoidance는 시스템이 unsafe state에 들어가지 않는 것을 보장
• 2가지 경우의 avoidance 알고리즘(자원 당 인스턴스가 하나인 경우, 여러 개인 경우)

safe state

• 시스템 내의 프로세스에 대한 safe sequence가 존재

safe sequence

• 프로세스 sequence <P1, P2, ... Pn> 이 safe 하려면 Pi 의 자원 요청이 '가용자원 + 모든 Pj (j < i) 의 보유 자원' 에 의해 충족되어야 함
• 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
  • Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j < i)가 종료될 때까지 기다린다.
  • Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.

자원 당 인스턴스가 하나인 경우 - Resource Allocation Graph Algorithm

자원 할당 그래프 알고리즘

자원 할당 그래프에서 Claim Edge 라는 개념 추가

 

Claim Edge

• 프로세스가 자원을 미래에 요청할 수 있음을 뜻함 (점선으로 표시)
• 프로세스가 해당 자원 요청 시 request edge(실선)으로 바뀜
• 자원이 release 되면 assignment edge는 다시 claim edge로 바뀜
• 점선을 포함하여 cycle이 생기지 않는 경우에만 요청 자원을 할당

자원 당 인스턴스가 여러 개인 경우 - Banker's Algorithm

가정

• 모든 프로세스는 자원의 최대 사용량을 미리 명시
• 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다

방법

• 기본 개념: 자원 요청 시 safe 상태를 유지할 경우에만 할당
• 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택 (그런 프로세스가 없다면 unsafe 상태)
• (총 요청 자원의 수 <= 가용 자원의 수) 인 프로세스 있으면 해당 프로세스에게 자원 할당
• 할당받은 프로세스가 종료되면 모든 자원을 반납
• 모든 프로세스가 종료될 때까지 이러한 과정 반복

예시

• 5개의 프로세스 : P0~P4
• 3개의 자원 : A 10개, B 5개, C 7개
• Allocation : 현재 각 프로세스에 할당된 자원
• Max : 각 프로세스가 평생 사용할 자원
• Available : 가용 자원 
• Need : 각 프로세스가 앞으로 사용할 자원

• Need <= Available 이면 safe 상태이므로 자원 할당
• safe sequence < P1 P3 P2 P4 P0 >이 존재하므로 시스템은 safe state
• 항상 최악의 경우 고려 (unsafe 상태라면 할당x 다른 프로세스 종료 후 자원 반납까지 대기)
• 절대 데드락이 생길 수가 없음. but 자원이 남는데도 최악의 상황을 가정하고 자원 할당을 안하는 것은 비효율적

Deadlock Detection and Recovery

Deadlock 발생은 허용하나 Deadlock Detiction Routine 을 두어서 Deadlock 발견 시 Recover시키는 방법으로, 교착 상태 발생을 인정하고 사후에 조치하는 방식입니다.

Detection) 자원이 인스턴스 당 하나인 경우 - 그래프 사용

자원 할당 그래프 vs. wait-for 그래프

Wait-for graph

• 자원 할당 그래프의 변형
• 프로세스만으로 node 구성
• Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj
• Wait-for graph 알고리즘
  • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사 (사이클이 곧 deadlock을 의미)
  • O(n^2)

Detection) 자원이 여러 개인 경우 - Banker's Algorithm과 유사한 방법 활용

 

• Banker's 알고리즘과 비슷하나 여기는 최선의 상황 가정
• 자원을 현재 요청하고 있지 않은 프로세스는 할당된 자원을 반납할 것이라고 본다.
• Request <= (Available + Request 0 0 0) 이면 자원 할당
• But 자원을 반납한다고 해도 Request 보다 적게 반납할 수 있으므로 Deadlock의 가능성은 있음

Recovery

Processs termination (종료)

방법 1) 데드락에 연관된 모든 프로세스를 한 번에 모두 종료

방법 2) 사이클 없어질 때까지 데드락 사이클에 있는 프로세스를 하나씩 종료시켜보는 방법

 

Resource Preemption (자원을 빼앗음)

- 비용을 최소화할 victim 선정

- safe state로 rollback하여 프로세스를 restart

- Starvation 문제 가능

   동일한 프로세스가 계속해서 victim으로 선정되는 경우 그 프로세스는 계속해서 진행하지 못할 수 있기 때문에 

   비용의 고려 요소에 rollback 횟수 (자원을 빼앗긴 횟수) 도 고려해서 자원 빼앗을 프로세스 정해야 함

Deadlock Ignorance

Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는(무시) 방법입니다.

 

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