Deadlock Problem
- Deadlock
한 process가 resource를 요청했을 때, 그 시각에 그 resource를 사용할 수 없는 상황이 발생, 그때 process가 waiting 상태가 됨. 이처럼 waiting인 process들이 요청한 자원들이 다른 프로세스들에 의해 점유되어있고 그들도 다 대기상태에 있기 때문에 다시는 그 상태를 변경시킬 수 없는 상황.
ex) semaphores A and B, initialized to 1
P0 P1
wait(A); wait(B);
wait(B); wait(A);
- - - - - - - - - - - - - - - - -
wait(T){
while T <=0 ;
T --;
}- Bridge Crossing Example
Deadlock 특징
-
다음 4가지가 동시에 만족되었을 때 일어날 수도 있다.(항상 발생은 아님)
- Mutual exclusion 상호배제: 오직 하나의 프로세스만 하나의 자원을 사용할 수 있다. 적어도 하나의 자원은 공유가 불가능한 자원이다.
- Hold and wait 점유하며 대기: 적어도 하나의 자원을 보유한 프로세스가 다른 프로세스의 자원을 추가로 얻기를 기다리는 상태
- no preemeption 비선점: 중간에 끊을 수 없는 상황, 이미 할당된 자원이 갑자기 반납되어서는 안된다. 프로세스가 스스로 반납.
- circular wait 순환 대기: 프로세스들이 자원을 소유하고 요청하는 형태가 원형을 이룰 때를 말한다.
각 프로세스에는 하나의 자원이 할당되어있고, P1은 P2자원을 기다림, P2는 P3자원을 기다림, P3는 P1자원을 기다릴 때 원형을 이룬다.
System Model
- Resource types: R1, R2...Rm (CPU cycles, memory space, I/O devices)
- 각 유형의 자원 Ri는 Wi instance들을 가진다.
- 각 process의 유형 활용
- request 요구
- use 사용
- release (반납)
Resource-Allocation Graph
자원 할당 그래프
- V(vertex), E(edge)의 집합으로 구성
- V: process 집합, resource 집합
- E
request edge: Pi→Rj
assignment edge: Ri→Pj
Deadlock을 가지는 자원 할당 그래프
p3가 R2 유형의 인스턴스를 요청하면 최소 두개의 cycle이 생성된다.
- Mutual exclusion 2. Hold and wait 3. No preemtion 4. Circular wait 다 만족
2) Deadlock이 아닌 자원 할당 그래프 case3
→ Hold and wait 조건이 깨짐!
P2, P4의 경우 R1을 가지고 있으나(Hold) 다른 자원을 기다리고 있지 않음(Wait X)
정리
- no cycle → no deadlock
- cycle O
- 각 자원 유형이 하나의 인스턴스만 가지면 하나의 사이클은 deadlock 상태! (case2)
- 여러개의 인스턴스를 가지면 반드시 dealock 상태라고 할수 없다.(case 3)
- 각 자원 유형이 하나의 인스턴스만 가지면 하나의 사이클은 deadlock 상태! (case2)
Deadlock Handling Method
1) deadlock이 절대 발생하지 않도록 설계 -> Prevention or Avoidance
deadlock prevention
- OS에서 deadlock이 발생하지 않도록 4가지 조건 중 최소 1가지를 절대 만족시키지 않도록 한다. → 요청 방법에 제한을 둔다.
- mutal exclusion
- 공유 가능 자원에서는 요구되지 않는다. -> 즉 deadlock이 걸리지 않는다,
- 공유가 불가능한 자원에 대해서는 반드시 성림해야한다. 따라서 일반적으로 이 조건을 어겨 예방하는 것은 불가능하다.
- hold and wait
- 자원을 요청할 때 다른 자원들을 점유하지 않을 것을 보장하면 된다.
- 1) 각 프로세스가 모든 자원을 확보했을 때만 실행되도록 한다. ->
- 2) 프로세스가 어떠한 자원도 점유하고 있지 않을 때 자원을 요청한다.
ex) 1번, 2번 resource를 동시에 잡을 수 있을 때만 요청하도록 한다.
→ 최소한 하나가 항상 다른 프로세스에게 할당되어 있기 때문에 starvation possible - 자원을 요청할 때 다른 자원들을 점유하지 않을 것을 보장하면 된다.
- no preemeption
- 이미 할당된 자원이 선점되지 않아야함 (강제로 방출되면 안됨)
-
어떤 자원을 점유하고 잇는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면(즉, 프로세스가 반드시 대기해야 하면) 현재 점유하고 있는 모든 자원을 release 하도록 한다 -> 이로써 preemption 되어버림.
ex) 10개의 resource가 필요해 6개를 요청 후 확보. 이후 다시 4개를 요청했을 다른 process에 할당되어 있어 때 바로 받을 수 없다면 가지고 있던 6개와 다른 prcess가 점유하고 있는 4개의 resource 모두 releas됨. 이로써 preemption이 되버림.
더불어, process는 요청 중인 새로운 자원(4개)를 할당 받은 후 대기 중에 선점되었던(끊겼던) 모든 자원(6개)를 회복할 때에만 다시 시작할 수 있음.
-
- circular wait
- resource에 ordering(순서)을 부여하여 증가하는 순서로만 resource를 요청할 수 있고 할당받을 수 있게 한다. 동시에 요청 불가능하기에 원형을 이룰 수 없다.
ex) R4(15)를 점유한 상태에서 번호가 작은 R6(6)을 요청할 수 없다.
→ 장치의 이용률 저하, 시스템 처리율(throughput) 감소의 문제점
Deadlock Avoidance
additional priori information이 필요하다.
- process는 자신에게 필요한 maximum 자원 개수를 미리 선언해야한다.
- 시도때도 없이 Resource-allocation-state를 확인해 circular-wait condition에 빠지지 않도록 해야 한다.
- Resource-allocation state는 available resource 수, 할당된 resource 수, process들의 최대 요구(maximum demand) 수에 의해 정의된다
Safe State 안전 상태
- 시스템이 어떤 순서로든 프로세스들이 요청하는 모든 자원을(최대 요구 수를 요구하더라도) deadlock 상태를 유발하지 않고 차례로 모두 할당해 줄 수 있다는 것
- 시스템은 safe sequence가 존재할 때 safe state라고 할 수 있다.
-Pi가 요청하는 resource를 시스템에 현재 남아 있는 자원 (여유분) + Pi 이전 process(Pi-1)들이 수행을 마쳐 반답하는 자원들로 만족시켜 줄 수 있으면 sequence가 safe하다고 할 수 있다.
정리 ; safe state
- system이 safe state -> no deadlock
- system이 unsafe state -> deadlock 일 가능성이 있다.
- avoidance : system이 unsafe state에 절대 빠지지 않도록 하는 것이다.
Resource-Allocation Graph Algorithm
- Claim edge 예약
- process가 request를 할 수도 있음. 점선
- process가 자원을 request하면 request edge로 바뀐다.
- 자원이 process에 의해 release 되면, edge는 다시 claim edge로 바뀐다.
<deadlock avoidance를 위한 자원 할당 그래ㅠㅡ>
<unsafe state의 자원할당 그래프>
한 유형의 resource 안에 하나의 instance만 존재할때,
그래프가 cycle을 포함한다 -> Unsafe 상태
Deadlock Avoidance
intance가 하나일 경우 -> 자원 할당 그래프 그려봄 (7-1)
Banker's Algorithm
자산 관리. 은행가 알고리즘.
자원할당그래프 알고리즘보다 효율성이 떨어짐
-
Multiple instances
-
모든 프로세스는 가지고 있을 자원의 최대 개수를 미리 명시한다.
-
프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 내에 자원을 다시 반납한다.
-
n : 프로세스 개수, m : 자원 유형 개수
- Available (여유분) : 현재 시스템 내에 남아있는 여유 자원의 개수.
- Available[j] = k // Rj(j유형의 자원)의 인스턴스가 k개 여유분이 있음- Max : n x m matrix
- MAX[i,j] = k // Pi가 Rj의 인스턴스를 최대 k개를 요청할 수 있음.
- Allocation : n x m matrix
- Allocation[i,j] = k // Pi가 현재 Rj의 인스턴스를 k개 할당받았음
- Need :n x m matrix
- Need[i,j] = k // Pi가 앞으로 추가적으로 Rj의 인스턴스가 k개 필요함.
- Need[i,j] = Max[i,j] - Allocation [i,j]
- Max : n x m matrix
여유분 : A 유형 자원의 인스턴스 3개, B 유형 자원의 인스턴스 3개, C 유형 자원의 인스턴스 2개
safety Algorithm (Banker's)
-
Work와 Finish = n x m matrix
<초기값>
Work = Available
Finish[i] = false (i = 1,2...n) //끝난 process 없음 -
다음 조건을 만족시키는 i 값 찾기
(a) Finish[i] = false //아직 종료되지 않은 프로세스 중에
(b) Need(i) <= Work //필요한 자원이 여유분 보다 작거나 같다
i값을 찾을 수 없다면 step 4로 감. -
Work = Work + Allocation(i) // 반납
Finish[i] = true // Process 종료
step 2로 간다. -
모든 i값에 대해 Finish[i] == true 이면 safe state!!
Example
- P0~P4 (5개의 프로세스), 자원 A(인스턴스 10개), B(5), C(7)
- safety algorithm을 돌려보면 Safe State Sequence 중 하나로 < P1, P3, P4, P0, P2 > 순서가 뽑힐 수 있다. < P1, P3, P4, P2, P0 >도 있음.
-> 따라서 P1의 요청을 즉시 들어줄 수 있다.
Available(2.3.0)인 상태에서 P4가 (3.3.0)을 요청하면 자원 모자람. 즉시 들어줄수 없음
P0가 (0.2.0)을 요청하면 자원은 충분히 있지만 (순서에 어긋나서) 불안전 상태로 만듬-> 즉시 들어줄 수 없음.
Resource-Requset Algorithm for Process Pi
- 자원 요청을 안전하게 들어줄 수 있는지 검사하는 알고리즘.
- Request = 프로세스 Pi의 요청 벡터
Request[j]=k면 Pi가 Rj를 k개 까지 요청하고 있음.
-
Requesti ≤ Need(i) -> step 2로
아니면 시스템에 있는 개수보다 더 많이 요청했으므로 error 처리 -
Request(i) ≤ Available -> step 3
아니면 요청한 자원을 당장 사용할 수 없으므로 Pi는 기다려야함 -
마치 시스템이 Pi에게 자원을 할당해준 것처럼 시스템 정보를 아래처럼 바꾼다.
Available = Available - Request(i);
Allocation(i) = Allocation(i) + Request(i);
Need(i) = Need(i) – Request(i);그 다음 Safety algorithm 적용
- safe ⇒ Pi에게 위의 정보대로 자원 할당해줌
- unsafe ⇒ 위의 자원 할당 상태는 원상태로 복원, Pi는 Request(i)가 만족될 때까지 기다려야함.
<P1 Request (1.0.2) 했을 때>
- Request ≤ Need (즉, (1,0,2) ≤ (1,2,2) ⇒ true, O.K.) 확인
- Request ≤ Available (즉, (1,0,2) ≤ (3,3,2) true. OK) 확인
- safe algorithm을 실행하면 시퀀스 <P1, P3, P4, P0, P2> 또는 <P1, P3, P4, P2, P0>이 safety requirment을 충족함을 보여준다. 따라서 (1,0,2)를 할당한다.
P1 요청을 들어준 후 - P4의 (3,3,0) 요청을 승인 할 수 있는가?
- Available이 (2,3,0)이라 모자람. 승인 X
- P0에 의한 (0,2,0) 요청을 승인 할 수 있는가?
- 자원이 충분하지만 P0의 요구를 먼저 들어주게 되면 unsafety state로 만듬 (sequence 순서에 어긋남)
Deadlock Detection
Single Instance of Each Resource Type
-
wait for graph
-
자원 할당 그래프로부터 자원유형의 노드를 제거하고 적절한 간선들을 결합함으로써 얻을 수 있다.
-
Pi→Pj
- Pj가 갖고있는 자원들을 방출하기를 Pi는 기다리고 있음
-
cycle를 포함하는 경우에만 deadlock 존재
-
주기적으로 그래프에서 cycle을 탐지하는 algorithm 호출
- O(n^2) 연산 요구 (overhead)
- n=정점 v의 개수)
-
no cycle → no deadlock
-
cycle
- 모든 리소스 당 한개의 인스턴스만 있다면 deadlock
- 모든 리소스 당 여러개의 인스턴스가 있다면, deadlock이 가능한 상태 (필연은 아님)
-
Several Instances of a Resource Type
- Available.
- Allocation : 할당되어있는 자원 개수
- Request[i,j] == k ; Pi가 Rj를 k개 요청함
-
Work = Available // 초기화
Allocation(i)!=0이면 Finish[i] = false 그렇지 않으면 Finish[i] = true -
아래 두 조건을 만족하는 i 값 찾기
Finish[i] == false
Requesti <= Work
없다면 4번으로 -
Work = Work + Allocation(i)
Finish[i] =true → 2번으로 -
Finish[i] == false → Pi는 deadlock 상태
- <P0,P2,P4,P1,P4> 혹은 <P0,P2,P4,P4,P1> 순서로 작업을 다 끝낼수 있음.
- 또한 Finish[i]==true 이기때문에 safe한 상태!
- P2가 C 자원 한개 더 request
P1~4가 연루된 deadlock 상태로 빠지게 된다.
Detection-Algorithm 사용
- 탐색 알고리즘은 언제 돌리는가?
- deadlock 발생 빈도에 따라
- deadlock 상태가 일어나면 얼마나 많은 프로세스가 연루되는가?
- detection algorithm 임의로 호출하면 어떤 프로세스가 deadlock 상태인지 알수 없다.
교착 상태로부터 회복
- 모든 deadlock 상태인 프로세스 종료
- deadlock 상태가 끝날 때까지 하나씩 종료시킨다
- 어떤 프로세스를 종료할지
- 프로세스의 우선순위
- 프로세스가 걸리는 시간
- 리소스 사용량이나 프로세스가 필요한 리소스양
- 종료할 프로세스 갯수
- 프로세스가 interactive 혹은 batch인지?
Recovery from Deadlock
Process Termination
- deadlock 상태 모든 프로세스 중지
- deadlock이 제거될 때까지 한 프로세스씩 중지(부분 종료)
- 어느 프로세스를 선택할 것인가?
- Process의 Priority
- 지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는 데 더 필요한 시간
- 프로세스가 사용한 자원 유형과 수 (ex. 자원들을 선점하기가 단순한지 여부)
- 프로세스가 종료하기 위해 더 필요한 자원의 수
- 얼마나 많은 수의 프로세스가 종료되어야 하는지
- 프로세스가 interacive(대화형)인지 batch(일괄처리)인지 여부
Resource Preemption
-
deadlock 회복을 위해 preemtion이 필요할
-
victim(희생자) 선택 : 비용 최소화
-
Rollback : safe state로 돌아가서 프로세스를 다시 시작
-
Starvation : 계속 동일한 프로세스를 victim으로 선택하면 기아 발생 → 해결: cost 요소에 Rollback의 횟수를 포함시킴
