지난 글에서는 공유 자원에 대해서 여러 스레드 및 프로세스가 접근했을 때 발생하는 문제와 이를 동기화하는 방법에 대해 알아보았습니다. 이번 시간에는 데드락(Dead lock)에 대해서 알아보겠습니다.
데드락이란?
위의 그림은 데드락을 설명하는데 자주 이용되는 그림입니다. 그림처럼 데드락은 오도가도 못하는 상태를 의미합니다. 좀 더 전문적인 시선에서 데드락을 바라보면 데드락은 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있는 상태입니다. 즉, 각각 서로 상대방이 가진 자원이 필요한데 이를 얻지 못해 두 작업 모두 끝을 맺지 못하는 상황을 의미합니다. 이렇게 된다면 CPU 자원의 낭비뿐만 아니라 시스템의 품질 저하를 유발하기에 데드락이 발생하는 것을 막거나 예방하는 것이 중요합니다. 먼저 데드락은 어떤 상황에서 발생하는지 알아보겠습니다.
데드락 발생조건
데드락의 발생조건은 4가지가 있으며 해당 네 조건이 모두 만족한 상황에서만 데드락이 발생합니다. 각 조건에 대해서 알아보겠습니다.
- 상호배제 : 자원은 하나의 프로세스 혹은 스레드만 접근할 수 있습니다.(자원을 공유해서 사용할 수 없습니다.)
- 점유대기 : 스레드 및 프로세스가 하나의 자원을 흭득한 상태로 다른 자원을 대기합니다. (한번에 필요한 자원을 모두 얻는 것이 아닌 순차적으로 자원을 얻는 상황입니다.)
- 비선점 : 다른 스레드 및 프로세스에 할당된 자원을 빼앗을 수 없습니다.(자원의 반납은 자원을 흭득한 스레드 및 프로세스만 할 수 있습니다.)
- 순환대기 : 스레드 및 프로세스들이 순환의 형태로 서로의 자원을 기다리고 있는 상태를 의미합니다.
데드락 해결 방법
데드락을 해결하는 방안에는 데드락 방지, 데드락 회피 , 데드락 감지와 복구 , 데드락 무시 가 있습니다. 각각에 대해서 알아보겠습니다.
데드락 방지
데드락 방지 기법은 데드락의 발생조건 네 가지 중 하나가 충족되지 않게 시스템을 설계하는 방식입니다. 네 가지 조건 중 하나만 성립하지 않아도 데드락이 발생하지 않기에 어느 한 조건을 방지하는 방식으로 구현됩니다. 각각의 조건을 방지하는 방법에 대해 살펴보겠습니다.
- 상호배제 방지 : 리소스를 여러 스레드 및 프로세스가 공유해서 사용하게 하는 방법 → 해당 방식은 사실상 불가능
- 점유대기 방지 : 스레드 및 프로세스가 작업을 시작하기에 앞서서 필요한 모든 자원을 흭득한 후에 작업을 수행 (어느 하나의 자원을 얻지 못하면 다른 필요한 자원들도 흭득하지 않는 방식) → 획득하려는 자원 중에 다른 작업에서도 자주 사용하는 자원이 있을 경우 기아현상이 발생할 수 있습니다.
- 선점 방식 : 스레드 및 프로세스가 다른 스레드 및 프로세스의 자원을 선점할 수 있는 방법
- 순환 대기 방지 : 모든 자원에 순서 체계를 부여하여 오름차순으로 자원을 흭득하는 방법
데드락 회피
다음으로는 데드락 회피 방법에 대해서 살펴보겠습니다. 데드락 회피는 말 그대로 데드락이 발생할 것 같은 상황을 피하는 방식입니다. 데드락의 발생을 회피를 하기 위해서는 추가적인 정보를 통해 데드락이 발생할 것 같은지 파악해야 합니다. (추가적인 자료에는 자원에 대한 정보, 현재 자원을 사용 여부 등이 있습니다.)
데드락 회피를 위한 알고리즘에는 자원 할당 그래프 알고리즘과 은행원 알고리즘이 있으며 자원 할당 그래프 알고리즘에 대해서 알아보기에 앞서서 먼저 자원 할당 그래프에 대해서 간단하게 살펴보겠습니다.
자원할당 그래프는 자원과 프로세스(스레드)간의 관계를 나타낸 방향 그래프입니다. 자원 → 프로세스(스레드)는 프로세스(스레드)가 자원을 현재 획득하는 것을 의미하며 프로세스(스레드) → 자원은 프로세스(스레드)가 해당 자원을 획득하고자 하는 것을 의미합니다. 해당 그래프를 통해서 교착상태가 발생하는지 아닌지를 파악할 수 있는데 이때의 전제 조건은 자원(R1과 R2)이 단일 개인 것이 보장되어야 합니다. (자원의 개수가 여러 개 이면 사이클을이 발생하더라도 항상 데드락이 발생하는 것은 아닙니다)
위의 그래프를 보면 R1 → T1, 이고 R2 → T2 이므로 T1은 R1을 가지고 있고 T2는 R2를 가지고 있는 상황입니다. 더불어 T1 → R2 이고 T2 → R1 이므로 T1은 R2를 필요로 하고 T2는 R1을 필요로 하는 상황으로 데드락 상태입니다. 좀 더 쉽게 파악하는 것은 해당 그래프에서 사이클이 발생하지는 파악하면 됩니다. 현재 그래프는 T1 → R2 → T2 → R1 → T1 인 사이클이 발생하기에 데드락이 발생하는 것을 알 수 있습니다.
자원할당 그래프 알고리즘은 해당 그래프에 예약 간선을 추가하는 것으로 예약 간선을 통해서 사이클이 생성되는 것이 감지되면 해당 과정에서 데드락이 발생할 수 있다고 판단해 자원을 제공하지 않고 사이클이 발생하지 않는 상태에서 자원을 제공하는 방식입니다. 해당 알고리즘은 프로세스(스레드)들이 필요로하는 자원에 대한 정보가 필요합니다.
은행원 알고리즘의 경우 프로세스(스레드)가 작업을 시작하기에 앞서서 필요로 하는 자원에 대한 정보를 미리 알리는 방식으로 해당 자원을 할당해 주었을 때 데드락이 발생한다면 제공하지 않고 그렇지 않다면 자원을 제공해주는 방식입니다.
데드락 감지와 복구
데드락 감지와 복구 방식은 일단 데드락을 막는 방식이 아닌 데드락을 허용하되 데드락이 발생하게 되면 이를 복구하는 전략입니다. 복구 전략에는 프로세스 종료와 자원의 일시적인 선점을 허용하는 방식이 있습니다.
프로세스를 중지하는 방법은 교착상태가 발생한 모든 프로세스를 중지시키는 방법과 교착 상태가 제거될 때까지 하나의 프로세스를 제거하는 방법이 있습니다. 프로세스를 중간에 종료하는 것은 큰 비용이 발생하는 작업이기에 다양한 요소들을 고려해야합니다. (프로세스의 우선순위, 남은 작업시간, 프로세스가 점유한 자원과 해당 자원의 수, 프로세스에 더 필요한 자원의 수, 종료되어야 하는 프로세스의 수 등)
자원의 일시적인 선점 방식은 교착상태가 사라질 때까지 한 프로세스의 자원을 다른 프로세스에게 제공하는 방식입니다. 자원 선점 방식을 활용하기 위해서는 고려할 점이 있습니다. 먼저 희생자가 선택될 때에는 작업 비용이 적은 프로세스(스레드)를 선정해야한다는 것입니다. 두 번째는 같은 프로세스가 여러번 희생자가 되지 않는 것입니다.
데드락 무시
데드락 무시는 OS 레벨에서 데드락에 대해서 무시하는 방식입니다. 데드락의 처리는 프로그램 부분에서 처리하게 하는 방식으로 무책임하다고 느낄 수 있지만 많은 OS가 채택하고 있는 방식입니다.
정리
- 데드락은 2개 이상의 프로세스 및 스레드가 서로의 자원을 기다리면서 아무런 작업을 수행하고 있지 않는 상태를 의미합니다.
- 데드락의 조건에는 상호배제, 점유 및 대기, 비선점, 환형 대기가 있습니다.
- 데드락을 해결하기 위한 방식에는 예방, 회피, 감지 및 회복, 무시 방법이 있습니다.
- 예방은 데드락 4가지 조건 중 1개의 조건을 예방해 데드락을 해결하는 방식입니다.
- 회피는 추가적인 정보를 바탕으로 데드락이 발생할 것을 예측하고 피하는 방식입니다. (자원 할당 그래프 알고리즘, 은행원 알고리즘)
- 감지 및 회복 방식은 데드락이 발생한 후에 이를 해결하는 방법으로 모든 프로세스를 종료시키는 방법과 자원의 일시적인 선점을 허용하는 방식이 있습니다.
- 무시는 데드락의 발생을 OS 레벨에서는 무시하고 이는 프로그램 레벨에서 처리하도록 하는 방식입니다.
