[운영체제] 교착 상태(Deadlock)

패스트캠퍼스 운영체제 강의와 쉽게 배우는 운영체제 교재에 대한 TIL입니다.

 

교착 상태

교착 상태란 2개 이상의 작업이 동시에 이루어지는 경우, 다른 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 의미한다. 교착 상태는 기아 상태(Starvation)와 비슷해 보이지만 차이가 있다. 기아 상태는 잘못된 정책으로 특정 프로세스의 작업이 지연되는 문제인 반면, 교착 상태는 여러 프로세스가 작업을 진행하다 보니 발생하는 자연적인 현상이다.

 

자원 할당 그래프

자원 할당 그래프는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다. 자원 할당 그래프에서 프로세스는 원으로, 자원은 사각형으로 표현한다. 자원을 사용하는 경우(할당된 경우)는 자원에서 프로세스로 향하는 화살표로 표시하고, 프로세스가 자원을 기다리는 경우(대기하는 경우)는 프로세스에서 자원으로 향하는 화살표로 표시한다.

 

 

다음은 식사하는 철학자 문제의 자원 할당 그래프이다.

 

 

위 그림에서 볼 수 있듯이 자원 할당 그래프가 원형이면 교착 상태가 발생한다.

 

교착 상태 필요조건

교착 상태는 다음과 같은 네 가지 조건에 의해 발생한다. 네 가지 조건 중 단 하나라도 충족하지 않으면 교착 상태는 발생하지 않는다.

상호 배제
상호 배제가 이루어진 자원은 임계 구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없으므로 이러한 자원을 사용하면 교착 상태가 발생한다.

비선점
한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다. 빼앗을 수 없으면 공유할 수도 없으므로 교착 상태가 발생한다.

점유와 대기
프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태일 때 교착 상태가 발생할 수 있다.

원형 대기
점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다. 프로세스가 특정 자원에 대해 점유와 대기를 한다고 해서 모두 교착 상태에 빠지는 것은 아니다. 점유와 대기를 하는 프로세스들이 원의 형태로 이루어져 있으면 프로세스들이 서로 양보하지 않기 때문에 교착 상태에 빠진다.

 

상호 배제와 비선점 조건은 임계 구역과 관련이 있다. 임계 구역을 보호하기 위해 잠금장치를 사용하면 상호 배제와 비선점 조건이 보장되기 때문에 교착 상태가 발생할 수 있다. 하지만 임계 구역을 보호되는 모든 자원이 교착 상태를 유발하는 것은 아니고 임계 구역 자원을 사용하는 프로세스들이 점유와 대기, 원형 대기 상황에 처할 때 교착 상태가 발생한다.

 

 

교착 상태 해결 방법

처음에 말했듯이 교착 상태와 기아 상태는 다르다. 기아 상태는 프로세스가 양보할 수 있는 상한선을 정하는 에이징으로 해결할 수 있다. 반면, 교착 상태는 스케줄링 정책상 잘못이나 오류가 없어도 자연적으로 발생한다. 따라서 교착 상태는 에이징으로 해결할 수 없고 스케줄링 정책을 바꾼다고 해서 막을 수도 없다. 따라서 교착 상태를 해결하기 위한 4가지 방법이 존재한다.

 

교착 상태 예방

교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식이다. 즉, 상호 배제 예방, 비선점 예방, 점유와 대기 예방, 원형 대기 예방의 방법 중 하나를 사용하여 네 가지 조건 중 하나의 조건을 무력화시킴으로써 교착 상태가 발생하지 않게 하는 방식이다.

 

이때, 상호 배제 예방과 비선점 예방은 사실상 불가능한 예방 방법이다. 왜냐하면, 상호 배제 예방을 한다는 것은 독점적으로 사용할 수 있는 자원을 없애버린다는 것과 똑같고, 비선점 예방을 한다는 것은 모든 자원을 빼앗을 수 있도록 만든다는 것과 똑같다. 이는 현실적으로 불가능한 방법이다.

 

 

반면, 점유와 대기 예방, 원형 대기 예방은 현실적으로 불가능하지는 않은 방법이다.

 

점유와 대기 예방

프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 다시 말해, 자원을 전부 할당하거나 아예 할당하지 않는 방식(all or nothing)을 적용하는 것이다. 이를 위해 프로세스는 작업 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납해야 한다.

 

하지만, 점유와 대기 예방은 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵고 당장 사용하지도 않을 자원을 미리 선점하므로 자원 낭비가 심하다는 단점이 있다. 또한, 많은 자원을 사용하는 프로세스는 자원을 동시에 확보하기가 어렵기 때문에 아사 현상이 발생할 수 있고, 점유와 대기 예방을 실제로 구현하면 거의 모든 프로세스가 일괄 작업 방식으로 처리되기 때문에 시스템의 효율이 떨어지는 단점이 있다.

 

