[ 운영체제 ] Deadlock

 

1. DeadLock 이란?

두 개이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리는 상태를 "교착상태(=Deadlock)이라고 한다.

 

예시) A라는 사람은 1번을 사용 중이고, B라는 사람은 2번을 사용 중이다.

각 사람은 자신의 물건을 사용 한 후에 A는 2번, B번은 1번을 사용하고자 하는데 서로 사용이 끝나기를 기다리고 있는 상태가 지속되면서 결과적으로는 A,B는 1,2번을 사용 중인 상태로 대기하게 되면서 자원의 공유가 불가해진다.

 

*Race Condition => 하나의 코드 영역의 2개 이상의 쓰레드가 동시에 접근 하는 경우, 예상하지 못하는 결과 값을 얻는 상황을 말한다.

반면, 데드락은 각각 다른 프로세스를 점유하면서 다른 프로세스를 기다리는 상태를 의미한다 : 헷갈리지 X!

 

1-1 ) 데드락의 시스템 모델

[1] 용어

Resource Types : R1 ~ Rn 이라고 칭한다 [ CPU cycle, Memory , I/O devices]

Instance : 각각의 자원은 인스턴스를 가진다.

 

[2]프로세스의 자원 사용 방법

1 Request : 어떤 자원을 요청했지만 즉시 얻을 수 없는 경우, 할당 될 때 까지 대기한다.

2. Use : 자원을 얻은 프로세스는 수행한다.

3. Release : 일을 마친 프로세스는 자원을 놓아준다.

 

1-1) 데드락의 필수 조건

* 하단의 4가지 조건이 모두 만족이 되어야, 데드락이 발생된다.

 

[1] 상호배제

하나의 쓰레드가 어떤 자원을 사용하고 있다면, 다른 쓰레드는 요청을 하고 반납이 될 때까지 대기해야한다.

 

[2] Hold & Wait

쓰레드는 반드시 적어도 1개의 자원을 가지고 있어야 하며, 추가적인 자원을 얻기 위해서는 다른 쓰레드의 사용이 끝나길 대기해야한다.

 

[3] 비선점

사용중인 자원은 중간에 빼앗아 갈 수 없다.

 

[4] Circular waiting

P1 -> P2 -> P3 -> P4 -> P1

대표사진 삭제

사진 설명을 입력하세요.

P0는 반드시 P1이 가지고 있는 자원 할당 받기위해 대기 해야한다.

 

2) Resource Allocation Graph ( 자원 할당 그래프 )

데드락은 자원 할당 그래프를 통해 쉽게 설명이 가능하다.

P는 프로세스, R은 시스템 내의 자원의 유형, R 내부에 존재하는 원은 인스턴스를 나타낸다.

 

대표사진 삭제

Cycle이 존재한다면, 데드락일수도 아닐 수도 있다!

그렇다면, 어떤 Cycle의 경우 데드락이 발생하는가? => 하나의 인스턴스에 사이클이 도는 경우는 데드락이다.

 

하지만, 위의 예시는 R2의 인스턴스를 P1,P2에게 할당하고도 P3가 접근을 하였으니 데드락 상태가 발생된다.

 

 

3-1) 교착상태 예방 [ DeadLock Prevention ]

데드락을 위한 4가지 조건 중 한가지 이상을 충족하지 못하게 하는 것이 목적.

 

3-1-1) 상호 배제 (Mutual Exclusion)

프린터와 같은 비공유 자원은 상호배제가 불가능한 경우가 있기에 상호배제를 막아서 해결한다는 접근은 옳지 않다.

 

3-1-2 )Hold & Wait

프로세스가 요청할때는 어떠한 프로세스가 그 자원을 사용하지 않는 상태여야한다. [ = All or Nothing ]

처리는 가능하지만, 성능이 저하되고 Starvation 발생이 가능하다.

 

3-1-3 ) 비선점 [ No preemption ]

선점을 가능하게 한다면, 데드락 상태를 벗어나기는 쉽지만

자원을 뺏긴 프로세스는 현재까지의 작업이 무효화 되고, 다시 작업을 시작하려면 Old + New resource를 모두 할당 받아야 하기 때문에 Starvation 현상이 발생 할 수 있다.

 

3-1-4 ) 순환 대기 [ Circular Wait ]

