<cs> 데드락 (DeadLock, 교착 상태)

두 개 이상의 프로세스나 스레드가 자원을 얻지 못하고 무한 대기 상태로 있는 경우를 의미하며, 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.

☠️ 데드락(Deadlock)의 발생조건

아래 4가지 조건이 모두 성립해야 데드락이 발생한다.

• 상호 배제

  • 한 번에 한 개의 프로세스만 해당 자원을 사용할 수 있다.
    (사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.)

• 점유 대기

  • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.

• 비선점

  • 다른 프로세스에 할당된 자원을 강제로 빼앗을 수 없다(비선점).

• 순환 대기

  • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

💫 데드락(Deadlock)의 해결법

크게 3가지로 분류할 수 있다.

1. 데드락이 발생하지 않도록 예방(prevention) 하기
2. 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기
3. 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기

1. 데드락 예방 (Prevention)

데드락의 발생조건 4가지 중 하나라도 발생하지 않게 하는 것이 데드락을 예방하는 방법이다. 즉, 각각의 조건을 방지(부정)하여 데드락 발생 가능성을 차단한다.

• 상호 배제 조건 방지

  • 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
  • 동기화 관련 문제가 발생할 수 있다.

• 점유 대기 조건 방지

  • 프로세스 실행 전 필요한 모든 자원을 할당하여 대기를 없애거나, 자원이 점유되지 않은 상태에서만 자원을 요구하도록 한다.

• 비선점 조건 방지

  • 이미 다른 프로세스에게 할당된 자원을 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.

• 순환 대기 조건 방지 : 자원에 고유 번호 할당 후 순서대로 자원 요구할 수 있도록 한다.

단점 : 자원 사용의 효율성이 떨어지고 비용이 많이 든다.

2. 데드락 회피(Avoidance)

시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 안정 상태(safe state)에 있다고 말한다.

특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서(safe sequence)라고 부릅니다.

회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 Safe state에 있을 수 있도록 할당을 허용하는 것이다.
회피 알고리즘으로는 자원 할당 그래프 알고리즘과 은행원 알고리즘이 존재한다.

은행원 알고리즘(Banker’s Algorithm)

어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션 해서 Safe state에 들 수 있는지 여부를 검사합니다. 즉 대기중이 다른 프로세스들의 활동에 대한 교착 상태 가능성을 미리 조사하는 것입니다.

예시) 시스템이 총 12개의 자원을 가지고 있다고 가정했을 때

현재 t0	프로세스의 최대 자원 요청량	프로세스에 할당 중인 자원 수	필요한 자원 수
P0	10	5	5
P1	4	2	2
P2	9	2	7

t0 일때 총 할당된 자원의 합은 5 + 2 + 2 = 9개로
시스템 자원 12개에서 할당 가능한 자원은 3개가 남았다.

여기서 순서가 p1 -> p0 -> p2 일 때 안전 순서를 만족한다.

• p1에 필요한 자원 2개를 할당해주면 시스템 자원은 1개가 남는다.
  • p1이 끝나면 할당된 자원 총 4개를 모두 반납한다.
    시스템 자원은 1 + 4 = 5개가 된다.
• p0에게 필요한 자원 5개를 할당하고 시스템 자원은 0개가 된다.
  • p0이 끝나면 할당된 자원 총 10개를 모두 반납한다.
    시스템 자원은 10개가 된다.
• p2에게 필요한 자원 7개를 할당하고 시스템 자원은 3개가 된다.
  • p2가 끝나면 할당된 자원 총 9개를 반납한다.
    시스템 자원은 3 + 9 = 12개가 된다.

이렇게 자원의 부족함 없이 올바르게 할당하여 모든 프로세스가 실행 할 수 있었다.

만약 t0일 때 p2가 2개가 아닌 3개를 할당받았다면?

• t0일 때 가능한 시스템 자원은 2개가 된다.
• p1에게 2개를 모두 주고 끝나면 시스템 자원은 4개가 된다.
• p0, p2의 필요한 자원이 충족하지 못하므로 p0, p2는 자원을 할당 받기를 계속 기다리게 된다.

따라서 운영체제가 사전에 p2가 자원을 3개를 요청했을 때 할당해 주지않고 대기하거나 2개만 할당했다면 데드락이 발생하지 않았을 것이다. 은행원 알고리즘을 사용해 자원 할당량을 사전에 파악하고 데드락을 회피할 수 있도록 하면 된다.

단점 : 미리 최대 자원 요구량을 알아야 하고, 할당할 수 있는 자원 수가 일정해야 하는 등 사용에 있어 제약조건이 많고, 자원 이용도가 떨어진다.

3.데드락 탐지(Detection) 및 회복(Recovery)

• 탐지 기법
  • 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악합니다.
  • 자원 할당 그래프를 통해 탐지
• 회복 기법
  • 프로세스 중단 시키기
    • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 누락될 수 있는 부작용이 발생할 수 있음
    • 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있음
  • 자원 선점하기
    • 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당한다. (해당 프로세스 일시정지 시킴)
    • 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

참고