교착상태 자세히 보기

네트워크에서 발생하는 교착 상태

N1이 보내야 하고

N2는 N1으로 보내야 하는데

 

입력 버퍼가 꽉 차 있는 것입니다.

(N2의 입력 버퍼가 N3, N4에서 온 것이 꽉 차 있는 것입니다.)

 

Thread_one은 mutex2개를 차지해야 합니다.

thread_two는 first_mustex를 차지해야 합니다.

 

아닙니다. thread들은 2개의 뮤 택스를 둘 개 다 차지해야 합니다.

 

thead_one이 second_mutex를 차지하려고 하고 

thread_two가 first_mutex를 차지하려고 하는 시간이 딱 맞아떨어지면 교착상태가 발생합니다.

 

교착상태의 필요조건

P이면 q가 될 수 있지만

q이면 p가 될 수 없습니다.

 

1. 상호 배재

2. 점유와 대기

여기에 뭐가 점유와 대기가 있다는 거예요?

서로 점유하려고 뺏는 형태입니다.

 

3. 비선점(다른 것을 뺏지 못하는 성질)

비선점 조건은 뭐가 있을까요?

Q가 프린터를 점유하고 있다면 dvd드라이브가 함부로 뺐을 수 없습니다.

 

 

4. 순환 대기

차지하고 있고 대기하고 있는 형태가 마치 원처럼 되어있습니다.

 

 

예시로 알아보자!

1. 상호 배재

입력 큐가 상호 배재입니다.

 

2. 점유와 대기 

N2의 입력큐가 점유를 당했고

N1의 입력큐가 비어있어야 갈 수 있으니 대기를 합니다.

 

3. 비선점

N2가 N1의 입력큐를 강제로 비워낼 수 없습니다.

 

4. 순환 대기

다른 노드들이 점유하고 있는 모습들이 순환 형태입니다.

 

예시로 알아보자!

1. 상호배재

first_mutex, second_mutex

는 한 번에 하나의 자원만이 존재합니다.

 

2. 점유와 대기 

first_mutex는 thead_one이 점유하고 있고 

second_mutex를 차지하기 위해 대기하고 있습니다.

 

second_mutex는 thead_two이 점유 하고 있고

first_mutex를 차지하기 위해 대기하고 있습니다.

 

3. 비선점

first_mutex는 thead_one이 점유하고 있으니 thread_two가 뺏지를 못하고 있습니다.

 

4. 순환 대기

thread_one, thread_two가 동시에 요청을 하면 순환을 하고 있습니다.

 

2번입니다.

점유하지 않은 상태에서만 <<- 규칙을 정하는 것입니다.

모든 자원을 다 차지함 <<- 대기가 없는 것입니다.

그것이 발생하면 교착상태이다.

교착상태가 발생하면 그것이다.

 

2번입니다. 순환 대기

 

 

교착상태의 표현

프로세스 - 동그라미

자원 - 네모

 

그래프를 해석해 봅시다.

공유자원 R1,2입니다.

P2가 R2를 점유하고 있습니다.

P1이 R1을 점유하고 있습니다.

 

P2가 R1을 차지하려고 대기합니다.

p1이 R2를 차지하려고 대기합니다.

 

 

자원에 대한 요청을 하는 것입니다.

화실 표가 박스까지만 있습니다.

 

왜 화살표가 점에 안 붙어 있고 박스에만 붙어있나요?

요청을 하는 것이기 때문입니다.

 

여기에 교착상태가 있나요?

없습니다.

만약 P1이 영원히 기다리지 않아도 될까요? 

P3가 R3의 점유를 끊내면 됩니다.

 

 

왼쪽부터 합시다.

왼쪽은 사이클이 있습니다.

 

왼쪽은 교착상태인가요? 

아닙니다.

P2가 R2의 자원을 끊으면 P1이 R1의 점유를 끊내고 R2에 들어가기 때문에 

 

P1은 P3가 R2를 끊내야지 됩니다. 그걸 P1이 들어가야 합니다.

 

즉, P3 -> P1 -> P2로 순서로 끊네야 만 교착상태가 일어나지 않습니다.

순서가 없다면 교착상태가 있을 것입니다.

 

끝내는 순서가 있다면 -> 교착상태가 없습니다.

 

오른쪽을 봅시다.

 

사이클이 있습니다. y

교착상태인가요? n

P2, P4 둘 중 하나만 먼저 끝나면 됩니다.

 

사이클이 있나요? n 

교착상태인가요? n 

 

사이클이 없다면 교착상태가 아예 없습니다.

 

사이클이 있나요? y

교착상태 인가요? y

 

끝낼 수 있는 순서가 없습니다.

프로세스 3개인데

누구라도 먼저 끝낼 수 있는 게 있어야 합니다.

 

사이클은 교착상태의 필요조건입니다.

 

 

사이클이 없다면 -> 교착상태 없음

 

사이클이 있다면

자원 안에 자원이 1개 있다면 바로 교착상태

자원안에 자원이 2개 있다면 교착상태 "있을 수도 있음"

 

사이클이 있는가? y

사이클이 있다면 반드시 교착상태 인가? n (가능성이 있음)

 

자원 할당 가능 순서가 존재하는가? y  P1 -> P2

 

자원할당 가능 순서가 왜 중요한가? 존재하면 교착상태가 필요 없음

 

프로세스 P2에게 먼저 할당(P2를 먼저 끝내보려는 것)하면 어떻게 되는가? n

자원 해재하고 R2를 바로 차지하려고 하면 교착상태가 발생합니다.

 

프로세스 P1에게 먼저 할당(P1를 먼저 끝내보려는 것)하면 어떻게 되는가? y

 

교착상태 인가? n

 

사이클이 있는가? y

 

자원 할당 가능 순서가 존재하는가? y  

끝내는 순서입니다.

P4 -> P2

-> P3

-> P1

 

교착상태 인가? n

 

사이클이 없으니 교착상태가 없다.

자원 할당 가능 순서

P3 -> P2 -> P1

 

사이클이 있습니다.

교착상태입니다.(자원이 하나밖에 없는 애들은 사이클이 있다면 교착상태입니다.)

P0를 끝내면 R6이 노는데 이때 P1, P4가 누가 들어가야 하는지 모릅니다.

 

 

교착상태의 해결방법

예방, 회피 -> 교착상태에 들어가지 않습니다.

탐지 후 회복 -> 교착상태 생기면 회복합니다.

 

가장 좋은 방법은 -> 무시(타조 알고리즘)

타조가 무서운 걸 만나면 바닥에 머리를 박아버리기 때문입니다.

 

4가지 중에 하나를 원천 봉쇄합니다.

하밴더스 알고리즘으로 방어합니다.

 

상호 배제 -> 실직적으로 사용하기 어렵습니다.

ex) 프린터에 상호 배제 안 하면 프린터에 많은 입력이 들어갈 것입니다.

 

점유와 대기가 일어나지 않게 하기 

자원을 한꺼번에 요청, 점유, 해제하는 것입니다.

 

대화식 -> 결과보고 입력하고, 결과보고 입력하는 방식입니다.

 

당장 이용해야 하는 자원을 차지하기 때문에 자원 이용률이 낮아집니다.

 

비선점 조건 제거- 일반적으로 쓰고 있는 자원을 뺏기 어렵습니다.

 

뺏기 쉬운 것을 뺏는대 프로세스를 뺏습니다.

 

선점 방법을 다르게 할 수도 있습니다.

점유 자원을 요청할 때 거부되면 대기표를 뽑는 것입니다.