원형 대기 예방

점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법이다. 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것이다. 숫자가 작은 자원을 잡은 상태에서 큰 숫자를 잡는 것은 허용되지만, 숫자가 큰 자원을 잡은 상태에서 작은 숫자를 잡는 것은 허용하지 않는다.

 

하지만, 원형 대기 예방은 프로세스 입장에서 번호에 따라 자원을 할당받을 수 없는 경우가 생기는 데 내부 구조를 모르는 사용자 입장에서는 납득할 수 없게 되고 자원에 번호를 어떻게 부여할지가 문제라는 단점이 존재한다.

 

교착 상태 회피

프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법이다. 자원을 많이 할당할수록 교착 상태가 발생할 확률이 커지기 때문에 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.

 

교착 상태 회피에서는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(Safe State)와 불안정 상태(Unsafe State)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.

 

 

위 그래프에서 볼 수 있듯이 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어나면 불안정 상태가 커진다. 교착 상태 회피에서는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 피한다.

 

은행원 알고리즘

교착 상태 회피를 구현하는 방법 중 한 가지는 은행원 알고리즘이다. 은행이 대출해 주는 방식, 즉 대출 금액이 가능한 범위 내이면, 즉 안정 상태이면 대출이 허용되지만 그렇지 않으면 거부되는 것과 유사하기 때문에 이러한 명칭이 붙었다.

 

 

위 표는 은행원 알고리즘에서 사용하는 변수를 정리한 것이다. 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다. 가용 자원이 기대 자원보다 크다는 것은 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 의미이므로 안정 상태다. 또한, 가용 자원이 어떤 기대 자원보다도 크지 않으면 자원을 할당하지 않는다. 이는 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미이므로 불안정 상태다.

 

따라서, 은행원 알고리즘에 빗대어 안정 상태를 정의하면, 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우이다.

 

다음은 은행원 알고리즘의 예제이다.

 

 

위의 그림처럼 돼있는 경우 Expect와 각 프로세스의 안정 상태를 가지는 순서를 구하는 문제이다. 해결 방법은 텍스트로 설명하기에는 다소 무리가 있어 해설 영상을 첨부하겠다. 참고로 영상에는 Need라는 것이 나오는데 Expect와 같은 변수이다.

 

주니온TV 아무거나연구소 채널의 운영체제 강의

 

다음은 교착 상태 회피의 문제점이다. 첫 번째로, 교착 상태 회피 방법을 사용하려면 프로세스가 자신이 사용할 자원을 미리 선언해야 하는데 이는 쉬운 일이 아니다. 두 번째로, 은행원 알고리즘에서 안정 상태나 불안정 상태를 파악하려면 시스템의 전체 자원 수가 고정적이어야 하는데 실제로는 시스템의 자원 수가 유동적이다는 점이다. 마지막으로, 교착 상태 회피에서는 실제로 교착 상태가 발생하지 않는데도 발생할 것이라고 예상하고 프로세스에 자원을 할당하는 데 제약을 둔다는 점이다.

 

 

교착 상태 검출

타임아웃

타임아웃을 이용하여 일정 시간 동안 작업이 진행되지 않는 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다. 실제로 유닉스나 윈도우 같은 운영체제에서는 일정 시간 동안 작업이 진행되지 않으면 해당 프로세스를 죽인다. 타임아웃을 이용하는 방법을 '가벼운 교착 상태 검출'이라고도 한다.

 

타임아웃을 이용한 방식은 교착 상태가 아닌 다른 이유로 작업이 진행되지 못하는 모든 프로세스가 강제 종료될 수 있고 하나의 운영체제 내에서 동작하는 프로세스들이 아닌 분산 시스템 같이 여러 시스템이 나뉜 경우에는 작업이 진행되지 않는 이유를 명확하게 알 수 없기 때문에 적용할 수 없다는 단점이 존재한다.

 

자원 할당 그래프를 이용한 교착 상태 검출

자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 혹은 기다리고 있는지 알 수 있다.

 

 

자원 할당 그래프를 이용하여 교착 상태를 검출하는 방법은 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 것이 장점이다. 하지만, 자원 할당 그래프를 유지, 갱신, 사이클 검사 같은 추가 작업으로 인해 오버헤드가 발생한다는 단점이 있다.

 

 

교착 상태 회복

교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는데 이를 교착 상태 회복이라고 한다. 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료한다. 이때, 프로세스를 강제로 종료하는 방법에는 교착 상태를 일으킨 모든 프로세스를 동시에 종료하는 방법과 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료하는 방법이 있다.