정의

DeadLock 이란 두 개 이상의 프로세스가 서로의 작업이 종료되기만을 기다리고 있는 상태를 의미한다

A : 너(B) 가 쓰고 있는 자원이 여유가 생기면 일해야지
B : 너(A) 가 쓰고 있는 자원이 여유가 생기면 일해야지
A,B : ?????

여기서 말하는 자원은 둘 이상의 주체가 같이 사용하는 것이라면 무엇이든 가능하다.

컴퓨터 입장에서는 cpu, file, I/O device, lock 등등이 자원이 될 수 있다

발생 필요조건

데드락이 발생할 수 있는 조건은 아래 4가지와 같다

다만 아래에서 나오는 조건들은 '필요 조건' 이라는 것을 알아둬야 한다

1. Mutual Exclusion (상호 배제)

하나의 자원에 대해서 단 하나의 프로세스만이 독점(사용)할 수 있는 상황

2. Hold and Wait

하나의 프로세스는 적어도 하나의 자원을 사용하고 있고, 다른 프로세스가 사용하는 자원을 사용하려고 하는 상황

3. No Preemption

자원을 사용하고 있는 프로세스에 개입하여 자원을 빼앗아 가는 것이 허용되지 않는 상황

4. Circular wait

1번이 2번 - 2번이 3번 - 3번 1번 의 자원을 요청하고 있는 상황

공유 자원에 대해서는 '독점권' 이 필요한 상황이 충분히 존재하지만, 이 독점권을 잘못 나눠줬을 경우에는 서로가 서로의 독점권을 얻기 위해 기다리는 상황이 벌어진다.

내 일이 끝나야 자원을 스스로 제자리에 돌려놓는다. 내 일이 끝나는 조건 중에 다른 사람이 쓰고 있는 자원이 필요한 경우가 존재한다. 자칫 잘못하면 서로의 로직에서 서로가 사용하고 있는 자원을 요구하는 상황이 벌어진다

Resource Allocation Graph

현재 프로세스들이 자원을 요청 하고 점유 하는 상황을 나타내기 위해서 작성할 수 있는 그래프이다.

Resouce / Vertex / Edge 로 이루어 져 있고

Edge 는
Resource -> Vertex 방향으로 향하는 Assignment Edge 와
Vertex -> Resource 방향으로 향하는 Request Edge 가 있다

요청을 하지 않는 자원은 언젠가는 free 된다 (데드락 상관 쓸 필요가 없다), 이렇게 언젠간 양보 가능한 자원을 남겨 두고, 할당 받은 자원을 지우고, 요청하는 자원을 얻으려 할 때, 자원이 부족하다면 데드락이 발생한다.

관리

사실 관리 방법이 다소 당연한(?) 것일 수 있는데

1. Prevention
   데드락이 발생하지 않게 잘 예방하자...

2. Allow process to enter deadlock, but detect and recover it
   데드락이 발생한다 치더라도, 자원을 뺏어서 다시 나눠주는(preemption) 방식을 채택 가능하다

3. 무시하고, 안 일어나길 빌기
   데드락은 웬만하면 잘 안 발생하고, 데드락을 예방하는데 드는 비용이 더 클 수 있다. 실제로 많이 채택하는 방식이라고 함

예방법

위에서 데드락의 발생의 필요 조건을 살펴보았다. 그렇다는 것은 4개 중 어느 하나라도 예방 한다면, 데드락에서 벗어날 수 있을 것이다.

1. 상호 자원 공유
   다만 동기화 로직을 추가해야한다

2. 자원을 할당받고, 추가 자원을 요청하는 것이 아닌, 모든 필요 자원이 가용할 때 비로소 자원을 통째로 할당 받는다

3. 선점 알고리즘을 추가한다. 가령 하나의 자원을 너무 오래 특정 프로세스가 소유하고 있으면, 할당된 자원을 빼앗아 오는 방식 등이 있다

4. 자원이 순환하지 않도록 구조를 만든다

데드락을 예방하기 위해서 로직을 만드는 것도 중요하지만, 관리에서 언급했듯 예방하는데 드는 비용이 더 커지는 것을 잘 고려해서 설계해야한다

회피

단어 마다 의미가 다소 비슷하다고 느껴지는데, 엄연히 예방과 회피는 다르다.
예방은 발생 요인을 없애는 것이고, 회피는 발생하기 전에 미리 알고 다른 방향으로 트는 것을 의미한다.
데드락이 없는 세상을 만드는 것과 데드락과 공존하는 법을 찾는 것의 차이?

데드락을 회피하기 위해서는

1. 데드락이 발생할 것이라고 예측을 할 수 있는 추가적인 정보 가 필요하다

2. 이 정보를 바탕으로 자원 요청에 대해서 자원을 할당할지 말지를 결정할 수 있다

사용하는 정보의 종류와 양에 따라서 알고리즘이 바뀐다고 생각하면 편할 듯 하다 !!

safe state

데드락이 발생할 수 있는 세상에서 회피법이 존재한다면 safe state 하다고 한다.

unsafe state

이게 조금 헷갈릴 수 있는데, 데드락이 발생할 위험이 있는 상황에서 회피법이 없지만..! 아직 데드락이 아니면 일단은 unsafe state 라고 하는 것 같다. 즉 데드락의 위험률이 굉장히 커진 상태

safe sequence

그리고 그 때의 회피 순서, 즉 어떤 프로세스부터 자원을 할당해주면 되는지를 프로세스 순서대로 나타낸 것을 의미한다

Banker's Algorithm

대표적인 데드락을 해결하는 방식을 구현한 알고리즘이다

전제 조건

1. 새로운 프로세스가 메모리에 적재 되었을 때, 해당 프로세스가 필요로 하는 자원 별 최대 값이 명시되어 있어야 한다.

2. 자원에 대한 요청이 있을 때, 해당 자원이 할당 되고나서 시스템이 safe state 에 존재해야 한다

3. 그렇지 않다면, 자원 할당을 하지 않고, 블로킹 시킨다

구조

프로세스 별 Max, Allocation, Need 가 존재하고,
전체 시스템의 Available Resource 가 주어진다

프로세스 별로 Max - Allocation = Need 가 나올 것 이고
해당 값이 Available Resource 의 수 보다 작거나 같아야지만 자원이 할당가능하다는 의미다

한계

SJF(Shortest Job First) 스케줄링 방식처럼 모든 프로세스의 작업 시간(여기서는 필요 자원 수) 를 예측 가능하다면 확실히 효과 있는 알고리즘이 될 수 있다.

다만 이러한 정보를 런타임에 예측한다는 것은 상당히 어렵기 때문에, 해당 알고리즘 보다는 현재 내 상황이 데드락 위험이 있는지 판단 하고 회피 하는 방식을 채택하는 것이 일반적이라고 한다