9일차 - Deadlock(교착상태)

오늘은 Deadlock에 대해 배웠다.

프로세스 동기화를 배우면서 deadlock상황에 대해 간단히 언급이 되었는데 오늘은 더 저세하고 처리방법에 대해 알 수 있었다.

 

 

 

1. Deadlock이란

deadlock은 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태를 말한다.

즉, 자신이 가지고 있는 자원들은 내어놓지 않고 다른 프로세스가 가지고 있는 자원을 요청하는 상태여서 진행이 되지 않는 상태이다.

여기서 말하는 자원은 하드웨어, 소프트웨어 등을 포함하는 개념으로 I/O device, CPU cycle, memory space, semaphore 등을 뜻한다.

 

deadlock 상태인 예를 들어 얘기해보자.

시스템에 2개의 tape drive A, B가 존재하고 프로세스1은 A를 가지고 있고 프로세스2는 B를 가지고 있다.

여기서 작업이 마무리 되고 자원을 반납한다면 deadlock을 발생하지 않을 것이다.

하지만 이 상태에서 프로세스1이 B를 요청하고 프로세스2는 A를 요청한다면 프로세스 둘 다 진행이 되지 않으므로

deadlock이 발생한다.

 

이러한 deadlock이 발생하는 조건은 무엇일까?

deadlock이 발생하는 조건은 4가지로 하나라도 만족하지 않으면 deadlock은 발생하지 않는다.

1) Mutual Exclusion (상호 배제)

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

2) No Preemption (비선점)

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

3) Hold and Wait (보유대기)

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

4) Circular Wait (순환대기)

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

 

 

 

2. Resource - Allocation Graph (자원할당 그래프)

자원할당 그래프는 deadlock이 발생했는지 알아보기 위해 사용되는 도표이다.

자원할당 그래프는 프로세스는 원으로 표시되고 자원(resource)는 박스로 표시된다.

자원의 instance 갯수는 박스 내에 점으로 표시한다.

또한, 자원할당 그래프에는 간선(화살표)가 두 가지 방향으로 존재하는데 프로세스에서 자원으로 향하는 화살표와

자원에서 프로세스로 향하는 화살표가 존재한다.

프로세스에서 자원으로 향하는 화살표는 프로세스가 자원을 요청한 상태를 의미하고 자원에서 프로세스로 향하는 화살표는 프로세스가 해당 자원을 보유하고 있는 상태이다.

자원할당 그래프 예시

 

이렇게 자원할당 그래프를 그릴 수 있고 deadlock의 판단 기준은 cycle이 형성되었는지를 보면된다.

하지만 cycle이 형성되었다고 무조건 deadlock이라고 판단할 수는 없고 자원의 instance갯수를 보고 판단해야한다.

cycle이 형성되었는데 자원의 인스턴스갯수가 1개 뿐이면 무조건 deadlock이다.

cycle이 형서되었는데 자원의 인스턴스갯수가 여러 개이면 deadlock일수도 있고 아닐 수도 있으므로 상황을 보고 판단해야한다.

 

 

3. Deadlock 처리방법

지금까지 deadlock이 무엇인지, deadlock이 발생하는 조건이 무엇이 있는지에 대해 배웠다.

오늘 배운 deadlcok 처리방법은 deadlock prevention, deadlock avoidance, deadlock detection and recovery, deadlock ignorance 4가지로 앞에 prevention과 avoidance는 deadlock이 발생하지 않도록 사전에 조치하는 것이다.

detection and recovery와 ignorance는 deadlock이 발생한 후에 처리하는 방법이다.

지금부터 하나씩 자세히 알아보도록 하겠다.

 

 

4. Deadlock Prevention

Deadlock Prevention은 자원을 할당할 때 deadlock 발생조건 4가지 조건 중 어느 하나가 만족되지 않도록 조치하는 것이다.

조건 4가지를 하나씩 어떻게 만족하지 않게 하는지 알아보자.

1) Mutual Exclusion

