교착상태 회피하는법

예방을 하면 자원 이용률이 낮아집니다.

 

자원에다가 번호를 붙이고

프로세스가 자원을 요청할 때 점유하고 대기도 할 수 있지만 오름차순으로만 할 수 있게끔 합니다.

 

이러면 왜 순환 대기가 제거가 된 것일까요? 

화살표가 뱅뱅 돌아가는 원 형태가 나오지 않기 때문에 순환 대기가 있을 수가 없습니다.

 

그렇지만 자원을 순서대로 사용하는 것이 어렵습니다.

프로세스가 왔다 갔다 필요할 수 있습니다.

 

ex) 내가 2번이 필요하다 -> 4,6은 놓아버리고 2를 요청합니다.

 

내가 위에꺼를 쓰려면 아래 꺼를 미리 할당받아놔야 합니다.

 

2번입니다.

2번은 회피를 말하는 것입니다.

 

 

교착상태 회피란?

원래 하던 대로 계속하되 할당, 시작이 될 때 교착상태를 회피합니다.

 

2가지 방법

• 프로세스 시작을 거부하는 것
• 자원 할당을 거부하는 것

 

교착상태 회피 - 프로세스 시작 거부

시작할지 말지를 결정할 때 자원을 얼마나 사용할지 체크합니다.

너무 많이 필요로 할 것 같다면 아예 시작을 안 한다.

 

교착상태 회피 - 자원할당 거부

 

 

교착상태회피 - 프로세스 시작 거부 자세히

할 것인가 말 것인가

 

R은 자원의 리소스 개수를 의미합니다.

V은 활용 가능한 개수(놀고 있는 것)입니다.

 

ex)

R1은 3개

R2는 2개

 

V1은 0개(놀고 있는 것이 없음)

V2는 1개

 

ex) R3라는 리소스를 현재 사용 중입니다, 현재 사용 중인 리소스 개수는?

m가지의 리소스가 있습니다.

R3 - V3를 하면 됩니다.

(전체 - 사용중인 것)

 

예시로 M, R, V의 값을 알아봅시다.)

M = 4

 

자원을 가지고 있는 개수

R1 = 1

R2 = 2

R3 = 1

R4 = 3

R=(1,2,1,3)

V = (0,0,0,3)

 

 

C는 무슨 의미일까요?

필요자원수를 claim 하는 것

첫 번째 프로세스가 자원을 몇 개씩 사용할지 주장하는 것입니다.

 

자원의 수가 m개 이기 때문에 claim도 m개가 있어야 합니다.

 

A는 무슨 의미일까요?

할당받은 것입니다.

 

 

 

 

n은 프로세스 수입니다.

즉, 행은 위 그림의 예시로는 3개입니다.

열은 4개입니다.

 

위 그림의 예시로

      0 1 0 0

A = 1 1 0 0

      0 0 1 0

값이 나옵니다.

 

클레임도 적어봅시다.

클레임은 프로세스가 리소스를 요청하는 것입니다.

요청과 할당받은 것 모두 다 적습니다.

      1 1 0 0

C = 1 1 1 0

      0 0 1 0

 

 

A와 C의 특성을 적어봅시다.

Aij <= Cij

Aij는 Cij에 포함됩니다.

 

Cij - Aij

를 하면 요청하는 것이 나옵니다.

 

V < R 

이면 리소스 개수가 할당받은 것보다는 큽니다.

 

이러한 것들로 어떻게 시작 거부를 할 수 있을 까요?

지금 까지 클레임, (j 가 고정되어 있을 때 적용됨)

리소스에 대한 모든 클레임과 새로 들어온 클레임들이 

리소스 개수보다 작아야 합니다.

j = 자원

 

리소스 갯수보다 더 많은 클레임이 생기면 안 됩니다.

 

즉, R2는 C의 2열 의 상태를 봐야 합니다.

R2가 같거나 커야 합니다.

 

 

 

 

교착상태 회피 - 자원 할당 거부 자세히

리소스당 자원이 한 개(점이 없는 경우) 일 경우 자원 할당 그래프로 해결할 수 있습니다.

왼쪽은 세이프 항태, 오른쪽은 세이프 하지 않은 상태

리소스당 자원이 하나인 것을 봐봅시다.

클레임까지 점선으로 그려놨습니다.

클레임은 요청, 할당은 그려놓지만 처음에 클레임을 하는 것입니다.

 

정리하면 

자원 할당 그래프에는 3가지의 화살표가 있습니다.

요청, 할당, 클레임(향후 필요량)

 

 

교착상태가 걸릴 수 도 있는 오른쪽 그림을 unsafe 상태라고 부릅니다.(교착상태가 될 수도 안될 수도 있는 상태)

예를 봅시다.

만약 P2가 R2를 할당받았다면 오른쪽 그림으로 바뀝니다.

그러면 현재는 교착상태는 아닙니다.

 

교착상태가 생길 거 같으면(= 사이클이 만들어질 거 같으면)

하지만 클레임은 점선입니다.(교착상태가 될 수도 있다는 뜻)

 

즉, unsafe이면 자원 요청을 거절합니다.

 

 

은행가 알고리즘 

하나의 리소스만 생각해봅시다.

 

사용 가능한 자원 수 - V에 해당하는 것

프로세스의 최대 요청 자원 수 - C에 해당하는 것

점유 자원 수  - A에 해당하는 것

 

안전 상태  - 자원 할당 순서가 한 가지라도 존재

불안전 상태 - 교착상태가 될 수도 있는 상태

 

 

단순하게 봅시다.

 

• 요청하면
• 일단 할당해봐
• 결과를 safe 했는지 아닌지 구분해
• 안전하면 할당

3번 같습니다 왜냐하면 알고리즘으로 돌리기 때문에 자원의 수에 따지지 않습니다.

 

 

은행가 알고리즘의 아이디어

은행은 총 100달러가 있습니다.

"150 달려 빌려줘"

은행은 "80달러 빌려주고 20달러 남음"

이 때는 문제가 없습니다. 왜냐하면

10 달러 빌려주고 -> 20달러 빌려주고 -> 40달러 빌려주면 됩니다.

 

여기서 프로세스는 "사람"들입니다.

사용 가능한 자원은 "은행"입니다.

남아 있는 금액들은 "추후 필요량"입니다.

 

즉, 추후 필요량을 계속 줘야 합니다.

 

근데 5달러밖에 안 남았지만 맨 처음 사람의 사업이 망해서 35달러를 다시 줄 수 도 있습니다.

그렇게 교착상태가 안 걸릴 수 있습니다.

 

클레임 - 최대 사용량