데드락(Deadlock, 교착상태)

What?

여러 프로세스가 같은 자원을 기다리며 blocked된 상태.

롸?//지금 충분하게 있는 자원상태 혹은 자원이랑 뱉어낼 애 있는 상태 합,...<-이 시퀀스가 되면  safe하다고 함.

Why? 

상호배제(Mutual exclusion) : 한번에 여러 프로세스가 쓸 수 없는 자원이다

 

2.점유대기 : 자원을 사용중인 프로세스가 자원을 내놓지 않는다

 

3.비선점 : 다른 프로세스로부터 자원을 빼앗을 수 없다

 

4.순환대기 : 프로세스가 순환적으로 자원을 요구한다. 1번 자원을 사용하며 2번 자원을 기다리고, 2번 자원을 사용하며 3번 자원을 기다리고, 3번 자원을  사용하며 1번 자원을 기다리는 세 개의 프로세스.

Solution?

예방-> 데드락 성립조건 4가지중 하나라도 충족되지 않도록  만든다.

 

1.상호배제-> 상호배제 조건을 제거한다

 

2.보유대기->한 프로세스에게 가용 자원을 모두 할당시키고 결국 스스로 내놓게 만듬

Issue->일어나지도 않은 일을 위해 자원들 몰아서 써서 성능이 낮아진다.

 

3.비선점-> 선점 가능한 프로토콜을 만든다. (ex. 프로세스가 cpu 선점 시 상태를 저장해둠)

 

4.순환대기->사이클이 없도록 순서를 정한다.(ex.1번을 획득해야만 2번획득)

 

 

 

 

회피-> 미리 사용할 자원을 모두 정의해둔 것을 바탕으로 데드락을 발생시킬 가능성이 높은 프로세스에게는 자원 할당을 안해준다. 

 

실선은 자원을 사용중이라는 뜻, 점선은 언젠가 한번은 쓸 자원이라는 뜻일 때,

 

점선이 향하는 자원을 p1에게 주면 사이클이 생겨서 데드락이 발생할 것을 알고 자원을 할당해주지 않는다.

or

가용자원에서 최대를 쓸 수 있는 프로세스에게'만' 자원을 줘서 보유대기예방과 같은 효과를 낸다.(은행원 알고리즘)

 

 

 

 

발견->

 

1)자원할당그래프를 그려서 사이클을 찾아본다

그래프에 사이클이 있으면 데드락'일 수도 있다.'

(인스턴스가 하나면 무조건 데드락인데 인스턴스가 두개면..)

 

왼쪽: 데드락이다.

 

오른쪽: 데드락 아니다. 사이클이 있긴하지만 P4가 여분을 쓰다가 반납하면 쓸 수 있는 상황이기 때문이다. 

 

 

 

 

다양한 그래프 종류가 있다..

롸?// 사이클 찾는 시간복잡도? n^2! 간선 다 따라가보면 된느데

간선이 결국 하나에서 모든 곳에 다 뻗쳐도 n-1개기 때문.

 

 

 

 

 

 

 

2)자원할당테이블을 그려서 가용자원들 쌓아서 생각해보고 시퀀스가 가능한지 합쳐나가면서 체크한다.(추천)

 

 

a 7,b 2,c 6개가 있는데 allocation처럼 프로세스들에게 분할이 되어있는 상태이다. 

이 상태에서 p1,p2,p3,p4가 request와 같이 자원을 추가 요청한다.

이때, 가용자원은 없지만 낙관적으로 생각해서, p0같은 경우 반납할거라고 생각한다. 그럼  요청을 받아들이는 시퀀스가 존재하므로 다 만족할 수 있어서 데드락이 아니다 .

 

 

 

 

 

 

하지만 p2가 자원 c를 더 요청한다면 ,

요청한 자원도 만족할 때까지 본인이 가진 자원을 내놓지 않기 때문에 시퀀스가 불가능하고, 데드락이다.

 

 

 

 

 

 

 

 

*데드락은 최대한 낙관적이게 생각해도 데드락인 경우에만 데드락이라 판정한다*

 

 

회복->

1.모두 죽인다.

2.차례로 하나씩 죽여본다.

3.특정 기준으로 하나만 지목하여 죽인다.(Issue:꼭 자원이 적은걸로만 하면 기아현상 될수도..)

4.회복 안하고 무시한다.( 데드락 판별 알고리즘을 코드로 넣는 것 등은 성능을 저하시키므로, 차라리 인간이 직접 처리하는 것이 낫기 때문에 요즘 채택하는 방식이다.)