Deadlock_운영체제(8)

Deadlock

• 서로 협력하는(연결된) process들이 발생할 수 없는 사건을 기다리는 상태를 의미한다.
• deadlock 상태의 process는 계속해서 block 상태를 유지한다.
• network, speed 등 상황에 따라 한번씩 일어날 수 있어서 debugging이 어렵다.
• 두 개 이상의 자원을 확보해야하는 상황에서 deadlock이 언제나 발생할 수 있는 것을 유의해야한다.

Deadlock Examples

• P1에서 A에 대한 lock을 가지고, P2는 B에 대한 lock을 먼저 가진다.
• 이후 다음 lock을 가지려고 할 때 서로 각자의 lock을 가지고 있기 때문에 두 개의 process 모두 block상태가 된다.
• [Ex 1]은 OS가 process가 왜 block이 되어있는지 모르는 상황이지만 [Ex 2]는 kernel이 무엇이 문제인지 알 수 있는 상황이다.

Dining Philosopher’s Problem

• lock을 동일한 형태로 가지도록 했지만, 모든 process가 cycle 형태로 작업을 하기 때문에 문제가 생긴다.
• 1개만 right 먼저 잡고 왼쪽을 다음으로 잡게하면 deadlock 문제가 해결된다.

Livelock

• 두 process가 모두 CPU를 이용하여 작업을 하는 것처럼 보이지만 오랜 시간동안 끝나지 않는 문제가 발생한다.
• blocking lock(I/O) : lock을 바로 가질 수 없으면 해당 process를 대기 상태로 전환시키는 system
• nonblocking lock(I/O) : trylock → system을 완료시킬 수 없으면 대기 상태가 아닌 바로 return을 하도록 하는 system
• deadlock은 kernel이 멈춰있으니 상황을 인지할 수 있지만, livelock은 지속해서 작동을 하고 있기 때문에 인지할 수 없다.

Necessary conditions for Deadlock (필요조건)

• 4가지의 상황이 모두 일어나야 Deadlock이 발생한다.
• 4가지 상황 중 1개의 상황만이라도 break를 하면 발생하지 않는다.

1) Mutual exclusion

• resource를 exclusive하게 사용해야하는 경우
• resource에 대한 독점권을 가져야하는 경우

2) Hold and wait

• 자원을 한 개 가지고 있으면서 다른 자원도 필요로 하는 경우

3) Non-preemption

• 자원을 가지고 있는 상태에서 다른 process가 자원을 빼앗지 못하는 경우

4) Circular wait

• 상황이 연쇄되어서 전체적으로 cycle을 이루는 경우

Resource Allocation Graph

• 자원 할당 그래프로 방향성 그래프이다.
• Pi → Rj : P가 R 자원을 요청
• Rj → Pi : 자원 R이 P에게 할당되었다.
• 요청되는 상황이 오래되고 있다면 자원 할당을 오래 기다리고 있는 것이다.
• 자원이 할당되어 있는 상황이라면 요청하는 화살표는 자원까지 그리는 것이 아니라 중간까지만 그린다.
• 1)의 상황은 circular wait이 아니어서 deadlock이 발생하지 않지만 2)는 circular wait 상황도 포함되어서 deadlock 상황이 발생할 수 있다.
• 3)의 상황은 circular wait이 존재하지만 가 자원 사용을 한 뒤 반납을 하면 deadlock이 해결된다.
• 즉, cycle만 있다고 deadlock이라고 할 수 없다.

Deadlock Handling

Prevention(예방)

• 4가지 조건을 최대한 만족시키지 않게 하는 것
• 너무 naive하기 때문에 system의 performance가 떨어질 수 있다.

1) Denying mutual exclusion

• 자원의 특성이기 때문에 불가능하다.

2) Denying non-preemption

• I/O 작업 중 멈춘다면 미완성의 상태로 중단되면 손실이 일어날 수 있기 때문에 일반적으로 불가능하다.
• CPU, Memory는 이전 상태를 복구할 수 있기 때문에 가능하다.

3) Denying hold and wait

• 추가적인 요청을 거절한다면 가능하다.
• 여러 자원을 동시에 사용을 해야 한다면 1개씩 할당을 받는 것이 아닌 자원을 한번에 할당받는 방식을 사용한다.
• all-or-nothing 전략
• Alloc(A, B) / lock(A, B) 와 같이 둘 다 가능한 경우에 동시에 할당을 받도록 한다.
• deadlock을 예방할 수 있지만 자원의 활용성이 낮아지기 때문에 Starvation이 발생할 수 있다.
• 사용하기 한참 전부터 자원을 선점할 수 있기 때문에 자원 활용성과 동시성(concurrency)이 낮아진다.

