Deadlock
- 멀티프로세싱 환경에서 두 개 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다리며 무한 대기에 빠지는 상황
시스템이 자원을 획득하는 과정
1. 자원 요청(Resource Request)
- 프로세스가 필요한 자원을 사용하기 위해 시스템에 요청하면 시스템은 자원의 현재 상태를 확인하여 사용 가능 여부를 판단한다.
- 이미 다른 프로세스에 의해 점유되어 있는 자원을 요청하는 경우, 해당 프로세스는 그 자원이 사용 가능해질 때까지 대기하게 된다.
2. 자원 사용(Resource Usage)
- 프로세스는 할당받은 자원을 사용하여 자신의 작업을 수행한다.
- 공유 자원을 사용하는 코드 부분은 임계 영역(Critical Section) 내에서 실행된다.
공유 자원에 대한 동시 접근은 데이터의 일관성 문제나 예상치 못한 오류를 일으킬 수 있기 때문에, 공유 자원에 대한 접근이 필요할 때 임계 영역을 설정하여 이를 보호한다.
3. 자원 해제(Resource Release)
- 프로세스가 자원 사용을 완료하면 시스템에 해당 자원이 더 이상 필요하지 않다는 신호를 보내 반납한다.
- 자원이 반납되면 해당 자원에 대기 중이던 다른 프로세스가 요청할 수 있게 된다.
데드락의 발생 조건
데드락이 발생하려면 다음 네 가지 조건이 동시에 만족되어야 합니다.
상호 배제(Mutual Exclusion)
- 자원을 한 번에 하나의 프로세스만이 사용할 수 있어야 한다.
점유 및 대기(Hold and Wait)
- 최소한 하나의 자원을 점유하고 있는 프로세스가 추가로 필요한 자원을 기다린다.
비선점(No Preemption)
- 한 프로세스가 사용 중인 자원을 다른 프로세스가 강제로 가져올 수 없다.
순환대기(Circular Wait)
- 프로세스의 집합
{P1, P2, ..., Pn}에서P1이P2가 점유한 자원을 대기하고,P2는P3가 점유한 자원을 대기하고,...,Pn은P1이 점유한 자원을 대기한다.
자원 할당 그래프(Resource Allocation Graph)
- 자원들이 모두 상호 배제(mutual exclusion) 상태라는 가정하에, 프로세스와 자원 간의 할당 상태를 나타내는 그래프이다.
- 이를 통해 시스템의 상태를 시각적으로 표현하고, 데드락의 발생 여부나 데드락에 연루된 프로세스와 자원을 쉽게 식별할 수 있다.
P1은 R2의 자원을 점유하고 R1의 자원을 대기 중이다.
P2는 R1과 R2의 자원을 점유하고 R3의 자원을 대기 중이다.
P3는 R3의 자원을 점유하고 있지만 추가 자원을 요청하지 않는다.
R3의 자원이 회수되면 P2가 점유할 수 있기 때문에 순환 대기 상태가 아니다.
P3가 R3의 자원을 점유하면서 R2의 자원을 대기하면 순환 대기 상태가 되어 데드락이 발생한다.
데드락의 예방
데드락을 해결하려면 위의 조건 중 하나 이상을 깨트려야 한다.
상호 배제의 제거
- 자원을 공유 가능하도록 만들어 상호 배제 조건을 제거한다.
- 프린터와 같이 일부 자원은 공유가 불가능하고, 상호 배제를 제거하면 추후 동기화 관련 문제가 발생할 수 있다.
점유 및 대기 조건의 제거
- 프로세스는 시작할 때 필요한 모든 자원을 한 번에 요청한다. 요청된 모든 자원이 동시에 사용 가능하지 않으면, 프로세스는 시작되지 않는다.
비선점 조건의 제거
- 자원을 점유하고 있는 프로세스가 다른 자원을 요청하면, 그 프로세스가 현재 점유하고 있는 자원을 반납하게 한다. 해당 프로세스는 원래의 자원과 새로 요청한 자원을 모두 다시 요청한다.
순환 대기 조건의 제거
- 시스템에 있는 모든 자원 유형에 순서 번호를 할당하고, 각 프로세스는 번호 순서대로 자원을 요청한여 순환 구조를 제거한다.
데드락의 회피
프로세스들이 자원을 요청할 때마다 시스템은 그 요청이 안전한지를 판단하고, 데드락을 초래할 가능성이 있는 요청은 거부한다.
자원 할당 그래프(Resource Allocation Graph)
- 자원 할당 그래프를 활용하여 데드락 가능성을 탐지한다.
- 그래프에 순환 구조가 발생할 경우, 해당 요청을 거부함으로써 데드락 회피가 가능한다.
은행원 알고리즘(Banker's Algorithm)
- 다중 인스턴스 자원 유형에 대해 프로세스가 최대 자원 요구량을 미리 선언한다.
- 요청이 들어올 때마다 시스템은 최대 요구량을 만족시키면서도 안전한 상태로 남아 있게 되는지를 검사한다.
- 만약 안전하다면 자원을 할당하고 그렇지 않다면 요청을 연기한다.
데드락 회피 방법들은 데드락 발생 가능성을 줄이지만, 선언된 최대 요구량에 따라 시스템의 자원이 비효울적으로 사용될 수 있다.
데드락의 탐지
시스템이 데드락 상태에 빠졌는지를 주기적으로 확인하거나 특정 조건에서 확인하는 접근 방식이다.
데드락 탐지 알고리즘(Deadlock Detection Algorithm)
현재 할당된 자원, 프로세스가 요청하는 자원, 사용 가능한 자원에 대한 정보를 기반으로 안전한 상태인지를 판단한다.
- 시스템의 사용 가능한 자원 벡터를 초기화한다.
- 요청 행렬의 각 행에 대해 사용 가능한 자원 벡터가 해당 행의 값보다 크거나 같은지를 확인한다.
- 조건을 만족하는 행이 있으면 해당 프로세스가 데드락에서 벗어날 수 있다고 가정하고, 해당 프로세스에 할당된 자원을 해제하여 사용 가능한 자원 벡터에 추가한다. 이후 해당 행과 열을 제거한다.
- 모든 행을 검사할 때까지 2-3단계를 반복한다.
- 모든 프로세스가 데드락에서 벗어날 수 있다면 데드락은 없는 것으로 간주된다. 그렇지 않으면, 남아 있는 프로세스들은 데드락 상태에 있는 것으로 판단한다.
데드락이 자주 발생하면 데드락 탐지 알고리즘이 계속해서 실행되어 시스템 오버헤드가 발생할 수 있기 때문에, 탐지 빈도를 줄이거나 시스템 전체가 아닌 지역화된 탐지를 통해 오버헤드를 줄일 수 있다.
데드락의 회복
데드락 탐지 알고리즘을 통해 데드락 상태가 발견되면, 해당 상태에서 시스템을 정상 상태로 돌려 놓는 방법이다.
프로세스 종료(Process Termination)
- 데드락에 관련된 프로세스를 종료하여 데드락을 해결한다.
- 이 방법은 간단하며 데드락을 빠르게 해결할 수 있지만, 많은 작업의 손실이 발생하게 된다.
자원 선점 (Resource Preemption)
- 데드락 상태를 해결하기 위해 일부 프로세스로부터 할당된 자원을 회수하고, 다른 프로세스에게 해당 자원을 할당한다.
- 이렇게 선점된 프로세스는 나중에 자원이 사용 가능해질 때까지 대기 상태에 둔다.
- 프로세스의 우선순위, 자원 요청 크기, 프로세스의 대기 시간 등의 기준을 통해 어떤 프로세스로부터 자원을 회수할 것인지 결정한다.
