Deadlock Detection - Banker’s 알고리즘에서 safe state 판단 방식

[guswns3371]

@LEEHYUNDONG @minseongkim97 @annie1004619

OS : Deadlock Detection

프로세스	Request	Allocation + Avaliable	state
P0	(0, 0, 0)		safe
P1	(2, 0, 2)		safe
P2	(0, 0, 0)		safe
P3	(1, 0, 0)		safe
P4	(0, 0, 2)		safe

Deadlock Detection의 Banker’s 알고리즘에서 safe state을 판단하는 과정을 모르겠습니다..

알려주세요! 스터디원!

[LEEHYUNDONG]

@guswns3371
안녕하세요. 현준님 오늘 만나긴 하지만? 글을 보게되어 제가 이해한 것을 토대로 한 번 떠들어 보겠슴다!

정보

• 5 processes :P0, P1, P2, P3, P4
• 3 resource types : A(7), B(2), C(6)

detection의 경우 ! 제가 이해한 포인트는

1. allocation의 크기와 request를 참고하여 available한 자원 파악
2. deadlock을 유발하지 않는 순서쌍이 존재하는지 파악

그러면 적어놓으신 표를 보고 하나씩 살펴보면
우선 available이 (0, 0, 0)입니다.
request에 (0, 0, 0)인 프로세스가 없으면 무조건 데드락 상태를 유발합니다.
하지만 프로세스 P0, P2는 request가 (0, 0, 0)이네요 그럼 순서를 P0 -> P2 or P2 -> P0로 해볼 수 있습니다.
그럼 자원을 P0, P2를 모두 수행하고 반환된 자원들로 인하여 available 상태는 (3, 1, 3)이 됩니다.
이후에 가용자원(available) (3, 1, 3) 보다 작은 쌍을 가지고 있는 프로세스는 P3가 있습니다. P1도 있구요.

이런식으로 찾아가다보면 <P2, P0, P3, P1, P4> 의 순서로 자원을 할당하면 deadlock이 발생하지 않을 거같아요.
그래서 detection은 safe한 seq를 보장하는 프로세스를 detect하면서 deadlock의 발생을 막는거 같습니다!!

글을 너무 빠르게 적어서 뭔가 두서 없지만 제가 이해한 것은 여기까지 입니다!
이따가 봬요 👍

[guswns3371]

아 여러가지 프로세스 sequence가 존재하는데 그 중 deadlock이 발생하지 않는 safe sequence가 <P2, P0, P3, P1, P4> 이거군요!!

추가 질문

Q) 저는 특정 프로세스에게 자원을 할당해줄 때 판단하는 기준이 해당 프로세스의 request < 시스템 내의 Available + 나머지 프로세스들의 보유 자원이라고 이해했는데 맞나요...?

만약 P1에게 자원을 할당해주려고 하면, P1의 request (2, 0, 2) < Available (0, 0, 0) + 나머지 프로세스들의 보유자원 (5, 2, 6)이라서 되는줄 알았어요. 하지만 논리적으로 Available이 (0, 0, 0)이니까 자원할당이 불가능하네요.....

Q) 아래서 available한 자원의 의미가 특정 프로세스에게 자원을 할당해줄 때 판단 기준으로 사용되는 "보유 자원"을 뜻하는 건가요?

1. allocation의 크기와 request를 참고하여 available한 자원 파악

Q) 아래서 말하는 쌍 은 Allocation인가요 Request인가요?

이후에 가용자원(available) (3, 1, 3) 보다 작은 쌍을 가지고 있는 프로세스는 P3가 있습니다. P1도 있구요.

Q) 만약 P0의 allocation이 (0, 1, 0)이고 request가 (0, 1, 0)이라면

프로세스	Allocation	Request
P0	(0, 1, 0)	(0, 1, 0)
P1	(2, 0, 0)	(2, 0, 2)
P2	(3, 0, 3)	(0, 0, 0)
P3	(2, 1, 1)	(1, 0, 0)
P4	(0 ,0 ,2)	(0, 0, 2)