조건 첫 번째는 항상 만족하는 것이므로 이것을 만족하지 못하도록 하는 방법은 없다.

2) No Preemption

process가 어떤 자원을 기다리는 경우 이미 보유한 자원을 강제로 빼앗게 하면 된다.

이렇게 강제로 빼앗으려면 state를 쉽게 저장하고 다시 불러올 수 있는 자원에서 사용해야한다.

3) Hold and Wait

프로세스가 자원을 요청할 때 다른 어떠한 자원도 가지고 있지 않은 상태에서 가능하도록 한다.

이렇게 하기 위해서는 2 가지 방법이 존재한다.

하나는 프로세스가 시작할 때 모든 필요한 자원을 할당하게 하는 방법이고

다른 방법은 자원이 필요할 경우 보유하고 있는 모든 자원을 놓고 다시 요청하는 것이다.

4) Circular Wait

모든 자원의 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.

예를 들어 순서가 3인 자원을 프로세스가 보유 중이고 순서가 1인 자원을 요청하여 할당받으려면 순서가 3인 자원을 놓고 받을 수 있는 것이다.

즉, 미리 정해진 순서(1,2,3,...)대로 자원을 할당받을 수 있는 것이다.

 

Deadlock prevention은 가자 원론적인 방법으로 효율성이 떨어지고 throughput이 감소하고 starvation 문제가 발생할 수 있다.

 

 

5. Deadlock Avoidance

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

여기서 말하는 부가적인 정보는 다양한 것이 있을 수 있는데 강의에서는 부가적인 정보를 프로세스가 시작할 때 알려주는 프로세스가 평생 쓸 자원의 최대량이라고 정하고 배웠다.

이렇게 부가적인 정보를 이용해서 2가지의 avoidance 알고리즘을 볼 수 있다.

 

1) Resource Allocation Graph Algorithm (자원의 instance가 하나 밖에 없는 경우)

이 알고리즘은 자원할당 그래프를 활용하는 것인데 앞에서 말한 그래프에서 점선 화살표가 추가 되었다.

점선으 화살표는 프로세스가 자원을 미래에 요청할 수 있음을 말하는 것이다.

이렇게 표현된 자원할당 그래프에서 프로세스가 자원을 요청했을 때 점선 화살표를 포함하여 cycle이 생기지 않는 경우에만 요청자원을 할당하는 것이다.

 

2) Banker's Algorithm (자원의 instance가 여러 개 있는 경우)

이 알고리즘은 예시를 들어 설명하면 이해하기 변할 것이다.

5개의 프로세스 P1, P2, P3, P4, P5가 있고 3개의 자원 A(10), B(5), C(7)이 있다. (괄호 안의 숫자는 instance갯수)

<Snapshot at time t0>

allocation은 현재 프로세스가 가지고 있는(할당받은) 자원의 갯수이고 max는 프로세스가 시작될 때 알려준 최대 사용량이다. available은 현재 상태에서 남아 있는(가용 가능한) 자원의 갯수를 나타낸다.

여기서 프로세스가 자원을 요청했을 때 남아 있는 자원의 갯수로 할당가능하더라도 요청을 모두 받아들이지 않는다.

먼저 Need의 갯수와 available의 갯수를 비교하여 need의 갯수가 available의 갯보다 작거나 같다면(모든 자원의 갯수를 비교) 요청을 받아들여 자원을 할당해준다.

만약 need가 더 크다면 할당가능한 자원이 있더라도 요청을 받아들이지 않는다.

 

즉, 위 상황에서 예시를 들어 다시 설명하면 P1이 A(1) B(1) C(1)를 요청했을 때 Need가 available보다 작으므로 요청을 받아들여 할당해준다.

반면 P2가 A(2)를 요청했을 때 available에 A(3)만큼있으므로 할당은 가능하지만 Need가 available보다 크므로 요청을 받아들이지 않는다.

 

