출처 인프런 강의
0. 서론
이 사진을 써먹기 위해 여기까지 기다렸다.
1. 시스템 모델
데드락이란 어떤 한 프로세스 집합내의 모든 프로세스가 집합 내 다른 프로세스에 의한 이벤트를 위해 대기하는 상황을 이야기 한다. 다시 말하면, 대기중인 스레드가 자신의 상태를 다시 바꾸지 못하는 상황으로, 필요로 하는 자원이 다른 스레드에 의해 점유되었기 때문이다.
유한 자원을 가정했을때, 어떤 자원을 요청했을때, 해당 종류의 자원 중 어느 인스턴스를 할당해줘도 상관없다. 이 경우 스레드는 request - Use - release의 과정을 거친다.
2. 데드락 발생
하지만 아래와 같은 경우에 데드락이 발생할 수 있다.
3. 데드락 발생 조건
데드락 발생의 4가지 필요조건
(1) 상호 배제: 적어도 하나의 자원이 공유되지 않는(non-shared) 않아야한다.
(2) 점유 대기: 어떤 스레드가 최소한 하나의 자원을 점유하고 다른 자원을 획득하기 위해 대기하고 있어야 한다.
(3) 선점 불가: 자원은 선점될 수 없다.
(4) 순환 대기: 대기중인 스레드의 집합이 의존 그래프를 그렸을 때 순환한다.(circular)
Resource-Allocation Graph: 데드락 발생을 묘사하기 위해 그리는 그래프
사이클이 존재하면 데드락이 발생한다.
데드락을 대하는 3가지 방법
(1) 그냥 문제를 무시한다.
(2) 데드락을 방지/회피한다. 하지만 방지는 굉장히 어렵다. 회피는 Banker's Algorithm을 사용한다.
(3) 하지만 주로, 데드락 상황을 감지하고 문제를 해결하는 방식을 적용한다.
4. 데드락 방지
데드락을 발생하지 않기 위해서는 위에서 말한 발생 조건 중 하나만 막으면 된다.
(1) 상호 배제: 하지만 일반적으로 대부분의 경우에서 이건 적용 불가능
(2) 점유 대기: 자원 요청시 다른 자원을 점유하지 않아야 한다는 조건을 적용할 수 있으나, 실용적이지 못한 방법이다.
(3) 선점 불가: 선점을 가능하게 만들 수 있다. 하지만 일반적으로 대부분의 응용에 적용하는 것이 불가능하다.
(4) 순환 대기: Some practical. 모든 자원 종류에 순서를 부여한다. 그리고 자원 요청을 오름차순으로만 할 수 있다. 하지만 기아 문제가 발생할 수 있다. 이 방법을 통해 순환 대기가 일어나지 않음을 증명할 수 있다. 하지만 이마저도, lock이 동적으로 획득되는 경우 데드락 방지가 보장되지 않는다.
5. 데드락 회피
데드락을 방지하는 것은 굉장히 많은 단점을 가지고 있다. 따라서 데드락을 회피하려는 시도가 등장했다.
시스템은 스레드가 향후 발생 가능한 데드락을 회피할 수 있도록 대기시킨다. 이를 위해서는 자원이 어떻게 요청되는지에 대한 정보가 필요하다.
사전 정보가 주어졌을때, 데드락 상황에 진입하지 않는 시스템 알고리즘을 구성할 수 있다. 요구되는 자원의 최대 개수, 가용 개수, 할당된 개수, 최대 수요를 알면 된다.
Safe State :
unsafe state가 데드락을 곧바로 의미하는 것은 아니나, safe state면 데드락은 확실하게 피할 수 있다.
시스템 초기 상태는 safe state다.(자원이 점유되지 않으므로) 이후부터 보든 자원 요청에 대해서 자원 할당 가능 여부를 결정하며, 자원 요청은 시스템이 safe state 상태를 유지할 때만 승인된다.
Claim edge라는 인스턴스를 추가하여 사이클이 없을 때, 자원이 할당 될 것이다.
하지만 RAG는 복수의 인스턴스를 가지는 자원의 경우 적용이 불가능하다.
따라서 Banker's Algorithm을 적용할 수 있으나, 덜 효율적이고 더 복잡하다.
6. Banker's Algorithm
6.1 Data structure
n개의 스레드, m개의 자원 종류가 있다. avilable은 가용 가능한 자원의 종류의 수를 가리키는 벡터다. Max는 각 스레드의 최대 수요를 정의한다. Allocation은 현재 각 스레드에 할당된 자원의 종류와 해당 자원의 개수를 나타낸다. Need는 앞으로 할당이 더 필요한 자원의 종류와 개수를 나타낸다.
6.2 알고리즘
7. 데드락 감지
시스템이 데드락을 방지 혹은 회피하지 않는 경우, 데드락은 발생 할 수 있다. 하지만 방지는 커녕 회피에도 상당한 비용이 발생한다. 그래서 일반적인 경우 데드락을 감지하고 해소하는 방식을 사용한다.
각 자원이 Single-instance를 가지는 경우, wait-for graph를 주기적으로 그려서 데드락을 감지한다.
복수의 인스턴스를 가지는 경우 위의 그래프는 사용할 수 없다. 따라서 banker's algorithm과 유사한 감지 알고리즘을 사용한다.
8. 데드락 해소
데드락 감지 알고리즘 수행 횟수는, 데드락 발생 빈도, 스레드의 수에 따라 달라진다. 너무 드물게 수행하면, 사이클이 너무 많이있어서 데드락을 발생시키는 사이클을 특정하기 어렵다.
데드락이 발생하는 경우, 알람을 보내고, 자동으로 해소하기도 한다. 해소하는 방법은 모든 프로세스를 중단하거나, 데드락 사이클이 해소될때까지 프로세스를 하나씩 중단하는 방법이다.
아니면 희생될 프로세스를 선택해서 safe state 상태로 rollback 시키고, 다시 시작한다. 단 기아 문제를 해결하기 위해 희생될 프로세스로 선정되는 횟수를 제한한다.