4) Denying circular-wait

• 각 자원들에 id를 부여한다.
• 자원을 요청할 때 id에 대해 increasing order만 요청할 수 있도록 한다.
• 예를 들어 5번 자원을 사용했으면 6번부터는 요청할 수 있지만 1번 자원은 요청할 수 없다.
• 이론적으로 가능하지만 programmer가 작업을 하는 것이 어려워진다.

Avoidance(회피)

Dijkstra’s Banker’s algorithm

• Safe state
  • bankrrupt로 가지 않는 상황을 확신하는 방법
  • process를 한 순간에 1개씩 순차적으로 실행하는 sequence가 존재할 때 safe 상태라고 한다.
• Unsafe state
  • safe한 sequence가 존재하지 않는 상태
  • deadlock이 무조건 일어나는 것이 아니라 deadlock이 일어날 가능성이 존재하는 것이다.

1 resource type case

• 자신이 쓸 수 있는 최대 자원의 수를 미리 제안한다.

1) p1에게 먼저 2개를 할당하고 작업을 끝낸다.
2) 반환된 5개의 자원을 p0에게 할당한 뒤 작업을 끝낸다.
3) 마지막으로 반환된 자원들을 p2에게 할당하여 작업을 끝낸다.
4) p2가 끝난 뒤 12개의 자원이 모두 반납된다. 이후 해당 자원들을 순서를 정하여 작업을 진행한다.

• 이러한 sequence가 존재하기 때문에 safe한 상태라고 한다.

n resource types

• Available[m] : system에서 가지고 있는 자원 m개 (할당하고 남아서 가용한 resource 수)

• Max[n, m] = k : n행 process가 m의 위치의 resource를 최대 k개 필요로 한다.

• Allocation[n, m] : n행 process가 현재 할당받은 m의 위치에 있는 resource 개수

• Need[n, m] : Max[n, m] - Allocation[n, m]

• p1에 먼저 할당을 한 뒤 작업을 끝내면 Available = 5, 3, 2

• p3를 만족하기 때문에 할당한 뒤 작업을 끝내면 Available = 7, 4, 3

• p0를 만족하기 때문에 할당한 뒤 작업을 끝내면 Available = 7, 5, 3

• p2를 만족하기 때문에 할당한 뒤 작업을 끝내면 Available = 10, 5, 5

• p4를 마지막으로 작업을 끝내면 최종적으로 Available = 10, 5, 7

• 최종적으로 반납된 상태의 Available = Allocation + 초기 Available

• <p1, p3, p4, p2, p0>의 sequence도 존재한다.

• if p1 = 1, 0, 2 : accept / if p0 = 0, 2, 0 : reject

BANKER’S Algorithm

• Finish[i] = false : 아직 진행하지 않은 상태 / true : 진행 완료된 상태
• Finish가 all true : safe한 상태
• Work : 단계를 진행할 때마다 합쳐진 자원들의 수(잔량)
• 3번 : 현재 need가 work로 해결될 수 있는지 없는지 판단, 만일 못 찾으면 unsafe
• loop에 따라 여러 가지 sequence가 나올 수 있다.(처음으로 돌아가서 loop / 현재 위치부터 다시 loop...)

Deadlock detection & Recovery

Detection

• deadlock이 허용을 하더라고 한번씩 check를 하는 방식
• 매번 할당할 때마다 check를 하는 것이 아닌 한번씩 check를 하도록 한다.
• safe sequence가 존재하지 않으면 deadlock이라고 판단한다.

Recovery

• deadlock이 발생했을 때 process를 종료(kill)한 뒤 남은 자원을 deadlock 상황에 있는 process들에게 할당
• rollback을 할 때는 복원점(가장 최근의 문제가 없던 지점)으로 돌아가서 진행하도록 한다.
• check point : rollback을 하기 위한 복원점
• check point는 계속해서 갱신하는 방식으로 진행하며 가장 최신 위치만 유효하다.
• 고려해야할 점
  • kill했을 때 다른 process에게 줄 수 있는 자원의 수
  • 계산량이 적은 process