데드락을 회피하기
데드락을 예방하는 것은 장치의 사용률이 낮고 system의 throughput을 줄인다.
자원을 요청후 release하는 순서를 안다는 전제 하에 우리는 각 요청을 기다려야 할지 할당받을 수 있는지 결정할 수 있다.
가장 간단하고 효율적인 모델은 각 프로세스가 스스로 가장 필요로하는 리소스의 수를 선언하는 정보를 아는 것을 요구한다.
시스템이 절대 데드락 상태에 들어가지 않도록 한다. 이것이 deadlock-avoidance 접근이다.
safe state
프로세스 진행 순서인 safe sequence이 존재한다면 시스템은 safe state에 있다고 한다.
1. safe state는 dealock state가 아니다.
2. dealock statae는 unsafe state이다.
3. 모든 unsafe state가 dealock인 것은 아니다.
만약 위의 사진과 같이 12개의 자원이 있고 프로세스는 P0, P1, P2가 있다. 현재 각 프로세스에 현재 할당되어 있는 자원의 개수는 5, 2, 2개이고 남은 자원의 개수는 3개이다. 그리고 각 프로세스가 필요로 하는 자원의 개수는 10, 4, 9개이다.
남은 자원의 개수와 프로세스가 필요로하는 자원의 개수를 따져서 먼저 할당하고 release할 수 있는 프로세스에 자원을 할당한다.
남은 자원의 개수가 3개이고 현재 할당되어있는 자원의 개수와 더했을 때 프로세스의 max needs를 만족시키는 프로세스는 P1이다. 따라서 P1에게 먼저 할당하고 P1은 자원을 모두 사용하고 release한다. 남은 자원의 개수는 5개가 된다.
같은 방식으로 다음은 P0에 할당하게 되고 남은 자원의 개수는 10개가 된다. 다음은 P2, 남은 자원의 개수는 12개.
위와 같은 방식으로 safe sequence를 도출해낼 수 있다. <P1, P0, P2>이다. safe sequence가 존재하므로 이 시스템은 safe state에 있다.
데드락 회피는 safty checking의 전략이 필요하다.
끝날 수 있는 프로세스를 찾는다. 프로세스의 요구를 만족하는 충분한 자원이 있는지 확인한다.
프로세스가 보유한 것들을 release하고 또 다른 프로세스가 끝날 수 있는지 체크한다.
더이상 프로세스들이 남지 않을 때까지 반복할 수 있어야한다.
Banker's Algorithm
자원할당 그래프 알고리즘은 각 자원의 타입의 두개 이상의 같은 자원이 있는 자원할당 시스템에 응용하지 못한다. 자원할당 그래프 전략보다 덜 효율적이다. 할당할 때마다 safty checking하기 때문이다.
i: 프로세스 개수 j: 자원 종류 수
Available[i,j]: 각 타입의 리소스에서 사용가능한 리소스의 개수
Max[i,j]: 각 프로세스에서 요구하는 최대 리소스의 개수
Allocation[i,j]: 각 프로세스에 할당되어 있는 리소스의 개수
Need[i,j]: 각 프로세스에서 필요로하는 리소스의 개수
Need[i,j] = Max[i,j] - Allocation[i,j]이다.
RA라는 타입의 리소스의 개수가 10, RB는 5, RC는 7이다.
위 사진의 시스템이 safe state에 있는지 확인하기 위해 safe sequence가 있는지 확인해야 한다.
현재 사용가능한 자원의 개수는 A, B, C 각각 3, 3, 2개이다. 이 사용가능한 자원의 개수를 가지고 각 프로세스가 필요로하는 자원의 개수를 따져서 어떤 프로세스를 끝낼 수 있는지 확인한다.
safe sequence : <P1, P3, P4, P2, P0>
