[OS] 운영체제 8. Deadlock : 교착상태의 발생 조건(상호 배제, 비선점, 보유대기, 순환대기)과 처리방법

교착상태 Deadlock

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

Resource (자원)

- 하드웨어, 소프트웨어 등을 포함하는 개념

  ex) I/O device, CPU cycle, memory space, semaphore 등

- 프로세스가 자원을 사용하는 절차

  : Request, Allocate, Use, Release

 

Deadlock example 1]

시스템에 2개의 tape drive가 있고

프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다

Deadlock example 2]

Binary semaphores A and B

 

Deadlock 발생의 4가지 조건

1. Mutual exclusion (상호 배제)

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

2. No preemption (비선점)

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

3. Hold and wait (보유대기)

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

4. Circular wait (순환대기)

  : 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

 

 

Resource-Allocation Graph

좌측은 deadlock 우측은 deadlock 아님

좌측 : P1에게 R2 자원 1개 가있고, P2에게 R2 자원 1개가 가있는 상황, P3가 R2자원 하나 더 요구

        P2 은 R3 자원 요청, R3은 P3 가 가지고 있고 P1 은 R1을 요청하나 이는 P2 가 가지고 있으므로

        모든 프로세스가 자원을 반납할 수 없는 상황 즉, deadlock 상태

우측 : P1에게 R2 자원 1개 가있고, P4에게 R2 자원 1개 가있는 상황, P3가 R2 자원 요구 

        P4가 자원 반납시 문제가 없음 

 

그래프에 cycle이 없으면 deadlock이 아니다

그래프에 cycle이 있으면

if only one instance per resource type, then deadlock

if several instances per resource type, possibility of deadlock

 

Deadlock 처리 방법

1. Deadlock prevention

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

ex)

비선점방식을 선점방식으로,

가지고 있으면서 대기하지 못하도록(자원 요청시 보유한 자원 반납),

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

 

2. Deadlock Avoidance

: 자원 요청에 대한 부가적인 정보(최대 요청 자원양)를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사하여 안전한 경우에만 할당

: 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법

ex)

※ Banker's algorithm

현재 요청(Need)을 충족시킬 수 있는 자원상황(Available)이라 할 지라도 최대 요청(Max) 가능성을 염두하여 현재 자원상황을 초과할 가능성이 있다면 자원 할당하지 않음. 

 

3. Deadlock detection and recovery

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

1) Process termination

- 데드락과 관련된 모든 프로세스를 죽인다

- 데드락이 풀릴 때 까지 데드락과 관련된 프로세스를 한 개 씩 죽인다

2) Resource Preemption

- 비용을 최소화할 victim 선정

- safe state 로 rollback 하여 process를 restart

- 동일한 프로세스가 계속해서 victim으로 선정되는 경우 starvation 문제 (cost factor에 rollback 횟수도 같이 고려)

 

4. Deadlock ignorance

: deadlock 을 시스템이 책임지지 않음, 현대 대부분의 OS는 해당 처리방법을 채택

- Deadlock이 매우 드물게 발생하므로 데드락 조치 자체가 더 큰 overhead 일 수 있음

- deadlock 발생하여 시스템이 비정상적일 경우 유저가 직접 process를 죽이는 방법으로 대처

 

 

※ 이화여대 반효경 교수님의 운영체제 강의 정리