은행가 알고리즘 코드, 시간복잡도, 회복 알고리즘

은행가 알고리즘 다시보기

가상으로 자원 할당을 해보기

그중에서 safety를 확인해야 합니다.

1단계 - 초과하지 않아야 다음단계로 이동합니다.

 

n: 프로세스 수

m: 자원 유형 수

 

Request와 Need의 자원 유형이 같으니 비교할 수 있습니다.

 

이 알고리즘의 시간복잡도는?

1단계 부터 봅시다. 

모든 프로세스가 필요치를 측정해야 하니 O(n)이 필요할 거 같습니다.

아니였습니다. Pi가 자원 요청하는 것을 가정하는 것 입니다.

 

ex) Pi가 B를 요청한다 하면 Request는 0100이 됩니다.

 

길이가 m인 벡터를 하나씩 비교해야 합니다.

Request, Need보다 남은 자원량이 큰지를 확인해야 합니다.

 

즉, O(m) 입니다.

길이가 m인 것을 비교하는 시간입니다.

 

2단계 에서 걸리는 시간

마찬가지로 O(m) 입니다.

각 원소들의 비교를 해야 합니다.

 

3단계에서 걸리는 시간

O(1)인거 같습니다.

아니였습니다.

 

각각의 길이가 m이니 비교해서 계산하는 것 입니다.

 

결국 이 알고리즘이 걸리는 시간은 O(m) 입니다.

 

결과가 안전한지 검사하는것이 safety 알고리즘 입니다.

아직 할당은 안한 것입니다.

회피할지 말지를 결정하려고 하는 것이빈다.

 

 

은행가 알고리즘 (안전 알고리즘)

Work, Finish 라는 백터를 선언합니다.

 

Work의 의미는?

available한 남은 자원의 수 입니다.

처음에는 진짜 available 수 입니다.

그 다음에는 가상으로 프로세스를 돌려본 결과입니다.

 

왜 Work의 길이는 m인가?

자원 유형의 수만큼 돌려야 하지 때문입니다.

 

Finish의 의미는?

가상으로 끝낸 프로세스 입니다.

프로세스의 숫자를 하나씩 true로 만듭니다.

 

Finish의 길이는 왜 n일까요?

프로세스의 개수가 n이기 때문입니다.

 

맨 마지막에는 finish 전부 true로 되어있겠지요

그렇게 되지 않으면 unsafe라고 판단하고 할당을 거부 합니다.

 

 

자원을 찾아서 프로세스를 끝낼 수 있는지 확인하는 부분 입니다.

 

만약 자원을 찾으면 

• 수행을 하고 
• 할당했던 자원과 남아있던 자원을 더해서 할당 가능 자원을 늘립니다.
• 그 다음 프로세스 i를 끝냅니다.

 

선언의 시간복잡도는?