[운영체제] 교착 상태 Deadlock

교착상태 (Deadlock)

: 한 스레드 집합 안의 모든 스레드가 집합 안의 다른 스레드에 의해서만 발생될 수 있는 이벤트를 무한정 기다리는 상태

ex) mutex lock을 release하는 이벤트는 다른 스레드에 의해서만 발생될 수 있음.

 

자원을 사용하는 순서

1. 자원 요청 ex. critical section 진입 전

2. 자원 사용 ex. critical section 영역

3. 자원 방출 ex. 작업 완료 후 자원 반납

 

Livelock

- 스레드가 실패한 행동을 계속해서 시도할 때 발생한다.

- Race condition 발생 시 자신의 lock을 즉시 release하지만, 교착 상태의 상대도 똑같이 release하기 때문에 같은 행동을 반복한다.

 

Deadlock 조건

1. 상호 배제 Mutual Exclusion

자원은 반드시 한 번에 한 개의 스레드만 접근해야 한다는 조건.

2. 점유 대기 Hold-and-Wait

스레드가 다음 자원을 요청할 때 기존에 갖고 있던 자원을 반납하지 않고 갖고 있는 상태.

3. 비선점 No preemption

어떤 스레드가 자원을 갖고 있을 때, 다른 스레드가 이를 선점하지 못하는 경우.

4. 순환 대기 Circular wait

스레드가 서로 점유하고 있는 자원을 요청하면서 사이클이 발생하는 상태

 

 

Deadlock 처리 방법

1. 무시 Ignorance

- 교착 상태가 발생해도 무시한다. 시스템을 정지시키고 수작업으로 다시 시작한다.

- 비용이 적게 든다.

ex) Linux, Windows 등 OS

 

2. 예방 Prevention

Deadlock 필요 조건 4가지 중 최소 하나를 제거한다.

 

- Mutual Exclusion 제거

a) read-only로 만든다.

 

- Hold and Wait 제거

a) 실행 시작 전에 모든 자원을 요청하고 할당한다.

b) 자원을 갖고 있지 않을 때만 요청하도록 한다.

=> 기아 현상이 발생할 수 있다.

 

- No Preemption 제거

스레드가 대기해야 할 경우 모든 자원을 사용할 수 있을 때 다시 시작한다.

대기 시 점유 자원을 선점할 수 있게 한다. (방출과 같은 의미)

=> mutex lock이나 세마포어에 적용 불가

 

- Circular wait 제거

순서대로 자원을 요청하도록 한다.

=> 장치의 이용률이 저하되고 throughput이 감소한다.

 

3. 회피 Avoidance

자원이 어떻게 요청될지 파악해서 Deadlock을 발생시키지 않도록 한다.

 

- 자원 할당 그래프 알고리즘

: 사이클 탐지 알고리즘을 사용해 사이클을 형성하지 않을 때만 요청을 허용한다.

=> 종류마다 자원이 여러 개 있으면 사용할 수 없다.

 

- 은행원 알고리즘

: 스레드가 자원을 요청할 때 요청을 수락할 경우에도 시스템이 안전 상태를 유지하는지 판단한다.

=> 종류마다 자원이 여러 개 있어도 사용할 수 있다.

 

4. 검출, 복구 Detection, Recover

교착 상태 예방/방지 알고리즘이 없을 경우 반드시 필요하다.

 

- 교착상태 검출/탐지

wait-for graph(DB) or 은행원 알고리즘과 유사한 알고리즘 사용.

 

- 복구

a) 교착 상태 프로세스를 모두 중지시킨다.

b) 교착 상태가 제거될 때까지 하나씩 중지시킨다.

c) 자원 선점을 이용해 Deadlock이 제거될 때까지 자원을 계속 선점해 다른 프로세스에게 준다.

-> 희생자 선택, 후퇴(rollback), 기아 상태 고려해야 함.

 

 

 

(참고)

Operating System Concepts 10/E. Abraham S. 박민규 옮김. WILEY