[운영체제][프로세스관리] Deadlocks #2 교착상태와 뱅커 알고리즘(Deadlocks & Banker's Algorithm) : 교착상태 회피(Deadlock Avoidance)

교착상태 방지(Prevention) 방법의 한계

• 교착상태가 발생 만족 조건 4가지인 상호배제, 점유와 대기, 선점 불가, 원형 대기중 조건을 하나라도 막는다면 교착상태를 막을 수 있습니다.
• 그러나 조건을 막는다 하더라도 근본적인 문제 해결이 불가능하거나 비실용적인 경우가 대부분이었습니다.
• 제일 실용적인 원형 대기 조건을 방지한다 하더라도 교착상태가 일어나지 않는 것을 보장할 수 없었습니다.

 

교착상태 회피(Deadlock Avoidance)

• 교착상태 회피 시스템은 미래의 발생가능한 교착상태를 회피하기 위해서 쓰레드가 대기를 해야하는지 안해야하는지에 대한 각각의 요청을 결정하는 시스템입니다.
• 교착상태 회피 시스템은 회피해야할지 결정하기 위해서 자원들이 어떻게 요청되었는지에 대한 추가적인 정보를 요구합니다.
• 예를 들어 시스템에 R1, R2 자원이 있다고 가정합니다.
  • 쓰레드 P가 R1을 요청하고 R2를 요청합니다.
  • 쓰레드 Q는 R2를 요청하고 R1을 요청합니다.
  • 위 상황으로 원형대기가 발생하여 교착상태가 발생합니다.
  • 회피 시스템은 위와 같은 상황을 파악하여 거부(Reject)합니다.

 

교착상태 회피 알고리즘

• 회피 알고리즘은 교착상태로 진입하지 않도록 보장하는 알고리즘을 구성하는것이 가능합니다.
• 각각의 자원 유형의 최대 개수가 필요합니다.
• 자원 할당의 상태는 이용가능한 자원의 개수, 할당된 자원의 개수, 쓰레드의 최대 수요 개수를 알고 있어야합니다.

 

안전 상태(Safe State)

• 안전상태는 만약 시스템에서 각각의 쓰레드에게 특정한 순서로 자원을 할당하여 교착상태를 회피한 상태를 말합니다.
• 시스템에서 안전 상태에 들게 하는 자원 할당의 특정한 순서를 안전 시퀀스(Safe Sequence)라고 합니다.

 

안전상태(Safe State)와 위험상태(Unsafe State)의 관계

• 안전상태는 교착상태가 될 수 없는 상태를 의미합니다.
• 반대로 말하면 교착상태는 안전상태의 반대인 위험 상태(unsafe state)에만 존재합니다.
• 모든 위험 상태가 교착상태는 아니지만 어느 특정 위험 상태는 교착상태가 될 수 있습니다.

 

안전상태(Safe State)의 개념

• 시스템이 절대로 교착상태로 들어가지 않으려고 하는 것을 보장하는 회피 알고리즘을 정의할 수 있습니다.
• 회피 알고리즘의 핵심은 시스템이 언제나 안전 상태에 있는 것을 보장하는 것입니다.
• 시스템은 초기에 안전 상태에 있습니다.
• 시스템은 어떤 한 쓰레드가 현재 이용가능한 자원을 요청할때마다 그 자원을 할당해도 될지 안될지를 결정합니다.
• 시스템은 해당 자원 요청이 안전상태에서 위험 상태로 전환된다면 그 요청을 거부합니다.

 

자원-할당 그래프의 재방문

