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

교착상태란 무엇인가?

그림을 보면 어느 누구도 움직이지 못하는 상황이다. 이처럼 자원이 모두 사용 중이어서 프로세스들이 계속 기다리는 상태를 교착상태라고 한다.

 

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

- 자원(resource): 하드웨어, 소프트웨어 등을 포함하는 개념

- ex) 시스템에 2개의 tape drive가 있다. 프로세스 A와 B가 각각 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.

 

deadlock 발생의 4가지 조건

1. 상호배제: 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

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

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

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

4가지를 모두 만족해야 함

 

자원할당그래프를 통해 데드락이 발생했는지 알 수 있다.

R: 자원, P: 프로세스

P -> R: 요청, R -> P: 할당

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

그래프에 cycle이 있으면

- 자원당 인스턴스가 하나면 deadlock

- 자원당 인스턴스가 여러 개면 deadlock일 수도 있고 아닐 수도 있다

왼쪽 그래프: 자원이 여러 개지만 자원이 모두 사용 중이므로 데드락이다

오른쪽 그래프: 데드락이 아니다. 자원 1의 하나는 프로세스 2한테 있고 자원 2의 하나는 프로세스 4에게 있는데 이들은 데드락 사이클에 들어가 있지 않기 때문에 기다리면 받아서 사용할 수 있다.

 

Deadlock의 처리 방법

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

1. Mutual Exclusion

  - 공유해서는 안 되는 자원의 경우 반드시 성립해야 함 

2. Hold and Wait

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

  - 방법 1: 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법

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

3. No Preemprion

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

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

4. Circular Wait

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

 

→ 자원 이용률 저하, 시스템 성능 저하, starvaion 문제, 비효율적이다

 

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

프로세스가 시작할 때 자원을 미리 예측하고 방지함.

시스템이 safe state에 있으면 no deadlock

시스템이 unsafe state에 있으면 possibility of deadlock

 

자원이 하나일 때: 자원 할당 그래프 사용

자원이 여러 개일 때: 은행원 알고리즘

- 모든 프로세스는 자원의 최대 사용량을 미리 명시

- 자원 요청 시 safe 상태를 유지할 경우에만 할당

- 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택

- 그런 프로세스가 있으면 그 프로세스에게 자원을 할당

- 할당받은 프로세스가 종료되면 모든 자원을 반납

- 모든 프로세스가 종료될 때까지 이러한 과정을 반복

프로세스가 5개 자원이 3종류, 자원이 할당된 현황이고 최대사용량에서 할당량을 빼서 가용량을 구한다

최악의 상황을 가정하기 때문에 프로세스 4가 요청해도 자원을 안 준다 프로세스 1이 요청하면 가용량에 여유가 있기 때문에 자원을 준다.

최대 자원 요청을 만족하면 받아들이고 아니면 받아들이지 않는다

→ 데드락은 안 생기는데 비효율적이다, 안전한 방식

 

Deadlock Detection and recovery

Deadlock을 미리 방지는 하지 않고 일단 자원을 주고 느려지면 탐지 루틴을 만들어서 복구한다

자원이 하나일 때: 자원 할당 그래프 사용

자원이 여러 개일 때: 

추가 요청이 없는 프로세스는 반납할 것이라고 가정한다

 

복구

- 데드락 연루된 프로세스를 모두 죽인다

- 데드락이 연루된 프로세스를 하나씩 죽인다

- 비용을 최소화할 희생자를 선정하고 rollback 하여 자원을 뺏어옴

- 동일한 프로세스가 계속 희생자로 선정되는 경우 starvation문제 발생

 

Deadlock Ignorance

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

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

- 만약 발생하면 사람이 직접 프로세스를 죽이는 방법으로 대처

- 대부분 범용 OS가 채택

 

 

 

자료출처

ABRAHAM SILBERSCHATZ ET AL., OPERATING SYSTEM CONCEPTS, NINTH EDITION, WILEY, 2013

반효경, 운영체제와 정보기술의 원리, 이화여자대학교 출판부, 2008