7. Deadlocks (2) - 2 (Deadlock Avoidance~Banker's Algorithm)

Deadlock Avoidance는 4가지 상황(Mutual Exclusion, No Preemption, Hold and Wait, Circular Wait) 중 한 가지는 무조건 막는 Deadlock Prevention과는 달리, 이들을 전부 허용하되, 동작 과정에서 Deadlock이 발생하지 않도록 제어한다.

자원을 할당할지, 말지에 대한 결정은 OS가 한다.

Deadlock이 발생할 가능성이 있는 상황이면, 자원을 줄 수 있는 상황임에도 주지 않는 선택을 한다. (위험한 길을 회피해서 안전한 길로 가기)

미래에 일어날 Deadlock의 가능성을 과거에 미리 예측하려면, 추가적인 사전정보를 가지고 있어야 한다.

• 제일 간단하고 유용한 방법은, 각 프로세스가 자원마다 최대 몇 개를 사용할 지에 대한 정보를 미리 선언해놓는 것이다. ("난 R1 최대 2개, "R2"는 최대 3개 사용할거야")
•  Deadlock-avoidance(Deadlock 회피) 알고리즘은 진행 과정에서 이러한 resource-allocation state(자원 할당 상태)를 활용하여 절대 circular-wait(꼬리물기, 선형대기)가 발생하지 않도록 보장한다.
• Resource-allocation state(자원 할당 상태)는 "사용 가능한 자원의 수", "할당된 자원의 수", 그리고 "최대 각 자원들을 몇 개 사용할 것인지"의 정보를 포함한다.

설령 실제로는 Deadlock이 발생하지 않을지라도, 최악의 상황에서는 발생할 수 있는 것이 확인되면 절대 그 길로 가지 않는다.(회피)

 

• 만약 프로세스가 현재 시스템에 남아있는 자원을 달라고 요청한다면, 시스템(운영체제)는 이 자원을 해당 프로세스에게 할당해 줬을 때 시스템이 safe state(안전한 상태)가 될 수 있는지 판단한다.
• 순서쌍 <P1, P2, ..., Pn>이 Safe인 상태는, 모든 Pi에 대해 "현재 Pi가 가지고 있는 자원", "시스템에 남아있는 할당 안된 자원", 그리고 "Pi보다 낮은 순서의 프로세스들이 현재 점유하고 있는 자원(일을 끝마치면 놓을 것이므로)"을 합쳤을 때, 이들을 가지고 일을 끝마칠 수 있으면 Safe 한 상태이다. -> 일을 끝마칠 수 있음이 보장됨.
  • 만약 Pi가 필요한 자원이 현재 바로 할당될 수 없는 상태라면 -> 자기보다 순서가 낮은 모든 프로세스 Pj들이 일을 끝마칠 때 까지 기다리면 됨.
  • 자기보다 순서가 낮은 프로세스 Pj들이 일을 끝마치면, Pi는 필요한 자원들을 모두 할당받을 수 있고, 해야됐던 일을 수행한 뒤, 할당받았던 자원들을 반납하고 종료할 수 있다.
  • Pi가 종료되면, Pi+1은 필요했던 자원들을 전부 할당받을 수 있다. 그리고 이런 논리로 모든 프로세스들이 전부 실행이 가능하게 된다.
• 이런식으로 모든 프로세스의 Safe sequence가 존재할 때, 시스템은 Safe state(안전한 상태)에 있다고 할 수 있다. -> 종료에 도달할 수 있는 길이 존재한다는 뜻.

• 만약 시스템이 Safe state(안전한 상태)라면 -> Deadlock이 절대 발생하지 않음.
• 만약 시스템이 Unsafe state(안전하지 않은 상태)라면 -> Deadlock이 발생할 "가능성"이 있음.
  • 모든 프로세스들이 자신이 초기에 선언했던 최대의 자원들을 전부 요청하는 경우
• Avoidance(회피) -> 시스템이 절대 Unsafe state(안전하지 않은 상태)에 접근하지 않도록 만들어버림.
  • "자원을 할당해도 Safe State가 되는 경우에만 자원 할당을 허용한다. 아닌 경우 절대 허용하지 않는다"

Unsafe 상태라고 무조건 Deadlock이 발생하는 것은 아니다. 하지만 Unsafe인 상황에서는 Deadlock이 발생할 가능성이 있다.

Safe 상태에서는 절대 Deadlock이 발생하지 않는다.

 

Avoidance(회피) 알고리즘

 

• 각각의 리소스 타입이 인스턴스(instance)를 하나만 가지는 경우
  • resource-allocation graph(자원 할당 그래프)를 사용한다
• 각각의 리소스 타입이 인스턴스(instance)를 여러개 가지는 경우
  • Banker's algorithm을 사용한다.

Case A: 리소스(자원)타입 마다 인스턴스(instance)를 하나만 가지는 경우 : Resource Allocation Graph Algorithm(자원 할당 그래프 알고리즘)

 

• Claim edge
  • Pi -> Rj 는 Pi가 리소스 Rj를 요청할 "가능성"이 있다는 것을 나타낸다. (점선의 화살표로 표시)
• Request edge
  • 만약 실제로 프로세스(Pi)가 리소스(Rj)에게 자원 요청(Request)을 보내면 Claim edge(점선)가 Request edge(실선)로 바뀐다.
• Assignment edge
  • 만약 실제로 자원이 해당 프로세스에게 할당이 되면 Request edge가 Assignment Edge로 바뀐다.(화살표 방향이 자원에서 프로세스로 향하도록 바뀜)
  • 만약 프로세스가 할당받은 자원을 내려놓으면, Assignment edge가 다시 Claim edge로 바뀜(초기 상황으로 되돌아감)
• 알고리즘: (자원들의 정보는 미리 시스템에 선언이 되어 있어야 함 -> 정보가 있어야 그래프를 그릴수 있다)
  • 프로세스 Pi가 자원 Pj에게 Request(요청)을 보냈다고 가정하자.
  • 이 Request Edge를 Assignment Edge로 변경했을 때, Resource Allocation Graph에 사이클(cycle)이 생기지 않는 경우에만 해당 Request(요청)이 받아들여지게 된다.

Deadlock Avoidance(Deadlock 회피)를 위한 Resource-Allocation graph(자원 할당 그래프) -> 모든 자원들의 Instance가 하나인 경우에 사용되는 방법임.

 

현재 위의 그림에서 P2와 R2의 관계는, 아직 요청은 하지 않았지만 P2가 R2에게 요청을 할 가능성이 있는 상황이다.

만약 P2가 실제로 R2에게 자원을 요청하면, 해당 점선이 실선으로 바뀐다.

 

이때 만약 R2가 요청을 받아들여서 자원을 P2에게 할당해주면, R2에서 P2로 향하는 실선으로 바뀌게 된다. -> 실선과 점선(Claim edge)을 포함하여 Cycle이 형성된다.

Cycle이 형성되는 상황이 되기 때문에 이 경우에는 R2가 P2의 요청을 절대 받아들이지 않는다. -> 만약 해당 점선(P1 -> R2)이 실선으로 바뀌게 되면 옴짝달싹 못하는 Deadlock 상황이 되기 때문이다.(가능성이 존재)

 

 

자원을 할당해도 사이클이 안생기면 -> Safe -> 허용

자원을 할당하는 경우 사이클이 생긴다면 -> Unsafe -> 불허

 

 

Case B: 자원들이 여러개의 instance를 가지고 있는 경우: Banker's Algorithm

 

• 모든 프로세스들은 먼저 자신들이 최대로 사용할 가능성이 있는 자원의 수를 선언해 놓아야 함.
• 만약 프로세스가 자원을 달라고 요청했을 때, 기다려야 될 수 도 있음.
• 만약 프로세스가 필요한 모든 자원을 다 할당받았을 때에는, 반드시 일정 시간 후에는 내려놓아야 함.

Banker's Algorithm을 위한 자료구조

 

n = 프로세스의 개수, m = 자원 타입의 개수

 

Vector

• Available[j] = k : 자원 Rj의 현재 사용 가능한 인스턴스의 개수가 k개이다.

Matrix(n x m)

• Max[i, j] = k : 프로세스 Pi가 자원 Rj에게 최대 k개의 인스턴스를 요청할 가능성이 있음.
• Allocation[i, j] = k : 프로세스 Pi가 자원 Rj에게 현재 인스턴스 k개를 할당받은 상태임.
• Need[i,j] = k : 현재 상황에서 프로세스 Pi가 자원 Pj의 인스턴스를 최대 k개 더 필요로 할 가능성이 있음.

Need[i, j] = Max[i, j] - Allocation[i, j]

 

시간이 너무 많이 걸려서 아마 더 이상의 정리는 힘들듯 하다.