• 시스템이 각각의 자원 유형에 대해서 오직 하나의 인스턴스만 가진다고 가정할때 간선의 새로운 타입인 차후-요청 간선(Claim Edge)을 표현할 수 있습니다.
• 차후-요청 간선은 Ti -> Rj 로 표현하며 어떤 한 쓰레드가 차후 미래의 어느 시점에 자원을 요청할 수 있다는 것을 의미합니다.
• 시스템은 차후-요청 간선을 자원-할당 그래프에 넣어서 교착상태가 발생하는지 확인합니다.
  • 차후-요청 간선을 넣었을 때 원형 대기가 발생하면 교착상태가 발생할수도 있고 발생 안할 수도 있습니다.
  • 차후-요청 간선을 넣었을 때 원형 대기가 발생하지 않는다면 안전 상태로써 자원 요청을 수락합니다.

다음 그림은 교착상태 회피를 위한 자원할당 그래프입니다.

• 위 그림에서 점선 간선이 차후-요청 간선(Claim Edge)입니다.
• T1과 T2가 차후에 R2 자원을 사용하고 싶다고 추후에 요청할 예정입니다.
• 시스템은 차후-요청 간선을 자원-할당 그래프에 넣고 계산한 결과 T1에 할당 또는 T2에 할당해도 교착상태가 발생하지 않는 안전 상태라고 판단할 수 있습니다.

 

다음 그림은 자원-할당 그래프에서 위험 상태에 있는 그래프입니다.

• T1이 R2 자원을 사용하고 싶어서 추후에 요청할 예정입니다.
• 시스템은 추후-요청 간선(T1->R2)을 자원-할당 그래프에 넣어 교착상태가 발생하는지 계산합니다.
• 계산 결과 원형 대기가 발생하여 해당 요청을 거부합니다.

 

