운영체제 - 교착상태(Deadlock)와 해결 방안

교착상태, 데드락 이란?

교착상태 : 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록(대기)되어 있는 상태

 

교착상태, 데드락의 원리

교착상태는 시스템 자원에 대한 경쟁 도중에 발생할 수도 있고 프로세스 간 통신 도중 발생할 수도 있습니다.

 

한 프로세스가 특정 사건의 발생을 기다리며 대기하고 있고, 이 사건이 다른 블록 된 프로세스에 의해 발생될 수 있다면 이 프로세스의 집합은 교착 상태가 됩니다. 왜냐하면 기다리고 있는 사건이 발생하지 않기 때문입니다.

 

예시를 하나 보겠습니다.

아래의 그림에는 사거리 교차로가 있고 차들은 직진을 하려고 대기 하고 있습니다.

여기서 차는 직진만 가능 하다고 가정하겠습니다. 차들이 교차로를 모두 지나가기 위해서는 한 차가 지나갈 때는 마주 보고 있는 차가 아니라면 옆에서 오는 차들은 멈춰 있어야 합니다. 하지만 모든 차들이 먼저 통과하기 위해 순서 없이 직진을 한다면 아래와 같은 상황이 발생할 수도 있을 것입니다.

차들은 직진만 가능하다고 가정했기 때문에 위와 같은 상황에서는 어떤 차도 더 이상 움직일 방법이 없습니다.

1번 차가 움직이려면 2번 차가 비켜줘야 하고, 2번 차가 움직이려면 3번 차가 움직여야 합니다.

 

이렇듯 프로세스가 어떤 사건이 일어나기를 대기하며 영구적으로 멈춰있는 것이 교착상태입니다.

 

교착상태가 발생하는 조건

교착상태가 발생하기 위해서는 우선 세 가지 조건이 기본적으로 필요합니다.

 

1. 상호 배제 조건 : 한 순간에 한 프로세스만이 자원을 사용할 수 있다. 즉 한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수는 없다.
2. 점유대기 조건 : 이미 자원을 보유한 프로세스가 다른 자원을 요청하며 기다리고 있다.
3. 비선점 조건 : 프로세스에 의해 점유된 자원을 다른 프로세스가 강제적으로 빼앗을 수 없다.

위 세 가지가 만족되면 교착상태가 발생할 수 있는 조건을 갖추게 된 것입니다.

 

이러한 상황에서 환형 대기 조건을 갖춘다면 교착상태가 발생하게 됩니다.

 

환형 대기란?

아래 그림과 같이 프로세스는 진행하기 위해 어떤 자원을 필요로 하지만 그 자원은 다른 프로세스에 의해 사용 중이며 반환되지 않는 상태가 환형으로 이루어진 상태입니다. (아래와 같은 그래프를 자원 할당 그래프라고 합니다.)

 

우리의 프로그램에서 교착상태가 발생하는 것은 매우 치명적입니다.

교착상태를 해결하기 위한 몇몇 방법들이 고안되었는데 교착상태의 예방, 회피, 발견이 각각 그 방법들입니다.

이어서 세 가지 방법에 대해 간단하게 알아보도록 하겠습니다.

 

교착상태 예방

교착상태 예방은 교착상태가 발생할 가능성을 없애는 것입니다. 위에서 교착 상태가 발생하는 조건들에 대해 알아보았습니다. 상호 배제, 점유 대기, 비선점, 환형 대기의 네 가지 조건중 한 가지를 허용하지 않는 것이 교착상태 예방의 방법입니다.

 

하지만 현실적으로 상호 배제와 점유대기 조건을 배제하는 것은 좋지 않은 선택입니다.

 

비선점 조건은 프로세스가 요구한 자원을 보유하고 있는 프로세스가 자원을 반납하도록 할 수 있을 것이며,

환형 대기 조건은 자원 할당에 순서를 부여 함으로써 조건을 배제할 수 있을 것입니다.

 

교착상태 회피

교착상태 회피는 상호 배제 ,점유대기, 비선점 조건을 허용합니다. 또한 자원 할당 순서를 미리 정하지도 않습니다. 단지 자원이 할당되었을 때 교착상태가 발생할 수 있는지를 미리 검사해서 교착상태가 발생 가능하다면 자원 할당을 거부합니다.

 

이 방법은 자원의 가용 개수와 프로세스의 자원 요구량을 미리 알고 있어야 합니다.

 

교착상태 회피에는 2가지 기법이 있습니다.

1. 프로세스 시작 거부 : 프로세스가 시작하려 할 때 요구하는 자원 할당이 교착상태 발생의 가능성이 있으면, 프로세스를 시작시키지 않는다.
2. 자원 할당 거부 : 수행 중인 프로세스가 요구하는 추가적인 자원 할당이 교착상태 발생의 가능성이 있으면, 자원을 할당하지 않는다. 자원 할당 거부 방법은 Banker's algorithm 이라고도 불린다.
   • 뱅커 알고리즘에 대해 자세히 알기

 

교착상태 발견

먼저 자원을 새로 할당할 때마다 가용 자원가 할당 자원의 수를 갱신해가며 교착 상태를 발견할 수 있습니다.

이 경우에 사용하는 알고리즘을 자세하게 설명한 블로그가 나와 있어 참고하였습니다. https://baked-corn.tistory.com/14

[11] 운영체제 - Deadlock-3

 

이렇게 교착상태를 발견하게 된다면 아래의 방법들을 통해 프로세스들을 교착상태에서 회복시킵니다.

1. 교착상태에 포함되어 있는 모든 프로세스를 중지시킨다.
2. 교착상태에 포함되어 있는 가 프로세스의 수행을 롤백시킨다.
3. 교착상태가 없어질 때까지 프로세스를 하나씩 종료시킨다.
4. 교착상태가 없어질 때까지 교착상태에 포함되어있는 자원을 하나씩 선점시킨다.