07. Deadlocks (1/2)

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

가. 자원: 하드웨어와 소프트웨어 모두 포함

-> Request, Allocate, Use, Release

나. 발생조건

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

2) No Preemption(비선점): 프로세스는 자원을 스스로 내어놓을 뿐 빼앗기지 않음

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

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

다. 자원할당 그래프

1) 그래프에 Cycle이 없으면 deadlock이 아니다.

2) Cycle이 있으면, 자원유형 당 instance가 하나만 있으면 deadlock이다.

3) 자원당 여러 instance가 있으면 deadlock의 가능성이 있다.

라. 처리 방법 (강한 순서)

1) Deadlock Prevention: 미연에 방지 (4가지 조건 중 하나를 원천적으로 차단)

가) Mutual Exclusion: 공유해서는 안 되는 자원의 경우 반드시 성립해야 하므로 막을 수 없음

나) Hold and Wait: 자원을 요청할 때, 다른 어떤 자원도 가지고 있지 않아야 한다.

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

(2) 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청

다) No Preemption

(1) Process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨

(2) 모든 필요한 자원을 얻을 수 있을 때, 그 프로세스는 다시 시작된다.

(3) State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU, memory)

라) Circular Wait

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

(2) 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj을 할당받기 위해서는 우선 Ri를 release해야 한다.

-> Utilization 저하, Throughput 감소, Starvation 문제 (생기지도 않을 deadlock 떄문에 성능이 떨어짐)

2) Deadlock Avoidance: 미연에 방지하는 방법으로, 자원 요청에 부가적인 정보를 이용해 deadlock의 가능성이 없을 경우에만 할당

-> 프로세스가 시작부터 종료될 떄까지, 평생의 쓸 자원량을 알고 있다고 가정

가) 자원당 instance가 하나만 있을 경우, 자원할당 그래프를 그려서 cycle이 생기지 않도록 한다. O(n^2)의 시간이 걸린다.

나) 자원당 instance가 여러개 있을 경우, Banker's Alogorithm 사용

-> 프로세스 별 할당된 자원, 최대 할당 자원, 남아있는 자원, 필요한 자원을 비교해서 구함

3) Deadlock Detection and recovery

4) Deadlock Ignorance: Deadlock을 시스템이 책이지지 않음, 대부분의 OS가 채택(사용자가 알아서 강제종료