모든 자원에 번호를 부여함으로써, 오름차순으로 자원을 요구한다면 데드락은 발생하지 않는다.

=> 하지만, 굉장히 복잡한 절차가 반영이 되어야한다.

 

궁극적으로, 데드락을 완전히 예방하는 것은 능력을 저하시키기 때문에 대부분의 운영체제는 회피 전략을 선택!

 

3-2) 교착상태 회피 [ Deadlock Avoidance ]

1) Safe Sequence or 2)Resource Allocation 을 꾸준히 검색함으로써, 일어날 가능성을 확인하는 경우 "회피"시키는 것을 의미한다.

 

3-2-1 ) Safe & UnSafe States

사진 삭제

사진 설명을 입력하세요.

 

3-2-2 ) by Resource Allocation Graph [ R have one instance ]

사진 삭제

---> : 미래에 사용 할 자원 (Claim Eage)

자원 요청에 다라 Claim - > Assignment Edge로 변경 ( ㅡ> )

3-2-2 ) by Resource Allocation Graph [ R have multiple instances ]

MAX : 한 프로세스의 최대 요구량

Allocation :프로세스에게 이미 할당된 양

Need : MAX - Allocation

사진 삭제

사진 설명을 입력하세요.

사진 삭제

순서구하기 : 이용가능한 양 > 필요한 양

 

P1 : 2 3 0 > 0 2 0 => 처리 가능 + 이후 반납받기

 

3-2-3 ) Safe Sequence

만약 한 프로세스가 자원을 요청하는 경우, 안전한 상태에 있다라는 것을 Safe Sequence 안에 모든 프로세스들이 있는지의 여부를 통해 확인한다.

 

Safe Sequence란?

프로세스들이 현재 할당 받은 자원과 추후 할당받을 자원이 무엇인지 확인하고, 순차로 실행을 했을 경우 데드락이 발생하지 않고 ( => not circle ) 모든 프로세스를 처리해줄 수 있는 순서를 의미한다.

다양한 순서 중, 하나의 안전 순서만 존재하더라도 "안전한 상태"에 있다고 표현 할 수 있다.

 

 

4. DeadLock Detection

알고리즘을 통해 데드락의 유무를 확인하고, 복구 하는 역할을 수행한다.

 

[1] Resource Allocation ( Single Instance )

 

사진 삭제

사진 설명을 입력하세요.

[2] Detection Algorithm ( Multiple Instance, 뱅커 알고리즘과 유사 )

 

[2-1] 자원 할당 그래프를 통해 Wait for 그래프를 도출한다.

자원의 상태는 이용가능, 할당, 요청, work ,finish 상태로 나뉜다.

 

알고리즘 진행 절차

1단계 : Allocation != 0 & Finish = False; otherwise Finish[i] = True

프로세스에 할당된 자원 X , Hold & Wait 규칙 준수

=> 프로세스가 없는 경우 Finish -> True로 전환하여 추가적인 검사를 하지 않도록 한다.

=> 프로세스가 있는 경우 Finish -> False로 전호나하여 검사 진행을 위해 2단계로 진입한다.

 

2단계 , 3단계 => Banker's Algorithm과 같다.

 

4단계

Finish[i] = false인 프로세스가 존재한다면, 데드락이 존재하지 않는 프로세스로 판명.

 

사진 삭제

뱅커 알고리즘의 need와 탐색 알고리즘의 request는 유사하다.

단, need는 현재 요청되지 않더라도 궁극적으로 사용되어야 할 양이고, Request는 당장 필요한 특정 자원의 수를 의미한다.

 

[2-2] Detection Algorithm 예시

사진 삭제

사진 설명을 입력하세요.

P0 -> P2 -> P3 -> P1 -> P4 [ 자원 할당 및 반납을 통해 Safe Sequence 형성 가능 ]

: 이용가능한 자원 & 요구 자원을 비교함으로써 데드락 가능성을 탐색

단, P2에 Request가 하나라도 존재한다면, P0를 제외한 어떠한 프로세스의 요구도 충족 할 수 X => DeakLock

 

5. 교착상태 회복 ( Deadlock Recovery )

1. 현재 상태에서 모든 프로세스 종료

2. 데드락에 빠져있는 프로세스를 순차적으로 종료