Deadlock (교착 상태)

1. 교착 상태 란?

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

2. Deadlock 발생 조건

1. 상호 배제 (mutial exclusion)
2. 점유 대기 (hold and wait)
3. 비선점 (no preemption)
4. 순환 대기 (circular wait)

• 네가지 조건을 모두 만족하면 교착 상태가 발생

1) 상호 배제

• 하나의 공유자원에 대해 두 개 이상의 프로세스가 동시에 접근 할 수 없다.

2) 점유 대기

• 하나의 자원을 점유하고 있는 프로세스가 있고,
• 해당 프로세스가 다른 프로세스에서 자원을 얻기 위해서는 요청을 하고 대기를 해야한다.

3) 비선점

• 특정 프로세스가 어떤 자원을 사용하고 있는데,
• 그 해당 자원 사용이 끝나기 전에 그 자원을 뺏을 수 없다.

4) 순환 대기

• 프로세스들이 서로 사용하고 있는 자원의 대해서,
• 순환적으로 대기하고 있는 형태를 의미

3. Deadlock 해결 방법

1. 교착 상태 예방
2. 교착 상태 회피
3. 교착 상태 탐지 및 회복
4. 교착 상태 무시

• 교착 상태가 발생되지 않도록 사전에 예방하는 방법
• 네 가지 발생 조건 중 하나를 제거함으로써 해결하는 방법

4. Deadlock 예방

1. 상호 배제 조건 제거
2. 점유 대기 조건 제거
3. 비선점 조건 제거
4. 순환 대기 조건 제거

• 일반적으로 자원 사용 효율성이 떨어지고 비용이 많이드는 방법

1) 상호 배제 조건 제거

• 상호 배제 조건 : 하나의 공유 자원에 대해 두개의 프로세스가 동시에 접근 할 수 없다
• 해결방법 : 하나의 공유자원에 대해 프로세스들이 동시에 접근할 수 있다.
• 현실적으로는 불가능

2) 점유 대기 조건 제거

• 특정 프로세스가 어떤 작업을 수행할 때 그 해당 작업에 필요한 리소드들을 먼저 요청
• 할당 받은 다음에 작업을 수행하므로써 점유 대기 조건을 제거 할 수 있다.

2.1) 단점

• 자원의 효율성이 떨어진다.
• 프로세스들이 주기적으로 어떤 자원을 필요로 하는지 파악하는데 추가적인 오버헤드가 발생

3) 비선점 조건 제거

• 프로세스가 다른 프로세스의 자원을 요청 하기 위해서는 자신이 할당 받았던 자원을 반납을 해야 한다.

3.1) 단점

• 여태까지 작업했던 프로세스의 상태를 읽을 수 있다.

4) 순환 대기 조건 제거

• 순환 대기 : 프로세스들간에 서로 사용하고 있는 자원들을 대기 함으로써 발생하는 문제
• 각각의 자원들에 대해 고유번호를 할당을 하고 특정 프로세스 내 자신이 할당받은 자원에 번호를 기준으로 오름차순이나
  혹은 내림차순으로만 요청을 할 수 있도록 하는 방식

5. Deadlock 회피

• 교착 상태 발생 가능성을 검사해서 발생 가능성이 있다면 사전에 회피하는 방식

1. 자원 할당 그래프 알고리즘 (Resource Allocation Graph Algorithm)
2. 은행원 알고리즘 (Banker’s algorithm)

1) flow

1. 프로세스가 자원 요청시, 자원을 할당한 후에도 안정 상태로 남아 있는지 사전 검사.
2. 안정 상태라면 자원을 할당
3. 불안정 상태라면 다른 프로세스가 자원을 해지할 때까지 대기

• 자원을 요청할 때마다 시스템 상태를 검사하는 만큼 오버헤드가 큼
• 은행원 알고리즘의 경우 전제 조건이 많음

6. Deadlock 탐지 및 회복

• 교착 상태를 허용하지만 상태를 탐지하고 회복하는 방식
• 알고리즘을 주기적으로 실행함으로써, 시스템에 발생한 Deadlock을 체크하고 회복
• 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복

1) 방법 1. 프로세스 종료

• 교착 상태의 프로세스를 모두 중지
• 교착 상태가 제거될 때까지 한 프로세스씩 중지

2) 방법 2. 자원 선점

• 교착 상태가 제거될 때까지 프로세스가 점유한 자원을 선점해 다른 프로세스에게 할당

7. 자원 할당 그래프 알고리즘

• 그래프 상에 교착 상태를 유발시키는 순환 사이클의 존재 유무를 체크
• 시스템에 특성이나 비용적인 측면들을 고려해서 어느 주기로 이 알고리즘을 실행 해야할지 결정

8. 회복 고려 사항

• 희생자 선택
• 후퇴 (Rollback)
• 기아 상태 (Starvation)

1) 희생자 선택, 후퇴 , 기아상태

• 데드락에서 회복할 때 어떤 프로세스를 죽일 것인지
• 어떤 프로세스의 자원을 선점해서 다른 프로세스에게 할당 할 것인지 선택
• 희생자 선택을 할때 비용적인 측면 뿐아니라 다양한 파라미터 혹은 가중치 등을 고려해서 선택

9. Deadlock 무시

• 교착 상태 자체를 무시하고, 특별한 조치를 취하지 않는 방법
• 교착 상태의 발생 확률이 낮은 상황에서 주로 사용
• 교착 상태의 발생 확률이 낮은 운영체제, OS에서 주로 사용

출처

케빈의 Deadlock