- 데드락은 우리말로 "교착상태"라 하여 그림과 같이 차가 막힌 상태처럼, 서로 자원을 내놓지 않고, 상대방이 가진 자원을 희생하기를 기다리는 것과 같다. 차들은 길목을 갖고 있고, 길을 원하는데 그 길은 다른 차들이 가지고 있고 그 차들도 양보하지 않은 채 다른 길을 원하는 것이다.
-
즉 일련의 프로세스들이 서로가 가진 자원을 기다리며 잠들어 있는 상태이다.
-
여기서 말하는 자원은 하드웨어일수도(ex. 메모리 공간) 소프트웨어일수도(ex.세마포어: 프로세스가 A,B가 서로의 자원을 획득하기를 기다리는 경우) 있다.
-
프로세스가 자원을 사용하는 4개의 절차가 있다. 자원을 요청하고, 자원을 획득하고, 자원을 사용하고, 자원을 반납하는 단계다.
- 데드락이 발생하는 조건 4가지를 만족해야 데드락이 된다.
- 첫 번째는 상호 배제이다. 자원을 독점적으로 써야지 데드락이 발생한다.
- 다음은 비선점, 자원을 강제로 빼앗기지 않는 경우다.
- 다음은 보유 대기다. 이미 가진 자원을 보유하며 추가 자원을 기다리는 경우다.
- 마지막은 순환 대기다. 필요로 하는 자원들이 꼬리에 꼬리를 물고 사이클이 형성되는 경우다.
- 데드락이 발생했는지를 자원할당 그래프를 통해 알아본다. 동그라미는 프로세스, 사각형은 자원, 사이의 화살표는 자원-> 프로세스, 프로세스->자원을 나타낸다. 자원->프로세스는 프로세스가 자원을 갖고 있다. 프로세스->자원은 프로세스가 자원을 요청했지만 획득하지 못했다는 뜻이다. 사각형 안의 점은 자원의 수(인스턴스)를 의미한다.
- 위 그래프에는 사이클이 존재하지 않는다. 그러므로 데드락이 아니다.
- 그래프에 사이클이 없으면 데드락이 아니다.
- 그래프에 사이클이 있는 경우는 데드락일 수도 아닐 수도 있다.
- 만약 자원 당 인스턴스가 하나밖에 없으면 데드락이고, 만약 여러개의 인스턴스가 프로세스마다 있으면 데드락이 아니다.
- 따라서 왼쪽 그림은 데드락이다. 자원2의 인스턴스가 2개지만 사이클이 2개 만들어졌다.
- 오른쪽은 데드락이 아니다. 프로세스 2와 4가 사이클에 연루되지 않아 다른 프로세스가 자원을 필요로 할 때 내어줄 수 있다.
- 데드락을 어떻게 처리할 수 있을까 크게 4가지가 있다.
- 데드락이 생기지 않도록 미연에 방지하거나, 데드락이 생기도록 놔두고, 데드락을 탐지하여 회복하는 방법이 있다. 혹은 데드락이 생기든 말든 시스템이 관여하지 않고 사람이 알아서 해결하도록 하는 방법이 있다.
-
데드락 프리벤션은 데드락을 미연에 방지한다. 데드락이 발생하는 네 가지 조건 중 하나를 원천적으로 차단한다.
-
먼저 자원을 공유하도록 할 수 있다. 그러나 공유해서는 안되는 자원의 경우 이는 성립시켜야 한다.
-
자원을 기다리는 상황에서는 자원을 보유하지 않도록 하여 보유대기 문제를 해결한다. 프로세스가 시작할때 필요한 모든 자원을 할당받게 하고 프로세스 종료 시 모두 반납하게 할 수 있다. 그러나 이 경우 매 시점마다 필요한 자원이 다른데 모두 처음에 다 받게 하면 비효율성이 생길 수 있으므로, 자원이 필요한 경우에만 그때그때 할당받게 하지만, 어떤 자원이 필요한 경우 현재 보유한 자원을 모두 뱉어내도록 한 후 기다리게 하면 된다.
-
다음 비선점 문제는, 자원을 선점할 수 있도록, 프로세스가 자원을 빼앗아 올 수 있도록 하여 해결한다. CPU와 메모리는 자원을 빼앗아도 괜찮은데 이는 cpu와 메모리는 자원을 뺏겨도 자원 상태를 쉽게 저장하고 자원을 다시 얻었을 때 복구하여 실행하는 것이 용이하기 때문이다. 그러나 어떤 자원은 뺏겼을 때 복구가 어렵다.
-
마지막은 사이클을 막는 것이다. 이를 위해서는 자원마다 번호를 매겨 순서를 정한다. 그리고 항상 낮은 번호부터 획득해야지만 높은 번호를 획득할 수 있도록, 정해진 순서대로만 자원을 할당한다. 그러면 누구는 3번 자원을 가지고 1번을 기다리고, 누구는 1번을 가지면서 3번을 기다리며 사이클이 생기는 상황을 해결할 수 있다.
-
데드락 프리벤션은 자원 이용률이 낮아지고 잦은 제약조건으로 시스템의 성능이 낮아지는 문제가 있다.
- 두 번째는 데드락 어보이던스다. 역시 미연에 데드락을 방지하는 방법이지만, 프로세스가 시작될 때 프로세스가 평생에 쓸 자원의 최대량을 알고 있다고 가정하고 데드락을 회피한다.
- 따라서 내가 어떤 자원을 할당했을 때 데드락이 발생할 여지가 있다면 자원의 여분이 있음에도 할당하지 않는 것이다.
- 데드락 어보인던스도 두 가지로 나뉠 수 있다.
- 자원의 인스턴스가 하나씩 밖에 없으면 이전의 자원 할당 그래프를 통해 어보이던스를 수행하고
- 자원의 인스턴스가 여러개면 뱅커스 알고리즘이라는 것을 통해 어보이던스를 수행한다.
- 자원의 인스턴스가 하나인 경우다.
- 여기서 점선 화살표는 프로세스부터 자원으로만 가는데 이는 이 프로세스가 평생에 적어도 한번은 이 자원을 사용할 여지가 있음을 얘기한다. 실제로 그 프로세스가 점선으로 연결된 자원을 요청하면 점선에서 실선으로 바뀐다.
- 위 사진은 아직 점선으로 되어 있으므로 데드락은 아니다.
- 그러나 데드락 어보이던스는 최악의 상황을 가정한다. 만약 그 프로세스가 자원을 요청했을 때 데드락이 생길 수 있는 가능성이 있으면 자원을 제공하지 않는다.
- 자원당 인스턴스가 여러개인 경우 뱅커스 알고리즘을 이용한다.
- 프로세스가 5개, 자원이 세 종류가 있다(A,B,C). 인스턴스가 a는 10 b는 5 c는 7개가 있다. 다섯개의 프로세스가 abc자원 중 몇개를 가졌는지 그림의 allocation에 나타나 있다. 그리고 max에 프로세스가 평생동안 사용할 자원을 선언한다. available에 현재 할당 가능한 자원을 표시하고, 프로세스가 자원을 요청하면 데드락의 가능성을 고려하여 자원을 할당한다. need는 추가 요청 가능성을 표시한다. max에서 현재 할당량을 빼면 need가 만들어진다.
- 따라서 need가 현재 가용할 수 있는 자원(available)으로 처리가 가능한 수준이면, 자원을 제공한다.