2. 뱅커 알고리즘(Banker's Algorithm)

• 각각의 자원 유형의 다수의 인스턴스가 있는 자원 할당 그래프에는 적용할 수 없습니다. 이 문제를 해결하기 위해서 뱅커 알고리즘이 사용됩니다.
• 뱅커 알고리즘은 각각의 자원 유형의 다수의 인스턴스가 있는 자원 할당 그래프에 적용할 수는 있지만 효율적이지 않고 더욱 복잡한 알고리즘입니다.
• 뱅커 알고리즘은 쓰레드의 자원과 관련된 데이터 구성과 Resource-Request Algorithm, Safety Algorithm을 이용하여 특정 쓰레드의 자원 요청을 승인 또는 거절하여 교착상태를 막는 알고리즘입니다.

 

뱅커 알고리즘의 데이터 구성

• 시스템에서 n개의 쓰레드와 m개의 자원 유형이 있다고 가정합니다.
• Available : 이용가능한 자원 유형의 개수를 나타내는 벡터입니다.
• Max : 각각의 쓰레드가 요구하는 최대 개수를 정의한 매트릭스입니다.
• Allocation : 각각의 쓰레드에 현재 할당된 각각의 자원 유형의 개수를 정의한 매트릭스입니다.
• Need : 각각의 쓰레드가 앞으로 요청할 자원을 나타내는 매트릭스입니다.

 

뱅커 알고리즘의 데이터 구성 의미

• Available[m] : 만약 Available[j] == k이라면 Rj의 k개의 인스턴스가 이용가능하다는 의미입니다.
• Max[n x m] : 만약 Max[i][j] == k라면 쓰레드 i가 자원 유형 Rj에 대해서 최대 k개까지 요청할 수 있다는 의미입니다.
• Allocation[n x m] : 만약 Allocation[i][j] == k라면 쓰레드 i는 자원 유형 Rj에 대해서 k개의 인스턴스를 할당됨을 의미합니다.
• Need[n x m] : 만약 Need[i][j] == k라면 쓰레드 i가 자원 유형 Rj에 k개 요청할 것이라는 의미입니다.

 

Safety Algorithm

1. Work와 Finish는 m과 n의 길이를 가진 배열로 지정합니다. Work = Available로 초기화하고 Finish 배열의 각각의 모든 요소를 false로 초기화합니다.
   
   • Work 배열의 각각의 요소는 이용가능한 자원 유형의 인스턴스 개수를 의미합니다. 예를 들어 Work = {3, 3, 2}이라면 이용가능한 자원 A의 개수 = 3, 자원 B의 개수 = 3, 자원 C의 개수 = 2를 의미합니다.
   • Finish 배열의 각각의 요소는 각각의 쓰레드가 작업 수행을 맞쳤는지 의미합니다. true이면 작업을 마친 것이고 false이면 작업을 마치지 않은 것을 의미합니다.
2. 두 조건을 만족하는 인덱스 i를 탐색합니다. 만약 그러한 인덱스 i가 존재하지 않으면 4번 과정으로 이동합니다.
   • Finish[i] == false
   • Need_i <= Work
3. 다음 로직을 수행하고 2번과정으로 되돌아갑니다.
   1. Work = Work + Allocation_i
   2. Finish[i] = true
4. 만약 모든 i에 대해서 Finish[i] == true라면 시스템은 안전상태에 있는 것을 의미합니다.

 

Resource-Request Algorithm

1. 만약 Request_i <= Need_i라면 2번과정으로 이동합니다. 그외에는 에러를 발생시킵니다. 왜냐하면 그 쓰레드는 최대 차후요청(Claim)을 초과했기 때문입니다.
2. 만약 Request_i <= Available라면 3번과정으로 이동합니다. 그외에는 쓰레드 i는 대기해야합니다. 왜나하면 그 자원들은 이용이 불가능하기 때문입니다.
3. 시스템은 쓰레드 i에게 요청한 자원을 할당합니다. 할당할때 다음과 같은 과정이 수행됩니다.
   1. Available = Available - Request_i : 이용가능한 자원에서 요청한 자원을 차감
   2. Allocation_i = Allocation_i + Request_i : 할당된 자원 집합에서 요청한 자원을 추가
   3. Need_i = Need_i - Request_i : 쓰레드가 요청한 자원중에서 방금 요청한 자원을 차감

 

알고리즘 예제

• T = {T0, T1, T2, T3, T4}, 다섯개의 쓰레드가 있는 집합 T
• R = {A, B, C}, 3개의 자원 유형이 있는 집합 R
• 각각의 자원 유형의 인스턴스 개수 : A = 10, B = 5, C = 7
• 시스템의 현재 상태를 표현하는 스냅샷은 다음과 같습니다.

• Allocation : 현재 쓰레드에 할당된 각각의 자원 유형의 인스턴스 개수를 의미합니다.
  • 예를 들어 쓰레드 T0은 자원 B의 인스턴스 1개를 가지고 있습니다.
• Max : 해당 쓰레드가 요청할 수도 있는 각각의 자원 유형의 인스턴스 최대 개수를 의미합니다.
  • 예를 들어 쓰레드 T0은 A자원의 인스턴스를 최대 7개, B 자원의 인스턴스를 최대 5개, C 자원의 인스턴스를 최대 3개까지 요청할 수 있습니다.
• Available : 현재 이용가능한 각각의 자원 유형의 인스턴스 개수를 의미합니다.
  • 예를 들어 현재 A 자원의 인스턴스 개수는 3개까지 이용가능합니다.
• 모든 쓰레드의 할당(Allocation)된 A자원의 인스턴스 개수의 합은 7개입니다. 집합 R의 A자원의 초기화된 인스턴스 개수는 10이므로 이용 가능한(Available) 자원은 3개입니다.

 

다음은 Need 배열의 계산식입니다.

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

• 쓰레드 T0에 대해서 계산을 수행하면 다음과 같습니다.
  • Need[0][0] = Max[0][0] - Allocation[0][0] = 7 - 0 = 7
  • Need[0][1] = Max[0][1] - Allocation[0][1] = 5 - 1 = 4
  • Need[0][2] = Max[0][2] - Allocation[0][2] = 3 - 0 = 3
• 다른 쓰레드에 대해서 Need를 계산하면 다음과 같습니다.

 

Safety Algorithm 수행과정

1. Work 배열와 Finish 배열을 초기화
   • 이용가능한 자원 Available 배열의 요소값을 Work 배열에 초기화
   • Work = {3, 3, 2}
   • 모든 쓰레드 T0 ~ T4에 대해서 false로 초기화, Finish[0] = false의 의미는 쓰레드 T0가 아직 작업을 마치지 못했다는 의미입니다.
   • Finish = {false, false, false, false, false}
2. 아직 작업을 마치지 못하고 필요한 자원이 이용가능한 자원안에서 수행하는 쓰레드를 탐색
   • i = 0 to n-1까지 반복합니다.
   • Finish[i] = false && Need[i] <= Work 조건을 만족하는 인덱스 번호 i를 탐색
   • 만약 조건을 만족하는 인덱스 번호 i가 존재하지 않으면 4번 과정으로 이동합니다.
3. 2번 과정의 조건에 만족하는 쓰레드를 탐색하였다면 필요한 자원으로 작업을 수행하고 다음 과정을 수행
   • Work = Work + Allocation[i] : 이용가능한 자원에 쓰레드 Ti에 할당된 자원을 추가함
   • Finish[i] = true : 쓰레드 Ti가 작업을 마쳤다는 것을 의미함
   • 2번 과정으로 이동
4. 모든 쓰레드가 작업을 마쳤는지 확인합니다.
   • 만약 Finish 배열의 모든 요소가 true이면 시스템은 안전한 상태(safe state)입니다.
   • 아니라면 2번 과정으로 이동합니다.

위 수행과정을 디버깅 표로 표시하면 다음과 같습니다.

 

새로운 요청이 들어온 경우 1 (Resource-Request 통과, Safety Algorithm 통과)

• 쓰레드 T1이 자원 A = 1개, 자원 C = 2개를 요청하였다고 가정합니다.
  • Request_i = (1,0,2)
• 1번 쓰레드가 새로운 요청이 들어왔을때 상황은 다음과 같습니다.

• 위와 같이 요청이 들어왔을때 Resource-Request Algorithm을 이용하여 승인할지 거부할지를 결정합니다.
• 새로운 요청에 따른 Safe Algorithm 결과는 다음과 같습니다.

 

새로운 요청이 들어온 경우 2 (Resource-Request 거부)

• 쓰레드 T4가 자원요청을 (3,3,0)으로 요청하였다고 가정할때 Resource-Request 조건을 만족하는지 확인합니다.
• Resource-Request 조건 검사 결과는 다음과 같습니다.

• 자원요청량(3,3,0)보다 Available(2,3,0)이 부족하므로 해당 요청은 거부됩니다.

 

새로운 요청이 들어온 경우 3 (Resource-Request 통과, Safety-Algorithm 거부)

• 쓰레드 T0가 자원요청을 (0,2,0)으로 요청하였다고 가정합니다.
• Resource-Request 조건 검사 결과는 다음과 같습니다.

위 결과를 기반으로 Safety Algorithm 결과는 다음과 같습니다.

• 위와 같이 Request[0] = (0,2,0)는 Safety Algorithm을 만족시키지 못하므로 거부(Reject)됩니다.

 

정리하며

• 교착상태를 해결하는 방지, 회피, 탐색 후 회복의 방법중 회피하는 방법에 대해서 알아보았습니다.
• 교착상태를 회피하는 대표적인 알고리즘이 뱅커 알고리즘입니다.
• 뱅커 알고리즘은 자원과 관련된 데이터 구성과 Resource-Request Algorithm, Safety Algorithm을 이용하여 어떤 쓰레드의 특정 자원요청이 Safe Sequence를 만들어 낼 수 있는지를 계산합니다.
• Safe Sequence를 만들어내지 못한다면 거부(Reject)하고 아니라면 승인합니다.

 

References

source code :https://github.com/yonghwankim-dev/OperatingSystem_Study
Operating System Concepts, 10th Ed. feat. by Silberschatz et al.
[인프런] 운영체제 공룡책 강의