[운영체제] Deadlocks

1. 데드락이란?

= 교착 상태. 일련의 프로세스들이 서로가 가진 자원을 기다리며 블락된 상태

리소스(자원): 하드웨어, 소프트웨어 등 프로세스가 실행되기 위해 필요한 말 그대로의 자원

I/O 디바이스, CPU, memory space, semaphore 등

프로세스 자원 사용 절차: Request - Allocate - Use - Release

발생 예시) 프로세스들이 자원을 갖고 있는 상태로 다른 프로세스(교착 상태로)의 프로세스를 요청한 상황

 

2. 데드락 발생 조건

1) Mutual exclusion: 매 순간 하나의 프로세스만이 자원을 사용할 수 있는데, 동시에 여러 프로세스가 자원에 접근 할 때 발생

// CPU 독점

2) No preemption: 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않기 때문에 발생. 내어놓을 때까지 기다려야 함

// CPU 독점

3) Hold & Wait: 자원을 가진 프로세스가 / 다른 자원을 기다릴 때 / 보유 자원을 놓지 않고 계속 갖고 있어서 발생

4) Circular wait: 자원을 기다리는 프로세스 간에 사이클 형성

➡️ 자원 할당 그래프로 사이클 확인: 박스는 리소스, 큰 원은 프로세스, 리소스 안의 점은 리소스의 개수를 의미한다

그래프에 사이클이 없으면 데드락이 아니다. 인스턴스 한 개 할당은 무조건 데드락, 이외에는 가능성만 존재

 

데드락 처리 방법

1) Deadlock Prevention

- Active, 적극적으로 막는다

- 위의 데드락 발생 조건 4가지를 원천 차단

(1) Mutual Exclusion: 공유해서는 안 되는 자원의 경우 명시

(2) Hold & Wait: 프로세스가 자원을 요청할 때 다른 어떤 자원도 갖고 있으면 안 됨

     - 프로세스 시작 시 모든 필요한 자원을 할당받게 함

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

(3) No Preemptive: process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점되고, 모든 필요한 자원을 얻을 수 있을 때 프로세스를 다시 시작. context switch가 원활하게 일어나야 한다(State를 쉽게 저장하고 리스토어 할 수 있는 자원의 경우 사용 -- CPU, memory)

(4) Circular Wait: 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다

➡️ Utilization 저하, throughput 감소, starvation 문제

 

2) Deadlock Avoidance: stay away from problem

자원 요청에 대한 부가 정보를 이용해 자원 할당이 데드락으로부터 안전한지(safe한지) 동적으로 조사해서 안전한 경우에만 할당.

safe state: 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

safe sequence: 가용자원만 갖고 프로세스를 하나씩 종료시킬 수 있는 sequence가 존재하는 상황. 안전한 프로세스에게 최대로 자원을 할당 → 프로세스 종료 → 자원 반납됨 이런 상황을 반복하다 보면 모든 프로세스가 종료하게 된다. 이게 가능한 시퀀스가 나올 때 세이프하다고 말함.

unsafe state: safe state가 아닌 상황. 데드락의 가능성이 있는 상황.

(1) single instance per resource types

- 그래프를 사용하여 조사

(2) Banker's Algorithm

- 평생을 최대로 쓸 자원을 미리 알고 있다고 가정

- 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 자원을 모두 반납한다고 가정

- 비록 자원의 여유가 있더라도 그 자원을 줬을 때 불안정한 상황이 생길 수 있다면 요청을 받아들이지 않음

- 자원을 요청했으면 그 자원을 내 놓지 않음. 일이 다 끝나야 내어놈. ⇒ 데드락

- 다 가져갔어도 최대 자원을 이미 다 할당 받았다면, 가용 자원으로 후에 내어 놓을 것. 때문에 1번의 요청을 받아들여준다

- 자원이 있다고 주는 게 아니고, 가용자원이 돌아올 거라고 생각되는. 맥스가 아닌 프로세스에게만 할당

 

3) Deadlock Detection & Recovery

데드락 발생은 허용하되 그에 대한 감지 루틴을 두어 데드락 발견시 리커버

 

// Detection

자원당 인스턴스가 하나만 있으면? → 그래프 그려서 확인

여러개 있으면? → 테이블을 만들어 판단자원이 회수가 된다면 데드락이 아니다(뱅커스 알고리즘은 최악의 자원요청을 한다고 가정을 한다. 자원이 있어도 요청을 받아들이지 않음. 하지만 Detection and recovery는 가용자원으로 요청을 처리, 할당된 자원을 내어놓고...)

뱅커스는 더 안전하다 + 그만큼 비효율적

데드락이 발생할 수 있는 상황에서도 프로세스의 자원할당 요청을 받아들인다

 

// Recovery

그러다 데드락이 발생하면? 리커버리

(1) Process termination

- 데드락에 연루된 프로세스를 다 죽임

- 하나씩 없애면서 데드락 없애보기

(2) 자원 빼앗기

- safe state로 롤백해서 프로세스 재시작

- starvation 문제. 동일한 프로세스가 계속해서 비용 최소화 대상으로 선정되는 경우

- cost factor에 roll back 횟수도 같이 고려

 

4) Deadlock Ignorance

(앞에 왜 배움?)

데드락이 일어나지 않는다고 생각하고 아무것도 안함

데드락은 애초에 자주 일어나지 않음 ➡️ 조치 자체가 오버헤드일수도

발생하면 사람이 감지해서 프로세스를 종료

대부분 이거 씀