운영체제의 이해 10장: 데드락 문제 및 그 해법 (2023.05.28)

  동기화는 공유 데이터의 일관성을 위해 프로세스들 간에 실행 순서를 적절히 유지할 수 있도록 해주는 것이다. 하지만 상호배제의 조건을 만족시켰어도 데드락의 문제가 발생할 수 있다. 데드락은 죽어있는 잠김 상태, 전혀 풀릴 수 없는 잠김 상태를 의미한다. 즉, 프로세스의 관점에서 본다면, 어떤 집합에 속한 프로세스들 모두가 대기 상태로서 존재하는데 이들이 기다리는 이벤트가 이 집합 속의 다른 프로세스에 의해서 발생해야 할 때를 말한다. 예를 들어 신호등이 없는 사거리 상황에서 모두 앞이 막혀 진행하지 못할 때가 그렇다.

  자원의 요청과 할당을 도식화로 표현한 것이 자원 할당 그래프다. 자원은 공유 데이터를 말하는데 그래프에서는 프로세스와 함께 노드로 표현하고 특정 자원에 대해 여러 개의 종류가 존재할 수 있다. 프로세스가 자원을 할당받았을 때는 할당에지로, 아직 할당받진 못했지만 필요로 할 때는 요구에지로 표현한다. 데드락의 발생여부는 이 자원 할당 그래프에서 사이클이 존재하는지의 여부로 판단한다. 사이클에 포함된 자원들이 한 개씩만 존재할 때 사이클이 발생한다면 데드락이 나타나지만 사이클이 있더라도 자원들이 여러 개가 존재할 경우에는 데드락이 아닐 수 있다.

  이러한 데드락 문제를 해결하기 위해 데드락 방지 기법, 데드락 회피 기법, 데드락 탐지 및 복구가 있다. 데드락 방지 기법은 데드락 발생 조건들 중 하나라도 만족시키지 않음으로써 데드락 발생을 방지하는 것이다. 현실적으로 보유 및 대기와 원형 대기 조건만 고려하는데, 보유 및 대기를 피하기 위해서는 필요한 모든 자원들이 사용 가능할 때까지 기다렸다가 일괄적으로 확보하는 방법이 있다. 이것은 당장 사용하지도 않을 자원들까지 미리 확보하므로 자원의 활용률을 저하시키고 또 동시에 사용가능한 상태까지 기다리는 과정에서 기아 문제가 발생할 수 있다는 단점이 있다. 원형 대기를 피하는 방법에는 자원들에 대해 요청 순서를 사이클이 없도록 고정해 놓는 것이다. 이는 자원 간의 대기 그래프에서 단방향으로 표현되므로 사이클이 발생하지 않아 데드락이 발생하지 않는 것이다.

  데드락 회피 기법은 이전 기법보다 자원의 활용률을 높일 수 있는 방식으로서 자원을 필요한 시점에 가서 요청하는데 요청한 자원을 할당할 때 데드락이 발생할 가능성을 고려하여 가능성이 없을 때만 할당하고 있을 때는 할당을 보류하는 방식이다. 데드락 발생 가능성을 따질 때 각 프로세스들이 향후 어떤 순서로 자원을 요청할 건지에 대한 정보가 필요하다. 그에 따라 다익스트라가 제시한, 기존의 그래프에 클레임 에지를 더한 자원 할당 그래프를 이용한다. 데드락 회피 기법은 자원 할당을 요청받을 때마다 데드락 발생 가능성을 검사하기에 오버헤드가 크고 발생 가능성은 있어도 실제로는 안 그럴 수 있으니 여전히 자원의 활용률이 떨어진다.

  데드락 탐지 및 복구는 현재 상태에 대한 정보만 사용하여 요청한 자원이 사용 가능하기만 하면 무조건 할당한다. 자원을 최대로 사용하지만 데드락이 발생할 수 있으므로 데드락이 발생하면 체크포인트로 롤백하거나 데드락과 관련된 프로세스들을 강제 종료시킨다.