멈춰버린 프로세스, 원인은 무엇일까?
지난번 세마포어(Semaphore)를 정리하며 공유 자원에 대한 동시 접근을 제어하는 방법을 알아봤다. 하지만 여러 스레드나 프로세스가 얽혀 자원을 요청하는 과정에서, 예상치 못한 문제가 발생하곤 한다. 마치 차들이 서로 꼬리를 물고 멈춰버린 교차로처럼, 모든 프로세스가 다른 프로세스가 끝나기만을 기다리며 영원히 멈춰버리는 상황을 마주하게 된 것이다.
이 현상을 운영체제에서는 '교착 상태(Deadlock)'라고 부른다. 단순히 뮤텍스 락(Mutex Lock)을 순서대로 잘 걸기만 하면 해결될 줄 알았는데, 막상 문제가 발생하니 어디서부터 잘못되었는지 파악하기가 쉽지 않았다. 이번 시간에는 교착 상태가 정확히 무엇인지, 어떤 조건에서 발생하는지, 그리고 이를 어떻게 해결할 수 있는지에 대해 깊이 있게 정리해보고자 한다.
교착 상태(Deadlock) 파헤치기
1. 교착 상태란 무엇인가?
교착 상태는 두 개 이상의 프로세스(또는 스레드)가 서로가 가진 자원을 기다리며 블록(block)된 상태를 의미한다. 각자 자원을 하나씩 점유한 상태에서, 상대방이 점유한 자원을 요청하며 무한정 기다리는 것이다. 결국 어느 프로세스도 다음 단계로 진행하지 못하고 영원히 대기하게 된다.
가장 흔한 예시는 두 개의 스레드가 두 개의 락(Lock)을 서로 엇갈리게 요청하는 경우다.
스레드 T0는락 L1을 획득하고, 다음으로락 L2를 기다린다.스레드 T1은락 L2를 획득하고, 다음으로락 L1을 기다린다.
이 상황을 그림으로 그려보면 명확해진다. T0는 L1을 점유(Hold)하고 L2를 원하며(Wanted by), T1은 L2를 점유하고 L1을 원한다. 결국 서로가 서로의 발목을 잡는 순환 고리가 형성되어, 영원히 풀리지 않는 상태에 빠지게 된다.
Example of DeadLock
2. 교착 상태 발생의 네 가지 조건
교착 상태는 다음 네 가지 조건이 모두 동시에 충족될 때 발생한다. 즉, 이 중 하나라도 깨트리면 교착 상태를 예방할 수 있다는 의미가 된다.
상호 배제 (Mutual Exclusion)
자원은 한 번에 하나의 프로세스만 사용할 수 있다. 다른 프로세스가 사용하려면, 이전 프로세스가 자원을 해제할 때까지 기다려야 한다. (e.g., 뮤텍스 락)
점유 및 대기 (Hold and Wait)
프로세스가 최소 하나의 자원을 점유한 상태에서, 다른 프로세스에 할당된 자원을 추가로 요청하며 대기한다.
비선점 (No Preemption)
프로세스가 점유한 자원은 해당 프로세스가 작업을 마친 후 자발적으로 해제할 때까지 강제로 빼앗을 수 없다.
순환 대기 (Circular Wait)
각 프로세스가 다음 프로세스가 요구하는 자원을 가지고 있는, 꼬리에 꼬리를 무는 순환 형태의 대기열이 형성된다. (
P0->P1->P2-> ... ->P0)
3. 교착 상태 처리 방법
교착 상태를 다루는 방법은 크게 세 가지로 나뉜다. 대부분의 최신 운영체제는 세 번째 방법을 사용하는데, 이는 꽤 흥미로운 지점이다.
1) 교착 상태 예방 (Prevention)
가장 근본적인 해결책으로, 앞서 말한 네 가지 발생 조건 중 하나를 원천적으로 차단하는 방식이다.
순환 대기 조건 깨기: 자원 획득 순서를 강제하는 방법이다. 모든 자원에 고유한 번호(순서)를 부여하고, 모든 스레드가 그 순서에 따라서만 자원을 요청하도록 규칙을 정하는 것이다. 예를 들어, 시스템에
L1과L2라는 락이 있다면, '반드시L1을 먼저 획득한 후에만L2를 획득할 수 있다'는 규칙을 설정한다. 이렇게 하면 한 스레드는L1->L2순으로, 다른 스레드는L2->L1순으로 락을 획득하려다 발생하는 순환 고리를 원천적으로 차단할 수 있다. 이 방법은 전체 시스템의 락 전략에 대한 신중한 설계가 필요하지만, 매우 효과적인 예방책이다.점유 및 대기 조건 깨기: 필요한 모든 자원을 한 번에, 원자적으로(atomically) 획득하는 전략이다. 특정 작업을 시작하기 전에 필요한 모든 락을 한꺼번에 요청하고, 모두 획득할 수 있을 때만 작업을 시작한다. 만약 하나라도 획득할 수 없다면, 이미 획득한 락이 있더라도 모두 반납하고 다시 시도해야 한다. 이 방식은 스레드가 자원을 일부만 점유한 채 다른 자원을 기다리는 상황 자체를 없애준다. 하지만 두 가지 단점이 있다. 첫째, 특정 코드 블록에 어떤 락들이 필요한지 미리 모두 파악해야 하므로 유연성이 떨어진다. 둘째, 필요 이상으로 오랫동안 많은 자원을 점유하게 되므로 시스템의 전반적인 동시성(concurrency)을 저해할 수 있다.
비선점 조건 깨기: '다 가질 수 없으면, 가진 것도 포기하라'는 전략이다. 스레드가 특정 자원을 점유한 상태에서 추가로 다른 자원을 요청했는데 즉시 할당받을 수 없다면, 현재 가지고 있던 자원까지 모두 반납하고 처음부터 다시 시작하는 방식이다.
pthread_mutex_trylock()과 같은 함수를 활용해 구현할 수 있다. 이 함수는 락을 획득할 수 있으면 즉시 성공을 반환하고, 아니면 기다리지 않고 바로 실패를 반환한다. 이를 이용해 "L1 획득 ->trylock(L2)시도 -> 실패 시 L1 반납 후 처음부터" 와 같은 로직을 짤 수 있다. 하지만 이 방식은 두 스레드가 계속해서 서로의 락을 획득하고 반납하기를 반복하며 실질적인 진전을 이루지 못하는 라이브락(Livelock) 상태에 빠질 수 있다. 이를 해결하기 위해 락 획득 실패 시, 랜덤한 시간 동안 대기한 후 재시도하는 방법을 추가할 수 있다.상호 배제 조건 깨기: 애초에 '락(Lock)'을 사용하지 않는 방식으로 문제를 해결하는 것이다. 락 없이도 여러 스레드가 공유 데이터를 안전하게 수정할 수 있도록 설계된 'Lock-Free' 자료구조를 사용하는 방법이다. 이는 하드웨어가 제공하는 Compare-And-Swap(CAS)과 같은 원자적 연산을 통해 구현된다.(저번에 다룬 바 있다) CAS 연산은 특정 메모리 주소의 값이 '예상하는 값'과 일치할 경우에만 '새로운 값'으로 변경하는 것을 원자적으로 보장한다. 스레드는 이 연산을 통해 자신이 값을 읽은 후에 다른 스레드가 값을 변경하지 않았음을 확인하고 안전하게 값을 업데이트할 수 있다. 이 방식은 락으로 인한 교착 상태를 완전히 배제할 수 있지만, 구현이 매우 복잡하고 특정 스레드가 계속해서 업데이트에 실패하는 기아(Starvation) 상태가 발생할 가능성이 있다.
2) 교착 상태 회피 (Avoidance)
교착 상태 예방이 너무 엄격한 제약이라고 생각될 때 사용하는 방법이다. 프로세스의 자원 요청 정보를 미리 파악하여, 앞으로 교착 상태를 유발할 가능성이 있는 자원 할당은 애초에 하지 않는 방식이다. '은행원 알고리즘(Banker's Algorithm)'이 대표적인 예다. 하지만 어떤 프로세스가 미래에 어떤 자원을 요청할지 미리 알아야 한다는 전제가 있어, 일반적인 운영체제 환경에서는 실용성이 떨어진다.
DeadLock Avoidance
3) 교착 상태 탐지 및 회복 (Detection & Recovery)
이 방법은 교착 상태 발생을 허용하되, 주기적으로 시스템을 검사하여 교착 상태를 '탐지'하고, 발견되면 '회복'하는 전략이다. 자원 할당 그래프에서 사이클이 있는지 확인하여 교착 상태를 탐지하고, 발견되면 관련 프로세스를 강제 종료하거나 할당된 자원을 선점하여 교착 상태를 해결한다. 데이터베이스 시스템에서 종종 사용되는 방식이다.
4) 현실: 문제를 무시하기
놀랍게도 Windows, Linux, macOS 같은 대부분의 범용 운영체제는 교착 상태를 적극적으로 처리하지 않는다. 교착 상태가 드물게 발생하며, 이를 예방하거나 탐지하는 데 드는 오버헤드가 더 크다고 보기 때문이다. 따라서 교착 상태를 방지하는 책임은 온전히 프로그래머에게 넘어온다. 결국 우리가 꼼꼼하게 락 순서를 지키고, 자원 점유 시간을 최소화하는 등 안전한 코드를 작성해야 한다는 결론에 이르게 된다.
책임은 결국 프로그래머에게
교착 상태는 여러 프로세스가 한정된 자원을 놓고 경쟁할 때 발생할 수 있는 필연적인 문제 중 하나라는 생각이 들었다. 운영체제는 이를 해결하기 위한 여러 이론적인 방법(예방, 회피, 탐지)을 제시하지만, 현실의 범용 OS는 성능과 실용성을 이유로 대부분의 책임을 프로그래머에게 넘긴다.
결국 시스템의 동작 원리를 깊이 이해하고, 자원을 요청하고 해제하는 로직을 신중하게 설계하는 것이 얼마나 중요한지 다시 한번 깨닫게 되었다. 특히 순환 대기를 피하기 위해 락을 획득하는 순서를 명확히 정의하는 습관은 반드시 지켜야 할 원칙인 것 같다. 다음에는 메모리 관리 기법에 대해 더 깊이 파고들어 볼 예정이다.
추천글:
[운영체제] 고급 동기화 메커니즘 | Condition Variable과 Semaphore
[운영체제] Lock | 단순 Mutual Exclusion을 위한 Test-And-Set부터 성능까지 챙긴 Futex까지
