CH7 Deadlocks (교착상태)
교착상태(Dead Lock)은 상호 배제에 의해 나타나는 문제점으로,
둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미
Deadlock Problem
Deadlock
- 일련의 프로세스들이 서로가 가진 자원을 기다리면서 block된 상태
Resource(자원)
- 하트웨어 소프트웨어 등을 포함하는 개념
- I/O device, CPU cycle, memory space, semaphore
- 프로세스가 자원을 사용하는 사용절차
- Request(요청)-> Allocate(자원획득) -> Use(사용) -> Relase (자원 반납)
Example
Deadlock 발생의 4가지 조건
- Mutual exclusion
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
- No preemption
- 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
- Hold and wait (보유대기)
- 내가 가진 자원을 놓지 않으면서 다른 자원을 기다림
- Circular wait (순환 대기)
- 자원을 기다리는 프로세스간에 사이클이 형성되어 있어야 함
Resource - Allocationn Graph 자원 할당 그래프
- 작은 점 -> 자원의 instance
- cycle 이 없음
- cycle 이 있음
- 자원의 instance가 여러 개 있으면 deadlock 일 수도 아닐 수도 있다
- 1 graph : deadlock O
- 2 graph : deadlock X
- 4번 프로세스가 다 사용하고 나서 반납하면 dead lock 사라지기 때문
Deadlock의 처리 방법
Deadlock Ignorance
- deadlock이 자주 발생하지 않기 때문에 현대 컴퓨터 에서는 미연에 방지하지 않음
1. Deadlock Prevention
- Mutual Exclusion (필수) -> 배제해서는 안되는 조건임
- Hold and Wait
- 자진 반납
- No Preemption
- 자원을 빼앗을 수 있게 한다. (CPU,memory) (자원 상태 저장)
- 생기지도 않을 deadlock 문제를 미리 방지하고 있어서 비효율적
2. Deadlock Avoidance
Deadlock 발생 가능성 계속 검사. 발생 가능성이 있다면 회피.
- Safe state : Deadlock이 발생하지 않는 상태
- Unsafe state : Deadlock 발생 가능성 있는 상태 (100%는 아님)
Safe state에 있던 프로세스는 언제든지 Unnsafe state로 넘어갈 수 있으며, 이것을 막아야 한다.
Deadlock을 회피하기 위한 알고리즘 2가지
1) 자원이 하나 종류일 때 -> 자원 할당 그래프
2) 자원이 여러 종류일 때 -> Banker's Algorithm 사용
일단 할당했다고 가정하고 Deadlock이 발생하는지 확인해 실제로 Deadlock이 발생하는 걸 막는다는 공통점이 있음
Resource Allocation Graph algorithm
자원이 한 종류일 때
- 점선화살표
- 프로세스가 새로 자원을 요구하는 것
- 프로세스가 평생에 적어도 한 번은 이 자원을 요청
- 3 graph
- deadlock 이 아님
- 점선이 실선이 되면(자원 요청하면) deadlock 이 생김
- deadlock 위험성이 있으면 애초에 자원을 주지 않음
Banker's Algorithm
자원이 여러 종류일 때
-
자원당 instance 여러 개인 경우 이 알고리즘 통해 dead lock을 막는다
-
Allocation : 현재 할당 중인 자원
-
Max : 프로세스가 작업을 끝내기 위해 필요한 총자원
-
Available : 현재 빌려줄 수 있는 자원의 양
-
Need : 추가로 요청할 수 있는 양
-
안전상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절한다.
-
p0이 b 2개 요청 -> 남아있는 양 있지만 추가요청 (7,4,3) 임 -> 남아있는 것 가지고 충족 x / 혹시 최대 요청을 할까봐
-
최악의 경우를 고려 (7,4,3)
-
보수적 알고리즘
-
가용자원 (0,0,0) 되면 무조건 deadlock은 아님 -> 다른 애가 반납할 수 있음
3. Deadlock Detection and recovery
- Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
싸이클을 찾는 오버헤드는 얼마인가?
O(n**2) -> n(n-1)
- Resource 당 multiple instance 인 경우
- 낙관적 관점으로 본다
p2 가 자원 c 하나를 요청
deadlock 이 있는지 찾아볼 때
- 가용자원으로 처리할 수 있는지 보기
- 요청하지 않은 프로세스 (Request) 가용자원으로 합치기 -> P0 같은 경우
- 거기서 처리할 수 있는지 체크
Deadlock이 발견이 되면 Recovery 해야함
- Process termination
- 데드락에 연루된 프로세스 종료
- Resource Preemption
- 데드락에 연루된 프로세스로 부터 자원 뺏기
4. Deadlock Ignorance
- 사용자가 deadlock을 알아서 처리
- OS는 deadlock에 대해 대처하지 않는다. (현대의 대부분 운영체제)
