교착 상태 회피(Deadlock Avoidance)
- 교착 상태 예방의 단점
- 장치의 이용률이 저하됨
- 시스템 총 처리율(throughput)이 감소
교착 상태 회피 원리
- 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것
- 각 스레드의 요청과 방출에 대한 완전한 순서를 미리 안다면,
각 요청에 대해 스레드가 대기해야 하는지의 여부를 결정할 수 있다.
→ 각 요청에서 발생할 수 있는 교착 상태를 피할 수 있다.
- 스레드 대기 여부를 결정하기 위해, 여러 가지 정보를 고려해야 한다.
- 현재 가용 자원
- 현재 각 스레드에 할당된 자원
- 각 스레드가 앞으로 요청하거나 방출할 자원
교착 상태 회피 알고리즘
- 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것
→ 가장 단순하고 제일 유용한 모델
- 시스템에 순환 대기 상황이 발생하지 않도록 자원 할당 상태를 검사
자원 할당 상태 : 가용 자원의 수, 할당된 자원의 수, 스레드들의 최대 요구 수에 의해 정의
안전 상태(Safe State)
- 시스템이 안전 순서(safe sequence)를 찾을 수 있다면 시스템은 안전하다.
→ 시스템이 스레드들이 요청하는 모든 자원을
교착 상태를 야기시키지 않고 모두 할당해 줄 수 있다.
<T1, T2, T3…Tn>과 같은 스레드 순서가 안전하다는 말의 구체적 의미
- 모든 T(i)에 대해 그 T(i)가 요청하는 자원을 아래의 자원을 사용해서 만족시킬 수 있다.
- 시스템에 현재 남아있는 자원
- 앞서 수행을 마칠 모든 스레드 T(k)들이 반납하는 자원
- 현재 T(i)가 요청한 자원들을 즉시 만족시켜 줄 수 없을 것으로 판단되는 경우
→ 모든 T(k)들의 수행이 마칠 때까지 T(i)가 기다리게 한다.
→ 이후, T(i)는 T(k)가 반납한 자원들을 가지고 수행
- 이런 경우를 불안전(unsafe)라고 한다.
불안전(unsafe) : 모든 스레드를 무사히 마칠 수 있는 시퀀스를 찾을 수 없는 경우
안전 상태와 불안전 상태의 관계
안전, 불안전, 교착 상태 공간
- 스레드의 행동 양태가 불안전 상태를 제어
- 시스템이 안전하다 → 교착 상태가 아니다.
- 시스템이 안전 상태에 있으면 운영체제는 불안전 상태와 교착 상태를 막을 수 있음
- 교착 상태에 있다. → 시스템은 불안전한 상태이다.
- 불안전 상태에 들어가면 교착 상태가 일어날 수 있는 자원 요청을 막을 수 없음
- 시스템이 불안전 상태라고 해서 반드시 교착 상태로 간다는 뜻은 아님
→ 시스템이 불안전하다는 것은 앞으로 교착 상태로 가게 될 가능성이 있다는 뜻
프로세스로 보는 예시 - 시스템의 상태가 안전인 경우
쓰레드 별 상태
- 가정
- 시스템에 12개의 자원이 있고 T0, T1, T2 3개의 프로세스가 있다고 가정
- 최대 소요량과 현재 사용하고 있는 자원의 수는 위와 같음
- 현재 상황에서 시스템의 상태는 안전
- T1 → T0 → T2 순서가 있기 때문에 안전 상태
- T1에게 시스템 보유분 2개를 줌으로써, 먼저 끝낸다.
→ 시스템에 남아있던 1개 + T1이 반납한 4개 = 시스템 보유분 5개가 됨
- T0이 시스템 보유분 5개를 가져가 수행을 끝냄
→ T0이 반납한 자원 10개 = 시스템 보유분 10개가 됨
- T2가 마지막으로 수행을 끝냄
→ 최종적으로 시스템 보유분은 12개가 됨
프로세스로 보는 예시 - 시스템의 상태가 불안전인 경우
T2에서 자원 하나를 더 씀
- 가정
- 위와 똑같이 시스템에 자원이 12개가 있다.
- 위의 예시와는 다르게 T2에서 현재 자원을 3개를 사용하고 있음
- 현재 상황에서 시스템의 상태는 불안전
→ 해당 상태에서는 T1 만이 원하는 자원을 다 할당받을 수 있음
→ T1이 마치고 자원을 반납해도 시스템 보유분은 4개밖에 되지 않음
- T0은 5개의 자원이 추가적으로 더 필요함
→ 시스템 보유분은 4개이므로, T0는 끝나지 못하고 기다려야 함
- T2는 6개의 자원이 추가적으로 더 필요함
→ 시스템 보유분이 4개이므로, T2는 끝나지 못하고 기다림
- 최종적으로 교착 상태가 발생한다.
- 최초에 T2가 1개의 자원을 요청할 때 그 요청을 들어줬기 때문에 발생한 교착상태임
→ T2의 요청을 다른 스레드가 끝날 때까지 기다리게 했다면 교착상태 발생 X
→ 회피 알고리즘이 교착 상태를 피하는 방법이자 정의
회피 알고리즘의 기본 원칙
- 기본 원칙 → 시스템의 상태를 항상 안전 상태를 떠나지 않도록 고수하는 것
- 최초의 상태는 안전하지만, 스레드 자원 요청에 따라 즉시 할당과 대기를 결정해야 함.
→ 요청한 자원을 즉시 할당해 주는 것은 시스템이 안전 상태에서 안전 상태로 옮길 때뿐
- 단점 : 자원의 이용률이 회피를 안 쓸 때에 비해 낮아질 수밖에 없음
- 이는 스레드가 요청한 자원보다 많은 양을 시스템이 보유하고 있어도 마찬가지
자원 할당 그래프 알고리즘
- 각 자원 유형마다 하나의 인스턴스를 갖는 자원 할당 시스템을 갖는 경우 사용 가능
- 교착 상태 회피를 위한 자원 할당 그래프의 변형
- 요청 간선과 할당 간선에
예약 간선(claim edge)을 추가
예약 간선 : 미래에 자원을 요청할 것이라는 의미
- 간선의 방향은 요청 간선과 유사하지만 점선으로 표시
- T(i) → R(j) : 프로세스 P(i)가 미래에 자원 R(j)를 요청할 것
- 프로세스 T(i)가 자원 R(j)를 요청
→ 예약 간선 T(i) → R(j)는 요청 간선으로 변환
- T(i)가 자원 R(j)를 방출할 때
→ 할당 간선 R(j) → T(i)는 예약 간선 T(i) → R(j)로 다시 변환
- 시스템에서 자원이 반드시 예약되어 있어야 한다.
→ 스레드 T(i)가 실행되기 전에, 스레드의 모든 예약 간선이 자원 할당 그래프에 표시되어야 함.
- 스레드 T(i)와 연관된 모든 간선들이 예약 간선일 때만
간선 T(i) → R(j)를 그래프에 추가할 수 있도록 허용
자원 할당 그래프 알고리즘 메커니즘
- 가정
- 스레드 T(i)가 자원 R(j)를 요청한다고 가정
- 동작
- 요청 간선 T(i) → R(j)를 할당 간선 R(j) → T(i)로 변환해도
자원 할당 그래프에 사이클을 형성하지 않을 때만 요청을 허용
- 사이클이 없다면 자원을 할당해도 시스템은 안전 상태가 됨
- 사이클이 발견되면 스레드 T(i)는 자신의 요청이 충족될 때까지 대기
- 사이클 탐지(Cycle Detection) 알고리즘을 이용해 안전성을 검사한다.
- 그래프에서 사이클 탐지 알고리즘은 n^2 차수의 연산이 필요
자원 할당 그래프 알고리즘 예시
교착 상태 회피를 위한 자원 할당 그래프
- T2가 R2를 요청한다고 가정
→ R2는 현재 가용한 상태지만, 이를 T2에 할당할 수 없음
- 할당할 경우 그래프에 사이클이 생기기 때문에 할당할 수 없음
- T1이 R2를 요청하고, T2가 R1을 요청하면 교착 상태가 발생한다
싸이클이 발생
은행원 알고리즘(Banker’s Algorithm)
- 자원 종류마다 자원이 여러 개씩 있을 때 사용할 수 있는 알고리즘
- 자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개면 사용 불가능
- 은행원 알고리즘은 자원 할당 그래프 알고리즘보다 효율은 떨어짐
- 이 알고리즘을 은행에 적용하면 모든 고객들의 요구를 일정한 순서에 의해 만족시킬 수 있음
→ 은행원 알고리즘으로 불리는 이유
메커니즘
- 스레드가 시작할 때 각 스레드 최대 자원 개수를 자원 종류마다 미리 신고해야 함
- 이 숫자가 자원의 총 보유 수를 넘어서면 안 됨
- 스레드가 자원들을 요청 → 시스템은 해당 요청을 수용했을 때 안전 상태인지 판단
- 계속 안전한 경우 → 그 요청을 들어줌
- 불안전한 경우 → 해당 요청은 허락이 되지 않은 채 다른 스레드가 끝날 때까지 대기
은행원 알고리즘 구현을 위해 필요한 자료구조
Available : 각 종류별로 가용한 자원의 개수를 나타내는 벡터(크기 m)
- Available [j] = k : 현재 R(j)를 k개 사용할 수 있다.
Max : 각 스레드가 최대로 필요로 하는 자원의 개수를 나타내는 행렬(크기 n * m)
- Max [i][j] = k : 스레드 T(i)가 자원 R(j)를 최대 k개까지 요청할 수 있음
Allocation : 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬(크기 n * m)
- Allocation [i][j] = k : 현재 스레드 T(i)가 R(j)를 k개 사용 중임을 의미
Need : 각 스레드가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬(크기 n * m)
- Need [i][j] = k : 스레드 T(i)가 향후 R(j)를 k개까지 더 요청할 수 있음
- Need [i][j] = Max [i][j] - Allocation [i][j] 관계가 성립
은행원 알고리즘 설명을 위한 표기법
- X와 Y를 크기가 n인 벡터라고 가정
X ≤ Y : 모든 i 값에 대해 X [i] ≤ Y [i] 관계가 있음을 의미
- X = (1,7,3,2), Y = (0,3,2,1)이라면 Y ≤ X 관계가 성립한다.
Y < X : Y ≤ X 이면서 Y ≠ X가 성립해야 한다.
- Allocation과 Need 행렬의 각 행을 벡터로 취급한다.
- Allocation(i), Need(i)와 같이 표기
Allocation(i) 벡터 : 스레드 T(i)에게 현재 나가 있는 자원들Need(i) 벡터 : T(i)가 앞으로 더 요청할 수 있는 자원을 의미
안전성 알고리즘(Safety Algorithm)
- 시스템이 안전한지 아닌지를 알아낼 수 있는 알고리즘
과정
Work = Available로 초기값을 준다.
i = 0, 1, …, n-1에 대해서 Finish [i] = false를 초기값으로 준다.
Work와 Finish는 각각 크기가 m과 n인 벡터를 의미
- 아래 두 조건을 만족시키는 i 값을 찾는다.
- Finish [i] == false
- Need(i) ≤ Work
- 이러한 i 값을 찾을 수 없다면 step 4로 간다.
Work = Work + Allocation(i) Finish [i] = true 이후, 2번으로 돌아감- 모든 i 값에 대해
Finish [i] == true 라면 이 시스템은 안전 상태에 있다.
- 이 알고리즘으로 안전 여부를 알아내는데 m * n^2개의 연산이 필요
자원 요청 알고리즘(Resource-Request Algorithm)
- 자원 요청을 안전하게 들어줄 수 있는지를 검사하는 알고리즘
가정
Request(i) : 스레드 T(i)의 요청 벡터
- Request(i)[j] == k : T(i)가 R(j)를 k개까지 요청하고 있음을 의미
- T(i)가 자원을 요청하게 된다면 아래 “과정”과 같은 동작을 한다.
과정
- 만일
Reqeust(i) ≤ Need(i)이면 2번으로 간다.
그렇지 않으면, 시스템에 있는 개수보다 더 많이 요청했으므로 오류로 처리
- 만일
Request(i) ≤ Available이면 3번으로 간다.
그렇지 않으면, 요청한 자원이 당장은 없으므로 프로세스 P(i)는 기다려야 한다.
- 시스템이 T(i)에게 자원을 할당해 준 것처럼 시스템 상태 정보를 아래와 같이 바꾼다.
// request(i)만큼 할당해주고 가용할 수 있는 자원을 갱신해줌
Available = Available - Request(i)
// 스레드 i에 할당된 Allocation(i)를 갱신
Allocation(i) = Allocation(i) + Request(i)
// Request만큼 할당해줬으므로, 스레드 i가 필요한 Need를 갱신
Need(i) = Need(i) - Request(i)
- 바뀐 상태가 안전한 경우
→ T(i)에 여기에 반영된 정보대로 자원을 할당해 준다.
- 바뀐 상태가 불안전한 경우
→ 자원 할당 상태를 원상 복구하고, T(i)는 Request(i)가 만족할 때까지 대기
은행원 알고리즘 예시
가정
쓰레드와 자원 상태
- 시스템에 5개의 프로세스가 있다고 가정
- A, B, C 세 가지 종류의 자원이 있다고 가정
- A 자원의 개수 = 10개
- B 자원의 개수 = 5개
- C 자원의 개수 = 7개
- 시스템의 현재 상태는 아래의 표를 따름
- Need의 행렬 값은 (Max - Allocation)으로 얻을 수 있다.
- 해당 시스템은 안전하다.
- <T1, T3, T4, T2, T0> 순서가 안전성 기준을 만족시키기 때문
- 해당 상태에서 T1이 A 자원 1개와 C 자원 2개를 추가로 요청한다고 가정
→ 즉, Request(1) = (1,0,2)
과정 및 동작
- 먼저,
Request ≤ Available 여부를 검사해야 함
← Reqeust(1) = (1,0,2) 요청을 들어줄 것인지 판단하기 위해
- (1,0,2) ≤ (3,3,2)인지 여부를 검사한다. → 해당 조건을 만족
- 해당 요청을 들어주는 것처럼 상태 정보를 만들어봄
- 해당 상태가 안전한지 확인하기 위해 안전성 알고리즘을 돌린다.
→ <T1, T3, T4, T0, T2>가 안전성 조건을 만족시킴을 알 수 있다.
- 안전성 조건을 만족시키기 때문에 T1의 요청을 즉시 들어준다.
- 해당 상태에서 T4가 (3,3,0)을 요청
→ 자원이 모자라므로 들어줄 수 없다.
- 해당 상태에서 T0가 (0,2,0)을 요청
→ 자원은 충분히 있지만 불안전 상태를 만들기 때문에 요청을 즉시 들어줄 수 없음