이 알고리즘은 최대량은 알지만 최대량을 언제 사용하는지는 모른다. 그래서 최악의 경우을 가정하여 언제라도 최대를 요청해서 deadlock이 걸릴 수 있다고 생각해서 판단을 하게 된다.

 

 

6. Deadlock Detection and Recovery

이 알고리즘은 deadlock이 발생한 것을 감지하고 그 후에 대처를 하는 것이다.

deadlock avoidance와 유사하게 자원의 instance 갯수가 1개뿐이면 자원할당 그래프를 변형한 wait-for graph를 활용하여 deadlock을 감지하고 자원의 instance 갯수가 여러개이면 그 때의 프로세스와 자원의 상황을 파악한다.

 

1) wait-for graph

wait-for graph는 자원할당 그래프를 변형한 것으로 자원의 instance 갯수가 하나일 때 사용하는 그래프이다.

자원할당 그래프는 프로세스와 자원을 node로 사용하여 표현했지만 wait-for graph는 프로세스만 node로 사용하여 표현한다.

예를 들어 P1이 가지고 있는 자원을 P2가 기다리는 경우에는 P2 -> P1으로 화살표로 표현한다.

이러한 wait-for graph에 cycle이 존재하는지를 주기적으로 조사하여 deadlock을 파악한다.

 

2) 자원의 instance가 여러개인 경우

이 경우에는 banker's algorithm에서 보여준 예시처럼 프로세스가 할당받은 자원의 갯수, 요청한 자원의 갯수, 가용 가능한 자원의 갯수를 파악한다.

여기에서는 프로세스가 사용할 최대량에 대한 정보는 모르는 상태이다.

banker's algorithm은 최악의 경우를 생각하며 deadlock이 발생하지 않도록 자원 요청을 받아들였다.

하지만, 여기에서는 최대한 낙관적으로 상황을 바라본다.

지금 당장 request를 하지 않은 프로세스는 자신이 가지고 있는 자원을 반납한다고 생각하여 available으로 취급한다.

그렇게 계산을 해서 request를 차례대로 받을 수 있는 sequence가 존재하면 deadlock은 발생하지 않는다고 생각한다.

만약 sequence가 존재하지 않고 request를 받을 수 없다면 deadlock이 발생했다고 생각한다.

 

자원의 instance 갯수가 하나 뿐인 경우와 여러 개인 경우에 detection을 어떻게 하는지 알아보았다.

그러면 deadlock을 detection했다면 recovery는 어떻게 하면 될까?

recovery방법은 2가지가 있다.

 

1) Process termination

이 방법은 deadlock에 연류된 프로세스를 종료시키는 방법이다.

모든 deadlock에 연류된 프로세스를 한번에 종료시킬 수도 있고

deadlock이 발생하지 않을 때까지 프로세스를 하나씩 종료시킬 수도 있다.

 

2) Resource Preemption

이 방법은 프로세스의 자원을 빼앗는 방법이다.

비용을 최소화 할 victim(프로세스)를 선정하여 safe state(deadlock이 발생하지 않는 상황)으로 rollback하여 프로세스를 재시작한다.

이 경우에는 비용을 최소화 할 victim이 계속해서 하나의 프로세스만이 선정될 수 있는 starvation문제가 발생할 수있다.

이를 해결하기 위해 비용과 더불어 rollback 횟수도 고려하여 victim을 선정한다.

 

 

7. Deadlock Ignorance

Deadlock Ignorance는 deadlock이 일어나지 않는다고 생각하고 사전에 아무런 조치를 취하지 않는다.

그 이유는 deadlock이라는 것이 매우 드물게 발생하는 현상이여서 deadlock을 사전에 조치하는 것 자체가 큰 overhead를 발생시키기 때문이다.

그러면 deadlock이 발생하면 어떻게 해야할까?

시스템이 자체적으로 해결하는 것이 아니라 deadlock이 발생하면 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 종료시키는 등의 방법으로 대처한다.

현재는 대부분의 운영체제가 deadlock ignorance를 채택한다.