교착상태(deadlock)
The Deadlock Probleam
- Deadlock
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
- Resource(자원)
- 하드웨어, 소프트웨어 등을 포함하는 개념
- ex. IO device, CPU cycle, memory space, semaphore 등
- 프로세스가 자원을 사용하는 절차
- Request(자원 요청), Allocate(실제 할당), Use(사용), Release(다시 내어놓음)
Deadlock 발생의 4가지 조건
4가지 조건을 모두 만족해야 deadlock이 발생한다.
- Mutual exclusion(상호 배제)
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
- No preemption(비선점)
- 프로세스는 자원을 스스로 내어놓지 않는 이상 강제로 빼앗기지 않음
- Hold and wait(보유 대기)
- 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
- Circular wait(원형 대기)
- 자원을 기다리는 프로세스 간에 사이클이 형성된다.
Resource Allocation Graph (자원 할당 그래프)
- R->P 해당 자원은 해당 프로세스가 점유하고 있다.
- P->R 해당 프로제스가 자원을 기다리고 있다.
- 참고로 자원 내의 동그라미는 특정 자원의 각 인스턴스를 나타냄
아래 두 그림을 보고 deadlock 상태인지 아닌지 확인해봅시다!
- 그래프에 cycle이 없으면 deadlock이 아니다.
- 그래프에 cycle이 있으면,
- 각 자원 당 instance가 하나라면, 무조건 deadlock이다.
- 각 자원 당 instance가 여러개라면, deadlock일 가능성이 있다.
- 예시1) 좌측의 R2는 instance가 2개이며, 두 instance 모두 cycle을 형성하고 있기 때문에 deadlock이다.
- 예시2) 우측의 R2는 instance가 2개이지만, 하나의 instance는 cycle을 형성하고 있지 않기 때문에(R2->P4) deadlock이 아니다.
Deadlock의 처리 방법
Deadlock Prevention
- 데드락을 미연에 방지하는 방식
- 자원 할당 시 deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
Deadlock Avoidance
- 데드락을 미연에 방지하는 방식
- 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없어지는 경우에만 자원을 할당
- 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
Deadlock Detection and recovery
- 데드락 발생했을 경우 recovery하는 방식
- 데드락 발생은 허용하되 그에 대한 detection 루틴 을 두어 deadlock 발견 시 recover
Deadlock Ignorance
- 데드락을 시스템이 책임지지 않음
- UNIX를 포함한 대부분의 OS가 채택
1. Deadlock Prevention
- 가장 강력한 deadlock 처리 방식
- 아래 Deadlock 발생의 4가지 조건에 대하여 Deadlock Prevention의 관점으로 다시 살펴보자
- Mutual Exclusion
- 공유해서는 안되는 자원의 경우 반드시 성립
- No Preemption
- 강제로 자원을 빼앗지 않아서 생기는 문제라면, 자원을 빼앗자 !
- 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다.
- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
- State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU, memory)
- Hold and Wait
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
- 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
- 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
- Circular Wait
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
- 예를 들어 순서가 3인 자원 Ri을 보유 중인 프로세스가 순서가 1인 자원 Rj을 할당받기 위해서는 우선 Ri를 release해야한다.
- Mutual Exclusion
- 문제점
- Utilization 저하
- Throughput 감소
- Starvation 문제
2. Deadlock Aviodance
-
개념
- 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당
- 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임
-
safe state
- 시스템 내의 프로세스들에 대한 sate sequence가 존재하는 상태
-
safe sequence
- 프로세스의 sequence <P1,P2,....,Pn>이 safe하려면 Pi(1<=i<=n)의 자원 요청이 가용자원 + 모든 Pi의 보유자원에 의해 충족되어야 함
- 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
- Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j<i)가 종료될 때까지 기다린다.
- P(i-1)이 종료되면 Pi의 자원요청을 만족시켜 수행한다.
-
시스템이 safe state에 있으면
- no deadlock
-
시스템이 unsage state에 있으면
- possibility of deadlock
-
Deadlock Aviodance
- 시스템이 unsafe state에 들어가지 않는 것을 보장
- 2가지 경우의 avoidance 알고리즘
- single instance per resource types
- Resouce Allocation Graph algorithm 사용
- Multiple instances per resource types
- Banker's Algorithm 사용
- single instance per resource types
Resouce Allocation Graph algorithm
여기서 점선은 지금 당장 프로세스가 해당 자원을 요청한 것은 아니지만 미래에 요청 가능성이 있는 것을 의미한다. 즉, 점선은 각 프로세스의 최대 자원 사용량을 표기하기 위한 것이라고 생각하면 된다.
Banker's Algorithm
- 가용자원으로 최대 요청을 처리할 수 있는지에 대해 고려
Need <= Avaliable을 만족시켜야 함
3. Deadlock Detection and Recovery
- 프로세스-자원-프로세스 형태가 아닌 우측과 같이 프로세스-프로세스 형태로 표시하면 더 빠르게 사이클을 찾을 수 있음
Detection
- 요청한 자원이 있는 프로세스는 가진 자원을 내어놓지 않을 것임
- 요청한 자원이 없는 프로세스는 가진 자원을 내어놓아 가용자원으로 만들어질 가능성이 있음
- 여기서 request의 의미는 추가 요청 가능량이 아니라 '현재 실제로' 요청한 자원량을 나타냄
Recovery
Process termination- 데드락에 연루된 모든 프로세스를 kill
- 데드락 사이클이 풀릴 때까지 데드락에 연루된 프로세스를 순차적으로 kill
Preemption- 비용을 최소화할 희생양(victim)을 선정
- sage state로 rollback해서 process를 restart
- Starvation 문제
- 동일한 프로세스가 계속해서 victim으로 선정되는 경우
- cost factor에 rollback 횟수도 함께 고려
4. Deadlock Ignorance
- 데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
- 데드락이 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일 수 있음
- 만약 시스템에 데드락이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이느 등의 방법으로 대체한다
- UNIX, 윈도우 등 대부분의 범용 OS가 채택하는 방식이다.
둔한 붓이 총명함을 이긴다