17. 교착 상태(DeadLock)

락(Lock)

: 동기화를 보장하는 툴

- 락을 사용하여 동기화를 수행하다 보면 필연적으로 데드락(DeadLock)이라는 부작용이 생김

- 데드락 상태가 되면 더 이상 프로세스나 스레드가 진행하지 못하기 때문에 이를 잘 파악하는 게 중요

 

cf) 비관적인 락

: 동시에 연산이 실행되지 않도록 락을 걸어서 다른 연산이 끼어들지 못하도록 함

- 성능이 느려질 수 있음

- 데드락 상태에 걸릴 수 있음

 

교착 상태(DeadLock)

: 두 개 이상의 일련의 프로세스 혹은 스레드들이 서로가 가진 자원을 기다리며 block된 상태

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

- 숫자 = 자원, 자동차 = 프로세스

- 각각의 자동차가 모두 2개의 자원을 확보하여 지나가려고 함 

-> 모두 한 가지 자원을 선점하는 데에는 성공했지만 그 이후 다른 차량이 가지고 있어 지나갈 수 없는 교착 상태에 빠지게 됨

 

1. DeadLock이 발생하는 4가지 조건

- 아래의 조건이 모두 성립해야 데드락이 발생함

 

1) Mutual Exclusion(상호 배제)

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

- 자원을 공유해서 사용할 수 없음

 

2) No Preemption(비선점)

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

- 자원 반환은 오직 그 리소스를 취득한 프로세스만 할 수 있음

 

3) Hold and Wait(점유 대기)

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

- 프로세스가 이미 하나 이상의 자원을 취득(hold)상태에서 다른 프로세스가 사용하고 있는 자원을 추가로 기다림(wait)

 

4) Circular Wait(순환 대기)

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

- 프로세스들이 순환 형태로 서로의 리소스를 기다림

 

2. OS의 DeadLock 처리 방법

1) DeadLock Prevention(예방)

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

- 시스템 레벨에서 설계를 통해 데드락이 발생할 조건 하나를 없애는 방법

- Mutual Exclusion

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

- No Preemption

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

- Hold and Wait

• 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 함
• ⓐ 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 -> 단계마다 필요한 자원이 다를텐데 지금 사용하지 않을 자원까지 hold하고 있으면 자원 효율이 떨어지고, 자원이 모두 확보되지 못한 겨우 계속 wait하는 상황이 될 수 있음
• ⓑ 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청 -> 자원을 전혀 가지지 않은 상태에서만 자원을 요청할 수 있도록 제약 조건을 줌

- Circular Wait : 가장 많이 사용

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
• Utilization 저하, Throughput 감소, starvation 문제

2) DeadLock Avoidance(회피)

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

- 부가적인 정보 : 현재 사용 가능한 자원, 이미 할당된 자원, 앞으로 있을 자원 요청이나 반환

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

 

- Banker Algorithm(은행 알고리즘)

• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데에서 유래
• 자원 요청을 허락해줬을 때 데드락이 발생할 가능성이 있으면서 자원을 할당해도 안정할 때까지 계속 요청을 거절하는 알고리즘

3) DeadLock Detection and Recovery(탐지 & 회복)

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

- 복구 전략

1. 프로세스를 종료 -> 데드락에 빠진 프로세스 모두 강제 종료 -. 작업 중인 자료를 잃을 수 있어서 risk가 큼
2. 자원의 일시적인 선점을 허용

4) DeadLock Ignore(무시)

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

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

 

cf) 기아 상태(Starvation)

: 특정 프로세스보다 우선 순위가 낮아 원하는 자원을 계속 할당받지 못하는 상태

- 주로 Priority Scheduling에서 발생