The Deadlock Problem
-
Deadlock(교착상태)
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태 -
Resource(자원)
-하드웨어, 소프트웨어 등을 포함하는 개념
-(예) I/O device, CPU cycle, memory space, semaphore 등
- 프로세스가 자원을 사용하는 절차
**Request, Allocate, Use, Release -
Deadlock Example 1
-시스템에 2개의 tape drive가 있다.
-프로세스P1과 프로세스P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다. -
Deadlock Example 2
- Binary semaphore A and B
Deadlock 발생의 4가지 조건
-
Mutual exclusion(상호 배제)
-매 순간 하나의 프로세스만이 자원을 사용할 수 있음 -
No preemption(비선점)
- 프로세스는 자원을 스스로 내어놓을 뿐 강제로 뺴앗기지 않음 -
Hold and wait(보유 대기)
- 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음 -
circular wait(순환대기)
- 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
- 프로세스 P0, P1...Pn 이 있을 때
P0은 P1이 가진 자원을 기다림.
P1은 P2이 가진 자원을 기다림.
Pn-1은 Pn이 가진 자원을 기다림.
Pn은 P0이 가진 자원을 기다림.
데드락이 걸렸는지 확인하기 위해서
Resource-Allocation Graph(자원 할당 그래프)를 그린다.
- 그래프에 cylce이 없으면 deadlock이 아니다.
- 그래프에 cycle이 있으면
- if only one instance per resource type, then deadlock
- if several instance per resource type, possibility of deadlock
Deadlock의 처리방법
-
1.Deadlock Prevention / 데드락이 발생하지 않게 미연에 방지 강한 데드락 처리방법
- 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것 -
2.Deadlock Avoidance / 데드락이 발생하지 않게 미연에 방지 강한 데드락 처리방법
- 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당 -
3.Deadlock Detection and recovery
- Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover -
4.Deadlock ignorance
- Deadlock을 시스템이 책임지지 않음
- UNIX를 포함한 대부분의 OS가 채택
데드락을 미연에 방지하기 위해 훨씬 더 많은 오버헤드를 들이는 것이 훨씬 더 비효율적이기 때문에 오버헤드가 생기든 말든 놔두는 방법을 주로 쓰고 있다.
1-1 Deadlock Prevention
- Mutual Exclusion
- 공유해서는 안되는 자원의 경우 반드시 성립해야 함 - Hold and Wait(자원을 기다리는 상황에서는 자원을 보유하지 않으면 된다.)
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
- 방법1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
- 방법2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청 - No Preemption(NO 선점)
- process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
- State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory) - Circular Wait
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로 자원 할당
- 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원Rj을 할당받기 위해서는 우선 Ri를 release해야 한다.
=> Utilization 저하, throughput 감소, starvation 문제
2-1 Deadlock Avoidance
-
Deadlock avoidance
- 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로 부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당
- 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임 -
safe state
- 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태 -
safe sequence
- 프로세스의 sequence <P1,P2, ... , Pn > 이 safe하려면 P1 (1<=i<=n)의 자원 요청이가용 자원+모든 Pj(j<i)의 보유 자원에 의해 충족되어야함.
- 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j<i)가 종료될 때까지 기다리나.
*Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.
//프로세스가 시작되고 종료될때 까지 평생에 쓸 자원의 최대량을 미리 알고 있다고 가정하고 데드락을 피해간다.
-
시스템이 safe state에 있으면
=> no deadlock -
시스템이 unsafe state에 있으면
=> possibility of deadlock -
Deadlock Avoidance
- 시스템이 unsafe state에 들어가지 않는 것을 보장
- 2가지 경우의 avoidance알고리즘
*Single instance per resource types- Resource Allocation Graph algorithm 사용
*Multiple instances per resource types
- Banker's Algorithm 사용
Resource Allocation Graph algorithm
- Claim edge Pi -> Rj
- 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻함(점선으로 표시)
- 프로세스가 해당 자원 요청시 request edge로 바뀜(실선)
- Rj가 release되면 assignment edge는 다시 claim edge로 바뀐다.
- Cycle 생성 여부 조사시 프로세스의 수가 n일 때 O(n2)시간이 걸린다.
Banker's Algorithm 사용
자원당 인스턴스가 여러개 있는 경우
- 가정
- 모든 프로세스는 자원의 최대 사용량을 미리 명시
- 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다. - 방법
- 기본 개념 : 자원 요청시 safe상태를 유지할 경우에만 할당
- 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택(그런 프로세스가 없으면 unsafe상태)
- 그런 프로세스가 있으면 그 프로세스에게 자원을 할당
- 할당받은 프로세스가 종료되면 모든 자원을 반납
- 모든 프로세스가 종료될 때까지 이러한 과정 반복
