12. Deadlock solution

Banker's Algorithm

 

 

뱅커스 알고리즘의 핵심은 resource allocation state를 도입해 프로세스들이 현존하는 리소스들 중 얼마만큼을 할당 받았는지 표현하는 것입니다. safe state는 모든 프로세스들이 성공적으로 실행을 마칠 수 있는 sequence가 존재하는 상태이고 unsafe state는 프로세스들이 최대치의 리소스를 요청했을 때, 요청을 다 들어주지 못하고 데드락에 빠지는 상태입니다.

 

unsafe state라고 해서 무조건 데드락에 걸리는 것이 아니라 모든 프로세스들이 자기들이 요구할 수 있는 최대치의 리소스를 요청할 때 발생하는 것입니다. 

 

 

 

뱅커스 알고리즘은 safe state 상태일때 프로세스가 unsafe state로 state를 이동시키는 요청을 한다면 그 요청을 무시합니다. unsafe state로 상태가 이동한다고 해서 무조건 데드락이 발생하는 것이 아니지만 보수적으로 리소스 요청을 처리합니다. 

 

 

 

뱅커스 알고리즘의 동작에 대해서 알아보겠습니다. P0, P1, P2 3개의 프로세스가 존재할 때 뱅커스 알고리즘을 적용할려면 이 프로세스들이 요청할 수 있는 리소스의 최대치를 알고 있어야합니다. 프로세스 번호 순서대로 10, 4, 9의 맥시멈 리소스를 요청할 수 있고 현재 할당된 리소스는 5, 2, 2 입니다. 

 

현재 할당된 리소스 상황을 본다면 9개의 리소스가 할당되어 있는 상태고 P1이 맥시멈 리소스를 요구하더라도 남은 3개 중 2개를 전달하면 작업을 마치고 4개의 리소스를 반환할 것입니다. 그러면 P0가 맥시멈 요청을 보내더라도 같은 방식으로 완료하고 리소스가 반환되며 P2의 경우도 마찬가지 입니다.

 

이 예제는 P1, P0, P2 순서로 작업을 완료한다면 데드락이 없이 모든 수행을 마칠 수 있기 때문에 safe state가 됩니다. (safe sequence는 P1, P0, P2), 여기서 P2가 먼저 1개의 리소스를 요청한다면 남은 리소스는 총 2개로 P1에게 리소스를 전달해주고 반환 받더라도 리소스가 부족하여 P1, P2 작업을 끝낼 수 없는 데드락에 빠지게 되기 때문에 요청을 거절하게 됩니다. (P2에게 리소스를 한 개 더 할당한다면 safe sequence가 존재하지 않음)

 

 

 

뱅커스 알고리즘을 조금 더 쉽게 표현하기 위해서는 몇 가지 locations이 필요합니다. available vector는 i번째 리소스가 몇 개가 available한지를 표현합니다. 앞의 예제에서는 마그네틱 드라이브라는 한 가지 타입의 리소스에 대해서만 뱅커스 알고리즘을 진행했는데 원래는 m가지 타입에 대해 동시에 뱅커스 알고리즘을 돌릴 수 있습니다.

 

max matrix는 i번째 프로세스가 j번째 리소스를 최대 몇 개까지 요청할 수 있는지를 담고 있습니다. (각 프로세스가 요구할 수 있는 맥시멈 리소스 수를 표현), allocation도 matrix로 allocation[i, j]라고 하면 i라는 프로세스가 j라는 타입의 리소스를 현재 몇 개 할당 받고 있는지를 표현합니다. (현재 리소스 할당 상태를 표현)

 

need도 matrix로 i번째 프로세스가 j번째 리소스를 추가로 얼마나 할당 받을 수 있는지를 표현한 것입니다.

 

 

 

먼저 safety를 확인하는 과정에 대해서 알아보겠습니다. finish[i]는 i번째 프로세스의 수행 완료 여부를 표현합니다. false면 아직 실행 중인 것이고 true면 실행이 완료된 것입니다. work[i]는 i번째 리소스가 얼마만큼 남았는지를 표현합니다. 첫 번째로 work는 available 벡터 값을 받아들이고, 현재 종료된 프로세스가 없으니 finish 벡터를 전부 false로 변경합니다.

 

그 다음 끝나지 않은 프로세스들 중에서 맥시멈 리소스 요청이 발생했을 때 현재 리소스로 들어줄 수 있는 프로세스를 찾습니다. 만약 있다면 이 프로세스 수행을 끝낼 수 있으니 이 프로세스의 finish 벡터값을 true로 변경하고 리턴된 리소스를 전부 Avail 벡터에 반환을 합니다. 이 작업은 step 2, 3에서 일어납니다.

 

이때 모든 프로세스가 종료되면 safe sequence에 도달한 것이고 종료되지 않은 프로세스가 존재한다면 unsafe state로 판별할 수 있습니다. 여기까지가 데드락 prevention입니다.

 

 

 

이번에는 dectection & recovery에 대해 알아보겠습니다. 이 경우에도 카운팅 세마포어를 사용할 때 뱅커스 알고리즘과 유사한 데드락 디텍션 알고리즘을 사용해야합니다. 

 

 

 

세이프티를 체크하는 알고리즘은 맥시멈 요청이 들어왔을 때를 전제로 safe seuqence를 찾습니다. 이후 pending request들을 한번에 처리해주는 방식으로 진행됩니다. request[i]는 i번째 프로세스가 pending 시켜둔 요청을 의미합니다. 이 프로세스가 걸어둔 요청들을 현재 리소스를 가지고 만족시키는 것입니다. 

 

이렇게 스탭2와 스탭3를 계속 루프를 돌면서 프로세스별 pending request들을 다 실행시키고 끝나면 finish 벡터에 true로 표시한 다음 리소스를 반환받습니다. 스탭4 전에 모든 프로세스가 끝나면 데드락이 없는 경우이고 만약 available한 리소스보다 더 많은 리소스를 원하는 프로세스가 존재해 스탭 4로 넘어가게 된다면 데드락이 발생하는 것입니다.

 

 

 

데드락이 발생하면 프로세스를 중지하는 것 외에는 해결책이 없습니다. 데드락이 발생한 프로세스 중 하나를 termination 시키고 리소스를 반환받아서 다른 프로세스들이 실행할 수 있도록 만들어주는 것이 데드락 recovery 입니다. 이렇게 중지시켜 리소스를 반환받으려면 rollback이라는 것이 필요합니다.