[OS] 교착 상태 (Dead lock)

데드락(DeadLock)

프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태, ‘교착 상태’라고도 부르며, 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생합니다.

프로세스1과 2가 자원1,2를 모두 얻어야 한다고 가정해보면

• t1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음

• t2 : 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림

현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠지게 되는데, 이것이 바로 데드락입니다.

데드락 발생 조건

4가지 모두 성립해야 데드락 발생 (하나라도 성립하지 않으면 데드락 문제 해결 가능)

1. 상호 배제(Mutual exclusion)

   자원은 한번에 한 프로세스만 사용할 수 있습니다.

2. 점유 대기(Hold and wait)

   최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 합니다.

3. 비선점(No preemption)

   다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없습니다.

4. 순환 대기(Circular wait)

   프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 합니다.

데드락의 예방

1. 상호배제

   교착상태의 첫번째 필요조건인 상호배제 가 일어나는 경우는 공유가 불가능한 자원 에 의해서 입니다. 만약 여러 프로세스가 읽기 전용의 파일을 열면 프로세스들은 그 파일에 대한 동시 접근을 보장받고 이 경우 상호배제 가 깨어지게 되어 교착상태를 예방할 수 있습니다. 하지만, 어떤 자원들은 근본적으로 공유가 불가능 하기 때문에 이러한 상호배제가 반드시 일어나야 하기 때문에 교착 상태를 예방하지 못하는 경우가 발생할 수 있습니다.

2. 점유 대기

   점유하며 대기 조건이 발생하지 않도록 하려면 프로세스가 자원을 요청할 때 다른 자원들을 점유하지 않고 있다는 것을 반드시 보장 해야 합니다. 즉, 자기 자신이 아무런 자원도 점유하지 않고 있을 때에만 다른 자원을 요청 할 수 있도록 하면, 대기 상태에 빠지더라도 자신은 아무런 자원도 점유하지 않고 있기 때문에 대기 하더라도 점유하며 대기는 발생하지 않게 됩니다.

   이 경우 사용할 수 있는 프로토콜은 프로세스가 실행되기 전에 자신이 필요한 모든 자원을 요청하여 할당받도록 하는 것입니다. 이렇게 되면 프로세스가 정도에 다른 자원을 요청하여 할당받을 때까지 대기하는 일이 없고 모든 자원을 가지고 프로세스를 시작하기 때문에 대기하는 일이 발생하지 않습니다. 하지만 이 경우 큰 단점이 발생하는데 바로 많은 자원들이 할당 된 후 오랫동안 사용되지 않기 때문에 자원의 이용률이 낮아 지는 것 입니다. 가령 어떤 명령이 디스크 접근과 인쇄를 같이 하는 것이라면 프로세스가 디스크 접근을 수행하는 동안에도 이 프로세스는 프린터의 자원을 점유하게 되어 그 시간동안 프린터가 이용되지 못하는 상황이 발생하게 됩니다. 또 기아 상태가 가능하다 는 단점이 있을 수 있습니다. 필요한 자원 중 최소 하나가 계속 다른 프로세스에게 할당되어 있으면 이 프로세스는 무한정 대기해야 할 가능성이 생기게 됩니다.

3. 비선점

   세 번째 필요조건인 비선점 이 발생하지 않도록 해봅시다. 비선점 이란 이미 할당된 자원이 선점되지 않아야 한다는 것 입니다. 이를 위해서는 자신이 점유하고 있는 자원을 강제로 방출시켜 다른 프로세스가 선점하게 함으로써 교착상태를 끊어버리는 다음과 같은 프로토콜 을 생각해 볼 수 있습니다.

   만일 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면 현재 그 프로세스가 점유하고 있는 모든 자원이 방출되어 필요로 하는 다른 프로세스에게 선점됩니다. 또 해당 프로세스는 자신이 요청하고 있는 새로운 자원은 물론 현재 강제로 방출한 옛 자원들을 다시 획득할 수 있을 때에만 다시 시작될 것입니다.

4. 순환 대기

   교착 상태가 일어나기 위한 마지막 조건인 순환대기 를 없애기 위해서는 모든 자원 유형들에게 전체적인 순서를 부여 하여 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 강제하는 것입니다. 이를 통해 모든 자원들은 먼저 할당되는 순서가 정해져 있기 때문에 교착상태가 일어날 수 없습니다.

데드락 처리 방법

회피 기법(Avoidance)

교착상태 회피 기법은 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법으로, 주로 은행원 알고리즘(Banker’s Algorithm)이 사용됩니다.

은행원 알고리즘

1. 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법입니다.

2. 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전상태, 교착상태가 발생할 수 있는 상태를 불안전 상태라고 합니다.

3. 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 합니다.

4. 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장합니다.

발견기법(Detection)

교착상태 발견 기법은 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것을 의미합니다.

1. 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용 할 수 있습니다.

회복기법(Recovery)

교착상태 회복 기법은 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것을 의미합니다.

프로세스 종료

교착상태에 있는 프로세스를 종료하는 것으로, 교착상태에 있는 모든 프로세스를 종료하는 방법과 교착상태에 있는 프로세스들을 하나씩 종료해가며 교착상태를 해결하는 방법이 있습니다.

자원선점

교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지시키는 방법입니다. 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점합니다.

※ 자원 선점시 고려사항

1. 자원 을 선점할 프로세스 선택 문제 : 최소의 피해를 줄 수 있는 프로세스를 선택합니다.

2. 자원을 선점한 프로세스의 복귀 문제 : 자원이 부족한 상태이므로 대부분 일시 중지시키고 다시 시작하는 방법을 사용합니다.

3. 기아 현상 문제 : 한 프로세스가 계속하여 자원 선점 대상이 되지 못하도록 고려해야 합니다.