교착상태(deadlock)
서로 가진 자원을 내놓지 않고 원하기만 하는 상태.
Deadlock
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
Resource(자원)
- 하드웨어, 소프트웨어 등을 포함하는 개념
- ex) 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 semaphores A and B
한 프로세스가 A를 획득하고 B를 획득하고 싶은 상황에서 CPU빼앗기고,
다른 프로세스는 B를 획득하고 A를 획득하고 싶은 상황에서 무한으로 기다릴 때
Deadlock 발생의 4가지 조건
-
Mutual exclusion | 상호배제
매 순간 하나의 프로세스만이 자원을 사용할 수 있음
-
No preemption | 비선점
프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
-
Hold and wait | 보유대기
자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
-
Circular wait | 순환대기
자원을 기다리는 프로세스간에 사이클이 형성되어야 함
프로세스 P0, P1, .., Pn이 있을 때
P0은 P1이 가진 자원을 기다림
P1은 P2가 가진 자원을 기다림
Pn-1은 Pn이 가진 자원을 기다림
Pn은 P0이 가진 자원을 기다림
자원할당 그래프 Res
ource-Allocation Graph
데드락이 발생했는지 알아보기 위해 사용
동글 → 프로세스, 네모 → 자원, 네모 안의 동글은 자원의 인스턴스 개수임
자원에서 프로세스 가는 화살표는 그 프로세스가 자원을 가지고 있음을 말함
프로세스에서 자원으로 가는 화살표는 프로세스가 그 자원을 요청함을 말함 얻진 못한 상태.
데드락인지 아닌지 어떻게 알까?
- 그래프에 cycle이 없으면 deadlock이 아니다. (왼 →사이클 2개 , 오 → 사이클 1개)
- 그래프에 cycle이 있으면
- if only one instance per resource type, then deadlock 만약 자원당 인스턴스가 하나밖에 없으면 데드락이다.
- if several instances per resource type, possibility of deadlock 만약 인스턴스가 여러개라면 데드락일 수도 있고, 아닐 수도 있다.
왼쪽같은 경우는 데드락이다. 오른쪽의 예제는 사이클이 있긴 하지만 데드락이 아니다.
P2와 P4가 자원을 반납 하면 P3과 P1이 자원을 사용할수있기 때문이다.
Deadlock의 처리 방법
1,2는 데드락이 생기지 않게 미연에 방지
-
Deadlock Prevention
자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
-
Deadlock Avoidance
자원 요청에 대한 부가적인 정보를 이용해서 Deadlock의 가능성이 없는 경우에만 자원을 할당
시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
-
Deadlock Detection and recovery
Deadlock 발생은 허용하되 그에대한 detection 루틴을 두어 deadlock 발견 시 recover
-
Deadlock Ignorance (현대의 운영체제가 채택)
Deadlock을 시스템이 책임지지 않음
Unix를 포함한 대부분의 OS가 채택
사람이 알아서 프로세스를 죽이든지.. 처리함
데드락은 자주 발생하는 일이 아니라 1,2번처럼 오버헤드를 발생하면서 데드락을 방지한다면 비효율적이다.
1. Deadlock Prevention
자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
-
Mutual Exclusion : 자원을 배타적으로 써야 함
- 이 조건은 배제할 수 있는 조건은 아니다.
- 공유해서는 안되는 자원의 경우 반드시 성립해야 함
-
Hold and Wait
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
- 해결 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 : 모든것을 hold하고 시작하기 때문에 wait가 필요 없음. 매 시점마다 필요로 하는 자원이 다를텐데, 미리 다 받아놓고 있으면 자원에 대한 비효율성이 생길 수 있음.
- 해결 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청 :
무언갈 hold하고 있는데 다른 자원을 기다려야 하면, 이미 hold한 자원을 뱉어놓고 요청.
-
No Preemption
- CPU 같은 자원은 타이머와 같이 preemtion(빼앗아오기)를 할 수 있었다. 그럴 때 데드락은 생기지 않았다.
- process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
- State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)
-
Circular Wait 막기
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
- 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서 1인 자원 Rj을 할당받기 위해서는 우선 Ri를 release해야 한다.
→ Utilization 이용률 저하, throughput 성능 감소, starvation 문제
→ 비효율적이다.
2. Deadlock Avoidance
자원 요청에 대한 부가적인 정보를 이용해서 Deadlock의 가능성이 없는 경우에만 자원을 할당
시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
-
프로세스가 시작될때, 이 프로세스가 평생을 쓸 자원의 최대량을 알고 있다고 가정하고, 데드락을 피해가는 방법. 평생 쓸 자원을 미리 알고있기 때문에, 어떤 프로세스가 자원을 요청했을 때, 이 자원을 주면 데드락이 발생할 가능성이 있겠다 싶으면 자원을 주지 않는 것.
-
자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당
-
가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임
-
safe state
- 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
-
safe sequence
- 프로세스의 sequence <P1,P2,...,Pn>이 safe 하려면 Pi(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 (자원당 인스턴스 1개)
→ Resource Allocation Glaph algorithm (자원 할당 그래프) 사용
자원 → 프로세스 : 자원이 이 프로세스에 할당되어있음
프로세스 → 자원 : 프로세스가 자원을 요청했는데 할당받진 못한 상태
점선 화살표 : 프로세스 ...> 자원 : 이 프로세스가 평생에 한번은 이 자원을 사용할 일이 있다.(1) 만약 프로세스 2번이 지금 R2 자원을 요청하게 되면 점선 화살표가 실선 화살표로 바뀌는 것.
(2) 2번 자원은 아무도 가지고 있지 않기 때문에 요청한 프로세스 P2에게 줄 수 있음.
(3) 마지막 그림은 프로세스1번이 R1을 가지고 있고, P2가 R2를 가지고 있음.
(4) 이 상황은 데드락이 아니다. 1번 프로세스가 평생에 한번 R2를 요청할 수는 있지만, 지금 당장은 자원을 가진 형태가 아님. 그치만 이 순간에 데드락의 가능성이 있음. 그렇기 때문에 두번째 그림 상태로 냅두는 것.
(5) 따라서 점선을 포함해서 싸이클이 형성된다면 자원을 주지 않음. 이 방식이 어보이던스 방식이다.
- Multiple instances per resource types (자원당 인스턴스 여러개)
→ Banker’s Algorithm 사용
프로세스가 5개가 있고, 자원이 3종류가 있다. 각 종류별로 인스턴스가 A는 10개, B는 5개, C는 7개가 있음.
평생 사용할 자원을 표시해놓음 Max에
2번 프로세스는 내 평생의 자원을 A를 9개, C를 2개 쓴다는 것.전체 자원 인스턴스에서 할당된 자원을 빼면 가용자원 Avaliable 3,3,2,가 되는 것
남아있는 자원은 줄 수 있지만, 문제가 생길 수 있으면 자원이 남아있더라도 주지 않는 것.
Need 는 추가로 요청할 수 있는 양.
이 상태에서 프로세스 1번이 (1,2,2)의 자원을 요청한다면?
→ 그럼 a1, c2는 a3,c2가 남아있기 때문에 줄 수 있을 것이다. 하지만 그냥 주는 것이 아니라, 프로세스 1번이 추가 요청할 수 있는 양이 가용 자원을 가지고 모두 충족이 가능한지를 봄. 앞으로 추가 요청 해봐야 1,2,2 이므로, 가용 자원에서 해결 가능함.
그래서 요청하면 그냥 준다. 줘도 데드락으로부터 안전한 것.
만약 p4가 b2개를 요청한다면? → 하지만 추가 요청 가능 한 것이 남아있는 자원으로 모두 충족이 안된다. 그럼 줄 자원이 있지만, 주지 않음.
p0이 반환하면 자원이 쌓이고, 그것이 다시 가용자원이 된다. 그렇게 되면 <프로세스 1,3,4,2,0> 순서대로 할 수 있다. 이 상태는 safe state가 된다. 이러한 요청에 대해서만 받아들인다.
하지만 대단히 비효율적이다. 자원이 남는데도 혹시 몰라 주지 않으니까. 사실은 데드락은 별로 안생긴다.
3. Deadlock Detection and recovery
Deadlock 발생은 허용하되 그에대한 detection 루틴을 두어 deadlock 발견 시 recover
- Resource type 당 single instance인 경우
- 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미
자원 할당 그래프를 좀 더 간결하게 그린다면 오른쪽처럼 (wait for graph). 자원을 빼버리고 프로세스들끼리만 화살표로 이어짐. p4는 p1이 가진 자원을 가지고 있다.
이 상태는 데드락인 상황임.Wait-for 알고리즘
Resource type 당 single instance인 경우- Wait-for graph
- 자원할당 그래프의 변형
- 프로세스만으로 node 구성
- Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk→Pj
- Algorithm
- Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
- O(n^2) : 프로세스가 n개 있다고 할때 사이클을 찾는 오버헤드. 사이클이 있는지 알아볼려면 점이 n개 있으면 화살표는 n-1개 있을 수 있음. 그래서 n(n-1)
- 깊이우선탐색(DFS) 또는 너비우선탐색(BFS)를 해보면 싸이클이 있는지를 찾을 수 있다.
- Wait-for graph
- Resource type 당 multiple instance인 경우
-Banker’s algorithm과 유사한 방법 활용
데드락 디텍션은 자원을 요청하면 다 줌.
p0,p2,p4,p1,p4로 하면된다.
데드락인지 아닌지 어떻게 아냐?
낙관적으로 보고, 현재 요청하지 않은 프로세스는 자원을 반납할 것이라고 가정한다. 요청하지 않은 p0의 자원 b1, p2의 자원 a3,c3을 반납 할 것이라고 생각하고 다 쌓아서, 자원을 순차적으로 주는 것.
만약 여기서 p2가 자원 c를 하나 더 요청한다면?
그럼 자원 요청 안한 프로세스는 p0밖에 없음. 그래서 줄 수 있는 자원이 0,1,0이기 때문에, 어느 요청도 받아들일 수 없음.
이런 상황이 데드락이다!
→ 가용 자원이 몇개 있는지 보고, 가용 자원으로 처리 가능한지 본다. 요청하지 않은 프로세스들의 자원을 가용 자원에 합쳐 놓는다. 그리고 끝까지 줄 수 있는지 본다.
이렇게 데드락이 발견되면 Recovery를 해야한다.
데드락에 연루된 프로세스를 사살.
사살 방법
1. Process termination : 프로세스 종료시키기
- Abort all deadlocked processes : 데드락에 연루된 프로세스를 한꺼번에 죽임
- Abortn one process at a time until the deadlock cycle is eliminated : 데드락에 연루된 프로세스를 하나씩 죽여봄. 데드락이 없어질 때 까지
- Resource Preemption : 자원 뺏기
- 비용을 최소화할 victim의 선점
- safe state로 rollback하여 process를 restart
- Starvation 문제 : 데드락을 없앴는데도 똑같은 패턴이 또 생길 수 있다. 비용을 최소화할 자원을 계속 고른다면, 똑같은 것으로 선정될 수 있다.
- 동일한 프로세스가 계속해서 victim으로 선정되는 경우
- cost factor에 rollback 횟수도 같이 고려
4. Deadlock ignorance (현대의 운영체제가 선택)
Deadlock을 시스템이 책임지지 않음
Unix를 포함한 대부분의 OS가 채택
사람이 알아서 프로세스를 죽이든지.. 처리함
데드락은 자주 발생하는 일이 아니라 1,2번처럼 오버헤드를 발생하면서 데드락을 방지한다면 비효율적이다.
- Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
- Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
- 만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처
- UNIX, Windows 등 대부분의 범용 OS가 채택
