[Operating System] 교착 상태(deadlock)

교착 상태(deadlock)

두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태를 말한다.

 

교착 상태의 원인

• 상호 배제 : 한 프로세스가 자원을 독점하고 있으며 다른 프로세스들은 접근이 불가능하다.
• 점유 대기 : 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하는 상태.
• 비선점 : 다른 프로세스의 자원을 강제적으로 가져올 수 없다.
• 환형 대기 : 프로세스 A는 프로세스 B의 자원을 요구하고, 프로세스 B는 프로세스 A의 자원을 요구하는 등 서로가 서로의 자원을 요구하는 상황

 

교착 상태의 해결 방법

1. 자원을 할당할 때 애초에 조건이 성립되지 않도록 설계한다. (하지만 자원을 보호하기 위해 상호 배제와 비선점을 예방하기 어렵다)
2. 교착 상태 가능성이 없을 때만 자원이 할당되며, 프로세스 당 요청할 자원들의 최대치를 통해 자원할당 가능 여부를 파악하는 은행원 알고리즘을 사용한다.
3. 교착 상태가 발생하면 사이클이 있는지 찾아보고 이에 관련된 프로세스를 한 개씩 지운다.
4. 교착 상태는 매우 드물게 일어나므로 이를 처리하는 비용이 더 크다. 따라서 교착 상태가 발생하면 사용자가 작업을 종료한다. 현대 운영체제는 이 방법을 채택했다.

안정 상태와 불안정 상태

교착 상태의 해결을 이야기 할 때 안정 상태와 불안정 상태의 개념이 나온다.

자원의 총 수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나눈다.

시스템이 안정 상태를 유지하도록 자원을 할당한다.

 

할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 커진다.

 

안정 상태는 시스템이 교착 상태를 일으키지 않고 각 프로세스가 요구한 양만큼 자원을 할당해줄 수 있는 상태다.

교착 상태는 불안정 상태일때만 발생하고 반대로 불안정 상태라 해서 무조건 교착 상태는 아니다.

교착 상태는 불안정 상태의 일부분이다.

불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아진다.

 

교착 상태의 해결은 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 피하는 것이다.

 

은행원 알고리즘

총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정 또는 불안정 상태로 나누고 안정 상태로 가도록 자원을 할당하는 알고리즘.

안정 상태를 유지할 수 있는 요구만을 수락한다.

 

은행이 대출을 해주는 방식이며, 대출 금액이 대출 가능한 범위 내이면(안정 상태이면) 허용되지만 그렇지 않으면 거부되는 것과 유사한 방식이다. 

 

은행원 알고리즘에 사용되는 변수

• 전체 자원(Total) : 시스템 내 전체 자원의 수. 예)프린터, 모니터의 개수 
• 가용 자원(Available) : 시스템 내 현재 사용할 수 있는 자원의 수(가용 자원 = 전체 자원 - 모든 프로세스의 할당 자원)
• 최대 자원(Max) : 각 프로세스가 선언한 최대 자원의 수(시작 전에 선언해야 한다)
• 할당 자원(Allocation) : 각 프로세스에 할당된 자원의 수
• 기대 자원(Expect, Need) : 각 프로세스가 앞으로 사용할 자원의 수(기대 자원 = 최대 자원 - 할당 자원)

은행원 알고리즘에서 자원 할당 기준

요청한 자원을 할당해 준 뒤에도 시스템이 안정 상태라면 그 요청을 수락.

 

 

특정 시점에 위 사진과 같은 프로세스 0,1,2,3,4와 자원 A,B,C가 있다고 가정하자.

지금 사용할 수 있는 자원의 수(Available)를 고려해서 어떤 프로세스를 수락할 수 있을지 생각한다.

먼저 프로세스가 요구하는 자원의 수를 계산한다.

 

프로세스가 요구하는 자원의 수(Need)는 최대 자원(Max) - 할당 자원(Allocation)이 된다.

현재 자원의 수가 A = 3, B = 3, C = 2 이므로 프로세스 1이나 3의 요청을 수락할 수 있다.

이때 작은 인덱스를 선택한다고 하면,

 

프로세스 1을 선택 후, 사용가능한 자원의 수(Available)는 (3 3 2) - (1 2 2) = (2 1 0)가 되며

프로세스 1에 할당된 자원의 수(Allocation 1)는 (2 0 0) + (1 2 2) = (3 2 2)

 

이렇게 프로세스 1에 자원을 할당하고 시간이 지나면 프로세스 1은 작업을 끝낸다고 본다.

 

이 다음에 또 같은 방식으로 사용가능한 자원의 수(Available)를 구하여 어떤 순서로 프로세스가 실행되는지 알 수 있다.

이 순서를 safe sequence라고 하며 이는 각 프로세스의 Need를 어떤 순서대로 만족시켜 줄 수 있을 때의 순서를 말한다.

 

 

참조

• 주홍철, 면접을 위한 CS 전공지식 노트, 길벗(2022)
• 조성호, 쉽게 배우는 운영체제, 한빛아카데미(2018)
• 배워서나줘