교착 상태(Dead lock)
교착 상태(Deadlock)는 멀티프로세스나 멀티스레드 환경에서 발생하는 문제로, 각각의 프로세스나 스레드가 서로가 가진 자원을 점유하면서 상대방의 자원이 해제되기를 기다리는 상황에서 무한정 기다리는 현상을 말한다.
교착 상태는 두 개 이상의 작업이 동시에 이루어지는 경우에 발생할 수 있는데, 이때 각 작업이 서로가 가진 자원을 요청하고 점유하며, 자원의 해제를 서로가 기다리는 상황에서 더 이상 작업을 진행할 수 없게 된다.
컴퓨터 시스템에서 교착 상태는 시스템 자원을 사용하거나 잠금을 사용할 때 발생할 수 있다.
자원 할당 그래프
자원 활당 그래프에서 프로세스는 원으로, 자원은 사각형으로 표현한다. 자원을 사용하는 경우(할당된 경우)는 자원에서 프로세스로 향하는 화살표로 표시하고, 프로세스가 자원을 기다리는 경우(대기하는 경우)는 프로세스에서 자원으로 향하는 화살표로 표시한다.
자원이 2개 이상의 프로세스를 동시에 허용할 수 있다. 여러 프로세스가 동시에 사용하는 자원을 다중 자원(multiple resource)라고 한다. 프로세스 수를 사각형 안에 원으로 표현된다.
교착 상태의 정의
교착 상태는 일반적으로 다음과 같은 4가지 조건이 동시에 성립할 때 발생한다.
- 상호 배제(Mutual exclusion): 자원은 한 번에 한 프로세스나 스레드에 의해서만 점유될 수 있다.
- 점유 대기(Hold and wait): 프로세스나 스레드가 자원을 가지고 있는 상태에서 다른 자원을 기다리면서 대기하는 상황이 발생한다.
- 비선점(Non-preemption): 다른 프로세스나 스레드가 가진 자원을 강제로 해제할 수 없다.
- 순환 대기(Circular wait): 다수의 프로세스나 스레드가 서로가 가진 자원을 기다리는 상황에서, 원형(사이클cycle)로 자원이 연결되어 순환 대기 상태가 되는 경우이다.
교착 상태를 해결하기 위해서는 위 조건 중 하나를 제거해야 한다. 예를 들어, 상호 배제 조건을 제거하여 여러 개의 프로세스나 스레드가 동시에 자원을 사용할 수 있도록 하는 방법이 있다. 하지만, 이는 일반적으로 복잡하고 어려운 문제로, 보통은 교착 상태가 발생하지 않도록 시스템 설계 및 운영 체제에서 교착 상태를 해결하기 위한 대표적인 방법으로는 다음과 같은 것들이 있다.
예방(Prevention): 교착 상태가 발생할 수 있는 조건 중 하나를 제거하여 교착 상태를 예방하는 방법이다. 예를 들어, 상호 배제 조건 중 하나를 제거하거나, 순환 대기 조건을 제거하는 것이다.
회피(Avoidance): 교착 상태가 발생할 가능성이 있는 자원 요청을 할 때, 시스템이 자원 할당을 결정하는데 있어 안전한 상태에서만 자원을 할당하도록 하는 방법이다. 이를 위해 자원 할당 상태를 추적하고, 안전 상태인 경우에만 자원을 할당하도록 하는 알고리즘이 사용된다.
검출(Detection): 교착 상태가 발생하는 것을 감지하여, 교착 상태가 발생하면 그 상황을 해결하는 방법이다. 이를 위해 시스템에서는 일정 주기마다 자원 할당 상태를 체크하고, 교착 상태가 발생하는지 여부를 검사한다.
회복(Recovery): 교착 상태가 발생한 경우, 교착 상태를 해결하고 시스템을 정상 상태로 복구하는 방법이다. 이를 위해 자원을 해제하거나, 프로세스나 스레드를 강제로 중지시키는 등의 방법이 사용된다.
교착 상태 해결 방법
교착 상태 예방
- 상호배제 예방: 자원을 한 번에 한 프로세스나 스레드에 의해서만 점유되는 것을 없애는 방법이다 즉 시스템 내의 모든 자원을 공유하는 것이다. 상호배제를 무력화하는 것은 현실적으로 쉽지 않다.
- 비선점 예방: 다른 프로세스를 강제로 빼앗을 수 있게 하는 방법이다. 임계구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없을 뿐만 아니라 상호 배제 예방도 보장할 수 없기 때문에 시스템의 모든 자원을 빼앗기는 어렵다. (아사 현상을 일으킨다.)
- 점유와 대기 예방: 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 다시 말해 전부 할당하거나 아예 할당하지 않는(all or nothing) 방식을 적용하는 것이다.
- 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.
- 자원의 활용성이 떨어진다.
- 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
- 일괄 방식으로 동작한다.
- 원형 대기 예방: 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법이다. 작은 번호에서 큰 번호로 자원을 할당하는 방식이다.
- 프로세스 작업 진행에 유연성이 떨어진다.
- 자원에 번호를 어떻게 부여할지가 문제다.
교착 상태 회피
교차 상태 회피에서는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태로 유지하도록 한다.
할당된 자원이 적으면 안정상태, 많으면 불안정 상태이다.
은행원 알고리즘
은행이 대출해 주는 방식이다. 즉 대출 금액이 가능한 범위 내이면(안정 상태이면) 대출이 허용되지만 그렇지 않으면 거부되는 것과 유사하다.
은행원 알고리즘은 최악의 경우를 기준으로 삼음으로써 문제 상황을 철저히 피하여 교착 상태를 막는다.
은행원 알고리즘 변수
- Total(전체 자원): 시스템 내 전체 자원의 수
- Avaliable(가용 자원): 시스템 내 현재 사용할 수 있는 자원의 수
- 가용자원 = 전체 자원 - 모든 프로세스의 자원의 수
- Max(최대 자원): 각 프로세스가 선언한 최대 자원의 수
- Allocation(할당 자원): 각 프로세스에 현재 할당된 자원의 수
- Expect(기대 자원): 각 프로세스가 앞으로 사용할 자원의 수
- 기대 자원 = 최대 자원 - 할당 자원
자원 할당 기준
- 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당
- 가용 자원이 어떤 자원보다는 크지 않으면 자원을 할당하지 않는다.
안정상태: 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우
교착 상태 회피의 문제점
- 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
- 시스템의 전체 자원 수가 고정적이어야 한다.
- 자원이 낭비된다.
교착 상태 검출
타임아웃을 이용한 교착 상태 검출
타임아웃을 이용한 교착상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다. ( 교착 상태가 자주 발생하지 않을 것이라고 간주)
- 타임아웃: 가벼운 교착 상태 검출
- 자원 할당 그래프: 무거운 교착 상태 검출
타임아웃 문제
- 엉뚱한 프로세스가 강제 종료될 수 있다.
- 모든 시스템에 적용할 수 없다.
자원 할당 그래프를 이용한 교착 상태 검출
자원 할당 그래프가 교착 상태인지 판단하는 방법은 사이클 존재 여부이다. 존재하면 교착 상태가 있다고 판단한다. (단 자원의 수가 하나이면 교착 상태이고 여러 개일 경우 모두 교착 상태라고 판단 할 수 없다.)
- (a)는 사이클이 존재하지 않기 때문에 교착상태가 아니다.
- (b)는 자원의 수가 1개이고 사이클이 존재하기 때문에 교착 상태이다.
교착 상태 회복
- 교착 상태를 일으킨 모든 프로세스를 동시에 종료
- 종료된 프로세스가 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 크므로 먼저 실행할 프로세스의 기준을 정해야 한다.
- 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
- 우선순위가 낮은 프로세스를 먼저 종료
- 우선순위가 같으면 작업 시간이 짧은 프로세스를 먼저 종료
- 위의 두 조건이 같으면 자원을 많이 사용하는 프로세스를 먼저 종료
교착 상태 회복에서는 종료하는 일뿐 아니라 강제 종료된 프로세스가 실행되기 전에 시스템으로 복구하는 일도 해야 한다. (체크포인트)
