[운영체제]chapter 08. Deadlock_#02 교착상태와 뱅커 알고리즘 : 교착상태 회피

Deadlock#2. 교착상태와 뱅커 알고리즘 (Deadlocks & Banker's Algorithm) : 교착상태 회피 (Deadlock Avoidance)

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

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

교착상태 회피(Deadlock Avoidance)

• 교착상태 회피 시스템은 미래의 발생가능한 교착상태를 회피하기 위해서 쓰레드가 대기를 해야하는지 안해야야하는지에 대한 각각의 요청을 결정하는 시스템이다.
• 교착상태 회피 시스템은 회피해야할지 결정하기를 위해서 자원들이 어떻게 요청되었는지에 대한 추가적인 정보를 요구한다.
• ex) R1, R2, 자원이 있다고 가정
  • Thread P 가 R1을 요청하고, R2를 요청한다.
  • Thread 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 Akgiruthm을 이용하여 특정 쓰레드의 자원 요청을 승인 또는 거절하여 교착상태를 막는 알고리즘

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

• 시스템에서 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 배열의 각각의 요소는 이용가능한 자원 유형의 인스턴스 개수를 의미. ex) 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: 현재 쓰레드에 할당된 각각의 자원 유형의 인스턴스 개수를 의미
  • ex) thread T0은 B자원 인스턴스 1개 가지고 있음
• Max: 해당 thread가 요청할 수도 있는 각각의 자원 휴영의 인스턴스 최대 개수를 의미
  • ex) thread T0은 A자원의 인스턴스를 최대 7개, B의 자원의 인스턴스를 최대 5개, C 자원의 인스턴스를 최대 3개가지 요청할 수 있다.
• Available: 현재 이용가능한 각각의 자원 유형의 인스턴스 개수를 의미
  • ex) 현재 A자원의 인스턴스 개수는 3개까지 이용 가능하다
• 모든 쓰레드의 할당 Allocation된 A자원의 인스턴스 개수의 합은 7개이다. 집합 R의 A자원의 초기화된 인스턴스 개수는 10이므로 이용가능한(Available) 자원은 3개이다.

Need 배열의 계산식 : Need[i][j] = Max[i][j] - Allocation[i][j]

 

 

 

Safety Algorithm 수행 과정

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

위의 수행과정을 디버깅 표로 표시

 

 

 

정리 

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

 

 

참고 : https://yonghwankim-dev.tistory.com/481