프로세스 할당 순서	시스템 속 가용 자원
P2이 반납	0 0 0 + 3 0 3(P2가 반납) -> 3 0 3
P3에게 할당	3 0 3 - 1 0 0(P3에게 할당) -> 2 0 3
P1에게 할당	2 0 3 - 2 0 2(P1에게 할당) -> 0 0 1
P3나 P1이 반납할 때까지 대기
P3가 반납	0 0 1 + 3 1 1(P3가 반납) -> 3 1 2
P1이 반납	3 1 2 + 4 0 2(P1이 반납) -> 7 1 4
P4에게 할당	7 1 4 - 0 0 2(P4에게 할당) -> 7 1 2
P0에게 할당	7 1 2 - 0 1 0(P0에게 할당) -> 7 0 0
P4가 반납	7 0 0 + 0 0 4(P4가 반납) -> 7 0 4
P0가 반납	7 0 4 + 0 2 0(P0가 반납) -> 7 2 4

인건가요?
어? 뭔가 잘못됐는데

Q) 프로세스가 자원을 할당받을 때 보유 자원을 모두 반납하고 할당 받는건가요?

어렵네요

[guswns3371]

스터디에서 실시간으로 설명해주시는게 더 좋을것 같아요 ㅋㅋㅋㅋ

[LEEHYUNDONG]

Q) 저는 특정 프로세스에게 자원을 할당해줄 때 판단하는 기준이 해당 프로세스의 request < 시스템 내의 Available + 나머지 프로세스들의 보유 자원이라고 이해했는데 맞나요...?

제 생각에는 deadlock avoidance가 약간 질문에서 말씀하시는거랑 비슷한거 같은데, detection에서는 최대 가용 자원을 합해서 계산 하는게 아닌 현재 시점에서의 가용자원만 보는거 같아요

Q) 아래서 available한 자원의 의미가 특정 프로세스에게 자원을 할당해줄 때 판단 기준으로 사용되는 "보유 자원"을 뜻하는 건가요?

네. available만 보는 거로 알고 있습니다. allocation은 이미 할당 된 자원이고 request는 현재 시점에서 프로세스가 요청하는 자원이기 때문에 돌려받는 자원(=allocation)과 available로 남은 순서를 찾는 방식인거 같습니다.

Q) 아래서 말하는 쌍 은 Allocation인가요 Request인가요?

위에 답변에서 말한 것 처럼 allocation은 이미 시스템에서 특정 프로세스에 할당한 자원이기 때문에 request만 보면 되는거 같아요!

Q) 만약 P0의 allocation이 (0, 1, 0)이고 request가 (0, 1, 0)이라면

위에 답변을 보시면 이부분은 해결될거 같아요. 가용자원이 초기 (0, 0, 0)이면 애초에 P0 request = (0, 1,0)이기 때문에 할당이 불가하고 P2부터 수행한 뒤에 (3, 0, 3)을 돌려 받아서 가용자원이 (0, 0, 0)+(3, 0, 3) = (3, 0, 3)이 되는거 같습니다.

Q) 프로세스가 자원을 할당받을 때 보유 자원을 모두 반납하고 할당 받는건가요?

• Available (0, 0, 0)
  프로세스 | Allocation | Request
  -- | -- | --
  P0 | (0, 1, 0) | (0, 1, 0)
  P1 | (2, 0, 0) | (2, 0, 2)
  P2 | (3, 0, 3) | (0, 0, 0)
  P3 | (2, 1, 1) | (1, 0, 0)
  P4 | (0 ,0 ,2) | (0, 0, 2)

이걸 보면 현재 available (0, 0, 0)이기 때문에 request 중에서 request만 응할 수 있습니다. 그래서 P2가 끝나고 available = 원래상태 (0, 0, 0) + P2가 반납한 자원(3, 0, 3) = (3, 0, 3)
이제 available (3, 0, 3)으로 P0를 제외하고 아무 순서로 request 전부다 받을 수 있게 됩니다!