개념

• 시스템 자원에 대한 요구가 뒤엉킨 상태
• 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황

발생 조건

아래 4가지 조건이 동시에 성립할 경우 교착 상태가 발생한다.

4가지 조건 중 하나라도 성립되지 않도록 만든다면 교착 상태를 해결할 수 있다.

1. 상호 배제 Mutual Exclusion

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

사용 중인 자원을 다른 프로세스가 사용하려면 요청 자원이 해제될 때까지 기다려야 한다.

2. 점유 대기 Hold and Wait

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

3. 비선점 No Preemption

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

4. 순환 대기 Circular Wait

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

프로세스의 집합 {P0, P1, P2, …, Pn} 에서 P0는 P1이 점유한 자원을 대기, P1은 P2가 점유한 자원을 대기, …, Pn은 P0가 점유한 자원을 요구해야 한다.

발생할 수 있는 경우

• 멀티 프로그래밍 환경에서 한정된 자원을 사용하려고 서로 경쟁하는 상황
• 한 프로세스가 자원을 요청했을 때 사용할 수 없는 상황이 발생할 수 있고, 프로세스는 대기 상태가 된다. 대기 상태가 된 프로세스가 실행 상태로 변경될 수 없을 경우

예시

1. Process1, Process2가 모두 Resource1, Resource2가 필요하다.
2. time1: P1이 R1을 얻고 P2가 R2를 얻었다.
3. time2: P1은 R2를 기다리고, P2는 R1을 기다린다.
4. 서로 원하는 리소스가 상대방에게 할당되어 있어서 두 프로세스는 무한정 기다리게 된다.

해결

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

대부분의 시스템은 데드락이 잘 발생하지 않으며 데드락 예방, 회피, 탐지, 복구하는 것은 비용이 많이 든다.

예방 Prevention

특징

• 발생조건 4가지 중 하나라도 발생하지 않게 하는 것
• 각각의 조건을 방지(부정)해서 발생 가능성을 차단한다.

방식

1. 자원 상호 배제 조건 부정
   • 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
   • 동기화 관련 문제가 발생할 수 있다.
2. 점유 대기 조건 부정
   • 프로세스 실행 전에 필요한 모든 자원을 할당한다.
3. 비선점 조건 부정
   • 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.
4. 순환 대기 조건 부정
   • 자원을 순환 형태로 대기하지 않도록 일정한 한 방향으로만 자원을 요구할 수 있도록 한다.
   • 자원에 고유한 번호를 할당하고 번호 순서대로 자원을 요구하도록 한다.

단점

• 시스템의 처리량과 효율성을 떨어뜨린다.

회피 Avoidance

키워드

1. 안정 상태 Safe state

   : 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있는 상태

2. 불안정 상태

   : 데드락 발생 가능성이 있는, 안정 상태가 아닌 상황

   • 데드락 ⊂ 불안정 상태

3. 안전 순서 Safe sequence

   • 특정한 순서로 프로세스들에게 자원을 할당, 실행, 종료할 때 데드락이 발생하지 않는 순서

특징

• 회피법보다 덜 제한적이고, 단점을 일부 해결할 수 있다.
• 교착 상태가 발생하면 피해나가는 방법
• 자원을 할당한 후에도 시스템이 항상 안정 상태(safe state)에 있을 수 있도록 할당을 허용하자

은행원 알고리즘 Banker’s Algorithm

은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법

• 자원 할당량을 사전에 파악한다.
• 프로세스가 자원을 요구할 때 시스템이 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사해서 교착 상태를 회피하는 방식
• 안정 상태라면 자원을 할당하고 그렇지 않으면 다른 프로세스가 자원을 해제할 때까지 대기
• 교착 상태를 예방하거나 회피하는 프로토콜 사용

탐지 및 회복 Detection and Recovery

탐지

자원을 요청할 때마다 탐지 알고리즘을 실행하면 그에 대한 오버헤드가 발생한다.

1. 자원 할당 그래프를 그린다.
   
   • 프로세스 Pi가 자원 Rj를 요청하고 기다릴 때 방향 그래프는 Pi→Rj로 표현된다.
   • 자원 Rj가 프로세스 Pi에게 할당된 상태는 간선 Rj→Pi로 표현한다.
2. 은행원 알고리즘 방식과 유사하게 Allocation, Request, Available 등으로 시스템의 자원 할당 상태 가지고 데드락이 발생했는지 파악한다.

회복

1. 데드락을 일으킨 프로세스 종료하는 방법
   1. 교착 상태의 프로세스를 모두 중지
      • 계속 연산 중이던 프로세스들도 모두 일시에 중지되어서 부분 결과가 폐기될 수 있는 부작용이 발생한다.
   2. 교착 상태가 제거될 때까지 한 프로세스씩 중지
      • 매번 탐지 알고리즘을 호출하고 수행해야 해서 부담이 된다.
2. 자원을 선점하는 방법
   1. 교착 상태의 프로세스가 점유하고 있는 자원을 선점해서 다른 프로세스에게 할당하고, 해당 프로세스를 일시정지 시킴
   2. 우선 순위가 낮거나 수행된 횟수가 적은 프로세스의 자원을 선점

---

출처

• Deadlock 개념이란? 그에 대한 해결책/회피책
• [운영체제] 데드락(Deadlock, 교착 상태)이란?