Deadlock(데드락)

Computer Science/Operating System

호준송 2023. 3. 8. 00:43

728x90

Deadlock

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

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

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

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

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

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

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

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

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

→ 잘 사용하지 않는다.

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

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

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

728x90