데드락이란?

데드락 DeadLock

데드락 (교착 상태) 이란?

: 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태.

두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있어 결과적으로 아무것도 완료되지 못하는 상태를 말함.

데드락 발생 상황

멀티 프로그래밍 환경에서, 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.

• 어떤 프로세스가 자원을 요청했을 때, 그 시각에 그 자원을 사용할 수 없는 상황이 발생
• 이런 경우 해당 프로세스는 대기 상태가 됨
• 대기 상태의 프로세스들이 실행 상태로 변경될 수 없을 때를 교착 상태라고 한다.

데드락 발생 조건

• 교착상태가 일어나려면 다음의 네 필요 조건을 충족시켜야 한다.
  • 즉, 아래 조건 중 하나라도 만족하지 않으면 교착 상태는 발생하지 않는다.
• 아래 4가지 조건은 서로 완전히 독립적인 것은 아니다.
  • 예를 들어, 4.순환대기는 2.점유대기와 3.비선점 조건을 만족해야 성립하는 조건이다.

1. 상호 배제 Mutual exclusion

프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.

즉, 자원을 한 번에 한 프로세스만 사용할 수 있다.

2. 점유 대기 Hold and Wait

프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

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

3. 비선점 No Preemption

프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.

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

4. 순환 대기 Circular Wait

각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

프로세스의 집합 P1, P2, P3 ... Pn에서 P1은 P2가 점유한 자원을 대기하고, P2는 P3이 점유한 자원을 대기하고, ... Pn-1은 Pn이 점유한 자원을 대기하고, Pn은 P1이 점유한 자원을 요구해야 한다.

데드락 관리

현재 대부분의 운영 체제들은 교착 상태를 해결할 수 없다.

대신 주로 위 4가지 조건 중 하나를 막음으로써 데드락을 예방한다.

데드락의 예방

• 상호 배제, 점유 대기, 비선점, 순환 대기 조건을 제거함으로써 데드락을 예방한다.
  • 상호배제 부정 : 여러 프로세스가 공유자원을 사용할 수 있게 함
  • 점유대기 부정 : 프로세스 실행 전 필요한 모든 자원을 할당함
  • 비선점 부정 : 자원을 점유하는 프로세스가 다른 자원을 요구할 때 점유하는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리도록 함
  • 순환대기 부정 : 자원에 고유번호를 할당하고, 번호 순서대로 자원을 요구하도록 함
• 단점 : 자원 낭비가 심하고, 비용이 많이 든다.

데드락의 회피

• 자원이 어떻게 요청될지에 대한 추가정보를 제공하도록 요구하는 것. 순환대기가 발생하지 않도록 자원 할당 상태를 검사한다.
  • 자원 할당 그래프 알고리즘
  • 은행원 알골즘

데드락의 무시

• 예방, 회피기법을 프로그램에 넣으면 성능에 큰 영향을 미칠 수 있다. 따라서 데드락의 발생 확률이 비교적 낮은 경우 이를 무시하고 특별한 조치를 취하지 않는다.

데드락의 발견

• 감시/발견을 하는 detection 알고리즘으로 데드락 발생을 체크하는 방식.

• 단점 : 성능에 큰 영향을 미칠 수 있다.

출처 : 위키백과, [블로그](