Deadlock(데드락)

Deadlock

---

• 두 가지 이상의 작업이 서로 상대방의 작업이 끝나기를 하염없이 기다리고 있는 상태

 

 

Deadlock 발생 조건

---

1. Mutual Exclusion(상호 배제)
   • 한 프로세스가 공유 자원을 점유중일 때 다른 프로세스가 동일한 자원에 접근하지 못하게 통제하는 것
2. Hold & Wait(보유 대기)
   • 프로세스가 하나의 공유 자원을 점유한 상태에서 다른 공유 자원에 접근하기 위해 대기하는 상태
3. No preemption(비선점)
   • 다른 프로세스가 점유한 자원을 다른 프로세스가 강제로 빼앗을 수 없다.
4. Circular Wait(순환 대기)

• 요청 관계가 그림과 같이 순환 구조를 이루는 상태

→ 4가지를 모두 만족해야 Deadlock이 발생한다.

 

 

Deadlock 처리 방법

---

1. Deadlock Prevention(데드락 예방)

4가지의 발생 조건을 하나라도 발생하지 않게 하는 방법이다.

• Mutual Exclusion 방지
  • 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
  • 동기화 문제가 발생 가능하여 현실적으로 불가능한 방법이다.
• Hold & Wait 방지
  • 프로세스가 시작할 때 필요한 모든 자원을 한 번에 요청하는 방식이다.
  • 자원 낭비와 starvation이 발생할 수 있다.
• No preemption 방지
  • preemption 으로 바꾼다.
  • 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스의 자원을 빼앗게 된다.
  • 마찬가지로 자원 낭비와 starvation이 발생할 수 있다.
• Circular Wait 방지
  • 자원에 번호를 부여하고 모든 프로세스가 자원을 오름차순으로 요청한다.
  • 높은 번호를 점유한 채로 낮은 자원을 요청할 수 없어서 deadlock이 발생하지 않는다.
  • 번호를 붙이는 overhead 발생한다.

→ 4가지 방식 모두 효율성을 떨어트린다.

 

 

2. Deadlock Avoidance(데드락 회피)

Deadlock 발생 가능성을 검사해서 발생 가능성이 있다면 사전에 회피하는 방식이다.

💡 3가지 정보와 1가지 가정을 전제로 한다.
1. 각 자원의 가용 인스턴스 개수
2. 모든 프로세스마다 보유하고 있는 자원 개수
3. 모든 프로세스마다 필요한 자원의 총 개수
가정 : 프로세스는 필요한 자원을 모두 사용하고 한 번에 해제한다.

기본 구조

💡 Safe State
- 데드락이 발생하지 않는 경우가 단 하나라도 있는 상태
- 데드락이 없는 프로세스 실행 순서를 Safe Sequence라고 한다.
💡 Unsafe State
- 데드락에 빠질 가능성이 있는 상태

• Safe State 에서는 Safe Sequence가 존재하기 때문에, Safe State를 계속 유지한다면 데드락에 빠지지 않는다.
• Unsafe State 로 향하는 자원 요청은 모두 거절한다.

 

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

• 먼저, 12개의 자원을 가지고 있다고 가정한다.(남은 자원 : 3)

1. P0 또는 P2 에게 3의 자원을 할당한다면 P0,P1,P2 모두 작업하지 못하는 Deadlock이 발생한다.
   • 따라서, P0 또는 P2 에게 3의 자원을 할당하지 않는다.
2. P1에게 2개의 자원을 할당해 P1의 작업을 완료한다. (남은 자원 : 1)
   • 작업 완료 이후 P1가 가지고 있던 자원 4개가 반납된다.(남은 자원 : 4 + 1 = 5)
3. 5개의 자원으로 P0 의 작업을 완료한다.(남은 자원 : 0)
4. 작업 완료 이후 P0가 가지고 있던 자원 10개가 반납된다.(남은 자원 : 10 + 0 = 10)
5. 마지막으로 P2의 작업을 완료한다.

• Deadlock을 피했지만, 초기 제약과 가정이 필요하다.
• 또한, 시스템 상태를 매번 검사하는 오버헤드가 발생한다.

→ 잘 사용하지 않는다.

 

 

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

일단 실행을 하면서 주기적으로 상태를 탐지한다. Deadlock 발생 시 회복하는 방식이다.

 

Deadlock Detection(탐지 기법)

1. Resource Request Algorithm
   • Banker’s Algorithm과 유사하다.

오른쪽 하단 오타 : Allocation Vector -> Available Vector

1. • Request matrix : 요청중인 자원의 개수를 나타낸 행렬
   • Allocation matrix : 현재 할당 된 자원의 개수를 나타낸 행렬
   • Available vector : 각 종류의 자원이 남은 개수를 나타내는 벡터
   • Resource vector : 현재 사용중인 자원의 개수를 나타내는 벡터
   • 수행 방식
     1. 모든 자원 요청이 0인 프로세스를 체크한다. (P4 체크)
     2. 자원을 할당했을 때 끝낼 수 있는 프로세스를 체크하고 자원을 반납한다.(P3 체크, 자원 반납)
     3. 2번 작업을 반복했을 때 체크되지 않은 프로세스는 Deadlock이 발생한 프로세스다.
        
        
2. Resource-Allocation Graph(자원 할당 그래프) 사용

1. • 자원이 각각 1개씩 있을 때 사용 가능하다.
   • 수행 방식
     1. (a) 그래프에서 자원을 지우고 방향을 유지, 연결한다.(a -> b 그래프 생성)
        • (b) 그래프 : 자원을 반납하는 것을 기다리는 상황을 표현한 그래프
     2. 새로 만들어진 (b) 그래프에서 사이클이 존재한다면 데드락이 존재함을 의미한다.

 

Deadlock Recovery(회복 방식)

1. Process Termination(프로세스 종료)
   1. Deadlock의 원인이 되는 프로세스를 모두 종료
   2. Deadlock이 제거될 때 까지 순차적으로 한 프로세스씩 중지
      • overhead가 크다.
2. Resource Preemption(자원 선점)
   1. Deadlock이 제거될 때 까지 한 프로세스가 점유한 자원을 다른 프로세스에게 할당

 

 

추가 질문

Q. 왜 현대 OS는 Deadlock을 처리하지 않을까요?

• Deadlock이 드물게 발생하기 때문에 Deadlock을 처리하는 과정이 더 큰 overhead일 수 있다.
• 시스템이 비정상적일 경우 유저가 직접 process를 지우는 방법으로 대처한다.

 

 

참고

---

[10분 테코톡] 🚴‍♂️ 케빈의 Deadlock데드락(Deadlock)

[ 운영체제 ] 데드락(Deadlock) 해결 방법

데드락(Deadlock)

[운영체제] 데드락(Deadlock, 교착 상태)이란?